问题描述

现在有两个长度为 $L$ 的序列 $a,b$，找出有多少个下标 $i$ 满足 $a_i=b_i(1\leq i\leq L)$。

由于 $L$ 十分地大，因此 $a$ 被体现为一个长度为 $N_1$ 的二元组序列。下面是二元组序列的生成方式：

• 对于所有 $a$ 序列中的 $a_i\neq a_{i+1}$，我们在 $(i,i+1)$ 中间切割一次。
• 最后 $a$ 序列会被切割成 $N_1$ 块，每一块都是由 $l_i$ 个相同的数 $x_i$ 组成的。我们将每一块表示成一个二元组 $(x_i,l_i)$，从左至右拼接起来即可得到一个长度为 $N_1$ 的二元组序列。

同理，$b$ 被体现为一个长度为 $N_2$ 的二元组序列。

给出 $L,N_1,N_2$ 以及两个二元组序列，解决本题开头的问题。

输入格式

按下面格式输入数据：

L N1 N2
v1,1 l1,1 
v1,2 l1,2
...
v1,N1 l1,N1
v2,1 l2,1
v2,2 l2,2
...
v2,N2 l2,N2

输出格式

输出每次询问的答案。

样例

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3

4

样例解释

我们有四个 $j$ 满足$x_{1,j}=x_{2,j};j=1,2,5,8$，所以答案为 $4$。

10000000000 1 1
1 10000000000
1 10000000000

10000000000

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

380

数据范围

• $1\leq\ L\leq\ 10 ^ {12}$
• $1\leq\ N _ 1,N _ 2\leq\ 10 ^ 5$
• $ 1\leq\ v\ _ {i,j}\leq\ 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq\ j\leq\ N _ i) $
• $ 1\leq\ l _ {i,j}\leq\ L\ (i\in\lbrace1,2\rbrace,1\leq\ j\leq\ N _ i) $
• $ v _ {i,j}\neq\ v _{i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq\ j\lt\ N _ i) $
• $ l_ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace) $