현금 인출기

어떤 화폐 체계든 다룰 수 있는 범용 현금 인출기를 개발하고 있다. 어떤 나라의 화폐 체계에서 n종류의 지폐를 쓰며, 액면가는 a1, a2, ..., an이다. 모든 액면가는 서로 다르고 오름차순으로 나열되어 있다. 즉 i > 2이면 $a_{i-1} < a_i$이고, $a_1 = 1$이다.

인출기는 다음 탐욕 알고리즘으로 지폐를 내준다. 고객이 금액 c를 요청했다고 하자. 처음에는 내줄 지폐의 묶음이 비어 있다. 각 단계에서 알고리즘은 묶음의 액면가 합이 c를 넘지 않는 범위에서 가능한 가장 큰 액면가의 지폐를 추가한다. 묶음의 액면가 합이 정확히 c가 되면 알고리즘은 멈춘다. 액면가 $a_1 = 1$인 지폐가 있으므로 알고리즘은 항상 유한한 단계 안에 끝난다.

이 알고리즘의 효율을 평가하려면, 요청할 수 있는 최대 금액이 b일 때 한 번에 내줘야 할 지폐 수의 최댓값을 구해야 한다. 최대 금액은 고객의 서비스 등급에 따라 달라질 수 있으므로, q개의 금액 b1, b2, ..., bq에 대해 질문에 답해야 한다.

지폐 액면가 목록과 요청 가능한 최대 금액이 주어졌을 때, 최대 개수의 지폐가 나오도록 고객이 요청해야 할 금액과 그때의 지폐 수를 구하는 프로그램을 작성하라.

첫째 줄에 지폐 종류의 수 n이 주어진다 (1 ≤ n ≤ 200000).

둘째 줄에 서로 다른 정수 n개 ai가 주어진다 (1 = a1 < a2 < ... < an ≤ $10^{18}$).

셋째 줄에 질의의 수 q가 주어진다 (1 ≤ q ≤ 200000).

다음 q개 줄에는 각각 정수 bi 하나가 주어진다 (1 ≤ bi ≤ $10^{18}$).

각 질의에 대해 최대 개수의 지폐가 나오도록 요청해야 할 금액과 그때의 지폐 수, 두 수를 출력한다.

최대 금액 이하의 금액 중 최대 개수의 지폐를 주는 금액이 여럿이면, 그중 아무거나 출력해도 된다.

예시에서 2는 1 + 1로, 8은 5 + 1 + 1 + 1로, 49는 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1로 내준다.