레이팅 미적용"Welcome to the SHOW! You are about to witness a spectacular magic performance
by Magic Ivor." This is how Ivor imagines the announcement of his first magic
performance, but first he needs to prepare.
Ivor will request \(n\) volunteers for his tricks and arrange them on the stage. At the
left end of the line is person 1, to the right of person 1 is person 2, to the right
of person 2 is person 3, and so on.
The tricks that Ivor learns during his preparation can be described in the form
\(l\) \(r\) len. In such a trick, Ivor learns to swap the positions of people, specifically
to swap two disjoint intervals of equal length: the interval [l, \(l + len - 1\)] and the
interval [r, \(r + len - 1\)]. Two intervals are disjoint if they do not have any common volunteers.
Often, Ivor wonders, for a given person \(x\), what are the minimum and maximum positions that this person
can occupy if he can use his learned tricks in any order and any ammount of times. He also does not have
to use all the tricks he has learned so far.
There are \(Q\) events describing Ivor’s preparation, and we distinguish between two types of events.
• An event of the form 1 \(x\) asks you to answer Ivor’s question considering the tricks he has learned so
far. He may use the tricks in any order and does not have to use all of them.
• An event of the form 2 \(l\) \(r\) len indicates a trick that Ivor has just learned.
Your task is to help Ivor and answer all events of the first type.
The first line contains the natural numbers \(n\) and \(q\) (\(1 \le n\), \(q \le 2 \cdot 10^{5}\)), as described in the problem text.
Each of the following \(Q\) lines describes one event of one of the following forms:
• 1 \(x\) – Ivor wants to know the minimum and maximum positions that person \(x\) can occupy (\(1 \le x \le n\)).
• 2 \(l\) \(r\) len – Ivor has learned to swap the intervals [l, \(l + len - 1\)] and [r, \(r + len - 1\)]. It holds that
\(1 \le len \le n\), \(l + len - 1 < r\), and \(r + len - 1 \le n\).
After each event of type 1, print two numbers: the minimum and maximum positions that the given
person can occupy, separated by a space.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 9점 | N, \(Q \le 5\) |
2 | 14점 | N, \(Q \le 15\) |
3 | 22점 | N, \(Q \le 1000\) |
4 | 11점 | \(N \le 4000\) |
5 | 17점 | \(N \le 10000\) |
6 | 37점 | No additional constraints. Sample Inp\(ut / Ou\)tput input 5 3 2 3 4 1 1 5 1 3 output 5 5 3 4 input 9 2 2 1 7 2 1 2 output 2 8 Explanation of the second sample: Ivor has learned to swap the intervals [1, 2] and [7, 8]. The minimum position that person 2 can occupy is 2. The maximum position that person 2 can occupy is 8 because Ivor can swap the intervals [1, 2] and [7, 8]. |
5 3
2 3 4 1
1 5
1 3
5 5
3 4
9 2
2 1 7 2
1 2
2 8