시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB96231418.667%

문제

$0$ 이상 $2^{20}$ 미만 정수 $N$개가 주어진다. 다음 두 종류의 쿼리 $Q$개를 수행하는 프로그램을 작성하시오.

  • 1 l r k: $N$개의 정수 중 $l$ 이상 $r$ 이하인 모든 정수의 $k$번째 비트를 뒤집는다. $k$번째 비트를 뒤집는 것은 정수를 이진수로 나타냈을 때 $k$번째 비트를 $0$이면 $1$로, $1$이면 $0$으로 바꾸는 것이다. 가장 작은 자릿수의 비트가 $0$번째 비트이다. $(0 \leq l \leq r < 2^{20}; 0 \leq k \leq 19)$
  • 2 k: $N$개의 정수에서 중복을 포함하여 $k$번째로 작은 수를 구한다. 가장 작은 수가 $1$번째로 작은 수이다. $(1 \leq k \leq N)$

입력

첫 번째 줄에 정수 $N$, $Q$가 공백으로 구분하여 주어진다. $(1 \leq N, Q \leq 10^6)$

두 번째 줄에 $N$개의 $0$ 이상 $2^{20}$ 미만 정수가 공백으로 구분하여 주어진다.

세 번째 줄부터 $Q$개의 쿼리가 한 줄에 하나씩 주어진다.

출력

첫 번째 줄부터 $2$번 쿼리가 주어질 때마다 정답을 한 줄에 하나씩 순서대로 출력한다. $2$번 쿼리는 적어도 한 번 이상 주어진다.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

7 10
13 11 13 5 9 11 0
1 12 14 3
2 3
2 5
1 10 12 1
2 4
2 6
2 4
1 5 7 3
1 3 12 1
2 3

예제 출력 2

5
9
5
9
5
11