<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 ≤ Xi ≤ N), second is the column number (1 ≤ Yi ≤ M). 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.

<|response|>
## 1. Abridged problem statement

We are given an `N x M` grid containing:

- `~` — empty cells
- `*` — cells that should be measured
- `R` — robot starting position

The robot starts facing upward and executes commands:

- `L` — turn left
- `R` — turn right
- `C` — move forward one cell, unless that leaves the grid

The robot is controlled by a small language called B++.

A B++ program consists of functions:

```text
f(args){operators}
```

Each function name is one lowercase letter. Each function has `0`, `1`, or `2` arguments. Arguments are uppercase letters except `L`, `R`, `C`.

Operators can be:

1. Direct command: `L`, `R`, or `C`
2. Argument usage: executes the command stored in that argument
3. Function call: `f(...)`

Execution starts from `m()`.

The program is valid, terminates, and executes at most `1000` primitive commands.

We need to output all `*` cells visited by the robot, in the order of their first visit.

---

## 2. Key observations needed to solve the problem

### Observation 1: Whitespace is irrelevant

The program may contain spaces and newlines anywhere.  
Before parsing, we can remove all whitespace from the program.

For example:

```text
m()
{
  L C
}
```

becomes:

```text
m(){LC}
```

---

### Observation 2: The program can be parsed function by function

Every function has the form:

```text
name(arguments){body}
```

Since function names are single lowercase letters and arguments are simple characters, parsing is straightforward.

Each operator in a body is one of:

- primitive command: `L`, `R`, `C`
- uppercase argument reference
- lowercase function call

---

### Observation 3: Function arguments are always commands

At runtime, every function argument is bound to one of:

```text
L, R, C
```

Example:

```text
a(X){X}
```

If we call:

```text
a(C)
```

then inside `a`, `X` means command `C`.

Arguments can also be forwarded:

```text
b(A){a(A)}
```

If `b(R)` is called, then `a(R)` is executed.

---

### Observation 4: Direct simulation is enough

The statement guarantees that the robot executes at most `1000` primitive commands.

Therefore, even a direct interpreter is fast enough.

However, we can also memoize repeated function calls. A function call result depends only on:

```text
function id
actual argument values
starting row
starting column
starting direction
```

So if the same call appears again, we can reuse its result.

---

### Observation 5: Star visit order must be global

When the robot enters a `*` cell, we record it only if it was not recorded before.

Even if memoization is used, we must replay the cached list of starred cells visited during that function call, because some of them may become first visits in the current global execution.

---

## 3. Full solution approach

### Step 1: Read input

Read:

```text
N M
grid
program
```

The program is everything after the grid. Remove all whitespace characters from it.

---

### Step 2: Parse functions

Store every function as:

```cpp
formal parameters
list of parsed operators
```

Each parsed operator is one of:

```text
command
argument reference
function call
```

For example:

```text
a(X,Y){XYCL}
```

is parsed as:

```text
argument X
argument Y
command C
command L
```

---

### Step 3: Simulate primitive robot commands

Represent direction as:

```text
0 = up
1 = right
2 = down
3 = left
```

Movement arrays:

```cpp
dr = {-1, 0, 1, 0}
dc = {0, 1, 0, -1}
```

For each command:

- `L`: `dir = (dir + 3) % 4`
- `R`: `dir = (dir + 1) % 4`
- `C`: attempt to move forward
  - if inside the grid, move
  - otherwise ignore the command

After each successful move, if the new cell is `*` and has not been reported before, add it to the answer.

---

### Step 4: Execute functions recursively

To execute a function:

1. Build an environment mapping formal arguments to actual command values.
2. Execute every operator in order.
3. If operator is:
   - command: execute it directly
   - argument: replace it by its bound value and execute
   - function call:
     - resolve its arguments
     - recursively execute the called function

---

### Step 5: Optional memoization

Cache key:

```text
function id
actual argument values
start row
start column
start direction
```

Cached value:

```text
end row
end column
end direction
number of primitive commands executed
list of starred cells entered during this call
```

On cache hit:

1. Replay the stored starred cells into the global answer.
2. Add cached primitive command count.
3. Return the cached final robot state.

---

### Complexity

Let:

- `S` be the input program size
- `K` be the number of executed primitive commands

Parsing is:

```text
O(S)
```

Simulation is bounded by:

```text
O(K)
```

The statement guarantees:

```text
K <= 1000
```

So the solution easily fits the limits.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Node {
    /*
        type:
        'C' = direct command L/R/C
        'A' = argument reference
        'F' = function call
    */
    char type;
    char value;              // Used for command or argument name
    int func_id;             // Used for function calls
    vector<char> call_args;  // Used for function calls
};

struct CallResult {
    int r, c, d;                     // Final robot state
    int command_count;               // Number of primitive commands executed
    vector<pair<int, int>> stars;    // Star cells entered during this call
};

int n, m;
vector<string> grid;
int start_r, start_c;

string source;
int pos_parser = 0;

// Function storage
map<char, int> id_of;
vector<vector<char>> func_params;
vector<vector<Node>> func_body;

int get_func_id(char name) {
    if (id_of.count(name)) {
        return id_of[name];
    }

    int id = (int)id_of.size();
    id_of[name] = id;

    func_params.push_back({});
    func_body.push_back({});

    return id;
}

/*
    Parses an argument list.

    Examples:
        ()      -> empty vector
        (X)     -> {'X'}
        (X,Y)   -> {'X', 'Y'}
        (L,C)   -> {'L', 'C'}
*/
vector<char> parse_args() {
    vector<char> args;

    // Skip '('
    pos_parser++;

    while (source[pos_parser] != ')') {
        if (source[pos_parser] != ',') {
            args.push_back(source[pos_parser]);
        }
        pos_parser++;
    }

    // Skip ')'
    pos_parser++;

    return args;
}

/*
    Parses a function body: { operators }
*/
vector<Node> parse_body() {
    vector<Node> body;

    // Skip '{'
    pos_parser++;

    while (source[pos_parser] != '}') {
        char ch = source[pos_parser];

        if (ch == 'L' || ch == 'R' || ch == 'C') {
            // Direct robot command
            body.push_back({'C', ch, -1, {}});
            pos_parser++;
        } else if (islower((unsigned char)ch)) {
            // Function call
            char fname = ch;
            pos_parser++;

            int fid = get_func_id(fname);
            vector<char> args = parse_args();

            body.push_back({'F', 0, fid, args});
        } else {
            // Uppercase argument reference
            body.push_back({'A', ch, -1, {}});
            pos_parser++;
        }
    }

    // Skip '}'
    pos_parser++;

    return body;
}

/*
    Parses one complete function definition:
        f(args){body}
*/
void parse_function() {
    char fname = source[pos_parser];
    pos_parser++;

    int fid = get_func_id(fname);

    func_params[fid] = parse_args();
    func_body[fid] = parse_body();
}

// Robot direction vectors: up, right, down, left
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int total_commands = 0;

set<pair<int, int>> visited;
vector<pair<int, int>> answer;

/*
    Records a star cell if this is its first global visit.
*/
void register_star(int r, int c) {
    if (grid[r][c] == '*' && !visited.count({r, c})) {
        visited.insert({r, c});
        answer.push_back({r, c});
    }
}

/*
    Executes one primitive command.
    Also stores every star entered into star_log.
*/
void apply_command(
    char cmd,
    int &r,
    int &c,
    int &d,
    vector<pair<int, int>> &star_log
) {
    if (cmd == 'L') {
        d = (d + 3) % 4;
    } else if (cmd == 'R') {
        d = (d + 1) % 4;
    } else {
        // cmd == 'C'
        int nr = r + dr[d];
        int nc = c + dc[d];

        if (0 <= nr && nr < n && 0 <= nc && nc < m) {
            r = nr;
            c = nc;

            if (grid[r][c] == '*') {
                star_log.push_back({r, c});
                register_star(r, c);
            }
        }
    }

    // Every primitive command counts, even blocked movement
    total_commands++;
}

/*
    Memoization cache.

    Key:
        function id
        packed actual arguments
        starting row
        starting column
        starting direction
*/
map<tuple<int, int, int, int, int>, CallResult> cache;

/*
    Converts argument bindings to a small integer.

    L -> 0
    R -> 1
    C -> 2
*/
int pack_args(const vector<char> &args) {
    int result = 0;

    for (char ch : args) {
        int value;
        if (ch == 'L') value = 0;
        else if (ch == 'R') value = 1;
        else value = 2;

        result = result * 3 + value;
    }

    return result;
}

CallResult execute_function(int fid, const vector<char> &bindings, int r, int c, int d);

/*
    Resolves an argument name using the current function bindings.
*/
char resolve_argument(
    char arg,
    const vector<char> &params,
    const vector<char> &bindings
) {
    for (int i = 0; i < (int)params.size(); i++) {
        if (params[i] == arg) {
            return bindings[i];
        }
    }

    // Program is guaranteed correct, so this should never happen
    return '?';
}

/*
    Executes one function call.
*/
CallResult execute_function(int fid, const vector<char> &bindings, int r, int c, int d) {
    auto key = make_tuple(fid, pack_args(bindings), r, c, d);

    // Reuse cached call result if available
    if (cache.count(key)) {
        CallResult cached = cache[key];

        // Replay star visits for global first-visit order
        for (auto [sr, sc] : cached.stars) {
            register_star(sr, sc);
        }

        total_commands += cached.command_count;

        return cached;
    }

    int before_commands = total_commands;

    vector<pair<int, int>> star_log;

    const vector<char> &params = func_params[fid];
    const vector<Node> &body = func_body[fid];

    for (const Node &node : body) {
        if (node.type == 'C') {
            // Direct command
            apply_command(node.value, r, c, d, star_log);
        } else if (node.type == 'A') {
            // Argument used as command
            char cmd = resolve_argument(node.value, params, bindings);
            apply_command(cmd, r, c, d, star_log);
        } else {
            // Function call

            vector<char> child_bindings;

            for (char arg : node.call_args) {
                if (arg == 'L' || arg == 'R' || arg == 'C') {
                    child_bindings.push_back(arg);
                } else {
                    child_bindings.push_back(resolve_argument(arg, params, bindings));
                }
            }

            CallResult child = execute_function(node.func_id, child_bindings, r, c, d);

            r = child.r;
            c = child.c;
            d = child.d;

            // Add child's star steps to this call's log
            for (auto cell : child.stars) {
                star_log.push_back(cell);
            }
        }
    }

    CallResult result;
    result.r = r;
    result.c = c;
    result.d = d;
    result.command_count = total_commands - before_commands;
    result.stars = star_log;

    cache[key] = result;

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    grid.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> grid[i];

        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'R') {
                start_r = i;
                start_c = j;
            }
        }
    }

    // Read the remaining program and remove whitespace
    char ch;
    while (cin.get(ch)) {
        if (!isspace((unsigned char)ch)) {
            source.push_back(ch);
        }
    }

    // Parse all function definitions
    while (pos_parser < (int)source.size()) {
        parse_function();
    }

    int main_id = get_func_id('m');

    // Initial direction is up: 0
    execute_function(main_id, {}, start_r, start_c, 0);

    cout << answer.size() << '\n';

    for (auto [r, c] : answer) {
        cout << r + 1 << ' ' << c + 1 << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

sys.setrecursionlimit(100000)


# ----------------------------
# Input reading
# ----------------------------

lines = sys.stdin.read().splitlines()

n, m = map(int, lines[0].split())

grid = []
start_r = start_c = -1

for i in range(n):
    row = lines[i + 1].strip()
    grid.append(row)

    for j, ch in enumerate(row):
        if ch == "R":
            start_r = i
            start_c = j

# Remaining lines contain the B++ program
program_text = "".join(lines[n + 1:])

# Remove all whitespace
source = "".join(ch for ch in program_text if not ch.isspace())


# ----------------------------
# Parsing
# ----------------------------

func_id = {}
func_params = []
func_body = []


def get_func_id(name):
    """
    Returns integer id of a function.
    Creates a new id if this function was not seen before.
    """
    if name in func_id:
        return func_id[name]

    idx = len(func_id)
    func_id[name] = idx
    func_params.append([])
    func_body.append([])
    return idx


pos = 0


def parse_args():
    """
    Parses an argument list.

    Examples:
        ()      -> []
        (X)     -> ['X']
        (X,Y)   -> ['X', 'Y']
        (L,C)   -> ['L', 'C']
    """
    global pos

    args = []

    # Skip '('
    pos += 1

    while source[pos] != ")":
        if source[pos] != ",":
            args.append(source[pos])
        pos += 1

    # Skip ')'
    pos += 1

    return args


def parse_body():
    """
    Parses a body enclosed in braces.

    Operators can be:
        - direct command L/R/C
        - argument reference
        - function call
    """
    global pos

    body = []

    # Skip '{'
    pos += 1

    while source[pos] != "}":
        ch = source[pos]

        if ch in "LRC":
            # Direct primitive command
            body.append(("cmd", ch))
            pos += 1

        elif "a" <= ch <= "z":
            # Function call
            name = ch
            pos += 1

            fid = get_func_id(name)
            args = parse_args()

            body.append(("call", fid, args))

        else:
            # Uppercase argument reference
            body.append(("arg", ch))
            pos += 1

    # Skip '}'
    pos += 1

    return body


def parse_function():
    """
    Parses one function definition:
        f(args){body}
    """
    global pos

    name = source[pos]
    pos += 1

    fid = get_func_id(name)

    params = parse_args()
    body = parse_body()

    func_params[fid] = params
    func_body[fid] = body


# Parse all definitions
while pos < len(source):
    parse_function()


# ----------------------------
# Robot simulation
# ----------------------------

# Directions:
# 0 = up, 1 = right, 2 = down, 3 = left
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

total_commands = 0

visited = set()
answer = []


def register_star(r, c):
    """
    Records a starred cell if it has not been recorded before.
    """
    if grid[r][c] == "*" and (r, c) not in visited:
        visited.add((r, c))
        answer.append((r, c))


def apply_command(cmd, r, c, d, star_log):
    """
    Executes one primitive robot command.

    Returns updated:
        r, c, d
    """
    global total_commands

    if cmd == "L":
        d = (d + 3) % 4

    elif cmd == "R":
        d = (d + 1) % 4

    else:
        # cmd == "C"
        nr = r + dr[d]
        nc = c + dc[d]

        if 0 <= nr < n and 0 <= nc < m:
            r, c = nr, nc

            if grid[r][c] == "*":
                star_log.append((r, c))
                register_star(r, c)

    # Every primitive command counts, even blocked C
    total_commands += 1

    return r, c, d


def resolve_argument(arg, params, bindings):
    """
    Finds the command value bound to an argument name.
    """
    for i, name in enumerate(params):
        if name == arg:
            return bindings[i]

    # Program is guaranteed correct
    return None


# ----------------------------
# Function execution with memoization
# ----------------------------

# Cache key:
#   (function id, argument bindings, start row, start col, start direction)
#
# Cache value:
#   (end row, end col, end direction, command count, star list)
cache = {}


def execute_function(fid, bindings, r, c, d):
    """
    Executes a function from the given robot state.

    bindings contains actual values of the function parameters,
    each one being 'L', 'R', or 'C'.
    """
    global total_commands

    bindings = tuple(bindings)

    key = (fid, bindings, r, c, d)

    if key in cache:
        end_r, end_c, end_d, command_count, stars = cache[key]

        # Replay star visits to preserve global first-visit order
        for sr, sc in stars:
            register_star(sr, sc)

        total_commands += command_count

        return end_r, end_c, end_d, command_count, stars

    before_commands = total_commands
    star_log = []

    params = func_params[fid]
    body = func_body[fid]

    for op in body:
        kind = op[0]

        if kind == "cmd":
            cmd = op[1]
            r, c, d = apply_command(cmd, r, c, d, star_log)

        elif kind == "arg":
            arg_name = op[1]
            cmd = resolve_argument(arg_name, params, bindings)
            r, c, d = apply_command(cmd, r, c, d, star_log)

        else:
            # Function call
            _, child_fid, call_args = op

            child_bindings = []

            for arg in call_args:
                if arg in "LRC":
                    child_bindings.append(arg)
                else:
                    child_bindings.append(resolve_argument(arg, params, bindings))

            child_r, child_c, child_d, child_count, child_stars = execute_function(
                child_fid,
                child_bindings,
                r,
                c,
                d,
            )

            r, c, d = child_r, child_c, child_d

            # Include child's star steps in this function's log
            star_log.extend(child_stars)

    command_count = total_commands - before_commands

    result = (r, c, d, command_count, tuple(star_log))
    cache[key] = result

    return result


# ----------------------------
# Run entry point m()
# ----------------------------

main_id = get_func_id("m")

# Robot starts facing up: direction 0
execute_function(main_id, (), start_r, start_c, 0)


# ----------------------------
# Output
# ----------------------------

out = [str(len(answer))]

for r, c in answer:
    out.append(f"{r + 1} {c + 1}")

print("\n".join(out))
```