beecrowd | 1230
# Integral

**Timelimit: 1**

Maratona de Programação da SBC Brasil

Given a positive integer *n*, denote by [*n*] the real interval {*x* : 0 ≤ *x* ≤ *n*}. A function *f* : [*n*] ⇒ R. Values of *f* are provided on a subset *S* of [*n*], thereby partially specifying *f*.

The set *S* satisﬁes the following properties:

1. The points in S are all integers.

2. The extremes 0 and *n* of [*n*] are both in *S*.

The function *f* satisﬁes the following properties:

1. The values of *f* in the integral points of [n] are integers.

2. For every integral point *x* in [*n*] \ *S* (ie, the integral points of [n] are not in S), the function f is monotonic in the interval [x − 1, x + 1]. In other words, at least one of the inequalities *f*(*x* − 1) ≤ *f*(*x*) ≤ *f*(*x* + 1) and *f*(*x* − 1) ≥ *f*(*x*) ≥ *f*(*x* + 1) is satisﬁed.

3. For each non-integral point *x* in [*n*], the value of *f*(*x*) is given by the linear interpolation of *f*(⌊*x*⌋) and f(⌈*x*⌉), ie, *f*(*x*) = (*x* − ⌊*x*⌋)*f*(⌊*x*⌋) + (⌈*x*⌉ − *x*)*f*(⌈*x*⌉).

We still have the freedom of specifying the values of f in the integral points of [*n*] \ *S* (note however that *S* can contain all the integral points of [*n*]). We would like to use this ﬂexibility to make _{}*f*(*x*)dx = *y*, i.e., the area under *f*(x) between the extremes 0 and *n* equal to *y*, a given value. Your problem then is to decide whether this is possible or not.

The input contains several test cases. The ﬁrst line of a test case contains three integers, **N** (1 ≤ **N** ≤ 10^{6}), **M** and **Y** (0 ≤ **Y** ≤ 10^{9}), respectively the amplitude of the interval, the size of *S* and the value of **y**. Each of the following **M** lines describes function *f *at a point of *S*, containing two integers **X** (0 ≤ **X** ≤ **N**, ∀**X** ∈ **S**) and **F** (0 ≤ **F** ≤ 10^{6}), representing *f**(X)* = **F**. The values of **X** are not necessarily in ascending order.

Note.: _{} *f(x)dx *≤ 10^{9 }for any assignment of values to *f*(*x*) para *x* ∈ [*n*] \ **S** satisfying the stated constraints.

For each test case, determine whether there is a value assignment to *f**(x)* for each integral point x ∈ [n] \ *S* such that _{}*f*(*x*)*dx* = *y*, i.e. the area under *f**(x)* between the ends 0 and *n* is equal to *y*. If not, your program should print a line containing only the character ‘N’. If the assignments are possible, your program should print a line containing the character ‘S’, followed by values of *f**(x)* for the integral points *x* in [n] \ *S*, in increasing order of the values of x. The initial character and following values, if any, should be separated by a blank space. If more than one solution is possible, then print the lexicographically smallest solution.

Sample Input | Sample Output |

5 6 10 |
S |