AT_abc421_d [ABC421D] RLE Moving

There is an infinitely large grid. One cell of the grid is named cell $ (0,0) $ . The cell located $ r $ cells down and $ c $ cells right from cell $ (0,0) $ is called cell $ (r,c) $ . Here, " $ r $ cells down" means " $ |r| $ cells up" when $ r $ is negative, and " $ c $ cells right" means " $ |c| $ cells left" when $ c $ is negative. Specifically, the cells around cell $ (0,0) $ are as follows:  Initially, Takahashi is at cell $ (R_t,C_t) $ and Aoki is at cell $ (R_a,C_a) $ . They will each make $ N $ moves according to strings $ S $ and $ T $ of length $ N $ consisting of `U`, `D`, `L`, `R`. For each $ i $ , Takahashi's and Aoki's $ i $ -th moves occur simultaneously: Takahashi moves one cell up if the $ i $ -th character of $ S $ is `U`, down if `D`, left if `L`, and right if `R`; Aoki moves similarly according to the $ i $ -th character of $ T $ . Find the number of times Takahashi and Aoki are at the same cell immediately after a move during the $ N $ moves. Since $ N $ is very large, $ S $ and $ T $ are given in the form $ ((S'_1, A_1),\ldots,(S'_M,A_M)) $ and $ ((T'_1,B_1),\ldots,(T'_L,B_L)) $ , where $ S $ is the string obtained by concatenating " $ A_1 $ copies of character $ S'_1 $ , $ \dots $ , $ A_M $ copies of character $ S'_M $ " in this order, and $ T $ is given similarly.

The input is given from Standard Input in the following format: > $ 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 $

Print the answer.

### Sample Explanation 1 In this case, $ S= $ `RRD` and $ T= $ `UUU`, and the movements proceed as follows: - Initially, Takahashi is at cell $ (0,0) $ and Aoki is at cell $ (4,2) $ . - After the $ 1 $ st move, Takahashi is at cell $ (0,1) $ and Aoki is at cell $ (3,2) $ . - After the $ 2 $ nd move, Takahashi is at cell $ (0,2) $ and Aoki is at cell $ (2,2) $ . - After the $ 3 $ rd move, Takahashi is at cell $ (1,2) $ and Aoki is at cell $ (1,2) $ . Thus, the number of times Takahashi and Aoki are at the same cell immediately after a move is $ 1 $ . ### Sample Explanation 2 From the $ 2000000000 $ -th move to the $ 3000000000 $ -th move, Takahashi and Aoki are at the same cell immediately after a move for $ 1000000001 $ times. ### 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 $ - Each of $ S'_i $ and $ T'_i $ is one of `U`, `D`, `L`, `R`. - $ 1 \leq A_i,B_i \leq 10^9 $ - $ A_1+\dots+A_M=B_1+\dots+B_L=N $ - All given values are integers.