DoMixi đang livestream giải Sudoku thì một viewer nhắn lên: "Anh ơi, bảng của anh sai rồi kìa!" DoMixi hoảng hồn nhìn lại bảng, nhưng không biết chỗ nào sai — anh ấy đang lag não sau 8 tiếng stream. Hãy giúp DoMixi kiểm tra xem bảng Sudoku của anh có lỗi không nhé!

Sudoku là một lưới ~9 \times 9~ gồm các chữ số từ ~1~ đến ~9~. Bảng không có lỗi khi thỏa mãn tất cả các điều kiện sau:

• Mỗi hàng chứa đúng một lần mỗi chữ số từ ~1~ đến ~9~.
• Mỗi cột chứa đúng một lần mỗi chữ số từ ~1~ đến ~9~.
• Mỗi trong ~9~ ô vuông ~3 \times 3~ chứa đúng một lần mỗi chữ số từ ~1~ đến ~9~.

Cho một bảng Sudoku chưa hoàn chỉnh, hãy kiểm tra xem bảng đó có lỗi không.

Lưu ý: Không cần kiểm tra xem bảng Sudoku có thể giải được hay không — chỉ cần kiểm tra các chữ số đã điền có vi phạm quy tắc không.

Dữ liệu vào

Dữ liệu vào mô tả bảng Sudoku. Các ký tự |, - và + tạo nên khung phân chia các ô ~3 \times 3~. Ký tự . đại diện cho ô trống. Các ký tự còn lại là chữ số từ 1 đến 9.

Kết quả

In ra OK nếu bảng không có lỗi. Ngược lại, in ra GRESKA.

Ví dụ

Đầu vào 1:

+---+---+---+
|52.|...|.81|
|.39|58.|...|
|.8.|.9.|...|
+---+---+---+
|24.|...|1.3|
|1..|43.|86.|
|.63|..7|.24|
+---+---+---+
|...|1.9|35.|
|..8|.74|6..|
|31.|86.|7.9|
+---+---+---+

Đầu ra 1:

OK

Đầu vào 2:

+---+---+---+
|3..|6..|..4|
|4.9|8.1|..7|
|..7|.49|6..|
+---+---+---+
|946|157|8.2|
|.2.|3..|745|
|.7.|28.|...|
+---+---+---+
|...|4..|..5|
|8.5|.6.|.2.|
|734|..8|5..|
+---+---+---+

Đầu ra 2:

GRESKA

Giải thích: Ở ví dụ 2, chữ số ~5~ xuất hiện hai lần ở cột ~9~, và cũng xuất hiện hai lần ở ô ~3 \times 3~ góc dưới bên phải.

Giới hạn

EJOI là gì so với MixiLand?

DoMixi đang dẫn đội stream vào một mê cung khổng lồ. Mê cung gồm ~n \times m~ phòng xếp theo lưới, phòng góc trên bên trái là ~(1, 1)~, phòng góc dưới bên phải là ~(n, m)~. Giữa mỗi cặp phòng kề nhau có một cửa, được sơn một trong bốn màu: xanh dương (P), đỏ (C), xanh lá (Z) và cam (N).

Người anh em stream MixiGa biết đường ra nhưng hắn ta chỉ chỉ đường nếu DoMixi trả lời được các câu hỏi của hắn.

Câu hỏi của MixiGa: "Nếu chúng ta đang ở phòng ~(a_i, b_i)~ và đích đến là phòng ~(c_i, d_i)~, thì cần đi qua tối thiểu bao nhiêu màu cửa khác nhau để đến đó?"

DoMixi đang bận cười với chat, nhờ bạn giúp trả lời ~q~ câu hỏi của MixiGa!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 100~, ~1 < n \times m~) — số hàng và cột của mê cung.

~n~ dòng tiếp theo, mỗi dòng chứa ~m-1~ ký tự (P, C, Z hoặc N) — màu cửa nối phòng ~(i,j)~ với ~(i,j+1)~.

~n-1~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự — màu cửa nối phòng ~(i,j)~ với ~(i+1,j)~.

Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 100~) — số câu hỏi.

~q~ dòng cuối, mỗi dòng chứa bốn số nguyên ~a_i, b_i, c_i, d_i~ (~1 \le a_i, c_i \le n~, ~1 \le b_i, d_i \le m~, ~(a_i,b_i) \ne (c_i,d_i)~).

Kết quả

Với mỗi câu hỏi, in ra số màu cửa khác nhau tối thiểu cần đi qua trên một dòng.

Ví dụ

Đầu vào 1:

1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3

Đầu ra 1:

4
2
3
1

Đầu vào 2:

4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

Đầu ra 2:

1
2
1
3

Giới hạn

Trong một buổi stream donation marathon, DoMixi trang trí studio bằng một bảng hiển thị ~n \times m~ con số — mỗi ô ~(i, j)~ hiển thị số tiền donation ~a_{i,j}~ (có thể âm nếu có refund). Bảng rất lớn nên DoMixi dùng một khung ~r \times s~ để nhìn vào từng phần.

DoMixi đặt khung sao cho ô góc trên bên trái của khung trùng với một ô nào đó trên bảng (khung phải nằm hoàn toàn trong bảng). Trong mỗi vị trí của khung, DoMixi ghi lại số donation lớn nhất nhìn thấy qua khung vào một tờ giấy ở vị trí tương ứng.

Anh ấy làm điều này với mọi vị trí hợp lệ của khung. Tờ giấy cuối cùng trông rất đẹp — nhưng nó ghi gì vậy?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 4000~) — số hàng và cột của bảng trên tường.

~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ (~|a_{i,j}| \le 10000~).

Dòng cuối chứa hai số nguyên ~r~ và ~s~ (~1 \le r \le n~, ~1 \le s \le m~) — kích thước khung.

Kết quả

In ra tờ giấy gồm ~(n-r+1)~ hàng và ~(m-s+1)~ cột — ô ~(i,j)~ là giá trị lớn nhất trong vùng khung đặt tại ~(i,j)~.

Ví dụ

Đầu vào 1:

3 3
1 1 2
2 3 4
4 3 2
3 3

Đầu ra 1:

4 

Đầu vào 2:

3 3
1 1 2
2 3 4
4 3 2
2 1

Đầu ra 2:

2 3 4 
4 3 4 

Đầu vào 3:

5 5
-1 -3 -4 -2 4
-8 -7 -9 -10 11
5 2 -8 -2 1
13 -3 -2 -6 -9
11 6 2 7 4
2 3

Đầu ra 3:

-1 -2 11 
5 2 11 
13 2 1 
13 7 7 

Giới hạn

Nhân dịp sinh nhật lần thứ mười ba của mình, DoMixi được fan tặng một hộp LEGO xịn! Trong hộp có ~n~ khối lego, khối thứ ~i~ có màu ~i~. DoMixi quyết định xây một bức tường trên một đế LEGO dạng hàng ngang có ~k~ vị trí đặt khối.

DoMixi xây tường theo quy tắc sau:

• Đầu tiên, đặt khối màu ~1~ vào một vị trí bất kỳ trên đế.
• Với mỗi khối từ ~2~ đến ~n~, đặt nó vào vị trí kề với khối vừa đặt. Nếu vị trí đó đã có khối, thì chồng khối mới lên trên tất cả các khối ở đó.

Sau khi xây xong, DoMixi ghi lên giấy một dãy độ dài ~k~: vị trí thứ ~i~ ghi màu của khối trên cùng ở vị trí đó, hoặc ~0~ nếu không có khối nào.

DoMixi tự hỏi: có bao nhiêu dãy khác nhau có thể xuất hiện? Hai dãy được coi là khác nhau nếu tồn tại ít nhất một vị trí mà hai dãy có giá trị khác nhau.

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên ~n~ và ~k~ (~2 \le n, k \le 5000~).

Kết quả

In ra số dãy khác nhau có thể xuất hiện, modulo ~10^9 + 7~.

Ví dụ

Đầu vào 1:

4 3

Đầu ra 1:

8

Đầu vào 2:

3 5

Đầu ra 2:

14

Đầu vào 3:

100 200

Đầu ra 3:

410783331

Giải thích ví dụ 1: Tất cả các dãy có thể là: ~(0,3,4)~, ~(2,3,4)~, ~(0,4,3)~, ~(1,4,3)~, ~(4,3,0)~, ~(4,3,2)~, ~(3,4,0)~, ~(3,4,1)~.

Giới hạn

Khi DoMixi giải được bài toán cầu Königsberg nổi tiếng, anh ấy không biết mình vừa khám phá ra cả một nhánh toán học mới — lý thuyết đồ thị!

Thật ra bài toán cầu Königsberg quá dễ với các lập trình viên thời này. Vì thế DoMixi nảy ra một bài toán khó hơn — bài toán cầu MixiLand!

Mạng lưới của MixiLand là một đồ thị liên thông gồm ~n~ đỉnh và ~m~ cạnh, trong đó các cạnh đại diện cho các cây cầu, còn các đỉnh là các hòn đảo. DoMixi hỏi: có bao nhiêu cạnh mà sau khi xóa cạnh đó cùng với hai đỉnh đầu mút của nó, ~n-2~ đỉnh còn lại trở nên không liên thông?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~4 \le n \le 100.000~, ~n-1 \le m \le 300.000~) — số đỉnh và số cạnh.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~ (~1 \le a_i, b_i \le n~) — cạnh nối đỉnh ~a_i~ với đỉnh ~b_i~.

Không có khuyên hay cạnh bội.

Kết quả

In ra một số nguyên duy nhất — số cạnh thỏa mãn điều kiện.

Ví dụ

Đầu vào 1:

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

Đầu ra 1:

1

Đầu vào 2:

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

Đầu ra 2:

4

Giải thích ví dụ 1: Xóa cạnh ~(1,3)~ cùng với đỉnh ~1~ và ~3~, đồ thị còn lại có đỉnh ~2~ và ~4~ không liên thông. Đây là cạnh duy nhất có tính chất này.

Giới hạn