Orac và Trò chơi Cuộc sống

Cho một bảng đen-trắng gồm $n$ hàng và $m$ cột. Mỗi ô có một trong hai màu: ký tự 0 (trắng) hoặc 1 (đen).

Tại mỗi bước (bước khởi tạo là bước thứ $0$), màu của mỗi ô thay đổi theo quy tắc sau:

• Nếu không có ô kề (kề cạnh) nào cùng màu với ô đó ở bước hiện tại, thì màu của nó ở bước tiếp theo giữ nguyên.
• Ngược lại, màu của nó ở bước tiếp theo đổi sang màu còn lại.

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

Bạn cần trả lời $t$ truy vấn. Mỗi truy vấn cho ba số $i$, $j$, $p$: hãy xác định màu của ô ở hàng $i$, cột $j$ tại bước thứ $p$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $t$.
• $n$ dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài $m$ mô tả màu khởi tạo của bảng.
• $t$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $i$, $j$, $p$ mô tả một truy vấn.

Dữ liệu ra

In ra $t$ dòng. Dòng thứ $k$ in ra một ký tự: 1 nếu ô được truy vấn ở dòng thứ $k$ có màu đen tại bước thứ $p$, ngược lại in ra 0.

Ràng buộc

• $1\le n,m\le 1000$
• $1\le t\le 100000$
• $1\le i\le n$, $1\le j\le m$, $1\le p\le {10}^{18}$

Ví dụ