D. Luxor
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Leal with his Arab scarf that he negotiated from 10 dollars to 1 dollar

In April 2024, two world finals took place in Luxor, Egypt, due to a delay from Covid. Egypt is known for many things, such as its rich history, stunning pyramids, and an intense bargaining culture. It is common to enter a store without any prices, and when asking how much something costs, the response is often "don't worry Habibi, choose everything you want and then we'll see the price." Because of this, the prices of items in stores vary greatly, ranging from dozens of dollars to just a few cents for others.

After his adventures in Egypt, Matheus Leal decides to open his own store. To do this, he makes a large purchase of various items, such as keychains, stones, sculptures, papyrus, and other souvenirs. Then comes the fun part: bargaining with customers, a battle of intellect and willpower to see who can get the best price.

However, at the end of each month comes the tedious part: doing the accounts. Throughout the month, Leal records all the purchase and sale amounts and has an array $$$A$$$ of size $$$N$$$, with values in cents. As a good computer scientist, Leal programmed his computer to sum the values in the given order. However, to his surprise, his program does not always work!

The reason is that Leal's machine has only $$$(x+1)$$$-bits, meaning that during his summation algorithm, the value can never exceed $$$2^x-1$$$ or be less than $$$-2^x$$$, otherwise he will experience overflow (or underflow), and the result will be incorrect!

Your task is to help Leal by reordering the list so that the sum never exceeds the limit values. If it is impossible, let Leal know!

Input

The first line contains an integer $$$N$$$, $$$1 \leq N \leq 10^5$$$. The second line contains an integer $$$L$$$, which is guaranteed to be a power of $$$2$$$, indicating the value of $$$2^x$$$. It is also guaranteed that $$$1 \leq L \leq 2^{20}$$$.

The next line contains $$$N$$$ integers separated by spaces, representing the array $$$A$$$. It is guaranteed that $$$-L \leq A_i \leq L-1$$$.

Output

If it is impossible, print only one line: "N".

If it is possible, print "S" on the first line. Then print $$$N$$$ integers separated by spaces, the array $$$A$$$ after being reordered.

Examples
Input
4
8
7 7 -8 1
Output
S
-8 1 7 7
Input
4
8
7 7 -8 3
Output
N
Input
6
64
1 2 4 8 16 32
Output
S
32 16 8 4 2 1
Note

Be careful not to cause overflow yourself!! Here is an example of how Leal computes his revenue:


revenue = 0
for value in a:
   revenue += value