思考题 long ago

Chess

Ninetail and Doragon are playing Global Chess on a chessboard with N*M grids. The left-upper corner is (1,1) and the right-lower corner is (N,M)

The Global Chess goes as follows:

  • Each player has some soldiers. Ninetail plays as White and Doragon plays as Black. All white soldiers face up. All black soldiers face down

  • In one turn, Ninetail or Doragon can ask one of her soldiers to go forward by 1 step(ie. From (x,y) to (x-1,y) for Ninetail and (x,y) to (x+1,y) for Doragon).

  • If there's an enemy soldier in the diagonal grid of a soldier's front. He can eat his enemy by moving into his grid and removing him from the board. (ie. A white soldier at (x,y) can eat (x-1,y-1) and (x-1,y+1) while a black soldier at (x,y) can eat (x+1,y-1) and (x+1,y+1)). If you still don't understand, this is similar to Chess.

If you don't know, Ninetail is a fox girl who can control others' minds. So today she controlled Doragon's mind and was going to have fun. She wonders, if she can control both sides and move despite the turn, can she move one of the white soldiers to (1,i) for each i from 1 to M?

Example

Board=

....
.B..
....
..W.

Output=
NYYN

Explain: The White soldier can move up, then eat the black soldier, then move up to reach (1,2)

He can also move up 3 times to reach(1,3)

Constraints

Subtask1(50%):there is only one soldier for each side

Subtask2(50%):N,M<=1000