题目描述

给定一个排列$P=(P_1, P_2, \ldots, P_N)$，其中$P_i$是$1,2,\ldots,N$的一个排列，以及一个整数$X$。

此外，给出了$Q$个查询。第$i$个查询表示为一个三元组$(C_i, L_i, R_i)$。每个查询对排列$P$执行以下操作：

• 如果$C_i=1$：按升序排序$P_{L_i}, P_{L_i+1}, \ldots, P_{R_i}$。
• 如果$C_i=2$：按降序排序$P_{L_i}, P_{L_i+1}, \ldots, P_{R_i}$。

在按给定顺序执行所有查询之后的最终排列$P$中，找到$i$，使得$P_i=X$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq X \leq N$
• $(P_1, P_2, \ldots, P_N)$是$(1,2,\ldots,N)$的一个排列。
• $1 \leq C_i \leq 2$
• $1 \leq L_i \leq R_i \leq N$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

N Q X
P_1 P_2 \ldots P_N
C_1 L_1 R_1
C_2 L_2 R_2
\vdots
C_Q L_Q R_Q

输出

输出答案。

示例输入1

5 2 1
1 4 5 2 3
1 3 5
2 1 3

示例输出1

3

初始排列为$P=[1,4,5,2,3]$。查询操作按以下方式更改该排列：

• 第一个查询将第3个到第5个元素按升序排序，得到$P=[1,4,2,3,5]$。
• 第二个查询将第1个到第3个元素按降序排序，得到$P=[4,2,1,3,5]$。

在最终排列中，我们有$P_3=1$，因此应该输出3。

示例输入2

7 3 3
7 5 3 1 2 4 6
1 1 7
2 3 6
2 5 7

示例输出2

7

最终排列为$P=[1,2,6,5,7,4,3]$。