CF274E.Mirror Room

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 (x__s, y__s) 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.

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.

想象一个 $n \times m$ 的网格，其中某些格子被阻塞。网格的左上角格子坐标为 $(1, 1)$，右下角格子坐标为 $(n, m)$。网格中共有 $k$ 个被阻塞的格子，其余格子为空。你从某个空格子 $(x_s, y_s)$ 的中心向某一斜对角方向（即东北、西北、东南或西南）发射一束激光。若光束撞击到被阻塞的格子或网格边界，则会发生反射。不同情形下光束反射的行为如下图所示：

经过一段时间后，光束将进入一个无限循环。请统计光束至少经过一次的空格子的数量。我们定义：当光束经过某个格子的中心时，即视为“经过该格子”。

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 x__i and y__i (1 ≤ x__i ≤ n, 1 ≤ y__i ≤ m) indicating the position of the i-th blocked cell.

The last line contains x__s, y__s (1 ≤ x__s ≤ n, 1 ≤ y__s ≤ 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.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 10^5$，$0 \leq k \leq 10^5$）。接下来的 $k$ 行每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \leq n$，$1 \leq y_i \leq m$），表示第 $i$ 个被阻挡的格子的位置。

最后一行包含 $x_s$、$y_s$（$1 \leq x_s \leq n$，$1 \leq y_s \leq m$）以及闪光的方向，该方向为 "NE"、"NW"、"SE" 或 "SW" 中的一个。这些字符串分别表示方向 $(-1, 1)$、$(-1, -1)$、$(1, 1)$、$(1, -1)$。

保证任意两个被阻挡的格子坐标均不相同。

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.

在输出的唯一一行中，打印光束至少经过一次的空单元格的数量。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin、cout 流，或 %I64d 格式说明符。