Cho ~1~ lưới điểm hình chữ nhật có ~n~ hàng và ~m~ cột nằm cách đều nhau, điểm ~(i,\ j)~ là giao của hàng ~i~ và cột ~j~. Mỗi điểm ~(i,\ j)~ sẽ được gán một giá trị tương ứng ~a[i][j]~. Ta định nghĩa square sum của một lưới điểm như sau :

• Ban đầu square sum bằng ~0~.
• Duyệt qua các bộ ~4~ điểm phân biệt trên lưới, nếu dựng được một hình vuông nhận ~4~ điểm này làm đỉnh thì cộng thêm giá trị ~a[i][j]~ của ~4~ điểm đấy vào square sum.

Lưu ý: Cạnh hình vuông KHÔNG NHẤT THIẾT phải nằm song song với ~2~ cạnh của lưới. (tham khảo hình vẽ bên dưới)

Cho các truy vấn có dạng ~(x1,\ y1)~, ~(x2,\ y2)~, mỗi truy vấn hỏi square sum của lưới điểm hình chữ nhật có góc trái trên ~(x1,\ y1)~ và góc phải dưới ~(x2,\ y2)~.

Vì số truy vấn tương đối lớn nên các truy vấn trong bài được nén lại dưới dạng nhóm như sau :

• Mỗi điểm ~(i,\ j)~ được gán một màu tương ứng là ~c[i][j]~.
• Ta định nghĩa bounding box của hai điểm trên lưới là hình chữ nhật nhỏ nhất về diện tích chứa cả hai điểm đó và có cạnh song song với cạnh của lưới. Lưu ý rằng diện tích của bounding box có thể = 0.
• Cho ~q~ nhóm truy vấn, mỗi nhóm được biểu diễn bởi một cặp số ~c1,\ c2~. Theo đó, xét toàn bộ các cặp điểm được tạo bởi một điểm có màu ~c1~ với ~1~ điểm có màu ~c2~ rồi tìm bounding box tương ứng của chúng. Tính kết quả của truy vấn sao cho ~(x1,\ y1)~, ~(x2,\ y2)~ chính là góc trái trên và phải dưới của bounding box được xét.
• Kết quả của một nhóm truy vấn là tổng XOR kết quả từng truy vấn trong nhóm đó. Có thể chứng minh được rằng tổng XOR sẽ không vượt quá ~2^{63} – 1~.

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,\ m,\ q~ ~(1\le n, m \le 10^5, 1 \le n * m \le 10^5)~ ~(1 \le q \le 10^5)~ ~-~ lần lượt là số hàng, cột trong lưới điểm và số nhóm truy vấn.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên tương ứng là giá trị ~a[i][j]~ của mỗi điểm ~(1 \le a[i][j] \le 10^9)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên tương ứng là màu ~c[i][j]~ được gán cho mỗi điểm ~(1 \le c[i][j] \le 10^5)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm một cặp số ~c1,\ c2~ (~c1 \neq c2~) biểu diễn hai màu của một nhóm truy vấn. Tổng số truy vấn ở ~q~ nhóm sẽ không vượt quá ~10^7~.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là kết quả tương ứng của nhóm truy vấn thứ ~i~, hay nói cách khác, tính tổng XOR kết quả từng truy vấn trong nhóm truy vấn thứ ~i~.

Sample Input

3 3 2
1 1 1
1 1 2
1 1 1
1 2 3
4 5 8
7 8 9
1 8
9 1

Sample Output

1
27

Subtask

• 20% số test có ~a[i][j] = 1~ ở mọi điểm trên lưới
• 20% số test khác đảm bảo mỗi điểm được gán một màu ~c[i][j]~ riêng biệt
• 60% số test còn lại không có điều kiện gì thêm

Note

Giải thích sample test

• Nhóm query ~(1, 8)~ bao gồm ~2~ truy vấn :
• Trái trên ~(1, 1)~ và phải dưới ~(2, 3)~, kết quả là ~9~
• Trái trên ~(1, 1)~ và phải dưới ~(3, 2)~, kết quả là ~8~
• Tổng XOR : 9 ~\oplus~ 8 = 1
• Nhóm query ~(9, 1)~ bao gồm duy nhất ~1~ truy vấn :
• Trái trên ~(1, 1)~ và phải dưới ~(3, 3)~, kết quả là ~27~
• Tổng XOR : 27