Бяцхан Крис шугаман алгебрын маш том фен. Энэ удаад түүнд квадрат матрицийн содон үржвэрийн тухай гэрийн даалгавар өгсөн.

$n$ хэмжээтэй $x$ ба $y$ векторуудын цэгийн үржвэр нь векторуудын харгалзах бүрэлдэхүүн хэсгүүдийн үржвэрүүдийн нийлбэр байна. $n × n$ хэмжээтэй $A$ матрицийн содон үржвэр нь $n$ цэгийн үржвэрүүдийн нийлбэр байна. Эдгээрийн $i$-р нь $A$ матриц дахь $i$-р мөрийн вектор болон $i$-р баганын векторуудын цэгийн үржвэр байна.

Аз болж крис зөвхөн $GF(2)$-тай ажиллана! Энэ нь бүх үйлдлүүд (нэмэх болон үржүүлэх) 2-т дээр явагдана гэсэн үг. Үнэн хэрэгтээ $A$ матриц нь хоёртынх ба $A$ матрицийн элемент бүр 0 эсвэл 1 байна. Жишээлбэл доорх $A$ матрицийг авч үзье:

$A$ матрицийн содон үржвэр нь $(1*1 + 1*0 + 1*1) + (0*1 + 1*1 + 1*0) + (1*1 + 0*1 + 0*0) = 0 + 1 + 1 = 0$ байна.

Гэсэн ч гэрийн даалгаварт илүү их зүйлс байна. Крис $q$ асуулгыг боловсруулах ёстой; асуулга бүр дараах зүйлсийн нэг байна:

1. өгөгдсөн мөрийн дугаар $i$-н хувьд $A$ дахь $i$-р мөрийн бүх утгыг эсрэгээр нь солих;
2. өгөгдсөн баганын дугаар $i$-н хувьд $A$ дахь $i$-р баганын бүх утгыг эсрэгээр нь солих;
3. $A$-н содон үржвэрийг олох.

Бит утга $w$-н утгыг солих гэдэг нь $1 - w$ болгож солино гэсэн үг буюу өөрөөр 1-г 0, 0-г 1 болгож солино гэсэн үг.

Анхны $A$ матриц өгөгдсөн бол гуравдугаар төрлийн асуулга бүрийн хувьд хариултуудыг хэвлэ. Та Крист гэрийн даалгавраа шийдэхэд нь туслах уу?

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 1000$) байх буюу $A$ матрицийн мөр болон баганын тоо юм. Дараагийн $n$ мөрөнд матрицийг тодорхойлно: $i$-р мөрөнд зайгаар тусгаарлагдсан $n$ бит байх ба $A$ матрицийн $i$-р мөрийг агуулна. $i$-р мөрний $j$-р элемент $a_{ij}$ ($0 ≤ a_{ij} ≤ 1$) нь $A$ матрицийн $i$-р мөр болон $j$-р баганын огтлолцол дээр байрлах элемент юм.

Оролтын дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 10^{6}$) байх буюу асуулгуудын тоо юм. Дараагийн $q$ мөр бүрт нэг асуулгыг тодорхойлох ба дараах хэлбэрүүдийн аль нэг нь байна:

• 1 $i$ -- $i$-р мөрийн бүх утгыг эсрэгээр нь солих;
• 2 $i$ -- $i$-р баганын бүх утгыг эсрэгээр нь солих;
• 3 -- $A$ матрицийн содон үржвэрийг хэвлэх.

Тэмдэглэл: оролт болон гаралтын хэмжээ маш их байж болох учраас програмчлалын хэлүүдийн гаралтын удаан аргуудыг бүү ашиглаарай. Жишээлбэл С++ хэлэнд (cin, cout) оролт гаралтын урсгалыг битгий ашиглаарай.

Гаралт

Оролт дахь 3-р төрлийн асуулгуудын тоог $m$ гэе. Гаралтанд $m$ урттай $s$ тэмдэгт мөр хэвлэх ба энд $s$ тэмдэгт мөрийн $i$-р тэмдэгт нь оролтонд байгаа $i$-р гуравдугаар төрлийн асуулгын хариу болох содон үржвэрийн утга юм.