26608번 - 캠핑하기

문제

동화는 느긋하게 캠핑하는 것을 즐긴다. 근처에 1ドル$번부터 $N$번까지 캠핑장 $N$개가 있는데, $i$번 캠핑장에 가는데 걸리는 시간은 $A_i,ドル 캠핑장에 가서 얻는 만족도는 $B_i$이다.

하지만, 캠핑은 그날의 날씨에 따라 걸리는 시간이나 만족도가 바뀔 수 있다. 비가 오는 날에는 캠핑장으로 가는데 더 오래 걸리고, 만족도도 줄어들게 된다. 동화는 이를 고려하기 위해 날씨 계수 $k$를 도입했다. 날씨가 안 좋은 정도를 1ドル$부터 $M$까지의 정수 중 하나인 $x$로 나타낸다면, 걸리는 시간은 $A_i + kx,ドル 만족도는 $B_i - kx$가 된다.

동화는 가능한 모든 날씨 상황에 대해서 가는데 걸리는 시간 당 만족도가 가장 큰 곳으로 캠핑을 가고 싶다. 1ドル$부터 $M$까지 정수 $x$에 대해 $(B_i - kx) / (A_i + kx)$ 의 값이 가장 큰 캠핑장을 구해보자.

입력

첫 줄에 $N, M, k$가 주어진다. $(1 \le N \le 300000, 1 \le M \le 100000, 1 \le k \le 100)$

이후 $N$줄에 걸쳐 $A_i, B_i$가 주어진다. $(1 \le A_i, B_i \le 10^9)$

출력

$M$줄에 걸쳐 $i$번째 줄에 날씨가 안 좋은 정도가 $i$일때 걸리는 시간 당 만족도의 최댓값을 값이 0ドル$일 경우 0ドル/0$으로, 아닌 경우 $p/q$ ($p$는 정수, $q$는 양의 정수, $\gcd(p ,q)=1$)꼴로 출력한다.

제한

힌트