Problem L
The Ending of the End - Part 2

Previously...

Twilight Sparkle: “No! I can’t leave you here!”

Fluttershy: “It’s our only chance!”

...soon, all of Equestria will fall.

Twilight Sparkle needs to make her way to the Crystal Empire to warn them and get help. The route is deadly; with the three pony races having turned on each other, the windigos have returned.

The land between Canterlot and the Crystal Empire can be represented as a grid with $R$ rows and $C$ columns. Canterlot is at the southwesternmost cell, and the Crystal Empire is at the northeasternmost cell. Windigos blow from the east and from the north; using a rare and powerful spell, Twilight learned of the strengths of these windigos. The $i^\text {th}$ row has a windigo blowing from the east with a strength of $l_ i$, and the $i^\text {th}$ column has a windigo blowing from the north with a strength of $d_ i$.

Twilight needs to reach the Crystal Empire as fast as possible, so she will only travel east or north. Traveling east or north drains units of energy equal to the strength of the windigo blowing from that direction.

Plan a route to the Crystal Empire that preserves as much of Twilight’s energy as possible.

The fate of Equestria hangs in the balance!

Now...

It’s time to save Equestria.

Figure 1: Illustration by Kyle Coate.

Twilight Sparkle has managed to rouse every last pony in the Crystal Empire to action. With the existential emergency recognized across the entire nation, it was then only a matter of time before every creature—dragons, yaks, Kirin, Hippogriffs, changelings, griffons, and many others—banded together and prepared for the fight of their lives.

They need to retake Canterlot immediately and decisively. Unfortunately, the windigos still howl, and stronger than ever; even on the return journey to Canterlot, they will still sap the much-needed energy of anyone that dares to pass. If our heroes are not careful in their return, they will be completely worn out before the battle even begins!

Having exhausted her magic abilities on the way here, Twilight can no longer use her spell to determine the strengths of the windigos. She remembers only the path she took. Unfortunately, our heroes cannot simply use this path to return—the paths are too narrow and there are way too many of them! They will need to somehow recover the strengths of the windigos—or at least a reasonable estimate—in order to find alternative, viable paths.

Because the information they have is limited, they decide to make the most use of it, and additionally assume that the path Twilight took was the unique best route; that is, it was the only route Twilight could have taken that would have preserved as much of her energy as possible.

Determine a possible estimate for the strengths of the windigos consistent with the information above.

The ultimate battle for the fate of Equestria is coming!

Input

The first line of input contains two integers, $R$ and $C$ ($1 \leq R, C \leq 300\, 000$; $2 \leq R\cdot C$), the number of rows and the number of columns of the grid, respectively.

The second line of input contains a string describing the route Twilight took. In particular, the $i^\text {th}$ of these characters describes the $i^\text {th}$ move Twilight made:

• an E denotes that she moved east, and

• an N denotes that she moved north.

This string has exactly $R-1$ occurrences of N and $C-1$ occurrences of E.

Output

If there is no set of estimates consistent with the given data, where the route Twilight took is additionally the unique best route, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first line, output $R$ integers $l_1, l_2, \dots , l_ R$ ($1 \leq l_ i \leq 10^{11})$, denoting a possible estimate for the strengths of the windigos blowing from the east.

On the second line, output $C$ integers $d_1, d_2, \dots , d_ C$ ($1 \leq d_ i \leq 10^{11})$, denoting a possible estimate for the strengths of the windigos blowing from the north.

If there are multiple correct answers, you can output any of them.

4 3
ENENN

7 3 9 2
12 5 4

3 3
EENN

1 10 10
10 10 1