$N$ đỉnh tạo thành một cây. Các đỉnh được đánh số từ $0$ đến $N-1$. Ngoài ra, cho một dãy số nguyên $A_0, A_1, \ldots, A_{N-1}$ có độ dài $N$.

Với các số nguyên $l, r$ thỏa mãn $0 \le l < r \le N$, đỉnh $v, d$ và số nguyên không âm $k$, ta định nghĩa $f(l, r, v, d, k) = 10^{-999999999} \cdot dist(v, d) + \sum_{i = l}^{r - 1} (A_i + k) \cdot dist(v, i)$. Ở đây $dist(a, b)$ là độ dài đường đi ngắn nhất giữa hai đỉnh $a, b$.

Bạn cần thực hiện các truy vấn sau:

• l r d k: In ra đỉnh $v$ làm cho $f(l, r, v, d, k)$ đạt giá trị nhỏ nhất. Có thể chứng minh rằng $v$ như vậy là duy nhất.

Lưu ý rằng các truy vấn được đưa ra trực tuyến. Chi tiết xem phần Dữ liệu vào.

Dữ liệu vào

Dòng đầu tiên chứa kích thước của cây $N$. ($1 \le N \le 150\,000$)

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$, cho biết có cạnh nối hai đỉnh $u$ và $v$. ($0 \le u, v \le N-1$)

Dòng tiếp theo chứa dãy $A_0, A_1, \ldots, A_{n-1}$. ($0 \le A_i \le 150\,000$)

Dòng tiếp theo chứa số lượng truy vấn $Q$. ($1 \le Q \le 150\,000$)

$Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $a, b, z, d$. ($0 \le a, b, d \le n-1$, $0 \le z \le 150\,000$)

Gọi $X_i$ là đáp án cho truy vấn thứ $i$ ($0 \le i \le Q-1$). Với truy vấn thứ $i$, các giá trị $l, r, k$ được khôi phục theo các công thức sau (còn $d$ được dùng trực tiếp từ đầu vào):

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

Dữ liệu ra

In ra $Q$ dòng, mỗi dòng chứa đáp án của bài toán.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

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