Город, в котором живет маленький G, можно представить в виде ориентированного графа с $N$ вершинами и $M$ ребрами. В процессе развития города дороги в нем меняются; в частности, происходит $Q$ операций двух типов:

1. Дана вершина $p$ и $tot$ чисел $a_i$. В граф добавляются ребра из $a_i$ в $p$.
2. Дана вершина $p$ и $tot$ чисел $a_i$. Из графа удаляются ребра из $a_i$ в $p$.

Любопытному маленькому G хочется после каждой операции знать состояние достижимости между всеми парами вершин.

Пусть $F(u, v)$ обозначает состояние достижимости между $u$ и $v$: если в графе существует путь из $u$ в $v$, то $F(u, v) = 1$, иначе $F(u, v) = 0$. Легко заметить, что $F(u, v)$ не обязательно равно $F(v, u)$, а $F(u, u)$ всегда равно 1.

Для удобства запросов каждой вершине присвоен вес $val_i$. После каждой операции вам необходимо вычислить значение следующего выражения:

$$ \sum_{u=1}^{N} \sum_{v=1}^{N} F(u, v) \times (val_u \oplus val_v) $$

где $\oplus$ обозначает операцию побитового исключающего ИЛИ (XOR). Гарантируется, что исходный граф, а также граф после каждой операции не содержат кратных ребер и петель; кроме того, при удалении ребра гарантируется, что оно существует в графе. Также предусмотрены механизмы для принудительной онлайн-обработки запросов.

Входные данные

• Первая строка содержит целое число $ID$, обозначающее номер текущего набора тестовых данных; для примеров $ID$ всегда равен 0.
• Вторая строка содержит целое число $flag$, гарантированно равное $0$ или $1$; если $flag=1$, данные требуют принудительной онлайн-обработки.
• Третья строка содержит три целых числа $N, M, Q$, обозначающие количество вершин, количество ребер в исходном графе и количество операций соответственно.
• Четвертая строка содержит $N$ неотрицательных целых чисел, обозначающих веса вершин $val_i$.
• Далее следуют $M$ строк, каждая из которых содержит два целых числа $u, v$, обозначающих наличие ориентированного ребра из $u$ в $v$ в исходном графе.
• Далее следуют $2Q$ строк, каждые две строки описывают одну операцию:
  • Первая строка содержит три целых числа $k, p, tot$. Здесь $k$ равно $0$ или $1$: если $k=0$, выполняется операция добавления ребер, иначе — удаления.
  • Вторая строка содержит $tot$ различных целых чисел $a_i$.

Если $flag = 1$ (онлайн-режим), пусть $lastAns$ — ответ на предыдущую операцию (для первой операции $lastAns=0$). Тогда истинное значение $p$ вычисляется как $p \oplus lastAns$.

Примечание: $lastAns$ может быть очень большим!

Выходные данные

Выведите $Q$ строк, каждая из которых содержит одно целое число — ответ после соответствующей операции.

Примеры

Пример 1

0
0
10 10 1
0 1 1 1 1 1 1 1 1 0
1 7
2 1
7 3
3 7
10 2
8 5
2 10
2 5
3 6
4 5
0 1 0

Выходные данные 1

10

Пример 2

0
0
5 0 10
775753708 730589119 295766137 411078803 10973174
0 1 1
3
0 2 1
3
0 1 1
4
0 3 1
2
0 5 1
4
0 4 1
1
0 1 1
2
0 2 1
5
0 4 1
3
0 1 1
5

Выходные данные 2

1067190165
2043082587
2961479386
4033244915
4438519384
8158342623
8158342623
12528106804
12528106804
12528106804

Пример 3

0
0
5 7 5
505212782 768758516 141501571 189544889 292811675
2 1
2 3
2 5
3 1
3 4
4 1
5 3
0 3 2
1 4
1 5 1
2
0 1 1
5
1 1 4
2 3 4 5
0 5 1
2

Выходные данные 3

5862031096
4844805513
4844805513
2982371382
3999596965

Примечание

Эти три примера соответствуют типам 1, 2 и 3 соответственно.

Ограничения

Всего в задаче 20 тестов, каждый оценивается в 5 баллов. Все тесты разделены на три типа:

Тип 1 (всего 20 баллов)

Гарантируется $Q = 1$, $tot = 0$, то есть требуется только вычислить ответ для исходного графа. Также $0 \le val_i \le 1$.

Тип 2 (всего 40 баллов)

Гарантируется отсутствие операций удаления ребер, то есть $k = 0$ для всех операций; также $tot = 1$, $M = 0$.

Тип 3 (всего 40 баллов)

Без дополнительных ограничений:

Гарантируется, что 100% данных удовлетворяют следующим условиям:

• $N \ge 2$
• $0 \le M \le N(N-1)$
• $1 \le u, v, p, a_i \le N$
• $0 \le tot < N$
• $0 \le val_i \le 10^9$