19588번 - 상품권 준비

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

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

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

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

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

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

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

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

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

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

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