Дано дерево (связный граф без циклов) с $N$ вершинами. Вершины пронумерованы от $1$ до $N$, рёбра — от $1$ до $N-1$. Каждая вершина имеет цвет (чёрный или белый) и вес.

Напишите программу, которая выполняет следующие три типа запросов:

• 1 i: изменить цвет вершины $i$ (белый $\to$ чёрный, чёрный $\to$ белый).
• 2 u: найти вершину $v$, соединённую с $u$, имеющую наибольший вес, и вывести его. Две вершины считаются соединёнными, если все вершины на пути между ними одного цвета. При этом $u$ и $v$ могут совпадать.
• 3 u w: изменить вес вершины $u$ на $w$.

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

Первая строка содержит $N$ ($2 \le N \le 100\,000$).

В следующих $N-1$ строках даны номера двух вершин $u$ и $v$, соединённых $i$-м ребром.

В следующей строке даны цвета вершин от $1$ до $N$: $0$ (чёрный) или $1$ (белый).

В следующей строке даны веса вершин в порядке от $1$ до $N$.

В следующей строке дано количество запросов $M$ ($1 \le M \le 100\,000$).

В следующих $M$ строках даны запросы, по одному в строке.

Все веса — натуральные числа, не превышающие $10^9$.

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

Для каждого запроса типа $2$ выведите результат в отдельной строке в порядке появления запросов.

Примеры

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

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
2 1
1 1
2 1

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

1
5

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

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

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

7
5
7