점프하는 메뚜기

하즈민의 집 앞 정원에는 왼쪽에서 오른쪽으로 일렬로 늘어선 $N$그루의 식물이 있다. 그녀는 식물의 높이를 아주 정밀하게 잰다. 식물마다 높이가 다르다고 믿기 때문이다.

어느 날 정원에서 메뚜기 한 마리를 발견했다. 메뚜기는 한 번 뛸 때마다 바라보는 방향에서 현재 식물보다 키가 큰 첫 번째 식물로 이동한다. 착지하기 전에 뒤로 공중제비를 돌아 방향을 바꾼다. 뛰기 전에 왼쪽을 보고 있었다면 착지 후에는 오른쪽을 보고, 그 반대도 마찬가지다. 바라보는 방향에 더 키가 큰 식물이 없을 때까지 계속 뛴다.

하즈민은 메뚜기를 볼 때마다 그 식물과 바라보던 방향을 기록했다. 식물이 자란 기록도 남겼다. 각 목격에 대해 메뚜기가 뛰기를 멈춘 식물의 번호를 구하라.

첫 줄에 두 정수 $N$과 $M$ ($1 \le N, M \le 2 \times 10^5$)이 주어진다. $N$은 식물의 수이고 $M$은 기록의 수이다. 식물은 왼쪽부터 $1$번에서 $N$번까지 번호가 매겨져 있다. 둘째 줄에는 서로 다른 정수 $H_1, H_2, \ldots, H_N$ ($0 \le H_i \le 10^9$)이 주어진다. $H_i$는 식물 $i$의 처음 높이이다.

이어지는 $M$개의 줄은 입력 순서대로 기록 하나씩이다.

성장 기록은 U I H 형식이다 ($1 \le I \le N$, $H \le 10^9$). 식물 $I$의 높이를 $H$로 바꾼다. 새 높이는 식물 $I$의 이전 높이보다 크고, 다른 어떤 식물의 현재 높이와도 같지 않다.

목격 기록은 L J 또는 R J 형식이다 ($1 \le J \le N$). 메뚜기가 식물 $J$에서 뛰기 시작한다는 뜻이다. L이면 왼쪽을, R이면 오른쪽을 보고 있다. 목격 기록은 적어도 하나 있다.

목격 기록마다 메뚜기가 뛰기를 멈춘 식물의 번호를 한 줄에 하나씩 출력한다. 답은 입력에 나온 목격 순서대로 출력한다.