비례대표 득표수

JAG 왕국이 의회 의원을 뽑는 선거를 치렀다. 이 나라는 정당명부식 비례대표제만 쓴다. 유권자는 정당 하나에 투표하고, 각 정당이 얻는 의석수는 득표수에 비례한다. 의회의 총 의석수는 정수이므로 정확히 비례하게 나누기는 대개 불가능하다. JAG 왕국은 동트 방식으로 의석을 나눈다.

정당마다 후보는 무제한이고, 한 정당의 후보에는 순서가 있다. $x$표를 얻은 정당의 $y$번째 후보에게 값 $\dfrac{x}{y}$를 준다. 모든 후보를 값이 큰 순서로 정렬한 다음 앞에서 $T$명이 당선된다. $T$는 총 의석수이고, 한 정당의 의석수는 그 정당에서 당선된 후보의 수다.

득표수가 각각 $40$, $60$, $30$인 정당 셋을 예로 들자. 총 의석수가 $T = 9$이면 첫 번째 정당이 $3$석, 두 번째 정당이 $4$석, 세 번째 정당이 $2$석을 얻는다.

값이 같은 후보는 추첨으로 가르므로, 값이 같은 후보는 모두 당선될 가능성이 있다. 같은 예에서 $T = 5$이면 값이 $20$인 후보 둘이 동점이고, 다음 두 결과가 모두 나올 수 있다.

• 첫 번째 정당이 $2$석, 두 번째 정당이 $2$석, 세 번째 정당이 $1$석을 얻는다.
• 첫 번째 정당이 $1$석, 두 번째 정당이 $3$석, 세 번째 정당이 $1$석을 얻는다.

당신은 방금 방송으로 선거 결과를 들었다. 총 유효 투표수와 각 정당이 얻은 의석수를 알고 나니 각 정당이 몇 표를 받았는지 궁금해졌다.

총 유효 투표수 $N$, 정당 수 $M$, $i$번째 정당이 얻은 의석수 $S_i$가 주어진다. 각 정당이 받았을 수 있는 최소 득표수와 최대 득표수를 구하라. 입력에 따라서는 주어진 의석수를 만들어 내는 득표 상황이 아예 없기도 하다.

첫째 줄에 총 유효 투표수 $N$ ($1 \le N \le 10^9$)과 정당 수 $M$ ($1 \le M \le 30000$)이 주어진다. 다음 $M$개 줄의 $i$번째 줄에는 $i$번째 정당이 얻은 의석수 $S_i$ ($0 \le S_i \le 30000$)가 주어진다. $S_i \ne 0$인 $i$가 적어도 하나 있다.

주어진 $N$, $M$, $S_i$를 만들어 내는 득표 상황이 없으면 impossible을 출력한다. 그렇지 않으면 $M$개 줄을 출력한다. $i$번째 줄에는 $i$번째 정당이 받았을 수 있는 최소 득표수와 최대 득표수를 두 정수로 출력한다.