分数: 425 点
问题陈述
有一个无限大的网格。网格中的一个单元格称为单元格 (0,0).
单元格位于 r 细胞下降并且 c 单元格右侧的单元格 (0,0) 称为单元格 (r,c).
这里,“r 单元格向下”表示“|r| 细胞向上”时 r 为负,并且“c 单元格右侧“表示”|c| 剩余单元格”时 c 为负。
具体来说,细胞周围的细胞 (0,0) 如下:

最初,高桥在牢房里 (R_t,C_t) 青木在牢房 (R_a,C_a)。他们每个人都会做出 N 根据字符串移动 S 和 T 长度 N 组成 U, D, L, R.
对于每个 i,高桥和青木的 i-th 次移动同时发生:高桥向上移动一个单元格,如果 i- 第一个字符 S is U,如果 D,如果 L,如果 R;青木的动作也类似 i- 第一个字符 T.
找出高桥和青木在移动后立即位于同一单元格的次数 N 移动。
自从 N 非常大, S 和 T 以以下形式给出 ((S'_1, A_1),\ldots,(S'_M,A_M)) 和 ((T'_1,B_1),\ldots,(T'_L,B_L)),其中 S 是通过连接“得到的字符串A_1 角色副本 S'_1, \dots, A_M 角色副本 S'_M“按此顺序,并且 T 类似地给出。
约束
- -10^9 \leq R_t,C_t,R_a,C_a \leq 10^9
- 1\leq N \leq 10^{14}
- 1\leq M,L \leq 10^5
- 每个 S'_i 和 T'_i 是其中之一
U,D,L,R. - 1 \leq A_i,B_i \leq 10^9
- A_1+\dots+A_M=B_1+\dots+B_L=N
- 所有给定值均为整数。
输入
输入由标准输入按以下格式给出:
R_t C_t R_a C_a N M L S'_1 A_1 \vdots S'_M A_M T'_1 B_1 \vdots T'_L B_L
输出
打印答案。
示例输入 1
0 0 4 2 3 2 1 R 2 D 1 U 3
示例输出 1
1
在这种情况下, S= RRD 和 T= UUU,动作进行如下:
- 最初,高桥在牢房里 (0,0) 青木在牢房 (4,2).
- 之后 1刚搬家,高桥在牢房里 (0,1) 青木在牢房 (3,2).
- 之后 2第二次搬家,高桥在牢房里 (0,2) 青木在牢房 (2,2).
- 之后 3rd 移动,高桥在牢房 (1,2) 青木在牢房 (1,2).
因此,高桥和青木在移动后立即位于同一单元格的次数为 1.
示例输入 2
1000000000 1000000000 -1000000000 -1000000000 3000000000 3 3 L 1000000000 U 1000000000 U 1000000000 D 1000000000 R 1000000000 U 1000000000
示例输出 2
1000000001
从 2000000000第 次移动到 3000000000第 次移动,高桥和青木在移动后立即位于同一牢房 1000000001 次。
示例输入 3
3 3 3 2 1 1 1 L 1 R 1
示例输出 3
0
示例输入 4
0 0 0 0 1 1 1 L 1 R 1
示例输出 4
0