You are given a rooted tree with $n$ nodes.

You are given $m$ queries, each consisting of $l, r, x$. For each query, you need to find the number of nodes $u$ such that there exists at least one node $v$ satisfying $l \le v \le r$ where $u$ is the $x$-th ancestor of $v$.

The $x$-th ancestor of $v$ is the node reached by moving $x$ steps from $v$ towards the root. If the number of edges on the path from $v$ to the root is less than $x$, the $x$-th ancestor of $v$ does not exist.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, where the $i$-th integer represents the parent $fa_i$ of node $i$. If $fa_i = 0$, then $i$ is the root.

The next $m$ lines each contain three integers $l, r, x$.

Output

Output $m$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

2
1
3
3
1

Subtasks

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le l \le r \le n$, $1 \le x \le n$, and $0 \le fa_i \le n$. It is guaranteed that the $fa$ array forms a tree.

Subtask 1 ($11\%$): $n, m \le 10^3$.

Subtask 2 ($13\%$): $n, m \le 10^4$.

Subtask 3 ($17\%$): $n \le 5 \times 10^4$, $m \le 2 \times 10^5$.

Subtask 4 ($19\%$): $n \le 10^5$, $m \le 4 \times 10^5$.

Subtask 5 ($17\%$): $l = 1$.

Subtask 6 ($23\%$): No special constraints.