Given a positive integer n, denote by [n] the interval {x : 0 ≤ x ≤ n} of real numbers. Consider 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: • The values of f in the integral points of [n] are integers. • Between two consecutive points of S, the function is monotonic. • 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 ∫ 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, M and Y , 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 and F, representing f(X) = F. The values of X are not necessarily in ascending order. Output For each test case, determine whether there is a value assignment to f(x) for each integral point ∫ Restrictions • 1 ≤ N ≤ 106 • 0≤X≤N,Xinteger,∀X∈S • 0 ≤ F ≤ 106, F integer • 0≤Y ≤109,Y integer ∫ that S can contain all the integral points of [n]). We would like to use this flexibility to make 0n f(x)dx = y, i.e., the area under f(x) between the extremes 0 and n equal to y, a given value. x ∈ [n]\S such that 0n 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 ∈ [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. • 0n f(x)dx ≤ 109 for any assignment of values to f(x) for x ∈ [n]\S satisfying the stated con- straints.
2/2 Sample Input 5 6 10 02 12 52 22 32 42 5 2 10 00 5 10 225 01 22 10 3 18 02 64 10 0 221 00 21 Sample Output S S0005 N S22222111 N