LCA

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Now you are given a rooted tree with N nodes(rank them from 0 to N-1). The depth of a node x is define as distance(x, root) + 1. The 0th node is always the root of the tree.

We have Q queries: given node x, and two integers L and R, you should calculate the value .

LCA(x,y) means the least common ancestor of node x and node y which is the common ancestor of x and y with maximum depth value.

Input

The first line contains two integers N and Q. (1 <= N, Q <= 50000)

The next N – 1 line each line contains an integer p indicate the father of node i. The integer in 2nd line indicating the father of node 1, 3rd line indicating the father of node 2, and so on.

The next Q lines each line contains three integers L, R, x which describe a query. (L <= R)

Output

For each query, you should output the answer moduled 201314.

Sample Input

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

Sample Output

8
5
1
5

Source

dut200901102

Manager

Information
Solved Number14
Submit Number76
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel