AT_abc294_e [ABC294E] 2xN Grid

[problemUrl]: https://atcoder.jp/contests/abc294/tasks/abc294_e $ 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 $ 行で出力せよ。

### 制約 - $ 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 マス目は以下の図のようになっています。 !\[\](https://img.atcoder.jp/abc294/14f38720983c464a322b504738344f24.png) $ x\ _\ {1,j}=x\ _\ {2,j} $ となるような整数 $ j $ は、$ j=1,2,5,8 $ の $ 4 $ つなので、出力すべき値は $ 4 $ です。 ### Sample Explanation 2 答えが $ 32\operatorname{bit} $ 整数に収まらない場合があることに注意してください。