오렌지 나누기

외계 행성 i1c5l에 사는 $n$명의 공동체가 오렌지 $k$개를 수확했다. 이제 그들은 수확물을 나누어 가져야 한다.

이 공동체는 순위를 바탕으로 한 민주적 원칙에 따라 운영된다. 수확물은 다음 방식으로 나눈다. 각 사람은 1부터 $n$까지의 순위를 하나씩 받는다. 1순위인 사람이 누가 오렌지를 몇 개 받을지 결정을 발표한다. 그다음 $n$명 모두가 "찬성" 또는 "반대"로 투표한다. 절반 이상이 찬성하면 결정이 받아들여진다. 그렇지 않으면 1순위인 사람은 공동체에서 쫓겨나고, 2순위인 사람이 결정을 발표하며 같은 절차를 반복한다.

각 사람은 자신이 가능한 한 많은 오렌지를 받으려고 한다. 받는 오렌지 수가 같으면 공동체에 남는 사람이 적은 쪽을 선호한다. 공동체에서 쫓겨난 사람은 음수 개수의 오렌지를 받은 것으로 본다. 최적의 해가 여러 개라면 그중 아무거나 선택할 수 있다. 모든 사람은 다른 사람들도 같은 원칙을 따라 최적의 해를 찾는다는 것을 안다.

그러나 공동체의 한 구성원은 미리 정해진 순위를 주는 와일드카드 $m$개를 사용할 수 있다. 각 와일드카드 순위에 대해, 그가 얻을 수 있는 오렌지의 최솟값과 최댓값을 구하라.

첫 줄에 정수 $n$, $k$, $m$이 주어진다 ($1 \le n, k \le 10^9$, $1 \le m \le 10^5$). 각각 사람 수, 오렌지 수, 와일드카드 수다. 둘째 줄에는 $m$개의 정수 $a_1, a_2, \ldots, a_m$이 주어진다 ($1 \le a_i \le n$). $a_i$는 $i$번째 와일드카드가 주는 순위다.

각 $a_i$에 대해, 와일드카드 소유자가 얻을 수 있는 오렌지의 최솟값과 최댓값을 한 줄에 출력한다. 그가 쫓겨나면 "-1 -1"을 출력한다.

첫 번째 예제에서 1순위인 사람은 오렌지를 전부 가져가고 "찬성"에 투표한다.

두 번째 예제에서 1순위인 사람은 오렌지 하나를 3순위인 사람에게 줘야 한다. 자신이 오렌지 하나를 가지면 나머지는 "반대"에 투표한다. 2순위인 사람에게 주면 그도 "반대"에 투표한다. 1순위를 쫓아내면 그들도 오렌지를 하나 얻지만, 공동체에 남는 사람이 더 적어지기 때문이다. 3순위인 사람도 "반대"에 투표하므로, 이 방법은 1순위인 사람에게 선택지가 되지 못한다.