Tree Trisection
Description
On the territory of Innopolis University there are many trees that require maintenance. In particular, Innopolis has weighted full binary trees that sometimes need to be pruned to prevent them from growing too quickly.
Consider a full binary tree with $n = 2^k$ leaves. Let's assign the root number $1$, its children numbers $2$ and $3$ (from left to right) and so on, numbering each layer of vertices with consecutive integers. The leaves of the tree will have numbers from $n$ to $2n - 1$. The weight of a vertex number $i$ is equal to $w_i$. The weight of a set of vertices is defined as the sum of the weights of the vertices in that set.
Your task is to determine how to prune the trees efficiently. A pruning request is specified by the leaf numbers $l$ and $r$, and is carried out as follows:
- First, a set of vertices $V$ is selected — this is the smallest connected set of vertices that contains all the leaves from the $l$-th to the $r$-th. Let's denote the vertex of the set $V$ that is closest to the root of the tree as $\mathtt{root}(V)$.
- Then, it is required to select in the set $V$ two different vertices $x$ and $y$ such that neither of them is a descendant of the other.
- Once the vertices $x$ and $y$ are chosen, the edges leading from $\mathtt{root}(V)$, $x$, and $y$ "upwards" (towards the root) are cut. As a result, $V$ is separated from the entire tree and breaks down into three subsets, denoted as $V_\mathtt{root}$, $V_x$ and $V_y$, respectively.
- After that, all three of these subsets are planted as separate sub-trees to enhance the landscaping of the territory.
The management has several options for how to prune the given tree. Your goal is to determine for each of their requests $(l, r)$ which vertices $x$ and $y$ should be chosen to minimize the maximum weight among $V_\mathtt{root}$, $V_x$, and $V_y$.
The first line contains two space-separated integers $n$ and $m$ — the number of leaves in the tree and the number of management's requests ($2 \le n \le 2^{16}$; $1 \le m \le 10^5$; $n = 2^k$ for some integer $k$).
The next line lists $2n - 1$ integers $w_i$ separated by a space — the weights of the tree vertices ($1 \le w_i \le 10^9$).
In the $i$-th of the following $m$ lines the $i$-th management's request is given as two integers $l_i$ and $r_i$ — the number of the first and last leaves involved in the pruning of the tree ($n \le l_i, r_i \le 2n - 1$; $r_i \ge l_i + 1$).
For each request, output in a separate line two space-separated integers $x$ and $y$ — the numbers of additional vertices where the tree should be cut to minimize the maximum weight of the three cut parts.
If there are several options for answers that minimize the maximum weight of the cut part, output any of them.
Scoring
By default, points for each subtask are awarded only if all tests of that subtask and the required subtasks are successfully passed. Points for a subtask with per-test scoring are awarded for each passed test independently (2 points for each of the sixteen tests).
| Subtask | Points | Constraints | Required subtasks | Scoring |
| 0 | – | examples | – | |
| 1 | 6 | $n \le 32$, $m \le 20$ | 0 | full group |
| 2 | 10 | $n \le 512$, $m \le 400$ | 0, 1 | full group |
| 3 | 13 | $r_i = l_i + 1$ for all $i$ | full group | |
| 4 | 23 | $w_i = 1$ for all $i$ | full group | |
| 5 | 16 | $n \le 1024$, $m \le 2000$ | 0 – 2 | full group |
| 6 | 16 $\times$ 2 | none | 0 – 5 | test-wise |
Input
The first line contains two space-separated integers $n$ and $m$ — the number of leaves in the tree and the number of management's requests ($2 \le n \le 2^{16}$; $1 \le m \le 10^5$; $n = 2^k$ for some integer $k$).
The next line lists $2n - 1$ integers $w_i$ separated by a space — the weights of the tree vertices ($1 \le w_i \le 10^9$).
In the $i$-th of the following $m$ lines the $i$-th management's request is given as two integers $l_i$ and $r_i$ — the number of the first and last leaves involved in the pruning of the tree ($n \le l_i, r_i \le 2n - 1$; $r_i \ge l_i + 1$).
Output
For each request, output in a separate line two space-separated integers $x$ and $y$ — the numbers of additional vertices where the tree should be cut to minimize the maximum weight of the three cut parts.
If there are several options for answers that minimize the maximum weight of the cut part, output any of them.
4 4
1 1 1 1 1 1 1
4 5
5 6
6 7
4 7
8 7
5 3 1 4 2 1 5 1 2 2 5 1 2 1 4
8 15
8 11
10 13
8 12
11 12
9 14
13 15
4 5
5 3
6 7
5 3
5 3
4 11
5 3
4 5
5 3
5 3
6 15
Note
Below is an illustration for the first four requests in the second example from the problem statement.
The weight of each vertex is marked. Vertices that are not included in the set $V$ are highlighted in gray. The selected leaves $l$ and $r$ are circled in green. The vertex $\mathtt{root}(V)$ is circled in red, and the vertices $x$ and $y$, which need to be chosen as the answer, are circled in blue. The edges that are cut during the corresponding pruning are highlighted with a dotted line.
