Tree in a Segment

Είσοδος

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

The next $n$ lines describe the vertices, one per line. For each vertex $i$, the description is given by p_i c_i, where p_i is the parent of vertex $i$, and c_i is the color of vertex $i$ (1 \leq c_i \leq n). For the root vertex, p_i = 0.

The next $m$ lines give the queries, each formed by two numbers l_i, r_i (1 \leq l_i \leq r_i \leq n).

Έξοδος

Output $n$ lines, each with $m$ numbers. The numbers in the $i$-th line are the counts of vertices in the subtree rooted at vertex $i$ whose color falls within each respective query range.

Παραδείγματα