CARDFLIP - Dolan and Nephews

Dolan has a stack of card. Each card is numbered from 1 to n from top to bottom. His nephews want to play with the cards. Each nephew can only do one kind of operation.

  • Nephew number 1 will reverse the order of the card from i-th to j-th position.
  • Nephew number 2 will ask uncle Dolan what is the card number on i-th position.
  • Nephew number 3 will ask uncle Dolan in what position is the card number i.

Since Dolan is a good uncle, he will have to answer all questions correctly. Please help Dolan.

Input

First line on input is n and q, the number of cards (n ≤ 100000) and number of operations by the nephews (q ≤ 100000). The next q lines will contain the operation by the nephews.

For each operation, the first number will be the nephew number. The second (and possibly third) number is i (and j) from the description above (1 ≤ i ≤ j ≤ n).

Output

For each question asked by the nephews (operation 2 and 3), output a single line containing the answer.

Example

Input:
10 5
1 2 6
2 5
1 4 9
3 4
2 4

Output:
3
9
9

Input file is huge, use faster I/O (scanf for C)


Added by:Andy
Date:2015-04-15
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2020-06-19 09:15:12
yOU can make use of a slight modifications of decart trees !!!!
2015-04-25 16:42:34 rafael859
@Andy
Well, check out my submissions.
When I check whether the value on the third operation is greater than N and in that case output "N", I get WA.
When I erase just that line I get a SegFault.

Edit: Sorry, my mistake

Last edit: 2015-04-25 17:03:38
2015-04-25 04:35:13 Andy
@rafael859
no you dont

Last edit: 2015-04-25 04:37:23
2015-04-24 20:56:42 rafael859
I have detected that (at least on the 3rd type of operation) there are numbers that are either less than one or larger than N.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.