Problem description

Bitek odnalazł drzewo genealogiczne swojej rodziny. Nie jest to zwykłe drzewo genealogiczne, ponieważ nie opisuje ono poszczególnych członków rodziny, ale klany należące do rodziny Bitka. Drzewo klanów składa się z N klanów, każdy klan bezpośrednio wywodzi się z innego klanu, poza klanem założycielskim. Każdy z klanów ma swój herb, jednakże Bitek zauważył, że pewne klany korzystały z tego samego herbu, niezależnie od odległości klanów w drzewie genealogicznym. Dla uproszczenia, klany opisane są kolejnymi liczbami naturalnymi 1, 2, …, N, a rodzaj herbu i-tego klanu to h_i. Klan założycielski ma numer 1.

Bitek wymyślił następującą grę. Zaczyna od wyboru dwóch klanów u i v oraz rodzaju herbu h, a następnie szuka takiego klanu w, z którego wywodzą się klany u oraz v, oraz jego rodzaj herbu to h. Wśród wszystkich możliwych klanów w interesuje go taki, który jest najmłodszy (tzn. nie ma żadnego klanu w′, który spełniałby powyższe warunki oraz wywodziłby się z klanu w).

Formalnie mówimy, że klan u wywodzi się z klanu w, jeżeli zachodzi jeden z poniższych warunków:

• u = w,
• u wywodzi się bezpośrednio z w,
• u wywodzi się bezpośrednio z pewnego klanu p, który wywodzi się z w.

Drzewo klanów rodziny Bitka okazało się na tyle duże, że zabawa sprawia mu większy kłopot, niż się początkowo spodziewał. Pomóż mu i napisz program, który będzie odpowiadał na zapytania Bitka.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N oraz Q oznaczające odpowiednio liczbę klanów oraz liczbę zapytań Bitka. W następnym wierszu znajduje się opis drzewa, składający się z N − 1 liczb p₂, p₃, …, p_N. Wartość p_i mówi o tym z jakiego klanu bezpośrednio wywodzi się klan i. W następnym wierszu następuje N liczb h₁, …, h_N opisujących numery herbów kolejnych klanów. W następnych Q wierszach następuje opis zapytań. Każde zapytanie składa się z trzech liczb u, v, h wg opisu gry Bitka.

Wyjście

Należy wypisać Q wierszy odpowiadających na kolejne zapytania Bitka, będące numerami klanów, które są odpowiedzią na dane zapytanie. Jeżeli dla danego zapytania nie istnieje klan spełniający warunki Bitka, należy dla tego zapytania wypisać liczbę -1.

Ograniczenia

1 ≤ N, Q ≤ 200 000, 1 ≤ p_i, h_i, u, v, h ≤ N, p_i < i dla i = 1, …, N.

Przykład

5 3
1 1 3 3
1 3 1 2 1
2 5 1
4 3 3
2 2 3

1
-1
2

10 10
1 2 2 3 5 5 6 6 8
2 3 1 2 4 1 4 1 2 4
5 4 2
1 1 1
10 6 3
10 9 2
1 1 1
6 3 3
2 1 1
5 7 1
3 5 3
3 9 1

1
-1
2
1
-1
2
-1
3
2
3