D - Cylinder Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

空の筒があります。Q 個のクエリが与えられるので順に処理してください。
クエリは次の 2 種類のいずれかです。

  • 1 x c：数 x が書かれたボールを筒の右側から c 個入れる
  • 2 c：筒の左側からボールを c 個取り出し、取り出したボールに書かれている数の合計を出力する

なお、筒の中でボールの順序が入れ替わることはないものとします。

制約

  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq x \leq 10^9
  • 1 \leq c \leq 10^9
  • 2 c のクエリが与えられるとき、筒の中には c 個以上のボールがある
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

Q
{\rm query}_1
\vdots
{\rm query}_Q

i 番目のクエリを表す {\rm query}_i は以下の 2 種類のいずれかである。

1 x c

2 c

出力

2 c のクエリに対する答えを順に改行区切りで出力せよ。

入力例 1

4
1 2 3
2 2
1 3 4
2 3

出力例 1

4
8
  • 1 番目のクエリでは、2 が書かれたボールを筒の右側から 3 個入れます。
    筒の中のボールに書かれた数は左から順に (2,2,2) となります。
  • 2 番目のクエリでは、筒の左側からボールを 2 個取り出します。
    取り出されたボールに書かれている数はそれぞれ 2,2 であり、合計は 4 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (2) となります。
  • 3 番目のクエリでは、3 が書かれたボールを筒の右側から 4 個入れます。
    筒の中のボールに書かれた数は左から順に (2,3,3,3,3) となります。
  • 4 番目のクエリでは、筒の左側からボールを 3 個取り出します。
    取り出されたボールに書かれている数はそれぞれ 2,3,3 であり、合計は 8 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (3,3) となります。

入力例 2

2
1 1000000000 1000000000
2 1000000000

出力例 2

1000000000000000000

入力例 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

出力例 3



出力するものがないこともあります。






Score : 400 points







Problem Statement
We have a horizontal cylinder.  Given Q queries, process them in the given order.

Each query is of one of the following two types.


    

  • 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
    • 

  • 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.
    • 



We assume that the balls do never change their order in the cylinder.











Constraints
    

  • 1 \leq Q \leq 2\times 10^5
    • 

  • 0 \leq x \leq 10^9
    • 

  • 1 \leq c \leq 10^9
    • 

  • Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


Q
{\rm query}_1
\vdots
{\rm query}_Q



The i-th query {\rm query}_i is in one of the following two formats.


1 x c



2 c












Output
Print the response to the queries of type 2 c in the given order, with newlines in between.















Sample Input 1
4
1 2 3
2 2
1 3 4
2 3












Sample Output 1
4
8



    

  • For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
    
  The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
    • 

  • For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
    
  The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed.
  The cylinder has now a ball with a number (2) written on it, from left to right.
    • 

  • For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
    
  The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
    • 

  • For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
    
  The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed.
  The cylinder has now balls with numbers (3,3) written on them, from left to right.
    • 














Sample Input 2
2
1 1000000000 1000000000
2 1000000000












Sample Output 2
1000000000000000000














Sample Input 3
5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1












Sample Output 3


There may be nothing you should print.