구간의 순서 통계

길이가 $N$인 정수 수열 $A_1,A_2,\cdots,A_N$과 $Q$개의 쿼리가 주어진다. 수열은 변하지 않는다. 각 쿼리를 처리해 보자.

• $0\ l\ r\ k$: $A_l,\cdots,A_r$에서 $k$번째로 작은 값을 구한다.
• $1\ l\ r\ x$: $A_l,\cdots,A_r$에서 $x$보다 작은 원소의 개수를 구한다.
• $2\ l\ r\ x\ y$: $A_l,\cdots,A_r$에서 $x$ 이상 $y$ 이하인 원소의 개수를 구한다.
• $3\ l\ r\ x$: $A_l,\cdots,A_r$에서 $x$보다 작은 원소 중 최댓값을 구한다.
• $4\ l\ r\ x$: $A_l,\cdots,A_r$에서 $x$보다 큰 원소 중 최솟값을 구한다.

같은 값도 각각 센다. $2$번 쿼리에서 $x>y$이면 답은 $0$이다.

첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$

두 번째 줄에 수열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-2^{31} \le A_i < 2^{31})$

세 번째 줄부터 $Q$개의 줄에 걸쳐 본문에서 설명한 형식의 쿼리가 주어진다. 각 쿼리의 정수는 공백으로 구분되어 주어진다. $(1 \le l \le r \le N; 1 \le k \le r-l+1; -10^{18} \le x, y \le 10^{18})$

각 쿼리의 답을 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다. $3$번 또는 $4$번 쿼리에서 조건을 만족하는 값이 없으면 NONE을 출력한다.