UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4235. 光

Statistics 下载数据

Description

假设有一个n×m的网格。左上角的格子坐标是(1,1),右下角的格子坐标是(n,m)。网格中有k个堵塞的格子,其他的格子是空的。你在空格子(xs,ys)的中心向一个对角线方向(也就是东北,西北,东南,西南)发射一束激光。如果光束碰到堵塞的格子或网格边界,它会反射。在不同情况下光束的反射方式如下图所示。
 
过了一会儿,光束进入了一个无限的循环。计算至少被光束通过一次的空格子数。我们认为光束通过了一个格子的中心才算是通过了这个格子。

Input

第一行三个整数n、m、k,接下来k行每行两个整数xi和yi,表示第i个堵塞的格子的坐标。
最后一行两个整数xs,ys和一个字符串表示激光发出的方向。“NE”,“NW”,“SE”,“SW”分别表示方向(-1,1),(-1,-1),(1,1),(1,-1)。
保证输入的堵塞的格子坐标不重复。

Output

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

Sample Input

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

Sample Output

14

Hint

100%的数据 n,m,k≤1000000


Source