Mai đang thiết kế một kim tự tháp gồm các khối lập phương đen và trắng.

Ban đầu, tầng đáy của kim tự tháp là một bảng ~N \times N~. Màu của các khối ở tầng đáy được mô tả bởi ma trận nhị phân ~M~: khối tại vị trí ~(i,j)~ là màu đen khi và chỉ khi ~M_{i,j}=1~.

Sau đó, các tầng ~1,2,\dots,N-1~ được xây lần lượt. Mỗi khối ở tầng ~h~ nằm trên đỉnh chung của bốn khối ở tầng ~h-1~. Cụ thể, khối ~(h,x,y)~ nằm trên bốn khối ~(h-1,x,y)~, ~(h-1,x+1,y)~, ~(h-1,x,y+1)~ và ~(h-1,x+1,y+1)~.

Khối mới sẽ có màu đen khi và chỉ khi bốn khối bên dưới tạo thành dạng bàn cờ, tức là mọi cặp khối kề cạnh nhau có màu khác nhau. Nói cách khác, nếu gọi màu bốn khối bên dưới lần lượt là ~a,b,c,d~ theo thứ tự trên-trái, dưới-trái, trên-phải, dưới-phải, thì khối mới màu đen khi và chỉ khi ~a=d~, ~b=c~ và ~a \ne b~.

Bạn cần trả lời ~Q~ câu hỏi. Mỗi câu hỏi cho ba số ~h,x,y~ và yêu cầu xác định màu của khối ở vị trí ~(h,x,y)~.

Các chỉ số đều bắt đầu từ ~0~. Trong mọi câu hỏi, ~1 \le h < N~ và ~0 \le x,y < N-h~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 < N \le 3000, 1 \le Q \le 1\,000\,000)~;

• Dòng thứ ~i+2~ trong ~N~ dòng tiếp theo chứa một xâu nhị phân độ dài ~N~, mô tả hàng thứ ~i~ của ma trận ~M~;

• Mỗi dòng trong ~Q~ dòng cuối chứa ba số nguyên ~h,x,y~ mô tả một câu hỏi.

Output

In ra ~Q~ dòng. Dòng thứ ~i~ chứa ~1~ nếu khối trong câu hỏi thứ ~i~ có màu đen, ngược lại chứa ~0~.

Scoring

Sample Input 1

5 7
01010
10101
01010
00101
11010
1 0 0
1 1 1
2 0 0
2 1 1
3 0 0
3 1 1
4 0 0

Sample Output 1

1
1
0
0
0
0
0

Notes

Ở ví dụ, khối tại vị trí ~(1,0,0)~ có màu đen vì bốn khối đáy ở các vị trí ~(0,0)~, ~(1,0)~, ~(0,1)~ và ~(1,1)~ tạo thành dạng bàn cờ. Tương tự, khối tại vị trí ~(1,1,1)~ cũng màu đen. Các truy vấn còn lại hỏi ở tầng cao hơn; khi xây tiếp các tầng theo đúng quy tắc, những khối này đều có màu trắng.