Sorting queries - MarisaOJ: Marisa Online Judge

Sorting queries

Time limit: 3000 ms
Memory limit: 256 MB
Given an array of integers $a$ consisting of $n$ integers. You are given $q$ queries of the following types: - `0 l r`: Sort the integers $a_l, a_{l+1}, \dots, a_r$ in ascending order. - `1 l r`: Sort the integers $a_l, a_{l+1}, \dots, a_r$ in descending order. After $q$ queries, determine the value at position $m$ in the array $a$. ### Input - The first line contains two integers $n$ and $q$. - The next $q$ lines each contain a query in the format described above. - The last line contains an integer $m$. ### Output - Print a single integer, the value at position $m$ after $q$ queries. ### Constraints - $1 \leq n, q \leq 10^5$. - $1 \leq m, a_i \leq n$. ### Example Input: ``` 5 3 1 5 4 2 3 0 2 4 1 3 5 0 1 4 2 ``` Output: ``` 2 ```