| Codeforces Round 238 (Div. 2) |
|---|
| Закончено |
Маленький Крис — большой любитель линейной алгебры. На этот раз в его домашней работе идет речь о необычном квадрате квадратной матрицы.
Скалярное произведение двух целочисленных векторов x и y размера n — это сумма произведений соответствующих координат этих векторов. Необычный квадрат квадратной матрицы A размера n × n определяется как сумма n скалярных произведений: i-е из них — это скалярное произведение вектора i-й строки на вектор i-го столбца матрицы A.
К счастью для Криса, все арифметические операции нужно производить в поле 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 запросов; каждый запрос может быть одним из следующих:
- дан номер строки i, выполните флип всех элементов в i-й строке A;
- дан номер столбца i, выполните флип всех элементов в i-м столбце A;
- вычислите необычный квадрат A.
Применить операцию флип к элементу w — значит, изменить его на 1 - w (1 меняется на 0, а 0 меняется на 1).
По заданной матрице A и всем запросам, выведите ответы для каждого запроса третьего типа! Можете ли вы решить домашнюю работу Криса?
В первой строке записано целое число n (1 ≤ n ≤ 1000), количество строк и столбов в матрице A. Следующие n строк описывают матрицу: i-я строка содержит n целых чисел через пробел, j-е число в этой строке aij (0 ≤ aij ≤ 1) — это элемент, стоящий на пересечении i-й строки и j-го столбца матрицы A.
В следующей строке записано целое число q (1 ≤ q ≤ 106), количество запросов. Каждая из следующих q строк описывает запрос. Описание запроса может иметь один из нижеперечисленных форматов:
- 1 i — выполните флип всех элементов в i-й строке A;
- 2 i — выполните флип всех элементов в i-м столбце A;
- 3 — выведите необычный квадрат A.
Обратите внимание: входные и выходные данные имеют очень большой размер, не стоит использовать медленные методы ввода и вывода данных вашего языка программирования. Например, в языке C++ не стоит использовать потоки ввода и вывода (cin, cout).
Пусть количество запросов третьего типа во входных данных равняется m. Выведите единственную строку s длины m, где i-й символ строки s является значением необычного квадрата по модулю 2 матрицы A для i-го запроса третьего типа.
3
1 1 1
0 1 1
1 0 0
12
3
2 3
3
2 2
2 2
1 3
3
3
1 2
2 1
1 1
3
01001
