J. The Lake of Ichkeul
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Miss Amina is organizing an excursion for primary school students to The Lake of Ichkeul, well-known locally as Bouhayret Echkel. She's managing the payment queue where students come to settle their trip fees.

The payment system works as follows:

  • Each student in the queue has a payment balance (in dinars).
  • Positive values represent payments made by the student.
  • Negative values represent refunds, scholarships, or discounts applied to the student.
The queue is quite dynamic! Students can join from either end:
  • Front: Priority students (e.g., class representatives, students with urgent matters).
  • Back: Regular arrivals.

Students may also leave the queue in groups from either end (called away for verification, already processed, etc.).

Miss Amina frequently needs to calculate the net payment for specific sections of the queue. This is crucial for:

  • Verifying which bus groups have fully paid their share.
  • Checking if a specific segment has a deficit that needs attention.

Your task is to help Miss Amina by simulating the queue operations and answering her payment queries.

Input

The first line contains a single integer $$$Q (2 \leq Q \leq 10^6)$$$ — the number of operations.

Each of the next $$$Q$$$ lines contains one of the following operations:

  • $$$1 \ x$$$ : Add a student with payment balance $$$x$$$ dinars to the back of the queue $$$(-10^9 \leq x \leq 10^9)$$$.
  • $$$2 \ x$$$ : Add a student with payment balance $$$x$$$ dinars to the front of the queue $$$(-10^9 \leq x \leq 10^9)$$$.
  • $$$3 \ k$$$ : Remove $$$k$$$ students from the $$$back$$$ of the queue $$$(1 \leq k \leq$$$ current queue size$$$)$$$.
  • $$$4 \ k$$$ : Remove $$$k$$$ students from the $$$front$$$ of the queue $$$(1 \leq k \leq$$$ current queue size$$$)$$$.
  • $$$5 \ l \ r$$$ : Calculate the net payment (sum of balances) from position $$$l$$$ to position $$$r$$$ (inclusive, $$$0$$$-indexed from the front) where $$$0 \leq l \leq r \lt $$$ current queue size.

It is guaranteed that:

  • Operations $$$3$$$ and $$$4$$$ will never remove more students than currently in the queue.
  • Operation $$$5$$$ will always query valid positions within the current queue.
  • At least one operation of type $$$5$$$ will be present.
Output

For each operation of type $$$5$$$, output a single integer — the net payment (sum of payment balances) in dinars for the specified range.

Example
Input
7
2 -50
1 100
1 -200
2 150
5 1 2
3 2
5 0 1
Output
50
100
Note

The queue is $$$0$$$-indexed from the front. So if the queue is $$$[a, b, c, d]$$$, then:

  • Position $$$0$$$ is $$$a$$$ (front).
  • Position $$$1$$$ is $$$b$$$.
  • Position $$$2$$$ is $$$c$$$.
  • Position $$$3$$$ is $$$d$$$ (back).