Hypercube Perfect Matching

We are given a positive integer (N) and a sequence (a_0,a_1,\ldots,a_{N-1}) of nonnegative integers. Initially, we have the set (S = {0,1,\ldots,2^N-1}). A process is performed exactly (2^{N-1}) times. In each operation, two numbers (X, Y \in S) are chosen so that (X \oplus Y = 2^k) for some (k \in \mathbb{N}) (here (\oplus) denotes bitwise XOR), these two numbers are removed from (S), and a counter (b_k) is increased by one. At the end, the resulting sequence (b = (b_0, b_1, \ldots, b_{N-1})) is compared with the given sequence (a = (a_0,a_1,\ldots,a_{N-1})).

It can be shown that a valid pairing exists if and only if the given sequence (a) is exactly one of the standard perfect matchings of the (N)-dimensional hypercube. In other words, a solution exists if and only if (\sum_{i=0}^{N-1}a_i = 2^{N-1}) and there is exactly one index (k) for which (a_k = 2^{N-1}) (with all other (a_i = 0)). In that case the unique solution is to take the perfect matching

[ M_k = {,(x, x \oplus 2^k) : 0 \le x < 2^N,; x < x \oplus 2^k},. ]

Your task is to determine whether a valid pairing exists. If it does, print "Yes" and output a valid set of (2^{N-1}\n pairs that partitions (S) (i.e. every element of (S) appears in exactly one pair) such that for the unique index (k) with (a_k = 2^{N-1}) every pair ((X,Y)) satisfies (X \oplus Y = 2^k). Otherwise, print "No".

All formulas are typeset in LaTeX.

inputFormat

The first line contains a positive integer (N). The second line contains (N) space‐separated integers (a_0,a_1,\ldots,a_{N-1}).

outputFormat

If a valid pairing does not exist, output a single line containing “No”. Otherwise, on the first line output “Yes”. Then output exactly (2^{N-1}) lines, each containing two space‐separated integers (X) and (Y) ((0 \le X,Y < 2^N)) representing a pair satisfying (X \oplus Y = 2^k) (with the same (k) for all pairs). The pairs must form a partition of (S).

sample

1
1

Yes
0 1