URI Online Judge | 1230

Integral

Maratona de Programação da SBC Brasil

Timelimit: 1

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

The set S satisfies 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 satisfies 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 satisfied.

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 flexibility 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.

Input

The input contains several test cases. The first line of a test case contains three integers, N (1 ≤ N ≤ 106), M and Y (0 ≤ Y ≤ 109), 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 ≤ XN, ∀XS) and F (0 ≤ F ≤ 106), representing f(X) = F. The values of X are not necessarily in ascending order.

Note.: f(x)dx ≤ 109 for any assignment of values to f(x) para x ∈ [n] \ S satisfying the stated constraints.

Output

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
0 2
1 2
5 2
2 2
3 2
4 2
5 2 10
0 0
5 10
2 2 5
0 1
2 2
10 3 18
0 2
6 4
10 0
2 2 1
0 0
2 1

S
S 0 0 0 5
N
S 2 2 2 2 2 1 1 1
N