360. B++ Interpreter

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



B++ programming language was developed in Berland for the purpose of controlling a robot, moving in the radioactively polluted area. The area is a rectangle of size NxM meters. The mission of the robot is to visit several unit squares, marked with asterisk "*" on the map, to measure radiation level.

Robot is controlled by three commands: L -- turn left (90 degrees counterclockwise), R - turn right (90 degrees clockwise) and C - move forward one meter. B++ program consists of description of several functions. Function description has the following format:

[function name]([argument list]){[operator list]}

[function name] consists of one small Latin letter. All functions have different names. Each function can have from 0 to 2 arguments. Argument name is one capital Latin letter (and cannot be L or R or C). If there are two arguments, they are separated by comma. Operator can be:

1) symbol L, R or C, meaning the correspondent robot command;

2) call of function in the format [function name]([argument list]). Any function described in the program can be called. Function cannot call itself. [argument list] of the invoked function corresponds to the list of its arguments in the function definition. L, R, C, and arguments of calling function may be used as arguments. Brackets must be written even if the function has no arguments (i. e. 0 arguments).

3) [argument]. In this case the command L or R or C, executed, depending on the value of the argument.

Entry point of the program is the function name m with no arguments. Execution of the program starts from execution of the entry point. Execution of function is performed by consecutive execution of its operators. Each function contains at least one operator. If some command asks robot to leave the field, the robot ignores such command and proceeds to the next command.

Given a program and territory map, determine which of marked with "*" cells will be visited by the robot.

Input
The first line of the input file contains integer numbers N and M (1 ≤ N, M ≤ 50) - dimensions of the map. Next N lines contain M characters each, that is description of the map. Character "~" corresponds to the regular cell, "*" - marked cell, "R" - initial position of the robot. Initially robot is turned towards upper border of the map. The rest of the file contains program on B++ language. You may assume that program is correct, that its execution doesn't lead to infinite recursion and that robot will execute not more that 1000 commands. Moreover, program always contains function m with no arguments. Program may contain white-spaces that should be ignored. Input file size doesn't exceed 10000 bytes.

Output
On the first line of the output print K - amount of cells marked with "*" visited by the robot. Print in the next K lines numbers Xi, Yi separated by a space - coordinates of that cells. First coordinate is the row number of the map (1 ≤ XiN), second is the column number (1 ≤ YiM). If one cell is visited several times, only first visit counts. Print cells in the order robot visit them.

Example(s)
sample input
sample output
3 4 
~*R* 
~~*~ 
*~~~
m() 
{ 
 LL a(L, C) C a(R, C) b(L) 
} 
a(X, Y){XYXYXYXY} 
b 
(
A 
) 
{ 
 c(L) 
} 

c(X) {L X L X} 

d(X,Y) {e()} 
e(){R}
2 
1 4 
2 3

Notes to the example
Robot will execute following sequence of commands: LLLCLCLCLCCRCRCRCRCLLLL.

Online Contester Team © 2002 - 2010. All rights reserved.