Ngoài giỏi thuật toán, Đăng còn là một chuyên gia về bảo mật! Đăng biết rằng một đoạn code bất kì có thể biểu diễn dưới dạng một dãy nhị phân. Cho một số đoạn code có chứa nội dung nguy hiểm (ví dụ như virus), ta có thể tìm những đoạn code tương tự bằng cách sử dụng thuật toán giống như các thuật toán so khớp chuỗi. Với ý tưởng đó, Đăng đố các bạn bài toán sau:

Cho một cơ sở dữ liệu gồm ~N~ đoạn code, biểu diễn dưới dạng các dãy nhị phân có độ dài ~M~ bit. Bạn cần xử lý truy vấn, mỗi truy vấn thuộc 1 trong 2 dạng sau:

• 1 u id: đảo ngược bit ở vị trí thứ ~id~ của dãy nhị phân thứ ~u~ ~(1 \le u \le N, 1 \le id \le M)~
• 2 x y: cho biết số vị trí ~j~ mà bit thứ ~j~ của dãy nhị phân thứ ~x~ và bit thứ ~j~ của dãy nhị phân thứ ~y~ là khác nhau ~(1 \le x, y \le N)~

Input

• Dòng đầu tiên của input chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M, \le 10^5)~, lần lượt là số dãy nhị phân và độ dài của từng dãy.
• ~N~ dòng tiếp theo, mỗi dòng chứa một chuỗi nhị phân gồm ~M~ bit.
• Dòng tiếp theo chứa ~Q~ ~(1 \le Q \le 2 \times 10^5)~, là số truy vấn bạn cần xử lý.
• ~Q~ dòng tiếp theo, mỗi dòng là một truy vấn với cấu trúc trên.

Tổng số lượng bit của các chuỗi nhị phân không vượt quá ~10^5~

Output

Với mỗi truy vấn loại 2, bạn cần đưa ra câu trả lời trên một dòng.

Sample Input

3 3
110
011
000
3
2 1 2
1 3 1
2 1 3

Sample Output

2
1

Subtasks

• ~30\%~ số điểm của bài tương ứng với các test có ~1 \le N, M \le 300~, ~1 \le Q \le 2000~.