Given a rooted tree with $n$ nodes, where the $i$-th node is labeled with the number $i$.

There are $m$ queries. Each query provides $l, r, x$. Find the number of pairs of node labels $(i, j)$ such that $l \le i < j \le r$ and the lowest common ancestor (LCA) of $i$ and $j$ is node $x$.

Input

The first line contains three integers $n$, $m$, and $rt$, where $rt$ is the label of the root node.

The next $n-1$ lines each contain two integers $u$ and $v$, representing an edge.

The next $m$ lines each contain three integers $l$, $r$, and $x$, representing a query.

Output

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

Examples

Input 1

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

Output 1

0
2
0
1
7
0
2
0
1
0

Note

For 2 6 2: the valid pairs are $(2, 4)$ and $(2, 6)$.

For 4 6 4: the valid pair is $(4, 6)$.

For 3 10 2: the valid pairs are $(4, 8)$, $(4, 9)$, $(6, 8)$, $(6, 9)$, $(8, 9)$, $(8, 10)$, and $(9, 10)$.

For 3 10 4: the valid pairs are $(4, 6)$ and $(4, 10)$.

For 2 6 4: the valid pair is $(4, 6)$.

Subtasks

Idea: Ynoi, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

For $100\%$ of the data, $1 \le n, m \le 2 \cdot 10^5$, $1 \le l, r, x \le n$.