C. Orders
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Turjo is managing the front counter at Akibdonalds. He has exactly $$$N$$$ pagers on his charging rack, numbered from $$$1$$$ to $$$N$$$.

A group of $$$k$$$ customers ($$$k \ge 1$$$) must receive $$$k$$$ consecutive pager IDs so that Turjo can carry them on one tray.

For every arriving group, Turjo chooses the smallest possible starting ID $$$l$$$ such that all pagers

$$$$$$ l,l+1,\dots,l+k-1 $$$$$$

are currently available.

When the customers' food is ready, they return their pagers to Turjo, making those pagers available again. The returned pagers always form a consecutive range.

You are given a sequence of $$$Q$$$ events in chronological order. Simulate Turjo's actions and determine which pager IDs each arriving group receives.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$.

The next $$$Q$$$ lines describe the following events.

  • The $$$(1+i)$$$-th line $$$(1 \leq i \leq Q)$$$ describes the $$$i$$$-th event.
    • 1 k — A group of $$$k$$$ customers arrives and places an order.

      It is guaranteed that $$$1 \leq k \leq N$$$.

    • 2 l r — Customers return pagers $$$l$$$ through $$$r$$$, making all of them available again.

      It is guaranteed that $$$1 \leq l \leq r \leq N$$$, and every pager in this range is currently being held by a customer.

All group arrivals can be fulfilled using the currently available pagers.

Output
  • If $$$k=1$$$, print one integer: the ID of the pager assigned to the customer.
  • If $$$k \gt 1$$$, print two integers $$$l$$$ and $$$r$$$: the first and last pager IDs assigned to the group.

Print the answers in chronological order.

Constraints

  • $$$1 \leq N \leq 200000$$$
  • $$$1 \leq Q \leq 200000$$$
  • $$$1 \leq k \leq N$$$
  • $$$1 \leq l \leq r \leq N$$$
Scoring

SubtaskPoints$$$\boldsymbol{N}$$$$$$\boldsymbol{Q}$$$$$$\boldsymbol{k}$$$Additional Constraints
00–––The examples
15$$$=1$$$$$$\le 200000$$$$$$=1$$$All events involve the only pager.
215$$$\le 5000$$$$$$\le 5000$$$$$$1 \le k \le N$$$No additional constraints.
315$$$\le 200000$$$$$$\le 200000$$$$$$=1$$$There are no Type 2 queries.
425$$$\le 200000$$$$$$\le 200000$$$$$$\le 3$$$No additional constraints.
540$$$\le 200000$$$$$$\le 200000$$$$$$1 \le k \le N$$$No additional constraints.

Example
Input
6 7
1 1
1 2
2 1 1
1 2
2 4 5
1 3
1 1
Output
1
2 3
4 5
4 6
1
Note

Examples

Example 1

Input


6 7
1 1
1 2
2 1 1
1 2
2 4 5
1 3
1 1

Output


1
2 3
4 5
4 6
1

Explanation

There are $$$6$$$ pagers, numbered from $$$1$$$ to $$$6$$$.

We process the events one by one:

  1. In the first event, one customer arrives and receives pager $$$1$$$.
  2. In the second event, a group of $$$2$$$ customers arrives.

    Pagers $$$2$$$ and $$$3$$$ are the smallest consecutive available pagers, so they receive $$$2,3$$$.

  3. In the third event, the customer using pager $$$1$$$ returns it.

    Pager $$$1$$$ becomes available again.

  4. In the fourth event, a group of $$$2$$$ customers arrives.

    Pagers $$$4$$$ and $$$5$$$ are the smallest consecutive available pagers, so they receive $$$4,5$$$.

  5. In the fifth event, pagers $$$4$$$ through $$$5$$$ are returned.

    Therefore, both pagers $$$4$$$ and $$$5$$$ become available again.

  6. In the sixth event, a group of $$$3$$$ customers arrives.

    At this moment, the available pagers are

    [ 1,4,5,6. ]

    The smallest three consecutive available pagers are $$$4,5,6$$$, so the group receives $$$4,5,6$$$.

    Therefore, we print: 


    4 6
  7. In the final event, one customer arrives.

    Pager $$$1$$$ is the smallest available pager, so the customer receives pager $$$1$$$.

Thus the complete output is:


1
2 3
4 5
4 6
1