{"raw_statement":[{"iden":"problem statement","content":"Given is a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $1,2,\\ldots,N$, and an integer $X$.\nAdditionally, $Q$ queries are given. The $i$\\-th query is represented as a triple of numbers $(C_i,L_i,R_i)$. Each query does the following operation on the permutation $P$.\n\n*   If $C_i=1$: sort $P_{L_i},P_{L_i+1},\\ldots,P_{R_i}$ in ascending order.\n*   If $C_i=2$: sort $P_{L_i},P_{L_i+1},\\ldots,P_{R_i}$ in descending order.\n\nIn the final permutation $P$ after executing all queries in the given order, find $i$ such that $P_i=X$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq Q \\leq 2\\times 10^5$\n*   $1 \\leq X \\leq N$\n*   $(P_1,P_2,\\ldots,P_N)$ is a permutation of $(1,2,\\ldots,N)$.\n*   $1 \\leq C_i \\leq 2$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$ $X$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$C_1$ $L_1$ $R_1$\n$C_2$ $L_2$ $R_2$\n$\\vdots$\n$C_Q$ $L_Q$ $R_Q$"},{"iden":"sample input 1","content":"5 2 1\n1 4 5 2 3\n1 3 5\n2 1 3"},{"iden":"sample output 1","content":"3\n\nInitially, the permutation is $P=[1,4,5,2,3]$. The queries change it as follows.\n\n*   $1$\\-st query sorts the $3$\\-rd through $5$\\-th elements in ascending order, making $P=[1,4,2,3,5]$.\n*   $2$\\-nd query sorts the $1$\\-st through $3$\\-rd elements in descending order, making $P=[4,2,1,3,5]$.\n\nIn the final permutation, we have $P_3=1$, so $3$ should be printed."},{"iden":"sample input 2","content":"7 3 3\n7 5 3 1 2 4 6\n1 1 7\n2 3 6\n2 5 7"},{"iden":"sample output 2","content":"7\n\nThe final permutation is $P=[1,2,6,5,7,4,3]$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}