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:
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.
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$$$):
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]$$$.
4 51 4 2 31 2 4 53 4 6 71 12 23 34 41 42 31 14 42 2
1 5 3 3 3 5 3 2 1 2 1 1