33585번 - 비트 뒤집기와 쿼리

문제

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ドル$번 쿼리는 적어도 한 번 이상 주어진다.

제한

힌트