Jazmín 在她家门前有一个花园，里面有 $N$ 株植物排成一排（从左到右）。她对自己的植物感到非常自豪，并且非常精确地测量它们的高度，因为她认为每株植物都是独特的，因此高度也应该各不相同。

一天，Jazmín 在花园里发现了一只蚱蜢。观察了一段时间后，她发现了一个非常奇特的行为。在每次跳跃中，蚱蜢会向它所朝向的方向移动，跳到该方向上第一株比它当前所在植物更高的植物上。此外，在落到新植物上之前，蚱蜢会做一次后空翻以改变其朝向。也就是说，如果跳跃前蚱蜢向左看，跳跃完成后它会向右看，反之亦然。蚱蜢会一直跳跃，直到在它所朝向的方向上没有比它当前所在植物更高的植物为止。

Jazmín 决定记录她看到蚱蜢的场景。每次看到它时，她都会写下蚱蜢所在的植物以及它所朝向的方向。她还像往常一样记录了植物的生长情况。现在 Jazmín 想知道，对于每次看到的蚱蜢，它最终会在哪株植物上停止跳跃。Jazmín 的笔记本现在坏了，所以她无法自己编写程序。你能帮帮她吗？

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 2 \times 10^5$），分别表示植物的数量和记录的数量。植物按从左到右的顺序用 $1$ 到 $N$ 的唯一整数标识。

第二行包含 $N$ 个互不相同的整数 $H_1, H_2, \dots, H_N$（$0 \le H_i \le 10^9$），其中 $H_i$ 是植物 $i$ 的初始高度。

接下来的 $M$ 行按时间顺序描述 Jazmín 的记录，每行一条记录：

• 如果记录表示植物生长，则该行包含大写字母 U，后跟两个整数 $I$（$1 \le I \le N$）和 $H$（$H \le 10^9$），表示植物 $I$ 的新高度为 $H$。新高度 $H$ 大于植物 $I$ 的旧高度，且与当前其他所有植物的高度都不同。
• 如果记录表示看到蚱蜢，则该行包含大写字母 L 或 R，后跟一个整数 $J$（$1 \le J \le N$），表示蚱蜢从植物 $J$ 开始跳跃。如果字母为 L，则蚱蜢开始时向左看；如果字母为 R，则开始时向右看。

保证输入中至少有一条记录是看到蚱蜢。

输出格式

对每次看到蚱蜢的记录输出一行。该行必须包含一个整数，表示蚱蜢停止跳跃时所在的植物编号。按时间顺序（即与输入相同的顺序）输出结果。

样例

输入样例 1

10 4
1 8 5 6 10 20 12 15 2 4
L 2
R 3
U 10 16
L 9

输出样例 1

2
5
6