Problem K
The Ending of the End - Part 1

Rarity: “Go, Twilight! Get help!”

Applejack: “We’ll hold ‘em ‘til you get back!”

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

Fluttershy: “It’s our only chance!”

Rainbow Dash: “You’ll come up with something to save the day!”

Pinkie Pie: “You always do!”

Spike: “We believe in you!”

Having unlocked the legendary power of Grogar’s bell, Cozy Glow, Lord Tirek and Queen Chrysalis annihilated all who stood in their path—including Grogar himself—and laid siege to Canterlot. They acquired even the power of Princess Celestia and Princess Luna... soon, all of Equestria will fall.

Figure 1: Illustration by Kyle Coate.

Twilight Sparkle, with the ultimate sacrifice of her closest friends, managed to escape. She needs to make her way to the distant Crystal Empire, far in the Frozen North, to warn them and get help. The route, however, is treacherous and deadly; worse, with the three pony races having turned on each other in these desperate times, the windigos—mythical wind spirits that spread cold and misery across the land—have returned. Flying is more dangerous than ever, anyone who dares to travel will quickly find their magic and life force sapped away.

The land between Canterlot and the Crystal Empire can be represented as a grid with $R$ rows, labeled $1$ to $R$ from south to north, and $C$ columns, labeled $1$ to $C$ from west to east. 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$.

Figure 2: Illustration of Sample Input 1.

There’s no time to spare. Twilight needs to reach the Crystal Empire as fast as possible, so she will only travel east or north, even if that means being drained of more energy. Traveling east or north drains units of energy equal to the strength of the windigo blowing from that direction; if she’s at the $i^\text {th}$ column, traveling a cell east will drain $L_ i$ units of energy, and if she’s at the $i^\text {th}$ row, traveling a cell north will drain $D_ i$ units of energy.

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!

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 $R$ integers $L_1, L_2, \dots , L_ R$ ($1 \leq L_ i \leq 10^{11})$, denoting the strengths of the windigos blowing from the east.

The third line of input contains $C$ integers $D_1, D_2, \dots , D_ C$ ($1 \leq D_ i \leq 10^{11})$, denoting the strengths of the windigos blowing from the north.

Output

Output a single string on a line by itself, describing the route Twilight should take. In particular, the $i^\text {th}$ of these characters should denote the $i^\text {th}$ move Twilight should make, and should be

• an E, if she should move east,

• an N, if she should move north.

This string should have exactly $R-1$ occurrences of N and $C-1$ occurrences of E, and the route it represents should, among all such routes, preserve as much of Twilight’s energy as possible.

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

4 3
7 3 9 2
12 5 4

ENENN

3 3
1 1 1
1 1 1

EENN