AT_abc413_c [ABC413C] Large Queue

There is an empty integer sequence $ A=() $ . You are given $ Q $ queries, and you need to process them in the given order. There are two types of queries: - Type $ 1 $ : Given in the format `1 c x`. Add $ c $ copies of $ x $ to the end of $ A $ . - Type $ 2 $ : Given in the format `2 k`. Remove the first $ k $ elements from $ A $ and output the sum of the removed $ k $ integers. It is guaranteed that $ k $ is at most the length of $ A $ at that time.

The input is given from standard input in the following format: > $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ where $ \text{query}_i $ represents the $ i $ -th query and is in one of the following formats: > $ 1 $ $ c $ $ x $ > $ 2 $ $ k $

Let $ q $ be the number of type $ 2 $ queries. Output $ q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th type $ 2 $ query.

### Sample Explanation 1 - $ 1 $ st query: Add $ 2 $ copies of $ 3 $ to the end of $ A $ . Then, $ A=(3,3) $ . - $ 2 $ nd query: Add $ 4 $ copies of $ 5 $ to the end of $ A $ . Then, $ A=(3,3,5,5,5,5) $ . - $ 3 $ rd query: Remove the first $ 3 $ elements from $ A $ . Then, the sum of the removed $ 3 $ integers is $ 3+3+5=11 $ , so output $ 11 $ . After removal, $ A=(5,5,5) $ . - $ 4 $ th query: Add $ 6 $ copies of $ 2 $ to the end of $ A $ . Then, $ A=(5,5,5,2,2,2,2,2,2) $ . - $ 5 $ th query: Remove the first $ 5 $ elements from $ A $ . Then, the sum of the removed $ 5 $ integers is $ 5+5+5+2+2=19 $ , so output $ 19 $ . After removal, $ A=(2,2,2,2) $ . ### Constraints - $ 1 \leq Q \leq 2 \times 10^{5} $ - In type $ 1 $ queries, $ 1 \leq c \leq 10^{9} $ . - In type $ 1 $ queries, $ 1 \leq x \leq 10^{9} $ . - In type $ 2 $ queries, letting $ n $ be the length of $ A $ at that time, $ 1 \leq k \leq \min(10^{9},n) $ . - All input values are integers.