#include <bits/stdc++.h>
inline void read(int& target) {
  char ch = getchar();
  target = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    (target *= 10) += ch - '0';
    ch = getchar();
  }
}
inline void read(char& target) {
  while (!isalpha(target = getchar()))
    ;
}
struct node {
  int x, y, block;
  node() {}
  node(const int& _x, const int& _y, const int& _block)
      : x(_x), y(_y), block(_block) {}
  inline bool operator<(const node& cmp) const { return x < cmp.x; }
  inline bool operator==(const node& cmp) const { return x == cmp.x; }
};
const int maxn = 101000;
std::vector<node> fov[maxn * 2], bav[maxn * 2], tmp;
int main() {
  int n, m, k;
  read(n);
  read(m);
  read(k);
  int xs, ys;
  for (int i = 0; i <= n + 1; i++) {
    xs = i, ys = 0;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
    xs = i, ys = m + 1;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = 0; i <= m + 1; i++) {
    xs = 0, ys = i;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
    xs = n + 1, ys = i;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = 1; i <= k; i++) {
    read(xs);
    read(ys);
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  read(xs);
  read(ys);
  --xs, --ys;
  char NS, EW;
  read(NS);
  read(EW);
  if ((NS == 'N') == (EW == 'W')) {
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
  } else {
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = maxn - m - 10, ed = n + maxn + 10; i <= ed; i++) {
    std::sort(fov[i].begin(), fov[i].end());
    tmp.clear();
    if (fov[i].size()) tmp.push_back(fov[i][0]);
    for (unsigned j = 1; j < fov[i].size(); j++)
      if (fov[i][j] == fov[i][j - 1])
        tmp.back().block |= fov[i][j].block;
      else
        tmp.push_back(fov[i][j]);
    fov[i] = tmp;
  }
  for (int i = 0, ed = n + m + 10; i < ed; i++) {
    std::sort(bav[i].begin(), bav[i].end());
    tmp.clear();
    if (bav[i].size()) tmp.push_back(bav[i][0]);
    for (unsigned j = 1; j < bav[i].size(); j++)
      if (bav[i][j] == bav[i][j - 1])
        tmp.back().block |= bav[i][j].block;
      else
        tmp.push_back(bav[i][j]);
    bav[i] = tmp;
  }
  long long ans = 0;
  node curr;
  curr.x = xs;
  node mem;
  if ((NS == 'N') == (EW == 'W')) {
    curr.y = ys, curr.block = 1;
    mem = curr;
    ++mem.x, ++mem.y;
    if (fov[curr.x - curr.y + maxn]
           [(std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                              fov[curr.x - curr.y + maxn].end(), curr) -
             fov[curr.x - curr.y + maxn].begin())]
               .block == 3) {
      ++curr.x, ++curr.y;
      --ans;
    }
  } else {
    curr.y = ys + 1, curr.block = 2;
    mem = curr;
    ++mem.x, --mem.y;
    if (bav[curr.x + curr.y]
           [(std::lower_bound(bav[curr.x + curr.y].begin(),
                              bav[curr.x + curr.y].end(), curr) -
             bav[curr.x + curr.y].begin())]
               .block == 3) {
      ++curr.x, --curr.y;
      --ans;
    }
  }
  while (1) {
    bool finished = 0;
    int ind;
    switch (curr.block) {
      case 1:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += curr.x - fov[curr.x - curr.y + maxn][ind - 1].x;
        curr = fov[curr.x - curr.y + maxn][ind - 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      case 3:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += bav[curr.x + curr.y][ind + 1].x - curr.x;
        curr = bav[curr.x + curr.y][ind + 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 2:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += curr.x - bav[curr.x + curr.y][ind - 1].x;
        curr = bav[curr.x + curr.y][ind - 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 4:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += fov[curr.x - curr.y + maxn][ind + 1].x - curr.x;
        curr = fov[curr.x - curr.y + maxn][ind + 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      default:
        abort();
    }
    if (curr.x == mem.x && curr.y == mem.y) {
      std::cout << ans + 1;
      return 0;
    }
    if (finished) break;
  }
  curr.x = xs + 1;
  if ((NS == 'N') == (EW == 'W')) {
    curr.y = ys + 1, curr.block = 4;
    if (fov[curr.x - curr.y + maxn]
           [(std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                              fov[curr.x - curr.y + maxn].end(), curr) -
             fov[curr.x - curr.y + maxn].begin())]
               .block == 3) {
      --curr.x, --curr.y;
      --ans;
    }
  } else {
    curr.y = ys, curr.block = 3;
    if (bav[curr.x + curr.y]
           [(std::lower_bound(bav[curr.x + curr.y].begin(),
                              bav[curr.x + curr.y].end(), curr) -
             bav[curr.x + curr.y].begin())]
               .block == 3) {
      --curr.x, ++curr.y;
      --ans;
    }
  }
  while (1) {
    bool finished = 0;
    int ind;
    switch (curr.block) {
      case 1:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += curr.x - fov[curr.x - curr.y + maxn][ind - 1].x;
        curr = fov[curr.x - curr.y + maxn][ind - 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      case 3:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += bav[curr.x + curr.y][ind + 1].x - curr.x;
        curr = bav[curr.x + curr.y][ind + 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 2:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += curr.x - bav[curr.x + curr.y][ind - 1].x;
        curr = bav[curr.x + curr.y][ind - 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 4:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += fov[curr.x - curr.y + maxn][ind + 1].x - curr.x;
        curr = fov[curr.x - curr.y + maxn][ind + 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      default:
        abort();
    }
    if (finished) break;
  }
  std::cout << ans + 1;
}

### Prompt

Please create a solution in Cpp 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>
inline void read(int& target) {
  char ch = getchar();
  target = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    (target *= 10) += ch - '0';
    ch = getchar();
  }
}
inline void read(char& target) {
  while (!isalpha(target = getchar()))
    ;
}
struct node {
  int x, y, block;
  node() {}
  node(const int& _x, const int& _y, const int& _block)
      : x(_x), y(_y), block(_block) {}
  inline bool operator<(const node& cmp) const { return x < cmp.x; }
  inline bool operator==(const node& cmp) const { return x == cmp.x; }
};
const int maxn = 101000;
std::vector<node> fov[maxn * 2], bav[maxn * 2], tmp;
int main() {
  int n, m, k;
  read(n);
  read(m);
  read(k);
  int xs, ys;
  for (int i = 0; i <= n + 1; i++) {
    xs = i, ys = 0;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
    xs = i, ys = m + 1;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = 0; i <= m + 1; i++) {
    xs = 0, ys = i;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
    xs = n + 1, ys = i;
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = 1; i <= k; i++) {
    read(xs);
    read(ys);
    --xs, --ys;
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  read(xs);
  read(ys);
  --xs, --ys;
  char NS, EW;
  read(NS);
  read(EW);
  if ((NS == 'N') == (EW == 'W')) {
    fov[xs - ys + maxn].push_back(node(xs, ys, 1));
    fov[xs - ys + maxn].push_back(node(xs + 1, ys + 1, 2));
  } else {
    bav[xs + ys + 1].push_back(node(xs + 1, ys, 2));
    bav[xs + ys + 1].push_back(node(xs, ys + 1, 1));
  }
  for (int i = maxn - m - 10, ed = n + maxn + 10; i <= ed; i++) {
    std::sort(fov[i].begin(), fov[i].end());
    tmp.clear();
    if (fov[i].size()) tmp.push_back(fov[i][0]);
    for (unsigned j = 1; j < fov[i].size(); j++)
      if (fov[i][j] == fov[i][j - 1])
        tmp.back().block |= fov[i][j].block;
      else
        tmp.push_back(fov[i][j]);
    fov[i] = tmp;
  }
  for (int i = 0, ed = n + m + 10; i < ed; i++) {
    std::sort(bav[i].begin(), bav[i].end());
    tmp.clear();
    if (bav[i].size()) tmp.push_back(bav[i][0]);
    for (unsigned j = 1; j < bav[i].size(); j++)
      if (bav[i][j] == bav[i][j - 1])
        tmp.back().block |= bav[i][j].block;
      else
        tmp.push_back(bav[i][j]);
    bav[i] = tmp;
  }
  long long ans = 0;
  node curr;
  curr.x = xs;
  node mem;
  if ((NS == 'N') == (EW == 'W')) {
    curr.y = ys, curr.block = 1;
    mem = curr;
    ++mem.x, ++mem.y;
    if (fov[curr.x - curr.y + maxn]
           [(std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                              fov[curr.x - curr.y + maxn].end(), curr) -
             fov[curr.x - curr.y + maxn].begin())]
               .block == 3) {
      ++curr.x, ++curr.y;
      --ans;
    }
  } else {
    curr.y = ys + 1, curr.block = 2;
    mem = curr;
    ++mem.x, --mem.y;
    if (bav[curr.x + curr.y]
           [(std::lower_bound(bav[curr.x + curr.y].begin(),
                              bav[curr.x + curr.y].end(), curr) -
             bav[curr.x + curr.y].begin())]
               .block == 3) {
      ++curr.x, --curr.y;
      --ans;
    }
  }
  while (1) {
    bool finished = 0;
    int ind;
    switch (curr.block) {
      case 1:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += curr.x - fov[curr.x - curr.y + maxn][ind - 1].x;
        curr = fov[curr.x - curr.y + maxn][ind - 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      case 3:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += bav[curr.x + curr.y][ind + 1].x - curr.x;
        curr = bav[curr.x + curr.y][ind + 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 2:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += curr.x - bav[curr.x + curr.y][ind - 1].x;
        curr = bav[curr.x + curr.y][ind - 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 4:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += fov[curr.x - curr.y + maxn][ind + 1].x - curr.x;
        curr = fov[curr.x - curr.y + maxn][ind + 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      default:
        abort();
    }
    if (curr.x == mem.x && curr.y == mem.y) {
      std::cout << ans + 1;
      return 0;
    }
    if (finished) break;
  }
  curr.x = xs + 1;
  if ((NS == 'N') == (EW == 'W')) {
    curr.y = ys + 1, curr.block = 4;
    if (fov[curr.x - curr.y + maxn]
           [(std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                              fov[curr.x - curr.y + maxn].end(), curr) -
             fov[curr.x - curr.y + maxn].begin())]
               .block == 3) {
      --curr.x, --curr.y;
      --ans;
    }
  } else {
    curr.y = ys, curr.block = 3;
    if (bav[curr.x + curr.y]
           [(std::lower_bound(bav[curr.x + curr.y].begin(),
                              bav[curr.x + curr.y].end(), curr) -
             bav[curr.x + curr.y].begin())]
               .block == 3) {
      --curr.x, ++curr.y;
      --ans;
    }
  }
  while (1) {
    bool finished = 0;
    int ind;
    switch (curr.block) {
      case 1:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += curr.x - fov[curr.x - curr.y + maxn][ind - 1].x;
        curr = fov[curr.x - curr.y + maxn][ind - 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      case 3:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += bav[curr.x + curr.y][ind + 1].x - curr.x;
        curr = bav[curr.x + curr.y][ind + 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 2:
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        ans += curr.x - bav[curr.x + curr.y][ind - 1].x;
        curr = bav[curr.x + curr.y][ind - 1];
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        if (!(fov[curr.x - curr.y + maxn][ind] == curr)) finished = 1;
        if (fov[curr.x - curr.y + maxn][ind].block == 3 ||
            !fov[curr.x - curr.y + maxn][ind].block)
          finished = 1;
        else
          curr.block = (fov[curr.x - curr.y + maxn][ind].block == 1 ? 1 : 4);
        break;
      case 4:
        ind = (std::lower_bound(fov[curr.x - curr.y + maxn].begin(),
                                fov[curr.x - curr.y + maxn].end(), curr) -
               fov[curr.x - curr.y + maxn].begin());
        ans += fov[curr.x - curr.y + maxn][ind + 1].x - curr.x;
        curr = fov[curr.x - curr.y + maxn][ind + 1];
        ind = (std::lower_bound(bav[curr.x + curr.y].begin(),
                                bav[curr.x + curr.y].end(), curr) -
               bav[curr.x + curr.y].begin());
        if (!(bav[curr.x + curr.y][ind] == curr)) finished = 1;
        if (bav[curr.x + curr.y][ind].block == 3 ||
            !bav[curr.x + curr.y][ind].block)
          finished = 1;
        else
          curr.block = (bav[curr.x + curr.y][ind].block == 1 ? 2 : 3);
        break;
      default:
        abort();
    }
    if (finished) break;
  }
  std::cout << ans + 1;
}

```