Background

Please note that this problem has an unusual memory limit.

Problem Description

Consider a permutation $p_1 \sim p_N$ of $1 \sim N$. Define an operation $(l, r, \mathrm{len})$ as follows:

• For $i = 0, \ldots, \mathrm{len} - 1$, swap $p_{l+i}$ and $p_{r+i}$.

It is guaranteed that $[l, l+\mathrm{len}-1]$ and $[r, r+\mathrm{len}-1]$ do not overlap.

There is an operation pool, initially empty.

There are $Q$ events:

• $\texttt{1}$ $x$: Starting from the permutation $[1,2,\ldots,N]$, perform any number of operations from the operation pool (possibly zero times), and find the minimum and maximum possible final index of $x$ after all operations are done.
  • An operation can be used multiple times.
  • The order of operations does not matter.
  • You do not have to use all operations in the pool.
• $\texttt{2}$ $l$ $r$ $\mathrm{len}$: Add an operation $(l, r, \mathrm{len})$ to the operation pool.

Answer each query.

Input Format

The first line contains two positive integers $N, Q$ ($1 \le N, Q \le 2 \times 10^5$).

The next $Q$ lines each contain two (or four) positive integers, in the form $\texttt{1}$ $x$ or $\texttt{2}$ $l$ $r$ $\mathrm{len}$, describing an event. Where:

• $1 \le x \le N$;
• $1 \le \mathrm{len} \le N$, $l+\mathrm{len}-1 \lt r$, $r+\mathrm{len}-1 \le N$.

Output Format

For each event $\texttt{1}$, output one line with two positive integers, representing the minimum and maximum possible final index, respectively.

5 3
2 3 4 1
1 5
1 3

5 5
3 4

9 2
2 1 7 2
1 2

2 8

Hint

Sample Explanation

Explanation for sample 2: doing no operations gives the minimum value; performing the operation once gives the maximum value.

Subtasks

Translated by ChatGPT 5