P7348 "MCOI-04" Heavy Control Cruise Aircraft.

This is a combat deployment order. We have obtained some classified intelligence about the enemy heavy command cruiser from the National Security Bureau. The enemy cruiser’s official name has been confirmed as P-1112 Aigaion. In the air fleet, there is a Kottos medium cruiser responsible for electronic support, and a Gyges medium cruiser responsible for short-range air defense. Aigaion, as the command aircraft, is responsible for everything related to cruise missiles. After obtaining this intelligence, we can draft a plan to destroy Aigaion. Listen carefully. Aigaion can only receive aerial refueling at the front of its fuselage. Multiple tankers must be simultaneously in front of Aigaion to conduct refueling operations. When tankers refuel at Aigaion’s front, Aigaion’s radar detection ability will be temporarily weakened. This is the key point. When Aigaion is refueling, its radar basically cannot detect objects flying in front of it. If you can maintain a fixed route and fly at a specific altitude, you can approach Aigaion from the air without being detected by the enemy. So the best time for us to take down this monster is when it is refueling in the air. Aigaion’s planned route map is also included in this intelligence. After the briefing, we will check the route map again in the hangar. Go get ready. ………… Garuda Squadron, engage! $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$

A rooted tree is given on the plane, with root $1$, and the depth of the root is $0$. For a node with depth $x$, its **$y$-coordinate** is $n-x+1$. For all children of a node, they are ordered **from left to right by increasing index**. Each edge is a **line segment connecting two points**. Each leaf node has a **ray parallel to the $y$-axis and extending infinitely in the negative $y$ direction**, and the root node has a **ray parallel to the $y$-axis and extending infinitely in the positive $y$ direction**. **Any two line segments or rays intersect only at the nodes of the tree.** If you do not understand how this tree is drawn, you can read the explanation of Sample 1. Given $q$ pairs $(u, v)$, you now start from point $u$ and can move freely on the plane, but you are not allowed to pass through any point other than $u$ and $v$. Each time you pass through a line segment or a ray, it costs $1$. Your goal is to move to point $v$. You need to find the minimum cost incurred during the movement.

Direct input would cause an enormous input size, so this problem uses a special input method. The following random number generator is given: ```cpp namespace GenHelper { unsigned z1,z2,z3,z4,b; unsigned rand_() { b=((z113; z1=((z1&4294967294U)

If $s=-1$, output $q$ lines, each being the answer to the corresponding query. If $s\geq 0$, output two integers separated by two spaces, representing the XOR of all answers and the sum of all answers, respectively.

**For the enhanced version, see [P7434](https://www.luogu.com.cn/problem/P7434).** #### Sample 1 Explanation In the second query, the actual query is $u=6, v=3$. All other queries satisfy $u'=u, v'=v$.  - It can be seen that going from $4$ to $7$ requires passing through one line. - Going from $6$ to $3$ does not require passing through any line. - Going from $5$ to $2$ does not require passing through any line. - Going from $4$ to $8$ requires passing through one line. - Therefore the answers are $1, 0, 0, 1$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (1 pts): $f_i=i-1$, $s=-1$. - Subtask 2 (9 pts): $f_i=1$, $s=-1$. - Subtask 3 (10 pts): $n, q\leq 2\times 10^3$, $s=-1$. - Subtask 4 (20 pts): $f_i=\left\lfloor\dfrac{i}{2}\right\rfloor$, $s=-1$. - Subtask 5 (59 pts): $s=-1$. - Subtask 6 (1 pts): no special constraints. For $100\%$ of the data: $1\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^6$, $1\leq u,v\leq n$, $1\leq f_i