#agc057c. [agc057_c]Increment or Xor

[agc057_c]Increment or Xor

Problem Statement

You are given a positive integer NN and a sequence A=(A0,A1,ldots,A2N1)A = (A_0, A_1, \\ldots, A_{2^N-1}) of 2N2^N terms, where each AiA_i is an integer between 00 and 2N12^N-1 (inclusive) and AineqAjA_i\\neq A_j holds if ineqji\\neq j.

You can perform the following two kinds of operations on AA:

  • Operation ++: For every ii, change AiA_i to (Ai+1)bmod2N(A_i + 1) \\bmod 2^N.
  • Operation oplus\\oplus: Choose an integer xx between 00 and 2N12^N-1. For every ii, change AiA_i to AioplusxA_i\\oplus x.

Here, oplus\\oplus denotes bitwise mathrmXOR\\mathrm{XOR}.

What is bitwise mathrmXOR\\mathrm{XOR}?

The bitwise mathrmXOR\\mathrm{XOR} of non-negative integers AA and BB, AoplusBA \\oplus B, is defined as follows:

  • When AoplusBA \\oplus B is written in base two, the digit in the 2k2^k's place (kgeq0k \\geq 0) is 11 if exactly one of AA and BB is 11, and 00 otherwise.

For example, we have 3oplus5=63 \\oplus 5 = 6 (in base two: 011oplus101=110011 \\oplus 101 = 110).

Your objective is to make Ai=iA_i = i for every ii. Determine whether it is achievable. It can be proved that, under the Constraints of this problem, one can achieve the objective with at most 10610^6 operations if it is achievable at all. Print such a sequence of operations.

Constraints

  • 1leqNleq181\\leq N\\leq 18
  • 0leqAileq2N10\\leq A_i \\leq 2^N - 1
  • AineqAjA_i\\neq A_j, if ineqji\\neq j

Input

Input is given from Standard Input in the following format:

NN A0A_0 A1A_1 ldots\\ldots A2N1A_{2^N - 1}

Output

If it is possible to make Ai=iA_i = i for every ii, print Yes; otherwise, print No.

In the case of Yes, it should be followed by a sequence of operations that achieves the objective, in the following format:

KK x1x_1 x2x_2 ldots\\ldots xKx_K

Here, KK is a non-negative integer representing the number of operations, which must satisfy 0leqKleq1060\\leq K\\leq 10^6; xix_i is an integer representing the ii-th operation, which should be set as follows.

  • If the ii-th operation is Operation ++, xi=1x_i=-1.
  • If the ii-th operation is Operation oplus\\oplus, xix_i should be the integer chosen in that operation.

If there are multiple possible solutions, you may print any of them.


Sample Input 1

3
5 0 3 6 1 4 7 2

Sample Output 1

Yes
4
-1 6 -1 1

The sequence of operations above changes the sequence AA as follows.

  • Initially: A=(5,0,3,6,1,4,7,2)A = (5,0,3,6,1,4,7,2)
  • Operation ++: A=(6,1,4,7,2,5,0,3)A = (6,1,4,7,2,5,0,3)
  • Operation oplus\\oplus (x=6x = 6):A=(0,7,2,1,4,3,6,5)A = (0,7,2,1,4,3,6,5)
  • Operation ++: A=(1,0,3,2,5,4,7,6)A = (1,0,3,2,5,4,7,6)
  • Operation oplus\\oplus (x=1x = 1):A=(0,1,2,3,4,5,6,7)A = (0,1,2,3,4,5,6,7)

Sample Input 2

3
2 5 4 3 6 1 0 7

Sample Output 2

No

No sequence of operations achieves the objective.


Sample Input 3

3
0 1 2 3 4 5 6 7

Sample Output 3

Yes
0

Performing zero operations achieves the objective. Whether an empty line is printed or not does not affect the verdict.