Description

Once upon a time, there was a Mivik who liked convolution. He defines the Mivik convolution of two polynomial functions $f\left(x\right)$ and $g\left(x\right)$ (both only related to $x$) as follows:

$$f\left(x\right)\otimes g\left(x\right)=\sum_{k=0}^{\deg f +\deg g}\max_{i\in [0,\deg f] \land j\in [0,\deg g]\land i+j=k}\left\{\left[x^i\right]f\left(x\right)+\left[x^j\right]g\left(x\right)\right\} x^k$$

Here $\deg f$ denotes the highest degree of $f$, and $\left[x^i\right]f\left(x\right)$ denotes the coefficient of the $x^i$ term in $f\left(x\right)$.

Note that Mivik convolution is left-associative, i.e., $a\otimes b\otimes c=(a\otimes b)\otimes c$.

Mivik defines a Mivik function as a function that can be written in the form $f\left(x\right)=ax+b$, where $a$ and $b$ are both integers. For example, $f\left(x\right)=-3+2x$ is a Mivik function, while $f\left(x\right)=\frac{1}{x}$ is not.

Mivik also defines a function $f\left(x\right)$ to be simple if and only if there exists a sequence $S$ of Mivik functions (of size $\left|S\right|$) such that:

$$f\left(x\right)=S_1\otimes S_2\otimes S_3\otimes\cdots\otimes S_{\left|S\right|}.$$

Now Mivik gives you a polynomial function. Determine whether this function is simple. If it is, also output any possible $S$.

Input Format

The first line contains a positive integer $n$, representing the number of terms of this polynomial function.

The second line contains $n$ integers. From low degree to high degree, they represent the coefficients $f_i$ of this polynomial function. It is guaranteed that the highest-degree coefficient is non-zero.

Output Format

If this function is not simple, output one line nice.

Otherwise, first output one line simple, then output one line with the size $\left|S\right|$ of the sequence $S$ you construct. In the next $\left|S\right|$ lines, output the sequence $S$ you construct. Each line contains two integers $a$ and $b$, describing a Mivik function $f\left(x\right)=ax+b$.

3
2 3 3

simple
2
2 1
1 1

3
97 109 101

simple
2
54 42
47 55

9
9 9 8 2 4 4 3 5 3

nice

Hint

Sample Explanation #1

The given function $f\left(x\right)=2+3x+3x^2$ can be obtained from $\left(2x+1\right)\otimes\left(x+1\right)$.

Constraints

This problem uses bundled testdata.

For all data, $1\le n\le 5\times 10^5$, $-10^8\le f_i\le 10^8$.

The detailed limits for each subtask are shown in the table below:

Subtask ID	Score	$n\le$
1	5	$1$
2		$2$
3	20	$20$
4	30	$5000$
5	40	$5\times 10^5$

The input and output size of this problem is large. Please use fast I/O.

Translated by ChatGPT 5