P7434 「MCOI-04 / AC6-M09」Heavy Command Cruiser

This is an operational deployment order. We have obtained some classified intelligence about the enemy’s heavy command cruiser from the National Security Agency. The official name of the enemy cruiser 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 in front of Aigaion at the same time to carry out the refueling operation. When tankers are refueling at the front of Aigaion, Aigaion’s radar detection capability will be temporarily weakened. This is the key point. While refueling, Aigaion’s radar is basically completely unable to 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 to take down this monster is when it is refueling. Aigaion’s planned route map is also included in this intelligence. After the briefing ends, we will check the route map again in the hangar. Go get ready. ………… Garuda team, 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 a plane, with root $1$, and the root has depth $0$. For a node with depth $x$, its **$y$-coordinate** is $n-x+1$. For all children of a node, they are arranged **from left to right in increasing order of node number**. 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**. Each segment or ray has a weight. **Any two segments or rays intersect only at the tree’s nodes.** If you do not understand how this tree is drawn, you may 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 cannot pass through any point other than $u$ and $v$. Each time you pass through a segment or ray, you must pay a cost equal to its weight. Your goal is to reach point $v$. You need to find the minimum cost during the movement.

Direct input would cause an extremely large 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)

Output two integers separated by two spaces, representing the XOR of all answers and the sum of all answers.

idea: Sol1, solution: dengyaotriangle & Sol1 & Guoyh, code: Sol1, data: Sol1. Constraints: For $100\%$ of the testdata, $1\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^6$, $1\leq f_i