Tích Lạ

Cho ma trận nhị phân $A$ kích thước $n\times n$ (mỗi phần tử là $0$ hoặc $1$). Mọi phép tính ở bài này được thực hiện trên $\mathrm{G}\mathrm{F}(2)$, tức là cộng và nhân đều lấy modulo $2$.

Định nghĩa tích lạ của ma trận $A$ là tổng (theo $\mathrm{G}\mathrm{F}(2)$) của $n$ tích vô hướng: tích vô hướng thứ $i$ là tích vô hướng giữa hàng thứ $i$ và cột thứ $i$ của $A$. Cụ thể:

$$\text{tích lạ}(A)=\sum _{i=1}^n\sum _{j=1}^n{a}_{i,j}·a_{j,i}\left(\mathrm{mod}2\right).$$

Cho ma trận $A$ ban đầu, bạn cần xử lý $q$ truy vấn, mỗi truy vấn thuộc một trong ba loại:

• 1 i — đảo bit toàn bộ hàng thứ $i$ (mỗi $a_{i,j}$ trở thành $1-a_{i,j}$).
• 2 i — đảo bit toàn bộ cột thứ $i$.
• 3 — in ra giá trị tích lạ của $A$ tại thời điểm hiện tại.

Gọi $m$ là số truy vấn loại $3$. Hãy in ra một xâu duy nhất gồm $m$ kí tự, kí tự thứ $i$ là kết quả của truy vấn loại $3$ thứ $i$ (theo đúng thứ tự xuất hiện trong dữ liệu vào).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ — kích thước ma trận.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,n}$ cách nhau bởi dấu cách.
• Dòng tiếp theo chứa số nguyên $q$ — số truy vấn.
• $q$ dòng tiếp theo mô tả các truy vấn theo định dạng ở trên.

Dữ liệu ra

In ra một xâu nhị phân duy nhất, mỗi kí tự là kết quả của một truy vấn loại $3$ theo thứ tự xuất hiện. Nếu không có truy vấn loại $3$ nào thì không in gì cả.

Ràng buộc

• $1\le n\le 1000$
• $1\le q\le {10}^6$
• $a_{i,j}\in \{0,1\}$
• Với mọi truy vấn loại $1$ hoặc $2$: $1\le i\le n$.

Lưu ý: do dữ liệu vào và dữ liệu ra có thể rất lớn, nên dùng các phương thức nhập xuất nhanh (ví dụ tránh cin/cout trong C++).

Ví dụ