JOI 2012 Final Camp - Ngày 3

Chủ tịch K rất thích bói toán và thường thử nhiều cách bói khác nhau. Hôm nay, ông quyết định dùng các lá bài để dự đoán thành tích của đoàn Nhật Bản tại kỳ thi IOI năm nay.

Cách bói được thực hiện như sau:

• Xếp các lá bài thành một hình chữ nhật gồm \(M\) hàng và \(N\) cột, tất cả đều ngửa mặt.
• Với mỗi \(i = 1, 2, \ldots, K\), lật tất cả các lá bài nằm trong các hàng từ \(A_i\) đến \(B_i\) tính từ trên xuống và các cột từ \(C_i\) đến \(D_i\) tính từ trái sang. Lật một lá bài nghĩa là đổi từ ngửa thành úp hoặc từ úp thành ngửa.
• Sau khi thực hiện xong các thao tác, kết quả bói được xác định từ số lá bài đang ngửa mặt.

Cụ thể, nếu ký hiệu lá bài ở hàng \(a\), cột \(b\) là \((a,b)\) thì thao tác thứ \(i\) lật tất cả các lá bài thỏa mãn:

Nhận ra rằng phải lật bài quá nhiều lần, chủ tịch K quyết định không thực hiện các thao tác bằng bài thật nữa.

Yêu cầu

Cho \(M\), \(N\), \(K\) và thông tin của \(K\) thao tác, hãy tính số lá bài ngửa mặt sau khi thực hiện tất cả các thao tác.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(M\), \(N\), \(K\), cách nhau bởi dấu cách.
• Dòng thứ \(i+1\) (\(1 \le i \le K\)) chứa bốn số nguyên \(A_i\), \(B_i\), \(C_i\), \(D_i\), mô tả thao tác thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số lá bài ngửa mặt sau \(K\) thao tác.

Ràng buộc

• \(1 \le M \le 1\,000\,000\,000\).
• \(1 \le N \le 1\,000\,000\,000\).
• \(1 \le K \le 100\,000\).
• \(1 \le A_i \le B_i \le M\) với mọi \(1 \le i \le K\).
• \(1 \le C_i \le D_i \le N\) với mọi \(1 \le i \le K\).

Phân nhóm

• Các bộ kiểm thử chiếm \(30\%\) tổng số điểm thỏa mãn \(K \le 3\,000\).

Ví dụ

6 5 3
2 4 1 4
4 6 3 5
1 2 3 5

11

Chủ tịch K quan tâm đến chuột túi và quyết định quan sát hành vi của chúng. Có \(N\) con chuột túi được đánh số từ \(1\) đến \(N\), mỗi con có một chiếc túi. Con thứ \(i\) có kích thước cơ thể là \(A_i\) và kích thước túi là \(B_i\). Túi luôn nhỏ hơn cơ thể của chính con chuột túi đó, tức là \(B_i < A_i\).

Ban đầu, không có con chuột túi nào nằm trong túi của con khác. Chúng lặp lại thao tác sau cho đến khi không thể thực hiện thêm thao tác nào:

Chọn hai con chuột túi \(i\) và \(j\) sao cho \(A_i < B_j\), con \(i\) không nằm trong túi của bất kỳ con nào khác và túi của con \(j\) đang trống. Khi đó, con \(i\) chui vào túi của con \(j\).

Thao tác này vẫn được phép nếu trong túi của con \(i\) đã có một con chuột túi khác, hoặc nếu con \(j\) đang nằm trong túi của một con khác. Khi con \(i\) di chuyển, tất cả những con nằm bên trong nó cũng di chuyển theo. Nếu có nhiều cặp \((i,j)\) hợp lệ, không biết cặp nào sẽ được chọn.

Yêu cầu

Cho kích thước cơ thể và kích thước túi của từng con chuột túi, hãy tính số trạng thái cuối cùng khác nhau có thể xuất hiện, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số con chuột túi.
• Dòng thứ \(i+1\) (\(1 \le i \le N\)) chứa hai số nguyên \(A_i\) và \(B_i\), cách nhau bởi dấu cách, lần lượt là kích thước cơ thể và kích thước túi của con thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa phần dư của số trạng thái cuối cùng khác nhau khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 300\).
• \(1 \le B_i < A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(50\%\) tổng số điểm thỏa mãn \(N \le 30\).
• Các bộ kiểm thử chiếm \(70\%\) tổng số điểm thỏa mãn \(N \le 70\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5
4 3
3 1
6 5
2 1
4 2

4

20
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3

21060

Sokoban là một trò chơi giải đố được yêu thích từ lâu. Trò chơi diễn ra trên một bảng gồm \(M\) hàng và \(N\) cột ô vuông. Người chơi điều khiển một nhân vật để đẩy thùng đến ô đích. Trong bài này, chỉ có một chiếc thùng.

Một số ô trên bảng là tường. Nhân vật, thùng và đích đều nằm trên những ô không phải tường; nhân vật và thùng không bao giờ đi ra ngoài bảng. Có thể thực hiện một trong hai thao tác sau:

• Chọn một ô kề với ô của nhân vật, không phải tường và không có thùng, rồi di chuyển nhân vật đến ô đó.
• Nếu nhân vật đứng kề thùng, đồng thời ô ngay phía bên kia của thùng theo hướng đẩy nằm trong bảng và không phải tường, đẩy thùng đến ô đó và di chuyển nhân vật đến ô mà thùng vừa rời khỏi.

Hai ô được gọi là kề nhau nếu chúng có chung một cạnh.

Trong các hình minh họa, # là tường, @ là nhân vật, O là thùng, X là đích và . là các ô còn lại. Xét trạng thái sau:

Có thể đưa thùng đến đích bằng các thao tác:

1. Di chuyển nhân vật sang phải.
2. Di chuyển nhân vật xuống dưới.
3. Đẩy thùng và di chuyển nhân vật sang trái.
4. Đẩy thùng và di chuyển nhân vật sang trái một lần nữa.

Ngược lại, không thể đưa thùng đến đích từ trạng thái sau:

Khi vị trí các bức tường và ô đích đã cố định, bạn muốn biết có bao nhiêu cách đặt nhân vật và thùng để tạo thành một trò Sokoban có thể giải được. Một cách đặt có thể giải được nếu có thể thực hiện một dãy thao tác để đưa thùng đến đích.

Ban đầu, nhân vật và thùng phải nằm ở hai ô khác nhau; cả hai ô đều không phải tường và không phải ô đích.

Yêu cầu

Hãy đếm số cách đặt thỏa mãn yêu cầu.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\), lần lượt là số hàng và số cột của bảng.
• \(M\) dòng tiếp theo mô tả bảng, mỗi dòng gồm \(N\) ký tự. Ký tự # biểu diễn tường, X biểu diễn đích và . biểu diễn các ô còn lại, cũng là những ô có thể chọn làm vị trí ban đầu của nhân vật hoặc thùng. Ký tự X xuất hiện đúng một lần.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số cách đặt nhân vật và thùng để tạo thành một trò Sokoban có thể giải được.

Ràng buộc

• \(1 \le M \le 1\,000\).
• \(1 \le N \le 1\,000\).
• Mỗi ký tự trên bảng là một trong ba ký tự #, X, ..
• Bảng có đúng một ký tự X.

Phân nhóm

• Các bộ kiểm thử chiếm \(20\%\) tổng số điểm thỏa mãn \(M \le 50\) và \(N \le 50\).

Ví dụ

3 5
..#..
.X...
##..#

9

2 3
.X.
...

0

4 7
.#.#.##
##.#..#
....X..
##.#...

24