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)
hide comments
abhineelnandi:
2020-06-19 09:15:12
yOU can make use of a slight modifications of decart trees !!!! |
|
rafael859:
2015-04-25 16:42:34
@Andy
|
|
Andy:
2015-04-25 04:35:13
@rafael859
|
|
rafael859:
2015-04-24 20:56:42
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. |
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 |