This page is still under construction.

Parts of this page are still being built. What you see may change.

Black-Red Square

Time limit2sMemory limit256 MB

Summary
Construct a rolling-square walk on a grid that paints exactly r cells red and b cells black, where the color of each visited cell alternates.
Level

Medium5 of 10

Topics
Implementation, Simulation, Greedy, Math
Solved
No attempts yet

Statement

On an infinite grid board there is an unusual chess piece: the black-red square. This piece is a square that occupies exactly one cell of the board, with one face painted black and the other painted red. Unlike ordinary chess pieces, the black-red square leaves traces on the board. Each cell it has visited is painted black or red, depending on which face of the square pointed downward while it was on that cell.

In one move the square can roll to an adjacent cell. As it does, it flips over: if it was lying black side up, it ends up black side down, and vice versa. The cell it rolls into is painted with the color of the square's bottom face. Initially the square lies black side down, so the starting cell of its path is painted black.

Initially every cell of the board is painted white. Find some path of the square after which the board has exactly rr red cells and exactly bb black cells. At least one such path is guaranteed to exist.

Input

The single line contains two integers rr and bb (0≤r≤10000 \le r \le 1000; 1≤b≤10001 \le b \le 1000).

Output

On the first line print the number nn of moves the square makes. nn must not exceed 100,000.

On the second line print the square's path: a string of length nn consisting of the letters N, S, W, E. These letters denote moves up, down, left, and right, respectively.

If there are several answers, print any of them. At least one answer is guaranteed to exist.

Examples1

  1. Example 1

    Input
    0 1
    
    Expected output
    0