Background

Translated from NOI SG 2024 Prelim D.Amusement Park.

Problem Description

There is an amusement park that provides a sightseeing cart service at the entrance. Obviously, each cart can carry only a limited number of people, so when a group arrives at the entrance and finds that there are not enough seats, they need to decide whether they are willing to split up. Some groups are willing, and some are not.

To solve this complicated problem, the park manager, Snail Stuart, wants you to help write a program that supports the following three operations:

• join: A new group enters the queue. We use two integers $s, w$ to describe this operation: $s$ is the total number of people in the group; if $w = 1$, then this group is willing to split up when boarding a cart; if $w = 0$, they are not willing to split up. Suppose this operation is the $i$-th join operation among all operations, then the group ID is $i$.

• leave: Given $i$, the group with ID $i$ leaves the queue.

• board: Given $b$, meaning a new cart arrives with $b$ seats. Starting from the front of the queue, when reaching a group, if the cart can carry all people in the group, then everyone boards; otherwise, if the group is willing to split up, then some people board; otherwise, the group stays in its original position, and the same process is repeated for the next group, until the cart is full, or no one is willing to board.

Input Format

The first line contains an integer $q$.

The next $q$ lines each describe one operation, in one of the following three forms:

• 1 s w: describes a join operation.

• 2 i: describes a leave operation.

• 3 b: describes a board operation.

Output Format

For join and leave operations, you do not need to output anything.

For each board operation, suppose there are $k$ groups with at least one person boarding the cart. You need to output $k + 1$ lines:

• The first line contains an integer $k$.

• The next $k$ lines each contain two integers: the first is the group ID, and the second is the number of people from that group who board the cart. Note: group IDs should be output in increasing order. (If $k = 0$, ignore this part.)

7
1 2 0
1 6 0
1 6 1
3 5
2 2
1 3 0
3 123456789012

2
1 2
3 3
2
3 3
4 3

5
1 1 0
1 1 0
1 1 0
3 2
1 1 0

2
1 1
2 1

4
1 19 1
3 10
3 10
3 10

1
1 10
1
1 9
0

Hint

Constraints

For $100\%$ of the testdata:

• $1 \le q \le 200000$.

• For all join operations, $1 \le s \le 200000, 0 \le w \le 1$.

• For all leave operations, it is guaranteed that every $i$ is in the queue at the time of the operation.

• For all board operations, $1 \le b \le 10^{12}$.

• There is at least one board operation.

Translated by ChatGPT 5