Thank you for applying to AUCPL.inc. While your skills were catastrophically unsuited for problemsetting, they were an exceptional match for our office janitorial department. Congratulations!

You are in charge of cleaning the main hall of our office. The hall is composed of a line of ~n~ zones, numbered from ~1~ to ~n~. All zones are initially dirty, and you start your workday in zone ~i~.

We define the "closest dirty zone to the left" as the dirty zone with the largest index strictly less than your current position, and the "closest dirty zone to your right" likewise.

Your workday has ~t~ minutes, and every minute you are given a command:

• ~\text{C}~: Clean the zone you are currently standing in (no effect if it is already clean).

• ~\text{L}~: Move to the closest dirty zone to your left. If none exists, do not move.

• ~\text{R}~: Move to the closest dirty zone to your right. If none exists, do not move.

• ~\text{QL}~: Output the closest dirty zone to your left, or -1 if none exists.

• ~\text{QR}~: Output the closest dirty zone to your right, or -1 if none exists.

Input

The first line contains three integers ~n~, ~t~, and ~i~ ~(1 \le n, t \le 5 \times 10^5, 1 \le i \le n)~, representing the number of zones in your hall, the number of minutes in your workday, and the zone you start in.

The next ~t~ lines each contain a command, which is one of the following:

• C: Clean your current zone.
• L: Move to the closest dirty zone to your left.
• R: Move to the closest dirty zone to your right.
• QL: Output the index of the closest dirty zone to your left (or -1 if none exists).
• QR: Output the index of the closest dirty zone to your right (or -1 if none exists).

There will always be at least one QL or QR command in the input.

Output

For each QL or QR command, output the requested zone index.

Example

Input 1

10 11 5
C
R
QL
QR
C
L
QR
L
QL
QR
C

Output 1

4
7
7
2
4

You start in zone ~5~ and process the following commands:

• Clean your current zone, ~5~.
• Move to the closest dirty zone to your right, ~6~.
• Report the closest dirty zone to your left, ~4~.
• Report the closest dirty zone to your right, ~7~.
• Clean your current zone, ~6~.
• Move to the closest dirty zone to your left, ~4~.
• Report the closest dirty zone to your right, ~7~.
• Move to the closest dirty zone to your left, ~3~.
• Report the closest dirty zone to your left, ~2~.
• Report the closest dirty zone to your right, ~4~.

This process is illustrated below:

Input 2

3 14 1
QL
QR
R
C
L
C
QL
QR
L
R
C
C
QL
QR

Output 2

-1
2
-1
3
-1
-1

You start in zone ~1~ and process the following commands:

• Report the closest dirty zone to your left, which does not exist.
• Report the closest dirty zone to your right, ~2~.
• Move to the closest dirty zone to your right, ~2~.
• Clean your current zone, ~2~.
• Move to the closest dirty zone to your left, ~1~.
• Clean your current zone, ~1~.
• Report the closest dirty zone to your left, which does not exist.
• Report the closest dirty zone to your right, ~3~.
• Move to the closest dirty zone to your left, but this does not exist, so you do not move.
• Move to the closest dirty zone to your right, ~3~.
• Clean your current zone, ~3~.
• Clean your current zone, ~3~. It is already clean, so nothing happens.
• Report the closest dirty zone to your left, which does not exist.
• Report the closest dirty zone to your right, which does not exist.

This process is illustrated below: