AT_past18_o 蟻の移動

$ N $ ants numbered $ 1 $ through $ N $ are on a number line, whose positive direction points to the right. In the **initial state**, ant $ i $ is at the initial coordinate $ X_i $ and facing the direction described by a character $ D_i $ . Specifically, $ D_i= $ `R` means it is facing right, and $ D_i= $ `L` means it is facing left. Here, it is guaranteed that $ X_1,X_2,\dots $ , and $ X_N $ are pairwise distinct even numbers. Once Snuke snaps his fingers, the ants starts moving according to the following rules. - Each ant moves at a speed of $ 1 $ per second in the direction it is facing. - Whenever two ants reach the same coordinate, they flip their directions and continue moving. This event is called a **collision** of ants. One can prove that three or more ants never reach the same coordinate at the same time. You are given a total of $ Q $ queries, each of one of the following types. Process them in order. - `1 x d` : Add an ant with initial coordinate $ x $ and initial direction $ d $ to the initial state. Here, it is guaranteed that $ x $ is even and does not coincide with the initial coordinate of any ant. - `2 l r` : If Snuke snaps his fingers at time $ 0 $ , let $ t_1,t_2,\dots $ be the times at which ant $ 1 $ collides with the other ants, listed in chronological order. Evaluate $ t_{l}+t_{l+1}+\dots +t_{r} $ and print it. It is guaranteed that $ l \leq r $ and ant $ 1 $ collides with the other ants at least $ r $ times. Note that queries of the second type are independent. In other words, processing a query of the second type does not actually modify the initial states of the ants.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ X_1 $ $ D_1 $ $ X_2 $ $ D_2 $ $ \vdots $ $ X_N $ $ D_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_i $ denotes the $ i $ -th query and is of one of the following formats: > $ 1 $ $ x $ $ d $ > $ 2 $ $ l $ $ r $

If there are $ T $ queries of the second kind, print $ T $ lines. In the $ i $ -th $ (1\leq i \leq T) $ line, print the answer to the $ i $ -th such query.

### Sample Explanation 1 If Snuke snaps his fingers in the initial state before the queries are processed, the ants move as follows. - At time $ 0 $ , all the ants start moving. The two ants are facing right and left. - At time $ 4\ (:=t_1) $ , ants $ 1 $ and $ 2 $ collide at coordinate $ 6 $ . Now the two ants are facing left and right. Thus, the answer to the $ 1 $ -st query is $ t_1=4 $ . If Snuke snaps his fingers in the initial state where the first three queries are processed, the ants move as follows. Here we call the ants added by the $ 2 $ -nd and $ 3 $ -rd query ant $ 3 $ and ant $ 4 $ , respectively. - At time $ 0 $ , all the ants start moving. The four ants are facing right, left, left, and right. - At time $ 1 $ , ants $ 3 $ and $ 4 $ collides at coordinate $ -1 $ . Now, the four ants are facing right, left, right, and left. - At time $ 4\ (:=t_1) $ , ants $ 1 $ and $ 2 $ collides at coordinate $ 6 $ . Now, the four ants are facing left, right, right, and left. - At time $ 6\ (:=t_2) $ , ants $ 1 $ and $ 3 $ collides at coordinate $ 4 $ . Now, the four ants are facing right, right, left, and left. Therefore, the answer to the $ 4 $ -th query is $ t_1+t_2=10 $ , and the answer to the $ 5 $ -th query is $ t_2=6 $ . ### Constraints - $ N $ and $ Q $ are integers. - $ 1\leq N,Q \leq 10^5 $ - $ X_i $ is even. - $ |X_i| \leq 10^9 $ - $ X_i \neq X_j\ (i \neq j) $ - $ D_i $ is `R` or `L`. - For each query of the first kind, - $ x $ is even. - $ |x| \leq 10^9 $ - At the point the query is processed, there is no ant with initial coordinate $ x $ . - $ d $ is `R` or `L`. - For each query of the second kind, - $ l $ and $ r $ are integers. - $ 1 \leq l \leq r \leq M $ , where $ M $ is the number of times ant $ 1 $ collides with the other ants, starting from the initial state at the point the query is processed.