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

463. Walking around Berhattan
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

As you probably know, Berhattan is a district of Berland's largest city and it consists of equal square blocks. There are n block lines in the east-west direction and m block lines in the south-north direction. The map shows Berhattan as a rectangle with n rows and m columns, so there are nx m blocks in total.

There are n+1 streets running parallel in the east-west direction (horizontally), and there are m+1 avenues running parallel in the south-north direction (vertically). Streets and avenues split the district into blocks and separate Berhattan from other districts of Berland. Each block in Berhattan is characterized by its beauty bij.

A pedestrian can walk only along streets and avenues. When the pedestrian walks along any of four sides of a block, we say he passes the block. Every time the pedestrian passes a block his satisfaction is increased by bij. If the pedestrian has already passed the block one or more times his satisfaction is increased only by bij/2 rounded down when he passes the block again.

You are given the map of Berhattan with the information about the blocks' beauty and the pedestrian's path along the streets and avenues. The path is given as a string containing letters 'L', 'R' and 'M', where 'L' means a 90 degree left turn, 'R' means a 90 degree right turn, and 'M' means walking one block forward by a street or avenue. Facing the east, the pedestrian starts his path in the north-west corner of Berhattan having zero satisfaction level. His path can cross itself and go along the same streets or avenues several times. Pedestrian's satisfaction is increased every time he moves according to the rules described above.

Your task is to calculate the total satisfaction the pedestrian will get after finishing his route.


Picture of the sample test


Input
The first line of input contains two integers n and m (1 ≤ n,m ≤ 100), where n is a number of block lines in Berhattan running in the east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 9) — the beauty of the corresponding block. The last line of input contains a path in the format specified above. The path consists of 1 up to 500 characters, inclusively. It is guaranteed that the given path doesn't go outside Berhattan.

Output
Print a single integer to the output — the total pedestrian's satisfaction.

Example(s)
sample input
sample output
3 3
123
456
789
MRMMLM
22

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

You have an n×m grid of square blocks (beauty values 0–9). Streets/avenues form the grid lines, so intersections are at (m+1)×(n+1) points.
A pedestrian starts at the north-west corner intersection, facing east. A path string uses:
- L: turn left 90°
- R: turn right 90°
- M: move forward by one block (one street segment)

When moving one segment, the pedestrian "passes" the adjacent block(s) of that segment:
- 2 blocks if the segment is internal; 1 block if it lies on the border.

Scoring:
- First time a block is passed: +bij
- Each subsequent time: +floor(bij/2)

The path never leaves the map. Compute the final satisfaction.

---

## 2. Key observations

- Intersections form a grid with coordinates:
  - x in [0, m] (west→east), y in [0, n] (north→south); start at (0, 0), facing east.
- Directions can be encoded cyclically:
  - 0: east, 1: south, 2: west, 3: north
  - L: dir = (dir + 3) % 4; R: dir = (dir + 1) % 4
- On each move M from (x, y) to (nx, ny), identify adjacent blocks by direction:
  - East: above (y-1, x) if y>0; below (y, x) if y<n
  - South: left (y, x-1) if x>0; right (y, x) if x<m
  - West: above (y-1, x-1) if y>0 and x>0; below (y, x-1) if x>0
  - North: left (y-1, x-1) if y>0 and x>0; right (y-1, x) if y>0 and x<m
- We only need to know whether a block has been passed before (boolean), not the exact count, because scoring is "first time vs later times".
- Complexity is O(|path|), with |path| ≤ 500, easily within limits.

---

## 3. Full solution approach

- Read n, m, the grid of digits (beauties), and the path.
- Maintain:
  - Current intersection (x, y) and direction dir (start at 0:east).
  - A visited[n][m] count grid, initially 0.
  - A running total satisfaction.
- For each character in path:
  - If L or R, update dir accordingly.
  - If M:
    - Compute the next intersection (nx, ny) = (x + dx[dir], y + dy[dir]).
    - Based on dir, identify 1 or 2 adjacent blocks (check boundaries).
    - For each adjacent block (r, c):
      - beauty = grid[r][c]
      - If visited[r][c] is 0: add beauty; else add beauty // 2
      - Increment visited[r][c].
    - Update (x, y) = (nx, ny).
- Output the final satisfaction.

---

## 4. C++ Solution

```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;
};

int n, m;
vector<string> grid;
string path;

void read() {
    cin >> n >> m;
    grid.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    cin >> path;
}

void solve() {
    // The solution to this problem is standard implementation. We essentially
    // just want to keep the current position (x, y) and direction dir, and
    // move along the grid. We will also keep the visited cells so far so that
    // we know if we need to divide by 2.

    int x = 0, y = 0;
    int dir = 0;
    int satisfaction = 0;

    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    vector<vector<int>> visited(n, vector<int>(m, 0));
    for(char c: path) {
        if(c == 'L') {
            dir = (dir + 3) % 4;
        } else if(c == 'R') {
            dir = (dir + 1) % 4;
        } else {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // Determine the blocks we pass when moving from (x, y) to (nx, ny).
            if(dir == 0) {
                // Blocks above and below this segment.
                if(y > 0 && x < m) {
                    int beauty = grid[y - 1][x] - '0';
                    satisfaction +=
                        (visited[y - 1][x] == 0) ? beauty : beauty / 2;
                    visited[y - 1][x]++;
                }
                if(y < n && x < m) {
                    int beauty = grid[y][x] - '0';
                    satisfaction += (visited[y][x] == 0) ? beauty : beauty / 2;
                    visited[y][x]++;
                }
            } else if(dir == 1) {
                // Blocks left and right of this segment.
                if(y < n && x > 0) {
                    int beauty = grid[y][x - 1] - '0';
                    satisfaction +=
                        (visited[y][x - 1] == 0) ? beauty : beauty / 2;
                    visited[y][x - 1]++;
                }
                if(y < n && x < m) {
                    int beauty = grid[y][x] - '0';
                    satisfaction += (visited[y][x] == 0) ? beauty : beauty / 2;
                    visited[y][x]++;
                }
            } else if(dir == 2) {
                // Blocks above and below this segment.
                if(y > 0 && x > 0) {
                    int beauty = grid[y - 1][x - 1] - '0';
                    satisfaction +=
                        (visited[y - 1][x - 1] == 0) ? beauty : beauty / 2;
                    visited[y - 1][x - 1]++;
                }
                if(y < n && x > 0) {
                    int beauty = grid[y][x - 1] - '0';
                    satisfaction +=
                        (visited[y][x - 1] == 0) ? beauty : beauty / 2;
                    visited[y][x - 1]++;
                }
            } else {
                // Blocks left and right of this segment.
                if(y > 0 && x > 0) {
                    int beauty = grid[y - 1][x - 1] - '0';
                    satisfaction +=
                        (visited[y - 1][x - 1] == 0) ? beauty : beauty / 2;
                    visited[y - 1][x - 1]++;
                }
                if(y > 0 && x < m) {
                    int beauty = grid[y - 1][x] - '0';
                    satisfaction +=
                        (visited[y - 1][x] == 0) ? beauty : beauty / 2;
                    visited[y - 1][x]++;
                }
            }

            x = nx;
            y = ny;
        }
    }

    cout << satisfaction << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5. Python Solution

```python
import sys

def main():
    data = sys.stdin.read().strip().splitlines()
    it = iter(data)

    # Read dimensions
    n_m = next(it).split()
    n = int(n_m[0])
    m = int(n_m[1])

    # Read grid rows as strings of digits
    grid_strs = [next(it).strip() for _ in range(n)]

    # Convert to integer grid (0..9)
    grid = [[ord(ch) - ord('0') for ch in row] for row in grid_strs]

    # Read path
    path = next(it).strip()

    # Directions: 0:east, 1:south, 2:west, 3:north
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # Start at top-left intersection, facing east
    x, y = 0, 0
    dir = 0

    # visited[r][c] = number of times block (r,c) has been passed
    visited = [[0] * m for _ in range(n)]

    satisfaction = 0

    for c in path:
        if c == 'L':
            dir = (dir + 3) % 4  # turn left
        elif c == 'R':
            dir = (dir + 1) % 4  # turn right
        else:
            # Move one segment forward
            nx = x + dx[dir]
            ny = y + dy[dir]

            if dir == 0:
                # East: adjacent blocks above (y-1, x) and below (y, x)
                if y > 0 and x < m:
                    r, c0 = y - 1, x
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
                if y < n and x < m:
                    r, c0 = y, x
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
            elif dir == 1:
                # South: adjacent blocks left (y, x-1) and right (y, x)
                if y < n and x > 0:
                    r, c0 = y, x - 1
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
                if y < n and x < m:
                    r, c0 = y, x
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
            elif dir == 2:
                # West: adjacent blocks above (y-1, x-1) and below (y, x-1)
                if y > 0 and x > 0:
                    r, c0 = y - 1, x - 1
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
                if y < n and x > 0:
                    r, c0 = y, x - 1
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
            else:
                # North: adjacent blocks left (y-1, x-1) and right (y-1, x)
                if y > 0 and x > 0:
                    r, c0 = y - 1, x - 1
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1
                if y > 0 and x < m:
                    r, c0 = y - 1, x
                    beauty = grid[r][c0]
                    satisfaction += beauty if visited[r][c0] == 0 else beauty // 2
                    visited[r][c0] += 1

            # Advance to the next intersection
            x, y = nx, ny

    print(satisfaction)

if __name__ == "__main__":
    main()
```
