题目描述

假设有一个$n \times m$的网格。左上角的格子坐标是（1,1），右下角的格子坐标是（n,m）。网格中有$k$个堵塞的格子，其他的格子是空的。你在空格子（$x_s$，$y_s$）的中心向一个对角线方向（也就是东北，西北，东南，西南）发射一束激光。如果光束碰到堵塞的格子或网格边界，它会反射。在不同情况下光束的反射方式如下图所示。

过了一会儿，光束进入了一个无限的循环。计算至少被光束通过一次的空格子数。我们认为光束通过了一个格子的中心才算是通过了这个格子。

输入格式

第一行三个整数$n$、$m$、$k$，接下来$k$行，每行两个整数$x_i$和$y_i$，表示第$i$个堵塞的格子的坐标。最后一行两个整数$x_s$，$y_s$和一个字符串表示激光发出的方向。“NE”，“NW”，“SE”，“SW”分别表示方向（-1，1），（-1，-1），（1，1），（1，-1）。保证输入的堵塞的格子坐标不重复。

输出格式

一行输出光束至少通过一次的空格子数。

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

14

提示

$100$的数据$n, m, k \leq 1000000$

题目来源

暂无来源