[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]
Two years ago we had a setback when Joaquín, a member of the jury, had an accident which prevented us from including the problem "Playing with lists" in that year's problemset for the Argentinian Programming Tournament. Thanks to the contest's participants, who kindly helped us solve that problem, we planned to include it in today's problemset. Unfortunately, we had a new inconvenience with Jacinto, another jury member.
As it happens, Jacinto doesn't like it when the sample test cases included along with the problem statements span more than one page. For the problem "Playing with lists", each test case consists of a single line with the description of a list. We don't want to say too much about them because the problem is definitely going to be used next year, so for now we'll just provide you with the total number of characters for each test case, clarifying that it's not allowed to "split" a test case in order to write it in multiple lines.
We would like to write the input for the N sample test cases in a single page, in which we can fit at most L lines of C characters each. The inconvenience appears when there are more sample test cases than there are lines available in the page, so that we cannot write each of them in a separate line. In order to circumvent this problem, Jacinto suggested drawing vertical segments spanning the whole height of the page, dividing it in two or more columns. These segments should have negligible width, so that the number of characters we can write in each line is not reduced, and will act as visual separators splitting each of the lines they cross. In this way, we can write each sample test case in a different line belonging to some column, as long as it doesn't cross the vertical segments. For the purposes of this problem, the order of the sample test cases is considered to be irrelevant.
For example, let's consider the situation in which there are N = 5 sample test cases in a page fitting L = 3 lines of C = 11 characters each. If the test cases have K1= 3, K2 = 4, K3 = 5, K4 = 6 and K5 = 7 characters, we can split the page in two columns in such a way that one column has a width of 7 characters, while the other one has a width of 4 characters. In the larger column we may write the test cases with K3 = 5, K4 = 6 and K5 = 7 characters in any order, whereas in the other column we can write the remaining sample test cases, having K1 = 3 and K2 = 4 characters, again in any order.
Thus, two possible ways in which we can fit the sample test cases in this example are
where for example 5/7 means we have used 5 of the 7 available characters in the corresponding column.
In an analogous situation for which the number of characters fitting in a single line is C = 10, we would need a column of at least 7 characters of width in order to write in it the larger sample test case. Therefore, it would be impossible to have any other column of width greater than 3 characters, which in turn means that 4 of the N = 5 sample test cases should be written in the largest column. But this is clearly impossible, as there are only L = 3 lines in the page. On the other hand, let us also note that although the sample test cases with K1 = 3 and K5 = 7 characters can in principle be written in a single line, as well as the sample tests cases with K2 = 4 and K4 = 6 characters, it is impossible to simultaneously put both pairs in one page in this way, as the width of each column should be the same along all the lines in the page.
Now we would like your help in order to determine if it is possible to make Jacinto happy by putting all the sample test cases in a single page as described above.
Input
There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, L and C. The integer N represents the number of sample test cases, L represents the maximum number of lines fitting in a page, and C represents the maximum number of characters fitting in a line (1 ≤ N, L, C ≤ 5000). The second line contains N integer numbers K1, K2, ..., KN, representing the total number of characters in each sample test case (1 ≤ Ki ≤ C for i = 1, 2, ..., N).
Output
For each test case, print a single line containing a character representing if it is possible to write all sample test cases in a single page as described in the problem statement. The printed character should be an 'S' if this is possible, and an 'N' otherwise.
Example
Input:
5 3 11
3 4 5 6 7
5 3 10
3 4 5 6 7
3 3 4
1 3 2
6 3 4
1 3 1 2 1 1
Output:
S
N
S
S
SS
N
S
S
