University of Oregon (UO), like most colleges in the United States (and Catalonia, I guess), is not exactly flush with cash. To save as much money as possible, professors not only have to teach and research and publish and organize responsible sports parties for their students — but now they also have to make sure all the lights in the college buildings are turned off before going back home.

However, this is not an easy task. In order to (again) save money, UO buildings only have exactly one switch per doorway. The switch is either on the right side (east) of a room, or in the bottom side (south) of a room. By pressing it, you will switch the lights of both rooms connected by the doorway. For example, in the following building, where ‘X’ means a room with the lights off, ‘O’ a room with the lights on, and ‘.’ an empty space,

O..X
XXXO
..X.

it is possible to turn off all the lights. For instance, we can first press the switch in the doorway below the room in position (1,1), that is, the room in the first row and first column of the map:

X..X
OXXO
..X.

Then, we can press the switch in the doorway to the right of the room in position (2,2):

X..X
OOOO
..X.

And finally, we can turn off all the lights by pressing the switch to the right of the rooms in positions (2,1) and (2,3):

X..X
XXXX
..X.

Tadaaaa! Another 14 cents saved. Five more years doing this and we will be able to pay the administrative team that oversees the overworked professors doing this important job.

Unfortunately, it is not always possible to turn off all the lights. For instance, on the following campus with four disconnected buildings,

...OX...O
.OXX.XXXO
..X....O.
X..OXO.X.

it turns out that it is possible to turn off all the lights of three of the four buildings, but not the fourth one.

Given a map of a UO campus, can you tell whether it is actually possible to turn off all lights? If so, can you provide a way?

Input

Input consists of several descriptions of campus maps. Each one begins with the number of rows

n

and the number of columns

m

(both between 1 and 400), followed by

n

lines with

m

characters each, describing the rooms of the campus as explained above. Assume that every map contains at least one room.

Output

Print a line for each case. If it is impossible to turn off all the lights, just print “NO”. Otherwise, print “YES” followed by a list of switch presses that, when executed in the given order, will turn off all the lights. A switch press is a triplet

i

j

d

where

i

and

j

are the (1-indexed) row and column of a room, and

d

is either ‘R’ (right doorway) or ‘B’ (doorway below). Values in a triplet are separated by a single space, while “YES” and switch presses are separated by double spaces.

There might be many ways to turn off the lights. We will accept any one as long as you do not press the same switch twice or more.

Problem information

Author: Omer Gimenez
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Penny-pinching

Input

Output

Problem information