Дано корневое дерево, состоящее из n вершин. В каждой вершине записано некоторое число: в i-й вершине — ai.
Определим расстояние между вершинами i и j в дереве — d(i, j) (количество ребер на кратчайшем пути из i в j). Также определим поддерево глубины k вершины x — набор вершин y такой, что выполняются следующие условия:
- x является предком y (каждая вершина считается своим предком);
- d(x, y) ≤ k.
Заданы m запросов к дереву. i-й запрос представляется двумя числами xi и ki. Ответ на запрос — минимальное значение aj среди таких вершин j, что j принадлежат поддереву глубины ki вершины xi.
Напишите программу, которая быстро обработает такие запросы.
Обратите внимание, что запросы подаются в особом виде.
Выходные данные
Выведите m чисел. i-е из них должно быть ответом на i-й запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
|
2
5
|