← 返回题目列表

Codeforces · 274/E

E. 镜室

中文机器翻译题面 查看原题

想象一个 n × m 的网格,其中有一些被阻挡的单元格。网格中左上角单元格的坐标为 (1, 1),右下角单元格的坐标为 (n, m)。网格中有 k 个被阻挡的单元格,其他单元格是空的。您从空单元格的中心(xs,ys)向对角线方向之一(即东北、西北、东南或西南)发出激光束。如果光束击中被阻挡的单元格或网格边界,它将反射。下图描述了不同情况下光束反射的行为。

一段时间后,光束进入无限循环。计算光束至少穿过一次的空单元的数量。如果光束穿过单元的中心,我们认为它就穿过单元。

输入

输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 105)。接下来的 k 行中的每一行都包含两个整数 xi 和 yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m),表示第 i 个阻塞单元的位置。

最后一行包含 xs、ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) 和闪光方向,等于“NE”、“NW”、“SE”或“SW”。这些字符串表示方向 ( - 1, 1)、( - 1, - 1)、(1, 1)、(1, - 1)。

保证没有两个被阻挡的单元格具有相同的坐标。

输出

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

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3 3 0
1 2 SW

输出 #1

6

输入 #2

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

输出 #2

14