EduBrick

O. K-я вершина пути

2500 мс · 256 МБ · всё или ничего

Для каждого запроса (u,v,k)(u, v, k) выведите kk-ю вершину на пути из uu в vv, считая от uu и начиная с нуля. Если путь короче, выведите −1-1.

Формат ввода

В первой строке nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5), во второй — n−1n-1 родителей. Далее qq (1≤q≤2⋅1051 \le q \le 2 \cdot 10^5) и qq строк по три числа uu, vv, kk (0≤k<n0 \le k < n).

Формат вывода

Для каждого запроса выведите номер вершины или −1-1.

Примеры

ввод
5
0 0 1 1
4
3 4 0
3 4 1
3 4 2
3 4 9
вывод
3
1
4
-1
ввод
1

2
0 0 0
0 0 1
вывод
0
-1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.