题目描述

$1,2,\ldots,N$ を並び替えた長さ $N$ の順列 $P=(P_1,P_2,\ldots,P_N)$ と整数 $X$ が与えられます。

また、$Q$ 個のクエリが与えられます。 $i$ 番目のクエリは $3$ つの数の組 $(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}$ を降順に並び替える。

クエリを $1$ 番目から順に最後まで処理したとき、最終的な順列において $P_i=X$ となる $i$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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 \sim N$ 的排列 $P = (P_1,P_2,\ldots,P_N)$ 和一个正整数 $X$。

接下来会进行 $Q$ 次操作，每次操作给出三个正整数 $(C_i,L_i,R_i)$：

• 若 $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}$ 按降序排序。

请输出最后数 $X$ 所在的位置，即输出满足 $P_i = X$ 的正整数 $i$。

输入

输入第一行，共三个正整数 $N,Q,X$。

接下来 $N$ 行，每行三个正整数 $C_i,L_i,R_i$，表示一次操作。

输出

一行一个正整数表示答案。

数据范围&提示

$1 \le N, Q \le 2 \times 10^5,1 \le X \le N\\[1.5ex] 1 \le C_i \le 2,1 \le L_i \le R_i \le N$。

保证输入全部是正整数。

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

3

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

7

提示

制約

• $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$
• 入力は全て整数である。

Sample Explanation 1

最初、順列は $P=[1,4,5,2,3]$ です。 これはクエリによって次のように変化します。 - $1$ つめのクエリでは $3$ 番目から $5$ 番目の要素を昇順にソートします。順列は $P=[1,4,2,3,5]$ となります。 - $2$ つめのクエリでは $1$ 番目から $3$ 番目の要素を降順にソートします。順列は $P=[4,2,1,3,5]$ となります。 最終的な順列において $P_3=1$ であるので、$3$ を出力します。

Sample Explanation 2

最終的な順列は $P=[1,2,6,5,7,4,3]$ となります。