AT_abc421_d [ABC421D] RLE Moving

無限に広いグリッドがあります。グリッドのあるマスはマス $ (0,0) $ と名前がついています。 マス $ (0,0) $ から下に $ r $ マス、右に $ c $ マスの移動した位置にあるマスをマス $ (r,c) $ と呼びます。 ここで、「下に $ r $ マス移動する」は $ r $ が負のときは「上に $ |r| $ マス移動する」ことを表し、「右に $ c $ マス移動する」は $ c $ が負のときには「左に $ |c| $ マス移動する」ことを表すものとします。 具体的には、マス $ (0,0) $ の周辺にあるマスは以下のようになります。  最初、高橋君はマス $ (R_t,C_t) $ に、青木君はマス $ (R_a,C_a) $ にいます。二人はそれぞれ `U`,`D`,`L`,`R` からなる長さ $ N $ の文字列 $ S,T $ に従って $ N $ 回移動を行います。 各 $ i $ について、高橋君と青木君の $ i $ 回目の移動は同時に行われます。具体的には、高橋君は $ S $ の $ i $ 文字目が `U` のとき上、`D` のとき下、`L` のとき左、`R` のとき右へ $ 1 $ マス移動し、青木君は $ T $ の $ i $ 文字目によって同様に移動します。 $ N $ 回の移動の中で、移動直後に高橋君と青木君が同じマスにいた回数を求めてください。 ただし、 $ N $ は非常に大きいため $ S,T $ は $ ( (S'_1, A_1),\ldots(S'_M,A_M) ), ( (T'_1,B_1),\ldots,(T'_L,B_L) ) $ の形で与えられ、 $ S $ は「文字 $ S'_1 $ を $ A_1 $ 個、 $ \dots $ 、文字 $ S'_M $ を $ A_M $ 個」をこの順に連結した文字列であり、 $ T $ も同様です。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

答えを出力せよ。

### Sample Explanation 1 このケースでは $ S= $ `RRD`、 $ T= $ `UUU` であり、移動は次のように行われます。 - 最初、高橋君はマス $ (0,0) $ に、青木君はマス $ (4,2) $ にいる。 - $ 1 $ 回目の移動後、高橋君はマス $ (0,1) $ 、青木君はマス $ (3,2) $ にいる。 - $ 2 $ 回目の移動後、高橋君はマス $ (0,2) $ 、青木君はマス $ (2,2) $ にいる。 - $ 3 $ 回目の移動後、高橋君はマス $ (1,2) $ 、青木君はマス $ (1,2) $ にいる。 よって、高橋君と青木君が移動直後に同じマスにいた回数は $ 1 $ です。 ### Sample Explanation 2 $ 2000000000 $ 回目の移動から $ 3000000000 $ 回目の移動までの $ 1000000001 $ 回で高橋君と青木君は移動直後に同じマスにいます。 ### Constraints - $ -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 $ - 与えられる数値は全て整数