#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, ix, iy, cx, cy, dx, dy, there_is_my_star, here_is_my_star;
char op[5];
long long i_find_my_star;
bool flag;
vector<int> x[100007 * 2], y[100007 * 2];
inline int i_need_its_x(int a, int b) { return a + b - 1; }
inline int i_need_its_y(int a, int b) { return m + a - b; }
inline int star_has_its_x(int id, int x) { return id - x + 1; }
inline int star_has_its_y(int id, int x) { return x + m - id; }
inline void where_the_ray_go() {
  if (dx == 1) {
    if (dy == 1) {
      int id = i_need_its_y(cx, cy);
      there_is_my_star =
          y[id][lower_bound(y[id].begin(), y[id].end(), cx) - y[id].begin()];
      here_is_my_star = star_has_its_y(id, there_is_my_star);
    } else {
      int id = i_need_its_x(cx, cy);
      there_is_my_star =
          x[id][lower_bound(x[id].begin(), x[id].end(), cx) - x[id].begin()];
      here_is_my_star = star_has_its_x(id, there_is_my_star);
    }
  } else {
    if (dy == 1) {
      int id = i_need_its_x(cx, cy);
      there_is_my_star = x[id][lower_bound(x[id].begin(), x[id].end(), cx) -
                               x[id].begin() - 1];
      here_is_my_star = star_has_its_x(id, there_is_my_star);
    } else {
      int id = i_need_its_y(cx, cy);
      there_is_my_star = y[id][lower_bound(y[id].begin(), y[id].end(), cx) -
                               y[id].begin() - 1];
      here_is_my_star = star_has_its_y(id, there_is_my_star);
    }
  }
}
inline bool maybe_that_is_my_star(int a, int b, int c) {
  if (a == c) {
    return 0;
  }
  if (a > c) {
    swap(a, c);
  }
  if (a < b && b < c) {
    return 1;
  }
  return 0;
}
inline bool where_is_my_star() {
  if (abs(cx - sx) != abs(cy - sy) || ix != dx || iy != dy ||
      (cx - sx) / dx > 0 || (cy - sy) / dy > 0 ||
      maybe_that_is_my_star(cx, there_is_my_star, sx)) {
    return 0;
  }
  i_find_my_star += (long long)abs(cx - sx);
  return 1;
}
inline bool how_will_the_ray_go(int tx, int ty) {
  int id1 = i_need_its_x(tx, ty), id2 = i_need_its_y(tx, ty);
  int sz1 = x[id1].size(), sz2 = y[id2].size();
  if (sz1 < sz2) {
    for (int i = 0; i < (int)x[id1].size(); i++) {
      if (x[id1][i] == tx) {
        return 1;
      }
    }
  } else {
    for (int i = 0; i < (int)y[id2].size(); i++) {
      if (y[id2][i] == tx) {
        return 1;
      }
    }
  }
  return 0;
}
inline void my_star_stops_the_ray() {
  if (flag) {
    printf("%lld\n", i_find_my_star), exit(0);
  }
  flag = 1, cx = sx, cy = sy, dx = -ix, dy = -iy, i_find_my_star--;
}
inline void ray_pass_my_star() {
  i_find_my_star += abs(there_is_my_star - cx), cx = there_is_my_star,
                                                cy = here_is_my_star;
  if (dx == 1) {
    if (dy == 1) {
      bool find_that_star =
               how_will_the_ray_go(there_is_my_star, here_is_my_star - 1),
           how_to_find_my_star =
               how_will_the_ray_go(there_is_my_star - 1, here_is_my_star);
      if (find_that_star == how_to_find_my_star) {
        my_star_stops_the_ray();
      } else {
        if (find_that_star) {
          cx--, dx = -1, dy = 1;
        }
        if (how_to_find_my_star) {
          cy--, dx = 1, dy = -1;
        }
      }
    } else {
      bool robs = how_will_the_ray_go(there_is_my_star, here_is_my_star + 1),
           how_to_find_my_star =
               how_will_the_ray_go(there_is_my_star - 1, here_is_my_star);
      if (robs == how_to_find_my_star) {
        my_star_stops_the_ray();
      } else {
        if (robs) {
          cx--, dx = -1, dy = -1;
        }
        if (how_to_find_my_star) {
          cy++, dx = 1, dy = 1;
        }
      }
    }
  } else {
    if (dy == 1) {
      bool find_that_star =
               how_will_the_ray_go(there_is_my_star, here_is_my_star - 1),
           find_this_star =
               how_will_the_ray_go(there_is_my_star + 1, here_is_my_star);
      if (find_that_star == find_this_star) {
        my_star_stops_the_ray();
      } else {
        if (find_that_star) {
          cx++, dx = 1, dy = 1;
        }
        if (find_this_star) {
          cy--, dx = -1, dy = -1;
        }
      }
    } else {
      bool robs = how_will_the_ray_go(there_is_my_star, here_is_my_star + 1),
           find_this_star =
               how_will_the_ray_go(there_is_my_star + 1, here_is_my_star);
      if (robs == find_this_star) {
        my_star_stops_the_ray();
      } else {
        if (robs) {
          cx++, dx = 1, dy = -1;
        }
        if (find_this_star) {
          cy++, dx = -1, dy = 1;
        }
      }
    }
  }
}
int main() {
  int a, b;
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 1; i <= t; i++) {
    scanf("%d%d", &a, &b);
    x[i_need_its_x(a, b)].push_back(a);
    y[i_need_its_y(a, b)].push_back(a);
  }
  for (int i = 0; i <= n + m; i++) {
    x[i].push_back(max(0, i - m));
    x[i].push_back(min(n + 1, i + 1));
    y[i].push_back(max(0, i - m));
    y[i].push_back(min(n + 1, i + 1));
  }
  for (int i = 1; i < n + m; i++) {
    sort(x[i].begin(), x[i].end());
    sort(y[i].begin(), y[i].end());
  }
  scanf("%d%d", &sx, &sy);
  scanf("%s", op);
  if (op[0] == 'S') {
    ix = 1;
  }
  if (op[0] == 'N') {
    ix = -1;
  }
  if (op[1] == 'W') {
    iy = -1;
  }
  if (op[1] == 'E') {
    iy = 1;
  }
  dx = ix, dy = iy, cx = sx, cy = sy;
  where_the_ray_go();
  while (1) {
    ray_pass_my_star();
    where_the_ray_go();
    if (where_is_my_star()) {
      break;
    }
  }
  printf("%lld", i_find_my_star);
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

Imagine an n × m grid with some blocked cells. The top left cell in the grid has coordinates (1, 1) and the bottom right cell has coordinates (n, m). There are k blocked cells in the grid and others are empty. You flash a laser beam from the center of an empty cell (xs, ys) in one of the diagonal directions (i.e. north-east, north-west, south-east or south-west). If the beam hits a blocked cell or the border of the grid it will reflect. The behavior of the beam reflection in different situations is depicted in the figure below. 

<image>

After a while the beam enters an infinite cycle. Count the number of empty cells that the beam goes through at least once. We consider that the beam goes through cell if it goes through its center.

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 105). Each of the next k lines contains two integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) indicating the position of the i-th blocked cell. 

The last line contains xs, ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) and the flash direction which is equal to "NE", "NW", "SE" or "SW". These strings denote directions ( - 1, 1), ( - 1, - 1), (1, 1), (1, - 1).

It's guaranteed that no two blocked cells have the same coordinates.

Output

In the only line of the output print the number of empty cells that the beam goes through at least once.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 3 0
1 2 SW


Output

6


Input

7 5 3
3 3
4 3
5 3
2 1 SE


Output

14

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, ix, iy, cx, cy, dx, dy, there_is_my_star, here_is_my_star;
char op[5];
long long i_find_my_star;
bool flag;
vector<int> x[100007 * 2], y[100007 * 2];
inline int i_need_its_x(int a, int b) { return a + b - 1; }
inline int i_need_its_y(int a, int b) { return m + a - b; }
inline int star_has_its_x(int id, int x) { return id - x + 1; }
inline int star_has_its_y(int id, int x) { return x + m - id; }
inline void where_the_ray_go() {
  if (dx == 1) {
    if (dy == 1) {
      int id = i_need_its_y(cx, cy);
      there_is_my_star =
          y[id][lower_bound(y[id].begin(), y[id].end(), cx) - y[id].begin()];
      here_is_my_star = star_has_its_y(id, there_is_my_star);
    } else {
      int id = i_need_its_x(cx, cy);
      there_is_my_star =
          x[id][lower_bound(x[id].begin(), x[id].end(), cx) - x[id].begin()];
      here_is_my_star = star_has_its_x(id, there_is_my_star);
    }
  } else {
    if (dy == 1) {
      int id = i_need_its_x(cx, cy);
      there_is_my_star = x[id][lower_bound(x[id].begin(), x[id].end(), cx) -
                               x[id].begin() - 1];
      here_is_my_star = star_has_its_x(id, there_is_my_star);
    } else {
      int id = i_need_its_y(cx, cy);
      there_is_my_star = y[id][lower_bound(y[id].begin(), y[id].end(), cx) -
                               y[id].begin() - 1];
      here_is_my_star = star_has_its_y(id, there_is_my_star);
    }
  }
}
inline bool maybe_that_is_my_star(int a, int b, int c) {
  if (a == c) {
    return 0;
  }
  if (a > c) {
    swap(a, c);
  }
  if (a < b && b < c) {
    return 1;
  }
  return 0;
}
inline bool where_is_my_star() {
  if (abs(cx - sx) != abs(cy - sy) || ix != dx || iy != dy ||
      (cx - sx) / dx > 0 || (cy - sy) / dy > 0 ||
      maybe_that_is_my_star(cx, there_is_my_star, sx)) {
    return 0;
  }
  i_find_my_star += (long long)abs(cx - sx);
  return 1;
}
inline bool how_will_the_ray_go(int tx, int ty) {
  int id1 = i_need_its_x(tx, ty), id2 = i_need_its_y(tx, ty);
  int sz1 = x[id1].size(), sz2 = y[id2].size();
  if (sz1 < sz2) {
    for (int i = 0; i < (int)x[id1].size(); i++) {
      if (x[id1][i] == tx) {
        return 1;
      }
    }
  } else {
    for (int i = 0; i < (int)y[id2].size(); i++) {
      if (y[id2][i] == tx) {
        return 1;
      }
    }
  }
  return 0;
}
inline void my_star_stops_the_ray() {
  if (flag) {
    printf("%lld\n", i_find_my_star), exit(0);
  }
  flag = 1, cx = sx, cy = sy, dx = -ix, dy = -iy, i_find_my_star--;
}
inline void ray_pass_my_star() {
  i_find_my_star += abs(there_is_my_star - cx), cx = there_is_my_star,
                                                cy = here_is_my_star;
  if (dx == 1) {
    if (dy == 1) {
      bool find_that_star =
               how_will_the_ray_go(there_is_my_star, here_is_my_star - 1),
           how_to_find_my_star =
               how_will_the_ray_go(there_is_my_star - 1, here_is_my_star);
      if (find_that_star == how_to_find_my_star) {
        my_star_stops_the_ray();
      } else {
        if (find_that_star) {
          cx--, dx = -1, dy = 1;
        }
        if (how_to_find_my_star) {
          cy--, dx = 1, dy = -1;
        }
      }
    } else {
      bool robs = how_will_the_ray_go(there_is_my_star, here_is_my_star + 1),
           how_to_find_my_star =
               how_will_the_ray_go(there_is_my_star - 1, here_is_my_star);
      if (robs == how_to_find_my_star) {
        my_star_stops_the_ray();
      } else {
        if (robs) {
          cx--, dx = -1, dy = -1;
        }
        if (how_to_find_my_star) {
          cy++, dx = 1, dy = 1;
        }
      }
    }
  } else {
    if (dy == 1) {
      bool find_that_star =
               how_will_the_ray_go(there_is_my_star, here_is_my_star - 1),
           find_this_star =
               how_will_the_ray_go(there_is_my_star + 1, here_is_my_star);
      if (find_that_star == find_this_star) {
        my_star_stops_the_ray();
      } else {
        if (find_that_star) {
          cx++, dx = 1, dy = 1;
        }
        if (find_this_star) {
          cy--, dx = -1, dy = -1;
        }
      }
    } else {
      bool robs = how_will_the_ray_go(there_is_my_star, here_is_my_star + 1),
           find_this_star =
               how_will_the_ray_go(there_is_my_star + 1, here_is_my_star);
      if (robs == find_this_star) {
        my_star_stops_the_ray();
      } else {
        if (robs) {
          cx++, dx = 1, dy = -1;
        }
        if (find_this_star) {
          cy++, dx = -1, dy = 1;
        }
      }
    }
  }
}
int main() {
  int a, b;
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 1; i <= t; i++) {
    scanf("%d%d", &a, &b);
    x[i_need_its_x(a, b)].push_back(a);
    y[i_need_its_y(a, b)].push_back(a);
  }
  for (int i = 0; i <= n + m; i++) {
    x[i].push_back(max(0, i - m));
    x[i].push_back(min(n + 1, i + 1));
    y[i].push_back(max(0, i - m));
    y[i].push_back(min(n + 1, i + 1));
  }
  for (int i = 1; i < n + m; i++) {
    sort(x[i].begin(), x[i].end());
    sort(y[i].begin(), y[i].end());
  }
  scanf("%d%d", &sx, &sy);
  scanf("%s", op);
  if (op[0] == 'S') {
    ix = 1;
  }
  if (op[0] == 'N') {
    ix = -1;
  }
  if (op[1] == 'W') {
    iy = -1;
  }
  if (op[1] == 'E') {
    iy = 1;
  }
  dx = ix, dy = iy, cx = sx, cy = sy;
  where_the_ray_go();
  while (1) {
    ray_pass_my_star();
    where_the_ray_go();
    if (where_is_my_star()) {
      break;
    }
  }
  printf("%lld", i_find_my_star);
  return 0;
}

```