Background

I do not need to be so fired up every day,
but I can keep living while searching for you.

Problem Description

Given a positive integer $h$. We define $n=2^h-1$.

Now, for every positive integer $u$ not greater than $n$ and every positive integer $k$ not greater than $2h-2$, the value of $f_{u,k}$ is given. You need to construct a pair $(r,w)$ satisfying $1 \le r \le n$, $0 \le w \lt 2^{30}$, such that there exists a full binary tree $T$ with $h$ levels satisfying:

• The labels of all nodes in the full binary tree $T$ form a permutation of $1 \sim n$, and each node has a weight.
• The root of the full binary tree $T$ is node $r$.
• The weight of each node in the full binary tree $T$ is a non-negative integer less than $2^{30}$, and the weight of the root node is $w$.
• For every positive integer $u$ not greater than $n$ and every positive integer $k$ not greater than $2h-2$, the xor sum of the weights of all nodes $v$ satisfying $\operatorname{dis}(u,v)=k$ is $f_{u,k}$. In particular, if there is no node $v$ satisfying the condition, then $f_{u,k}=0$ must hold.

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

It is guaranteed that there exists at least one pair $(r,w)$ that satisfies the requirements.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

Then each test case is given as follows. For each test case:

• The first line contains a positive integer $h$.
• The next $n$ lines: line $u$ contains $2h-2$ integers, where the $k$-th integer represents the value of $f_{u,k}$.

Output Format

For each test case, output one line with two integers, representing $r$ and $w$ in your constructed pair $(r,w)$.

• If your constructed pair $(r,w)$ satisfies the requirements, you get $100\%$ of the score for that test point.
• Otherwise, if your constructed pair $(r,w)$ does not satisfy the requirements, but there exists a valid pair $(r',w')$ such that $r'=r$, you get $50\%$ of the score for that test point.
• Otherwise, if your constructed pair $(r,w)$ does not satisfy the requirements, but there exists a valid pair $(r',w')$ such that $w'=w$, you get $50\%$ of the score for that test point.
• Otherwise, you get no score for that test point.

2
2
1 0
2 0
1 2
4
75 0 89 1 0 56
0 52 19 84 1 0
0 27 19 108 1 0
0 89 1 0 56 0
85 19 108 1 0 0
75 0 89 1 0 56
1 1 56 0 0 0
0 88 19 84 1 0
0 79 19 108 1 0
74 0 88 1 0 56
0 88 1 0 56 0
109 19 84 1 0 0
19 56 1 0 0 0
74 0 88 1 0 56
18 1 0 56 0 0

2 1
7 19

Hint

[Sample Explanation #1]

For the first test case:

When the constructed pair $(r,w)=(2,1)$, there exists a binary tree as shown in the figure that satisfies the requirements, where the weights of nodes $1,2,3$ are $2,1,0$ respectively.

When you output 2 2, you can get $50\%$ of the score for that test point, because although $(r,w)=(2,2)$ does not satisfy the requirements, there exists a valid pair $(r',w')=(2,1)$ such that $r'=r=2$.

When you output 1 1, you can also get $50\%$ of the score.

But when you output 1 2, you will get no score for that test point.

[Constraints]

Let $\sum n$ denote the sum of $n$ within a single test point.

For all testdata, $1\le T \le 1000$, $2 \le h \le 16$, $\sum n \le 2^{16}$, $0 \le f_{u,k}\lt2^{30}$, and it is guaranteed that there exists at least one valid pair $(r,w)$.

This problem uses bundled judging.

• Subtask 1 (20 points): $h=2$.
• Subtask 2 (20 points): Satisfies a special property.
• Subtask 3 (60 points): No special restrictions.

Special property: There exists a pair $(r,w)$ satisfying $1 \le r \le n$, $0 \le w \lt 2^{30}$, and based on this, there exists a full binary tree that satisfies the requirements, where the weights of all nodes are equal to $w$.

Translated by ChatGPT 5