시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 179 42 38 30.400%

문제

해조는 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 ≤ KM2)가 주어진다.

출력

Q개의 줄에 걸쳐 만들 수 있는 두 글자 닉네임 중 사전 순으로 K번째로 앞선 것을 출력한다. 앞글자와 뒷글자 사이는 공백으로 구분한다.

만약 만들 수 있는 닉네임의 개수가 K개보다 적다면 -1 -1을 출력한다.

앞선 쿼리는 이후의 쿼리에 영향을 주지 않는다.

예제 입력 1

5 5 3
1 2 3 4 5
6
12
18

예제 출력 1

3 3
5 2
-1 -1