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

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

• 1 i: Изменить цвет вершины $i$ (белый $\to$ чёрный, чёрный $\to$ белый).
• 2: Вывести максимальное расстояние между всеми парами белых вершин $a$ и $b$. При этом $a$ и $b$ могут совпадать. Если белых вершин нет, вывести $-1$.

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

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

Со второй строки на протяжении $N-1$ строк задаются номера двух вершин $u$ и $v$, соединённых $i$-м ребром, и длина ребра $w$.

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

Далее на $M$ строках по одному в строке заданы запросы.

Длина ребра всегда является целым числом, не меньшим $-1\,000$ и не большим $1\,000$.

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

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

Примеры

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

3
1 2 1
1 3 1
7
2
1 1
2
1 2
2
1 3
2

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

2
2
0
-1