Условие

---

N. Най-близък общ предшественик 
---
Дадено е кореново дърво с n (1 ≤ n ≤ 100000) върха, номерирани с целите числа от 0 до n-1. Трябва да се отговори на m заявки за намиране на най-близкия общ предшественик на два върха.
 
Заявките се генерират по следния начин. Дадени са целите числа a1,a2 и числата x,y,z. Числата a3,a4,…,a2m се генерират по следния начин:  ai=(x.ai-2+y.ai-1+z)mod n. Първата заявка е за върховете (a1,a2). Ако отговора на (i-1)-вия въпрос е v, то i-тия въпрос е от вида ((a2i-1+v)mod n, a2i).  

Вход: Входът се състои от няколко набора входни данни. Всеки набор от входни данни има следния вид. Първо са дадени целите числа n и m. Корен на дървото е връх 0. Следва един ред с n-1 числа, като i-тото от тях е номера на предшественика на върха i. Следва един ред с целите числа a1 и a2 (0 ≤ a1,a2 ≤ n-1). Следващият ред съдържа три цели числа x,y,z (0 ≤ x,y,z ≤ 109). 

Изход: За всеки набор от входни данни изведете на отделен ред едно цяло число – сумата от отговорите на всички заявки за съответния набор от данни.
 
Примерен вход: 
3 2
0 1
2 1
1 1 0

Примерен изход:
2