B. Generalized Segment Tree
time limit per test
10 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a binary tree with $$$2n-1$$$ nodes, numbered from $$$1$$$ to $$$2n-1$$$.

Each node $$$p$$$ has two integer values $$$L_p$$$ and $$$R_p$$$ satisfying $$$L_p\le R_p$$$.

This binary tree satisfies the following properties:

  • Node $$$1$$$ is the root, and $$$L_1=1$$$, $$$R_1=n$$$.
  • For any node $$$p$$$:
    • If $$$L_p=R_p$$$, then node $$$p$$$ has no children.
    • If $$$L_p \lt R_p$$$, then node $$$p$$$ has two children. Here, we distinguish between the left child and the right child. Let $$$u$$$ be the left child and $$$v$$$ the right child; they satisfy $$$L_u=L_p$$$, $$$R_u+1=L_v$$$, and $$$R_v=R_p$$$.
We call such a tree a generalized segment tree.

For any interval $$$[l,r]$$$ with integer endpoints satisfying $$$1\le l\le r\le n$$$, consider the following algorithm: $$$$$$ \begin{array}{l} \textbf{function }\text{visit}(p,l,r,\textit{id})\\ \begin{array}{rl} 1&\textbf{if }r \lt L_p\text{ or }R_p \lt l\\ 2&\quad\textbf{return}\\ 3&\textit{cnt}_1[\textit{id}]\gets\textit{cnt}_1[\textit{id}]+1\\ 4&\textit{cnt}_2[p]\gets\textit{cnt}_2[p]+1\\ 5&\textbf{if }l\le L_p\text{ and }R_p\le r\\ 6&\quad\textbf{return}\\ 7&u\gets\text{left child of }p\\ 8&v\gets\text{right child of }p\\ 9&\text{visit}(u,l,r,\textit{id})\\ 10&\text{visit}(v,l,r,\textit{id}) \end{array} \end{array} $$$$$$ You are given $$$m$$$ intervals $$$[l_i,r_i]$$$ ($$$i=1,2,\cdots,m$$$). For each $$$i$$$, you call $$$\text{visit}(1,l_i,r_i,i)$$$ exactly once. All elements of the arrays $$$\textit{cnt}_1$$$ (indexed by $$$1,2,\cdots,m$$$) and $$$\textit{cnt}_2$$$ (indexed by $$$1,2,\cdots,2n-1$$$) are initially $$$0$$$. Your task is to find their final values.

Input

The first line contains two integers $$$n,m$$$ ($$$1\le n,m\le10^6$$$).

Each of the next $$$2n-1$$$ lines describes node $$$i$$$ (for $$$i=1,2,\cdots,2n-1$$$):

  • Each line first contains two integers $$$L_i,R_i$$$ ($$$1\le L_i\le R_i\le n$$$).
  • If $$$L_i \lt R_i$$$, there are two more integers $$$u,v$$$ ($$$2\le u,v\le2n-1$$$), denoting the left child and the right child of node $$$i$$$, respectively.
Each of the next $$$m$$$ lines contains two integers $$$l_i,r_i$$$ ($$$1\le l_i\le r_i\le n$$$).
Output

Output two lines.

The first line contains $$$m$$$ integers, the $$$i$$$-th of which is the final value of $$$\textit{cnt}_1[i]$$$.

The second line contains $$$2n-1$$$ integers, the $$$i$$$-th of which is the final value of $$$\textit{cnt}_2[i]$$$.

Example
Input
4 5
1 4 2 3
1 2 4 5
3 4 6 7
1 1
2 2
3 3
4 4
1 4
2 3
1 1
4 4
2 2
Output
1 5 3 3 3 
5 3 2 1 2 1 1