想象一个 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