This is an interactive 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 $2hn$ queries. Your score depends on the number of queries per test case and the maximum number of times any single integer $u$ is queried.

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

Implementation Details

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

You must ensure your program includes the header file tree.h, which can be done by adding the following line at the beginning of your code:

#include "tree.h"

You need to implement the following function:

long long solve(int subtask, int h);

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

You 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 \le u \le n$.
• $d$ is the distance limit; you must ensure $1 \le d \le 10^9$.
• This function returns the sum of $f$ values for all nodes $v$ such that $\operatorname{dis}(p_u, v) = d$.

The interactor is guaranteed to run within $1$ second under the specified query limits. The memory usage of the interactor is fixed and does not exceed $32 \text{ MiB}$.

Testing Your Program

The grader.cpp provided in the problem directory is a reference implementation of the interactor. The actual interactor used for final testing may differ from this reference, so your solution should not rely on the specific implementation of the interactor.

You can compile your program with the following command:

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

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

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

For the compiled executable:

• The program reads from standard input in the following format:
  • The first line contains two integers $c$ and $T$, representing the test case ID 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.
    • 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. 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 you use small test data when debug mode is enabled to avoid unexpected output.

Examples

Input 1

1 1
2
2 1 3
11 45 14

Output 1

70

Note

The interaction process for the example above: - The interactor calls solve(1, 2). - The participant calls ask(1, 1), returns $11$. - The participant calls ask(2, 1), returns $59$. - The participant calls ask(3, 1), returns $11$. - The participant returns $70$.

Provided Files

In the problem directory:

1. grader.cpp is the provided reference interactor.
2. tree.h is the header file; you do not need to worry about its contents.
3. template_tree.cpp is the provided sample code, which you can use as a base for your implementation.

Participants should back up all provided files. During final evaluation, only tree.cpp in the problem directory will be tested; modifications to other files will not affect the evaluation results.

Constraints

For all test cases: $2 \le h \le 15$, $1 \le T \le 1\,500$, and the sum of $n$ over all test cases $\sum n \le 10^6$.

There are $2$ test points. The score and constraints for each are shown in the table below.

Scoring

Note:

• Participants must not obtain internal information about the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating.
• The final evaluation interactor is different from the sample interactor and may be adaptive: it may dynamically adjust the hidden permutation $p$ and node weights $f$ as long as it does not contradict previous ask results.

This problem is subject to the same standard constraints as others. For example, compilation errors result in $0$ points, while runtime errors, time limit exceeded, or memory limit exceeded result in $0$ points for the corresponding test point. You may only access variables or data defined by you 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 solve function call, the number of operations $q$ must satisfy $q \le 2hn$; otherwise, you will receive $0$ points.

Based on the above conditions:

• For Test Point $1$, you receive full marks if and only if the solve function returns the correct answer.
• For Test Point $2$, your score is calculated as follows:
  • If the solve function returns an incorrect answer, you receive $0$ points.
  • If the solve function returns the correct answer, your score for the test point is calculated based on all test cases: let $q$ be the number of operations used, and $x$ be the maximum number of times any single integer $u$ is queried. Your score is $f(q) - g(x)$.

$f(q)$ is the maximum score corresponding to the conditions satisfied by $q$ in the table below:

$g(x)$ is calculated as follows: