Vườn hoa của Jackson được trồng theo mô hình công nghệ cao; do đó việc thu hoạch được thực hiện hoàn toàn bằng robot. Để làm được điều đó, Jackson đã trồng vườn hoa theo dạng lưới gồm ~m~ hàng và ~n~ cột. Các hàng của lưới được đánh số từ 1 đến ~m~, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến ~n~, từ trái sang phải. Tại mỗi điểm giao nhau của hàng và cột, Jackson trồng một khóm hoa. Mỗi khóm hoa được xác định thông qua vị trí của hàng và cột và một giá trị được gán cho nó. Ví dụ ở vị trí giao của hàng ~i~ và cột ~j~ xác định khóm hoa ~(i, j)~ và giá trị gán cho khóm hoa đó là một số nguyên không âm ~a_{i,j}~ (~a_{i,j} \le 10^6~). Cho biết, khóm hoa chỉ được thu hoạch khi giá trị tại nó là một số nguyên tố.

Yêu cầu: Với ~Q~ bộ bốn số nguyên dương ~x_k, y_k, r_k, c_k~, hãy cho biết robot có thu hoạch được tất cả các khóm hoa trong phạm vi hình chữ nhật có kích thước ~(r_k \times c_k)~ bắt đầu từ tọa độ ~(x_k, y_k)~ hay không?

Input

• Dòng đầu chứa ba số nguyên ~m, n, Q~;
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên không âm ~a_{i,1}, a_{i,2}, \dots, a_{i,n}~ (~i = 1, 2, \dots, m~) là các giá trị được gán cho các khóm hoa trong vườn;
• ~Q~ dòng tiếp theo, dòng thứ ~k~ (~k = 1, 2, \dots, Q~) chứa bốn số nguyên ~x_k, y_k, r_k, c_k~ mô tả câu hỏi thứ ~k~. Trong đó ~x, y~ là hai số nguyên (~1 \le x \le y \le m~); ~r, c~ là hai số nguyên (~1 \le r \le y-x+1~; ~1 \le c \le n~).

Output

• Gồm ~Q~ dòng, trên mỗi dòng ghi số 1 nếu tồn tại cách chọn hình chữ nhật thỏa mãn, ngược lại ghi số 0.

Sample Input 1

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

Sample Output 1

1
0
1