C. Необычное произведение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Крис — большой любитель линейной алгебры. На этот раз в его домашней работе идет речь о необычном квадрате квадратной матрицы.

Скалярное произведение двух целочисленных векторов 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 запросов; каждый запрос может быть одним из следующих:

  1. дан номер строки i, выполните флип всех элементов в i-й строке A;
  2. дан номер столбца i, выполните флип всех элементов в i-м столбце A;
  3. вычислите необычный квадрат 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