This is an interactive problem.

After solving Ad-hoc Master, you want to solve the following problem.

Given a positive integer $h$, let $n=2^h-1$.

The interactor hides a permutation $p$ of $1 \sim n$ and a sequence $f$ of length $n$, where each element is a positive integer not exceeding $10^9$.

There is a full binary tree $G$ of depth $h$ containing $n$ nodes, with node $1$ as the root. For any node $u$ such that $2 \le u \le n$, its parent is node $\left\lfloor\dfrac u 2\right\rfloor$.

In each query, you can choose two integers $u$ and $d$ such that $1 \le u \le n$ and $1 \le d \le 10^9$. The interactor will return the sum of $f_v$ for all nodes $v$ that satisfy $\operatorname{dis}(p_u, v) = d$. Specifically, if no such node $v$ exists, the interactor returns $0$.

Here, $\operatorname{dis}(u, v)$ is the number of edges on the simple path between node $u$ and node $v$. Specifically, $\operatorname{dis}(u, u) = 0$.

You need to find the value of $\sum\limits_{i=1}^n f_i$ using no more than $5n$ queries; furthermore, for each integer $u$, you may perform at most $5$ queries. There are no other restrictions on the integer $d$. The contestant's score depends on the number of queries per test case.

It is not guaranteed that the permutation $p$ and the sequence $f$ are fixed; that is, the interactor may be adaptive.

Implementation Details

Contestants do not need to, and should not, implement the main function.

Contestants should ensure that the submitted program includes the header file tree.h, which can be achieved by adding the following code at the beginning of the program:

#include "tree.h"

Contestants need to implement the following function:

long long solve(int subtask, int h);

• subtask is the subtask number.
• $h$ is the height of the binary tree.
• This function must return the value of $\sum\limits_{i=1}^n f_i$.
• For each test point, this function may be called multiple times by the interactor.

Contestants can send a query to the interactor by calling the following function:

long long ask(int u, int d);

• $u$ is the center node of the query; you must ensure $1 \leq u \leq n$.
• $d$ is the distance limit of the query; you must ensure $1 \leq d \leq 10^9$.
• This function returns the sum of $f$ values of nodes whose distance to $p_u$ is exactly $d$.

The problem guarantees that the interactor runs within $1$ second under the specified operation limits. The memory used by the interactor is fixed and does not exceed $128 \text{ MiB}$.

Testing

The grader.cpp in the problem directory is a provided reference implementation of the interactor. The interactor used for final testing differs from this reference, so the contestant's solution should not rely on the implementation details of the interactor.

Contestants can compile the executable in the problem directory using the following command:

g++ grader.cpp tree.cpp -o tree -O2 -std=c++14

You can also add the -DDEBUG option to enable debug mode:

g++ grader.cpp tree.cpp -o tree -O2 -std=c++14 -DDEBUG

For the compiled executable:

• The executable will read data from standard input in the following format:
  • The first line contains two integers $subtask, T$, representing the subtask number and the number of test cases.
  • Each test case consists of three lines:
    • The first line contains a positive integer $h$.
    • The second line contains $n = 2^h - 1$ space-separated integers, representing the hidden permutation described in the problem.
    • The third line contains $n = 2^h - 1$ space-separated integers, representing the values of the sequence $f$.
• For each test case, the interactor will call the solve function once. After all tests are completed, the interactor will output the following information to the standard error stream:
  • The first line contains your score information.
  • The second line contains a description of the test results provided by the interactor.
• If debug mode is enabled, the interactor will print detailed information about each query to the standard error stream. Please ensure that the test data provided when debug mode is enabled is small to avoid unexpected issues.

Examples

Input 1

1 1
2
2 1 3
11 45 14

Output 1

70

Note

The interaction process for the example above: 1. The interactor calls solve(1, 2). 2. The contestant calls ask(1, 1), which returns $11$ (only node $1$ is at distance $1$ from $p_1 = 2$). 3. The contestant calls ask(2, 1), which returns $59$ (nodes $2, 3$ are at distance $1$ from $p_1 = 1$, sum is $45 + 14 = 59$). 4. The contestant calls ask(3, 1), which returns $11$ (only node $1$ is at distance $1$ from $p_1 = 3$). 5. The function returns $70$.

Provided Files

In the problem directory:

1. grader.cpp is the provided reference implementation of the interactor.
2. tree.h is the header file; contestants do not need to worry about its specific content.
3. template_tree.cpp is the provided sample code; contestants can implement their solution based on this code.
4. tree1.in is the sample interactor input corresponding to the "Examples" section.
5. tree2.in, tree3.in, tree4.in are sample interactor inputs satisfying subtasks $2 \sim 4$ respectively.

Constraints

For all test data, it is guaranteed that: $2 \leq h \leq 18$, the number of test cases $1 \leq T \leq 10^5$, and the sum of $n$ across all data $\sum n$ does not exceed $10^6$.

There are $4$ subtasks in total. The score and data range for each subtask are shown in the table below.

The score for a subtask is the minimum score among all test points in that subtask. See "Scoring" for the calculation method for a single test point.

Scoring

Note:

• Contestants should not obtain internal information of the interactor through illegal means, such as attempting to directly read the permutation $p$ or the sequence $f$, or interacting directly with standard input/output streams. Such behavior will be considered cheating.
• The final evaluation interactor is implemented differently from the sample interactor and may be adaptive: the final interactor may dynamically adjust the hidden permutation $p$ and node weights without contradicting the results previously returned by ask.

This problem is subject to the same standard constraints as traditional problems. For example, compilation errors will result in $0$ points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded will result in $0$ points for the corresponding test point. Contestants may only access variables or data defined by themselves or provided by the interactor, along with their corresponding memory space. Attempting to access other memory locations may result in compilation or runtime errors.

In each call to the solve function, the number of operations $q$ performed by the program must satisfy $q \leq 5n$, and the number of operations for the same $u$ must be at most $5$; otherwise, you will receive $0$ points.

Based on the above conditions, the score for the program will be calculated as follows:

• If the answer returned by the solve function is incorrect, you receive $0$ points.
• If the answer returned by the solve function is correct, the score is calculated for each test case in the subtask, and the minimum score is taken: let $q$ be the number of operations used by the program, and $x$ be the score of the subtask. The program will receive $x \cdot f(q)$ points, where $f(q)$ is calculated as the maximum score ratio corresponding to all satisfied conditions in the table below: