E. Запросы частот
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Пети есть подвешенное дерево, на вершинах которого написаны целые числа. Корень — вершина $$$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$$$.

Ответьте, пожалуйста, на все вопросы про дерево.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^6$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит одно целое число $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 10^6$$$) — количество вершин в дереве и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$), где $$$a_i$$$ — число записанное на $$$i$$$-й вершине.

Третья строка содержит $$$n-1$$$ целых чисел $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$), где $$$p_i$$$ — родитель вершины $$$i$$$. Гарантируется, что значения $$$p$$$ задают корректное дерево.

Каждая из последующих $$$q$$$ строк содержит по три целых числа $$$v$$$, $$$l$$$, $$$k$$$ ($$$1 \leq v, l, k \leq n$$$) — описание вопросов.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого из запросов, выведите ответ на него. Если ответов несколько, то выведите любой.

Пример
Входные данные
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