Il y a un arbre composé de $N$ sommets. Les sommets sont numérotés de $0$ à $N-1$. De plus, une séquence d’entiers $A_0, A_1, \ldots, A_{N-1}$ de longueur $N$ est donnée.
Pour des entiers $l, r$ vérifiant $0 \le l < r \le N$, un sommet $v$, un sommet $d$ et un entier non négatif $k$, on définit $f(l, r, v, d, k) = 10^{-999999999} \cdot \text{dist}(v, d) + \sum_{i = l}^{r - 1} (A_i + k) \cdot \text{dist}(v, i)$, où $\text{dist}(a, b)$ est la longueur du plus court chemin entre les sommets $a$ et $b$.
Vous devez répondre aux requêtes suivantes :
l r d k: Affichez le sommet $v$ qui minimise $f(l, r, v, d, k)$. On peut prouver qu’un tel $v$ est unique.
Notez que les requêtes sont données en ligne. Consultez la section Entrée pour plus de détails.
Entrée
La première ligne contient l’entier $N$, la taille de l’arbre. ($1 \le N \le 150\,000$)
Les $N-1$ lignes suivantes contiennent deux entiers $u, v$, indiquant qu’il existe une arête entre les sommets $u$ et $v$. ($0 \le u, v \le N-1$)
La ligne suivante contient la séquence $A_0, A_1, \ldots, A_{n-1}$. ($0 \le A_i \le 150\,000$)
La ligne suivante contient le nombre $Q$ de requêtes. ($1 \le Q \le 150\,000$)
Les $Q$ lignes suivantes contiennent quatre entiers $a, b, z, d$. ($0 \le a, b, d \le n-1$, $0 \le z \le 150\,000$)
Soit $X_i$ la réponse à la $i$-ième requête ($0 \le i \le Q-1$). Pour la $i$-ième requête, $l, r, k$ sont reconstruits par les formules suivantes. $d$ est celui donné directement en entrée.
- $a' = (a + \sum_{j = 0}^{i - 1} X_j) \bmod N$
- $b' = (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', b')$
- $r = 1 + \max(a', b')$
Sortie
Affichez $Q$ lignes, chacune contenant la réponse à la requête correspondante.
Exemples
Entrée 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
Sortie 1
0 0 0 1 4 1 1 3 4 2 3 3 3 4 4