33OJ
登录 注册

#P17527. [JAG 2026 Summer Camp #1] XOR Cycle

[JAG 2026 Summer Camp #1] XOR Cycle

Problem Description

You are given 2N2N nonnegative integers A1,B1,A2,B2,…,AN,BNA_1,B_1,A_2,B_2,\ldots,A_N,B_N.

Determine whether there exists a sequence of nonnegative integers X=(X1,X2,…,XN)X=(X_1,X_2,\ldots,X_N), each less than 2302^{30}, that satisfies the following condition. If such a sequence exists, output any one of them.

  • For each i=1,2,…,Ni=1,2,\ldots,N, $X_i\equiv (A_i\oplus X_{i-1})+(B_i\oplus X_{i-1})\pmod{2^{30}}$.

Here, we define X0=XNX_0=X_N. Also, a⊕ba\oplus b denotes the bitwise XOR of aa and bb.

Input Format

The input contains one or more test cases. The first line of the input contains an integer TT (1≤T≤2×1051\le T\le 2\times 10^5), representing the number of test cases. The descriptions of the TT test cases follow, each in the following format:

N
A_1 B_1
A_2 B_2
...
A_N B_N

The first line contains an integer NN, representing the length of AA and BB (1≤N≤2×1051\le N\le 2\times 10^5). For each i=1,2,…,Ni=1,2,\ldots,N, the ii-th of the following NN lines contains two integers AiA_i and BiB_i (0≤Ai,Bi<2300\le A_i,B_i<2^{30}).

The sum of NN over all test cases does not exceed 2×1052\times 10^5.

Output Format

For each test case, if such a sequence XX exists, output Yes followed by XX in the following format:

Yes
X_1 X_2 ... X_N

Otherwise, output No.

If multiple sequences XX satisfy the condition, you may output any one of them.

3
2
4 7
1 0
1
0 1
1
536870912 536870912
Yes
3 5
Yes
1
Yes
0