У Пети есть подвешенное дерево, на вершинах которого написаны целые числа. Корень — вершина \(1\). Вам нужно ответить на некоторые вопросы про это дерево.
Дерево — это связный ацикличный граф. Подвешенное дерево имеет специальную вершину — корень. Родителем вершины \(v\) называется следующая вершина на кратчайшем пути от \(v\) до корня.
Каждый запрос задан тройкой целых чисел \(v\), \(l\), и \(k\). Чтобы на него ответить вы должны проделать следующие шаги:
- Сначала, выпишите последовательность чисел, записанных на вершинах простого пути от \(v\) до корня (включая вершину \(v\) и сам корень).
- Посчитайте, сколько раз каждой число встречается в этой последовательности. Выкиньте из неё числа, которые встречаются меньше, чем \(l\) раз.
- Преобразуйте последовательность, удалив из неё дубликаты, и упорядочив числа в ней возрастанию количеств вхождений в изначальную последовательность. В случая совпадения таких количеств, два числа располагаются в произвольном относительном порядке.
- Ответом на запрос является число, стоящее \(k\)-м в получившейся последовательности. Важно отметить, что так как порядок определён неоднозначно, то в качестве ответа примется любое число, которое могло стоять на этой позиции. Также может получиться, что в результирующей последовательности меньше \(k\), в таком случае ответом считается \(-1\).
Например, если последовательность чисел на пути от \(v\) до корня равна \([2, 2, 1, 7, 1, 1, 4, 4, 4, 4]\), \(l = 2\) и \(k = 2\), то ответ равен \(1\).
Ответьте, пожалуйста, на все вопросы про дерево.
Выходные данные
Для каждого из запросов, выведите ответ на него. Если ответов несколько, то выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 3
1 1 1
1 2
3 1 1
3 1 2
3 2 1
5 5
1 2 1 1 2
1 1 2 2
3 1 1
2 1 2
4 1 1
4 2 1
4 2 2
|
1 -1 1
1 1 2 1 -1
|