Thành phố JOI có một mạng lưới đường dạng ô vuông, gồm \(H\) con đường đông-tây dài vô hạn và \(W\) con đường bắc-nam dài vô hạn. Giao lộ \((i,j)\) (\(1 \le i \le H\), \(1 \le j \le W\)) là nơi con đường đông-tây thứ \(i\) tính từ phía bắc gặp con đường bắc-nam thứ \(j\) tính từ phía tây.

Hiện một số đoạn đường bị đóng do tình trạng xuống cấp. Cụ thể:

• Trên con đường đông-tây thứ \(i\) tính từ phía bắc (\(1 \le i \le H\)), đoạn nối giao lộ \((i,j)\) và \((i,j+1)\) (\(1 \le j \le W-1\)) bị đóng nếu \(A_{i,j}=0\), và đi lại được nếu \(A_{i,j}=1\).
• Trên con đường bắc-nam thứ \(j\) tính từ phía tây (\(1 \le j \le W\)), đoạn nối giao lộ \((i,j)\) và \((i+1,j)\) (\(1 \le i \le H-1\)) bị đóng nếu \(B_{i,j}=0\), và đi lại được nếu \(B_{i,j}=1\).
• Mọi phần đường còn lại, tức là các phần nằm ngoài \(H \times W\) giao lộ, đều bị đóng.

Chủ tịch K, thị trưởng thành phố JOI, quyết định lập một kế hoạch sửa đường. Một kế hoạch gồm không hoặc nhiều lần sửa. Trong một lần sửa, chọn một số nguyên \(i\) thỏa mãn \(1 \le i \le H\), rồi mở lại mọi đoạn đang bị đóng nối \((i,j)\) với \((i,j+1)\), với mọi \(1 \le j \le W-1\). Như vậy, sau lần sửa này, toàn bộ các đoạn giữa các giao lộ trên con đường đông-tây thứ \(i\) đều đi lại được. Cả lần sửa mất \(C_i\) ngày, trong đó \(C_i\) bằng \(1\) hoặc \(2\).

Không thể thực hiện hai lần sửa song song. Vì vậy, thời gian thực hiện một kế hoạch bằng tổng số ngày của tất cả các lần sửa trong kế hoạch đó.

Để bảo đảm việc đi lại giữa các cơ sở quan trọng của thành phố, chủ tịch K đưa ra \(Q\) câu hỏi. Câu hỏi thứ \(k\) (\(1 \le k \le Q\)) như sau: có tồn tại kế hoạch sửa đường để từ bất kỳ giao lộ nào trong \(T_k\) giao lộ \((X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\ldots,(X_{k,T_k},Y_{k,T_k})\) đều có thể đi đến mọi giao lộ còn lại bằng các đoạn đường đi lại được hay không? Nếu có, thời gian thực hiện nhỏ nhất của một kế hoạch như vậy là bao nhiêu ngày?

Các câu hỏi được xét độc lập trên mạng lưới đường ban đầu. Cho tình trạng đường, số ngày cần để sửa từng con đường đông-tây và nội dung các câu hỏi, hãy trả lời tất cả các câu hỏi.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(H,W,Q\).

\(H\) dòng tiếp theo mô tả \(A\). Dòng thứ \(i\) là một xâu gồm \(W-1\) ký tự 0 hoặc 1 viết liền nhau, không có dấu cách; ký tự thứ \(j\) biểu diễn \(A_{i,j}\).

\(H-1\) dòng tiếp theo mô tả \(B\). Dòng thứ \(i\) là một xâu gồm \(W\) ký tự 0 hoặc 1 viết liền nhau, không có dấu cách; ký tự thứ \(j\) biểu diễn \(B_{i,j}\).

Dòng tiếp theo chứa \(H\) số nguyên \(C_1,C_2,\ldots,C_H\), cách nhau bởi dấu cách.

Sau đó là \(Q\) câu hỏi. Câu hỏi thứ \(k\) có dạng:

T_k
X_{k,1} Y_{k,1}
X_{k,2} Y_{k,2}
...
X_{k,T_k} Y_{k,T_k}

Dữ liệu được đọc từ đầu vào chuẩn.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số ngày nhỏ nhất cần thiết của một kế hoạch làm cho \(T_k\) giao lộ trong câu hỏi thứ \(k\) đi lại được với nhau. Nếu không tồn tại kế hoạch như vậy, in ra -1.

Ràng buộc

• \(2 \le H\).
• \(2 \le W\).
• \(H \times W \le 1\,000\,000\).
• \(1 \le Q \le 100\,000\).
• \(A_{i,j}\) bằng \(0\) hoặc \(1\) (\(1 \le i \le H\), \(1 \le j \le W-1\)).
• \(B_{i,j}\) bằng \(0\) hoặc \(1\) (\(1 \le i \le H-1\), \(1 \le j \le W\)).
• \(C_i\) bằng \(1\) hoặc \(2\) (\(1 \le i \le H\)).
• \(2 \le T_k\) (\(1 \le k \le Q\)).
• \(T_1+T_2+\cdots+T_Q \le 200\,000\).
• \(1 \le X_{k,l} \le H\) (\(1 \le k \le Q\), \(1 \le l \le T_k\)).
• \(1 \le Y_{k,l} \le W\) (\(1 \le k \le Q\), \(1 \le l \le T_k\)).
• Với mỗi \(1 \le k \le Q\), các giao lộ \((X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\ldots,(X_{k,T_k},Y_{k,T_k})\) đôi một khác nhau.
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 10 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\); \(T_k=2\) với mọi \(1 \le k \le Q\); \(A_{i,j}=0\) với mọi \(1 \le i \le H\), \(1 \le j \le W-1\).
2. 6 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\); \(T_k=2\) với mọi \(1 \le k \le Q\).
3. 15 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(Q \le 5\).
4. 11 điểm: \(C_i=1\) với mọi \(1 \le i \le H\); \(T_k=2\) với mọi \(1 \le k \le Q\).
5. 6 điểm: \(C_i=1\) với mọi \(1 \le i \le H\).
6. 12 điểm: \(Q \le 5\).
7. 26 điểm: \(T_k=2\) với mọi \(1 \le k \le Q\).
8. 14 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 3 4
00
00
00
00
100
001
000
1 1 1 1
2
1 1
3 3
2
3 1
1 2
2
2 3
3 3
2
4 2
3 2

1
3
0
-1

4 4 4
100
110
011
010
0010
1001
0101
1 1 1 1
2
1 2
3 1
2
1 4
4 1
2
3 2
1 2
2
4 3
1 1

1
3
2
2

7 3 3
10
00
00
10
00
01
00
110
101
011
001
110
100
1 1 1 1 1 1 1
3
7 2
3 1
3 2
3
3 1
6 3
2 3
7
2 2
1 3
7 3
5 2
1 2
7 2
3 1

3
2
4

4 3 3
00
00
10
00
110
011
001
1 2 2 2
2
1 1
3 1
2
4 3
2 1
2
4 1
1 3

1
2
5

7 3 2
01
00
00
00
00
10
01
100
110
011
001
101
001
1 1 2 1 1 2 2
3
7 2
1 3
5 1
5
1 1
2 2
3 1
2 3
4 2

4
1

Nguồn

Road Service 2, JOI 2024, vòng chung kết quốc gia, bài 5 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc, hình minh họa và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.