Дано дерево из $N$ вершин. Вершины пронумерованы от $0$ до $N-1$. Дополнительно дана целочисленная последовательность $A_0, A_1, \ldots, A_{N - 1}$ длины $N$.

Для целых чисел $l, r$ с $0 \le l < r \le N$, вершин $v, d$ и неотрицательного целого числа $k$ определим $f(l, r, v, d, k) = 10^{-999999999} dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) dist(v, i)$. Здесь $dist(a, b)$ — длина кратчайшего пути между вершинами $a$ и $b$.

Необходимо выполнить следующие запросы:

• l r d k: вывести $v$, минимизирующее $f(l, r, v, d, k)$. Можно доказать, что такое $v$ единственно.

Обратите внимание, что запросы поступают в онлайн-режиме. Подробнее см. в разделе «Входные данные».

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

В первой строке задан размер дерева $N$. ($1 \le N \le 150\,000$)

В следующих $N-1$ строках заданы два целых числа $u, v$, означающих, что существует ребро между вершинами $u$ и $v$. ($0 \le u, v \le N-1$)

В следующей строке задана последовательность $A_0, A_1, \ldots, A_{n-1}$. ($0 \le A_i \le 150\,000$)

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

В следующих $Q$ строках заданы четыре целых числа $a, b, z, d$. ($0 \le a, b, d \le n-1$, $0 \le z \le 150\,000$)

Пусть $X_i$ — ответ на $i$-й запрос ($0 \le i \le Q-1$). Для $i$-го запроса $l, r, k$ восстанавливаются по следующим формулам. Значение $d$ берется непосредственно из входных данных.

• $a^\prime = (a + \sum_{j = 0}^{i - 1} X_j) \text{ mod } N$
• $b^\prime = (b + 2 \sum_{j = 0}^{i - 1} X_j) \text{ mod } N$
• $k = (z + (\sum_{j = 0}^{i - 1} X_j)^2) \text{ mod } 150\,001$
• $l = \min(a^\prime, b^\prime)$
• $r = 1 + \max(a^\prime, b^\prime)$

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

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

Примеры

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

5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 0 0 0
0 1 150000 1
2 0 0 2
3 0 150000 3
4 2 150000 4
1 1 149975 0
0 0 149965 1
1 2 149951 2
1 4 149901 3
3 4 149804 4
2 0 149745 0
3 1 149639 1
1 4 149517 2
4 3 149375 3
0 1 149160 4

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

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