410467: GYM104023 L Novice Magician
Description
HoshiYo the Fox is a magician who is new to the magic school. As a novice, he is not proficient in many kinds of magic, especially those about numbers.
One day, HoshiYo learns a kind of magic that can change the integers in an array of length $$$2^n$$$. However, due to a lack of proficiency, he can only change half of the integers in the array each time he uses magic. Formally, let's denote the array as $$$a_0, a_1, \dots, a_{2^n-1}$$$, the following action can be performed by using the magic once:
- Choose $$$2^{n-1}$$$ different integers in the array and an integer $$$x$$$ (possibly negative), add $$$x$$$ to one of them, add $$$x+2$$$ to another one of them, add $$$x+4$$$ to another one of them, ..., and add $$$x+2^n-2$$$ to the last remaining one. In other words, choose $$$2^{n-1}$$$ different indices ranging from $$$0$$$ to $$$2^n-1$$$ denoted by $$$p_0,p_1,\dots,p_{2^{n-1}-1}$$$, and add $$$x+2i$$$ to $$$a_{p_i}$$$ for each integer $$$i$$$ within $$$0 \le i < 2^{n-1}$$$.
Initially, each integer in the array is $$$0$$$. HoshiYo has an ideal array $$$b_0, b_1, \dots, b_{2^n-1}$$$ in his mind. He wonders if he can get this ideal array by using magic at most $$$2^n$$$ times, i.e., to make $$$a_0=b_0,a_1=b_1,\dots,a_{2^n-1}=b_{2^n-1}$$$.
InputThe first line contains an integer $$$n$$$ ($$$1 \le n \le 11$$$), indicating that the length of the array is $$$2^n$$$.
The second line contains $$$2^n$$$ integers $$$b_0, b_1, \dots, b_{2^n-1}$$$ ($$$0 \le b_i \le 10^5$$$), indicating the ideal array.
OutputIf the ideal array cannot be obtained by using magic at most $$$2^n$$$ times, output NO in a single line.
Otherwise, output YES in the first line and an integer $$$k$$$ ($$$0 \le k \le 2^n$$$) in the second line indicating the number of times to use magic. Then output $$$k$$$ lines, each of which contains $$$2^{n-1}+1$$$ integers $$$x, p_0, p_1, \dots, p_{2^{n-1}-1}$$$ separated by spaces. You need to ensure that $$$p_0, p_1, \dots, p_{2^{n-1}-1}$$$ are distinct integers between $$$0$$$ and $$$2^n-1$$$, and each of $$$a_0, a_1, \dots, a_{2^n-1}$$$ is always in the range of $$$[-10^{18},10^{18}]$$$.
If there are multiple solutions, output any.
ExamplesInput2 1 14 5 14Output
YES 4 0 1 0 2 1 2 12 1 3 -1 0 2Input
2 11 45 1 4Output
NONote
For the first sample, the result after each use of magic is as follows:
- $$$\{0+2,0+0,0,0\}=\{2,0,0,0\}$$$
- $$$\{2,0+2,0+4,0\}=\{2,2,4,0\}$$$
- $$$\{2,2+12,4,0+14\}=\{2,14,4,14\}$$$
- $$$\{2-1,14,4+1,14\}=\{1,14,5,14\}$$$