Маленький Крис — большой любитель линейной алгебры. На этот раз в его домашней работе идет речь о необычном квадрате квадратной матрицы.
Скалярное произведение двух целочисленных векторов 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 и всем запросам, выведите ответы для каждого запроса третьего типа! Можете ли вы решить домашнюю работу Криса?
Выходные данные
Пусть количество запросов третьего типа во входных данных равняется m. Выведите единственную строку s длины m, где i-й символ строки s является значением необычного квадрата по модулю 2 матрицы A для i-го запроса третьего типа.