<|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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

struct ast_node {
    char kind;
    char val;
    int func_id;
    vector<char> args;
};

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

map<char, int> func_id_of;
vector<vector<ast_node>> func_body;
vector<vector<char>> func_params;

int get_or_create_func(char name) {
    auto it = func_id_of.find(name);
    if(it != func_id_of.end()) {
        return it->second;
    }
    int id = (int)func_id_of.size();
    func_id_of[name] = id;
    func_body.emplace_back();
    func_params.emplace_back();
    return id;
}

int parse_pos = 0;

vector<char> parse_arg_letters() {
    parse_pos++;
    vector<char> args;
    while(source[parse_pos] != ')') {
        if(source[parse_pos] != ',') {
            args.push_back(source[parse_pos]);
        }
        parse_pos++;
    }
    parse_pos++;
    return args;
}

vector<ast_node> parse_block() {
    vector<ast_node> ops;
    parse_pos++;
    while(source[parse_pos] != '}') {
        char c = source[parse_pos];
        if(c == 'L' || c == 'R' || c == 'C') {
            ops.push_back({'C', c, -1, {}});
            parse_pos++;
        } else if(islower((unsigned char)c)) {
            parse_pos++;
            int fid = get_or_create_func(c);
            vector<char> args = parse_arg_letters();
            ops.push_back({'F', 0, fid, args});
        } else {
            ops.push_back({'A', c, -1, {}});
            parse_pos++;
        }
    }
    parse_pos++;
    return ops;
}

void parse_function_def() {
    char name = source[parse_pos];
    parse_pos++;
    int fid = get_or_create_func(name);
    func_params[fid] = parse_arg_letters();
    func_body[fid] = parse_block();
}

void read() {
    cin >> n >> m;
    grid.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    char ch;
    while(cin.get(ch)) {
        if(!isspace((unsigned char)ch)) {
            source += ch;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 'R') {
                start_r = i;
                start_c = j;
            }
        }
    }
}

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int total_commands;
vector<pair<int, int>> visit_order;
set<pair<int, int>> visited_set;

struct call_result {
    int end_r, end_c, end_d;
    int cmd_count;
    vector<pair<int, int>> stars;
};

map<tuple<int, int, int, int, int>, call_result> cache;

int pack_args(const vector<char>& args) {
    int p = 0;
    for(char c: args) {
        int v = (c == 'L' ? 0 : (c == 'R' ? 1 : 2));
        p = p * 3 + v;
    }
    return p;
}

void register_star(int r, int c) {
    if(grid[r][c] == '*' && !visited_set.count({r, c})) {
        visited_set.insert({r, c});
        visit_order.push_back({r, c});
    }
}

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 if(cmd == 'C') {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if(nr >= 0 && nr < n && nc >= 0 && nc < m) {
            r = nr;
            c = nc;
            if(grid[r][c] == '*') {
                star_log.push_back({r, c});
                register_star(r, c);
            }
        }
    }
    total_commands++;
}

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

call_result execute_block(
    const vector<ast_node>& ops, const vector<char>& params,
    const vector<char>& bindings, int r, int c, int d
) {
    call_result res;
    res.cmd_count = 0;
    for(const auto& op: ops) {
        if(op.kind == 'C') {
            int prev = total_commands;
            apply_command(op.val, r, c, d, res.stars);
            res.cmd_count += total_commands - prev;
        } else if(op.kind == 'A') {
            char cmd = 0;
            for(int i = 0; i < (int)params.size(); i++) {
                if(params[i] == op.val) {
                    cmd = bindings[i];
                    break;
                }
            }
            int prev = total_commands;
            apply_command(cmd, r, c, d, res.stars);
            res.cmd_count += total_commands - prev;
        } else {
            vector<char> sub;
            sub.reserve(op.args.size());
            for(char a: op.args) {
                if(a == 'L' || a == 'R' || a == 'C') {
                    sub.push_back(a);
                } else {
                    for(int i = 0; i < (int)params.size(); i++) {
                        if(params[i] == a) {
                            sub.push_back(bindings[i]);
                            break;
                        }
                    }
                }
            }
            call_result child = execute_function(op.func_id, sub, r, c, d);
            r = child.end_r;
            c = child.end_c;
            d = child.end_d;
            for(const auto& s: child.stars) {
                res.stars.push_back(s);
            }
            res.cmd_count += child.cmd_count;
        }
    }
    res.end_r = r;
    res.end_c = c;
    res.end_d = d;
    return res;
}

call_result 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);
    auto it = cache.find(key);
    if(it != cache.end()) {
        const auto& cached = it->second;
        for(const auto& [sr, sc]: cached.stars) {
            register_star(sr, sc);
        }
        total_commands += cached.cmd_count;
        return cached;
    }
    call_result res =
        execute_block(func_body[fid], func_params[fid], bindings, r, c, d);
    cache[key] = res;
    return res;
}

void solve() {
    // Pure implementation simulation. The robot executes at most 1000 commands,
    // so we just run the B++ program directly: parse each function definition
    // into a list of operators (direct command L/R/C, argument reference, or
    // function call) and execute m() from the robot's start cell. Function
    // arguments are substituted at every call site, since each argument is
    // itself L, R, C or an argument of the caller.
    //
    // To keep the work bounded even when the call tree branches heavily, we
    // memoize dp[(func_id, bound_args, start_state)] -> (end_state, ordered
    // stars stepped on during the call, command count). On a cache hit we
    // replay the cached star list (registering any not-yet-visited cell
    // globally) and jump to the cached end state without re-walking the
    // body, so each unique key is executed at most once.

    parse_pos = 0;
    while(parse_pos < (int)source.size()) {
        parse_function_def();
    }

    int main_id = get_or_create_func('m');
    total_commands = 0;
    execute_function(main_id, {}, start_r, start_c, 0);

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

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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))
```