문제
해조는 2019년 8월 3일에 오픈베타가 열리는 대작 MMORPG '패스 오브 여로'에서 사전예약을 하려고 한다. 해조는 예쁜 두 글자 닉네임을 갖고 싶었지만 발 빠른 다른 유저들이 선점하여 가질 수 없었다.
해조가 선점된 닉네임의 규칙을 살펴본 결과 특정 소설에서 순서대로 두 글자를 따온 닉네임들은 전부 등록되어 있었고 그 외의 두 글자 닉네임은 모두 만들 수 있었다. 예를 들어 소설의 내용이 '나랏말싸미듕귁에달아'이라고 해보자. 해조가 발견한 규칙에 따르면 '나미'는 이미 있는 닉네임이고, '아싸'는 언급된 글에서 '아'보다 '싸'가 앞에 있어서 소설에서 만들 수 없는 단어이므로 생성할 수 있는 닉네임이다.
해조는 만들 수 있는 두 글자 닉네임 중에서 사전 순으로 K번째로 앞서는 것을 닉네임으로 정하려고 한다. 해조는 Q개의 K를 정하여 닉네임을 구한 다음 그중에서 가장 예쁜 것을 선택할 예정이다. 해조를 도와 소설의 내용이 주어졌을 때 만들 수 있는 닉네임 중에서 사전 순으로 K번째로 앞선 것을 온라인으로 구하는 프로그램을 작성하여라.
편의상 모든 글자는 1 이상 M 이하의 정수로 표현하며, 닉네임 AB가 닉네임 CD보다 사전 순으로 앞선다는 것은 A < C이거나, A = C이고 B < D임을 의미한다.
입력
첫 번째 줄에는 소설의 길이 N(1 ≤ N ≤ 100,000), 글자의 종류 수 M(1 ≤ M ≤ 1,000,000), 쿼리의 수 Q(1 ≤ Q ≤ 100,000)가 주어진다.
두 번째 줄에는 소설의 내용에 해당하는 N개의 1 이상 M 이하의 정수가 주어진다.
세 번째 줄부터 Q개의 줄에는 가지려는 닉네임의 사전 순 번호를 계산할 수 있는 값 K(1 ≤ K ≤ M2)가 주어진다. 첫 번째 쿼리인 경우 계산해야 하는 쿼리는 K이며, 그 이외의 경우 직전 쿼리의 답이 “a b”라면 계산해야 하는 쿼리는 (K+a+b+2)%M2+1이다.
출력
Q개의 줄에 걸쳐 만들 수 있는 두 글자 닉네임 중 사전 순으로 K번째로 앞선 것을 출력한다. 앞글자와 뒷글자 사이는 공백으로 구분한다.
만약 만들 수 있는 닉네임의 개수가 K개보다 적다면 -1 -1을 출력한다.
앞선 쿼리는 이후의 쿼리에 영향을 주지 않는다.
예제1
553
12345
6
3
8
33
52
-1-1