The Extended Album


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

After escaping her FLOP era, PKL launched the GIỮA MỘT VẠN TOUR (Among Ten Thousand Tour). After 4 shows, she released the extended album GIỮA MỘT VẠN NGƯỜI (MỞ RỘNG) (Among Ten Thousand People (Extended)). However, it seems her fans and antifans weren't very happy with the number of songs added. So she decided to please both fans and antifans by composing \(N\) new songs. She numbered the songs from 1 to \(N\).

To make the album feel random, she shuffled the songs all over the place. As a result, the album ended up with the song order \(p_1, p_2, ..., p_N\). However, she found this order really fun, so she decided to experiment with other versions too. She wants to perform \(Q\) operations of the following types:

  • P x: Find which song comes right before the song with ID \(x\).
  • N x: Find which song comes right after the song with ID \(x\).
  • S x y: Swap the positions of the songs with IDs \(x\) and \(y\).
  • Z K: Press Ctrl-Z \(K\) times, i.e., undo the \(K\) most recent swap operations one by one.

For each operation of type P and N, help PKL answer her question.

Note: the Ctrl-Z operation works just like the Undo feature in applications.

Input

  • The first line contains 2 positive integers \(N, Q \ (1\le N, Q \le 10^5)\);
  • The second line contains \(N\) positive integers \(p_i \ (p_i \) is a permutation of \(1, 2, 3, ..., N)\);
  • Each of the next \(Q\) lines describes one of the 4 queries above \((1\le x,y \le N)\).

It is guaranteed that each Ctrl-Z operation never undoes more changes than currently exist at that moment (counting only changes that have not already been undone by previous Ctrl-Z operations).

Output

  • For each operation of type \(P\) or \(N\), print the answer on its own line. The song before the first song of the album is song \(0\), and the song after the last song of the album is considered song \(N+1\).

Scoring

  • Subtask 1 (50%): \(N,Q \le 10^3\).
  • Subtask 2 (10%): There are no \(Z\) operations.
  • Subtask 3 (40%): No additional constraints.

Examples

Example 1

input

5 8
1 2 3 4 5
P 3
S 3 5
P 3
S 2 4
P 3
Z 1
S 5 4
P 3

output

2
4
2
5

Explanation

  • The initial album is: [1,2,3,4,5].
  • The song right before song 3 is song 2.
  • Swap songs 3 and 5. The album becomes: [1,2,5,4,3].
  • The song right before song 3 is song 4.
  • Swap songs 2 and 4. The album becomes: [1,4,5,2,3].
  • The song right before song 3 is song 2.
  • Ctrl-Z once, the album becomes: [1,2,5,4,3].
  • Swap songs 5 and 4. The album becomes: [1,2,4,5,3].
  • The song right before song 3 is song 5.

Comments

There are no comments at the moment.