题目描述

$2$ 行 $L$ 列のマス目があります。 上から $i$ 行目 $(i\in\lbrace1,2\rbrace)$、左から $j$ 列目 $(1\leq\ j\leq\ L)$のマス目を $(i,j)$ で表します。 $(i,j)$ には整数 $x\ _\ {i,j}$ が書かれています。

$x\ _\ {1,j}=x\ _\ {2,j}$ であるような整数 $j$ の個数を求めてください。

ただし、$x\ _\ {i,j}$ の情報は $(x\ _\ {1,1},x\ _\ {1,2},\ldots,x\ _\ {1,L})$ と $(x\ _\ {2,1},x\ _\ {2,2},\ldots,x\ _\ {2,L})$ をそれぞれ連長圧縮した、長さ $N\ _\ 1$ の列 $((v\ _\ {1,1},l\ _\ {1,1}),\ldots,(v\ _\ {1,N\ _\ 1},l\ _\ {1,N\ _\ 1}))$ と長さ $N\ _\ 2$ の列 $((v\ _\ {2,1},l\ _\ {2,1}),\ldots,(v\ _\ {2,N\ _\ 2},l\ _\ {2,N\ _\ 2}))$ として与えられます。

ここで、列 $A$ の連長圧縮とは、$A$ の要素 $v\ _\ i$ と正整数 $l\ _\ i$ の組 $(v\ _\ i,l\ _\ i)$ の列であって、次の操作で得られるものです。

1. $A$ を異なる要素が隣り合っている部分で分割する。
2. 分割した各列 $B\ _\ 1,B\ _\ 2,\ldots,B\ _\ k$ に対して、$v\ _\ i$ を $B\ _\ i$ の要素、$l\ _\ i$ を $B\ _\ i$ の長さとする。

输入格式

入力は以下の形式で標準入力から与えられる。

$L$ $N\ _\ 1$ $N\ _\ 2$ $v\ _\ {1,1}$ $l\ _\ {1,1}$ $v\ _\ {1,2}$ $l\ _\ {1,2}$ $\vdots$ $v\ _\ {1,N\ _\ 1}$ $l\ _\ {1,N\ _\ 1}$ $v\ _\ {2,1}$ $l\ _\ {2,1}$ $v\ _\ {2,2}$ $l\ _\ {2,2}$ $\vdots$ $v\ _\ {2,N\ _\ 2}$ $l\ _\ {2,N\ _\ 2}$

输出格式

答えを $1$ 行で出力せよ。

题目大意

现在有两个长度为 $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$ 以及两个二元组序列，解决本题开头的问题。

Translated by

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

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)$
• 入力はすべて整数

Sample Explanation 1

マス目は以下の図のようになっています。  $x\ _\ {1,j}=x\ _\ {2,j}$ となるような整数 $j$ は、$j=1,2,5,8$ の $4$ つなので、出力すべき値は $4$ です。

Sample Explanation 2

答えが $32\operatorname{bit}$ 整数に収まらない場合があることに注意してください。