아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

칠흑의 날개

시간 제한3초메모리 제한512 MB

요약
전체 XOR 갱신이 반복되는 배열에서 K번째로 작은 원소까지의 합을 구한다.
난이도

어려움10점 중 8점

유형
트라이, 비트 연산, 분할 정복, 구현
정답자
아직 제출이 없습니다

문제

"으아아아아악..."

스스로를 '칠흑의 날개'라고 부르는 에디는 악의 조직 다크 리유니온과 싸우고 있었다. 그러다 화들짝 놀라며 꿈에서 깼다.

'더 강해져야 해.' 에디는 속으로 되뇌었다.

에디는 강한 전사가 되려고 자주 수련한다. 수련하는 동안 에디는 마법석 NN개를 모았다. ii번 마법석에는 어둠의 힘이 AiA_i만큼 담겨 있다. 에디는 QQ번의 차례를 진행하고, 각 차례마다 다음 두 가지 중 하나를 고른다.

  • 1 X: 모든 마법석에 어둠의 힘 XX를 사용한다. 각 마법석의 어둠의 힘은 지금 값과 XX의 비트 단위 배타적 논리합으로 바뀐다. 즉 어둠의 힘이 AiA_i인 마법석은 Ai⊕XA_i \oplus X가 된다.
  • 2 K: 모든 마법석을 어둠의 힘이 작은 순서대로 정렬한 다음, 앞에서 KK개의 어둠의 힘을 더한다. 이 차례는 마법석의 어둠의 힘을 바꾸지 않는다.

에디의 계산이 맞는지 확인해 주자.

x⊕yx \oplus y는 두 정수 xx와 yy에 비트 단위 배타적 논리합을 적용한 결과이다. 이 연산은 현대 프로그래밍 언어라면 모두 제공한다. C++와 자바에서는 ^로 쓰고, 파스칼에서는 xor로 쓴다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스의 첫째 줄에는 마법석의 개수 NN과 명령의 개수 QQ가 주어진다.

둘째 줄에는 정수 NN개 A1,A2,…,ANA_1, A_2, \dots, A_N이 주어진다. AiA_i는 ii번 마법석에 담긴 어둠의 힘이다.

이어지는 QQ개의 줄에는 명령이 한 줄에 하나씩 1 X 또는 2 K 형태로 주어진다.

다음을 가정해도 된다.

  • T≤1000T \le 1000
  • 1≤N,Q≤1000001 \le N, Q \le 100000
  • 0≤Ai,X<2310 \le A_i, X < 2^{31}
  • 1≤K≤N1 \le K \le N
  • N+Q>200N + Q > 200인 테스트 케이스는 최대 5개다.

출력

2 K 명령마다 정렬한 뒤 앞에서 KK개의 어둠의 힘을 더한 값을 한 줄에 하나씩 출력한다.

예제7

  1. 예제 1

    입력
    1
3 6
4 8 3
1 3
1 1
2 3
1 2
2 2
2 1
    예상 출력
    17
7
3

  2. 예제 2

    입력
    1
1 4
2147483647
2 1
1 2147483647
2 1
2 1
    예상 출력
    2147483647
0
0

  3. 예제 3

    입력
    1
5 6
0 0 0 0 0
2 5
1 1073741824
2 3
2 5
1 1073741824
2 5
    예상 출력
    0
3221225472
5368709120
0

  4. 예제 4

    입력
    1
100 5
2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646
2 100
1 1
2 100
1 2147483647
2 100
    예상 출력
    214748364650
214748364650
50

  5. 예제 5

    입력
    1
6 7
5 5 5 9 9 1
2 4
1 4
2 4
2 1
2 6
1 4
2 3
    예상 출력
    16
8
1
34
11

  6. 예제 6

    입력
    3
2 3
1 2
2 2
1 3
2 1
4 4
7 7 0 1
2 4
1 6
2 2
2 4
1 2
0
2 1
1 5
    예상 출력
    3
1
15
2
15
0

  7. 예제 7

    입력
    1
5 8
10 20 30 40 50
2 5
1 123456789
2 5
2 2
1 123456789
2 5
2 2
2 3
    예상 출력
    150
617283983
246913548
150
30
60