시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 88 41 35 48.611%

문제

2120년에도 “2120 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름대회”가 성공적으로 개최된다. 올해 HI-ARC에서는 총 N명의 학회원이 참가를 희망한다. HI-ARC의 운영진들은 서로 다른 정수로 수치화된 모든 학회원의 “실력” 정보를 가지고 있으며, 이를 바탕으로 다음과 같은 방법으로 팀을 구성한다.

  1. 정확히 a개의 팀이 대회에 참가하며, 각 팀의 팀원은 M명이다.
  2. 실력이 높은 상위 b명은 이번 대회의 출제진이 된다. 따라서 남은 Nb명의 학회원이 이번 대회에 참가할 수 있는 후보다.
  3. 후보 중 × a명을 골라 최강의 팀 구성을 만든다. 한 팀의 “강력함”은 그 팀의 모든 팀원들의 실력의 곱으로 정의된다. 최강의 팀 구성은 모든 팀의 “강력함”의 합이 최대가 되는 구성이다.

HI-ARC에서는 대회 참가의 독려를 위해 모든 팀에게 소정의 상품권을 제공하는 이벤트를 준비하기로 하였다. 각 팀이 받는 상품권의 액수는, 팀원들의 이름을 Bitwise XOR한 값과 같다. 알다시피 2120년 대한민국에서 모든 사람의 이름은 10이하의 자연수이다.

문제는 한 팀의 팀원 수인 M은 이미 결정되었지만, 아직 ab는 확정되지 않았다는 것이다. 따라서 HI-ARC 운영진들은 상품권을 총 얼마나 준비해야 할지 예산 계획을 세우는 데 어려움을 겪고 있다. 대회 준비로 바쁜 운영진들을 대신하여, 다양한 ab의 후보에 대해서 준비해야 하는 상품권 액수의 총합을 구해보자.

입력

첫 번째 줄에 대회에 참가하는 학회원의 수 N과 한 팀의 팀원 수 M가 주어진다. (1 ≤ M ≤ ≤ 100,000)

다음 N개의 줄에 걸쳐 각 학회원의 정보를 나타내는 정수 x, y가 주어진다. x는 이 학회원의 실력, y는 이 학회원의 이름이다. (1 ≤ x, y ≤ 109) 서로 다른 두 학회원의 x가 같은 경우는 없다.

다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 500,000)

다음 Q개의 줄에 쿼리의 정보를 나타내는 정수 aibi가 주어진다. (1 ≤ ai ≤ N, 0 ≤ b< N) 최강의 팀 구성을 만드는 방법이 하나인 쿼리들만 주어진다.

입력의 양이 많은 편이므로 빠른 입력 함수의 사용을 권장한다.

출력

(1 ≤ Q)번째 줄에 a = ai이고 b = bi일 때 준비해야 하는 상품권 액수의 총합을 출력한다. 

예제 입력 1

5 2
10 2
20 7
30 6
40 8
50 4
1
2 1

예제 출력 1

19

“4”가 출제진이 되어야 하며, [“2”, "7”], [“6”, “8”] 로 팀을 구성하는 것이 (10 × 20 + 30 × 40)으로 최강의 팀 구성이다. 따라서 총 (2 ⊕ 7) + (6 ⊕ 8) = 19가 준비해야 할 총액이다.

노트

Bitwise XOR은 두 값을 이진수로 표현하고 자리 단위로 적용되는 이진 연산자로, 두 피연산자의 각 자릿수를 비교하며 같으면 1, 다르면 0을 계산한다. C/C++, Java, Python에서 두 정수 xy의 Bitwise XOR 결과는 (x ^ y)로 계산 할 수 있다.