Integral

For a positive integer $n$, let $[n]$ be the real interval $\{x : 0 \le x \le n\}$. A function $f : [n] \to \mathbb{R}$ is only partly specified: the values of $f$ are given at the points of a subset $S$ of $[n]$.

The set $S$ has these properties:

1. Every point of $S$ is an integer.
2. Both endpoints $0$ and $n$ of $[n]$ belong to $S$.

The function $f$ has these properties:

1. At every integer point of $[n]$, the value of $f$ is an integer.
2. Between two consecutive points of $S$, $f$ is monotone. If $L$ and $R$ are consecutive points of $S$ with $L < R$, then $f(L) \le f(L+1) \le \cdots \le f(R)$ or $f(L) \ge f(L+1) \ge \cdots \ge f(R)$.
3. At a point $x$ of $[n]$ that is not an integer, $f(x)$ is the linear interpolation of $f(\lfloor x \rfloor)$ and $f(\lceil x \rceil)$, that is, $f(x) = (\lceil x \rceil - x) f(\lfloor x \rfloor) + (x - \lfloor x \rfloor) f(\lceil x \rceil)$.

The values of $f$ at the integer points of $[n] \setminus S$ are still yours to choose. ($S$ can already contain every integer point of $[n]$.) For a given $y$, decide whether those values can be chosen so that $\int_0^n f(x)\,dx = y$, that is, so that the area under $f$ between $0$ and $n$ equals $y$.

The input holds several test cases and ends at the end of the file.

The first line of a test case has three integers $N$, $M$ and $Y$: the length of the interval, the size of $S$, and the value of $y$. Each of the next $M$ lines describes $f$ at one point of $S$ with two integers $X$ and $F$, meaning $f(X) = F$. The values of $X$ are not necessarily in increasing order.

Constraints

• $1 \le N \le 10^6$
• the sum of $N$ over all test cases is at most $10^6$
• $0 \le X \le N$, and the $M$ values of $X$ are distinct integers that include $0$ and $N$
• $0 \le F \le 10^6$, $F$ integer
• $0 \le Y \le 10^9$, $Y$ integer
• $\int_0^n f(x)\,dx \le 10^9$ for every assignment of values to $f$ at the integer points of $[n] \setminus S$ that obeys the rules above

For each test case, decide whether values can be assigned to $f$ at the integer points $x \in [n] \setminus S$ so that $\int_0^n f(x)\,dx = y$, that is, so that the area under $f$ between $0$ and $n$ equals $y$.

If they cannot, print a line containing only the character N. If they can, print a line containing the character S followed by the values of $f(x)$ at the integer points $x \in [n] \setminus S$, in increasing order of $x$. Separate the leading character and each value by one blank space. When more than one assignment works, print the one whose sequence of values is the smallest in lexicographic order.