출발

국내 최고 권위의 축구 선수권대회 결승전이 막 끝났다. 지금은 자정이고, 전국에서 모인 축구 팬들이 마우스랜드에서 가장 큰 경기장인 국립 경기장을 떠나 버스를 타고 집으로 돌아가려 한다.

마우스랜드는 동서 방향으로 매우 길게 뻗은 직선 도로로 본다. 주민들은 이 도로를 따라 늘어선 집에 산다. 국립 경기장은 마우스랜드에서 가장 중요한 건물이라 도로의 0 킬로미터 지점에 있다. 모든 위치는 경기장을 기준으로 한 하나의 수로 나타낸다. 경기장보다 동쪽은 양수, 서쪽은 음수다. 예를 들어 10은 경기장에서 동쪽으로 10 킬로미터 떨어진 곳이고, -4는 서쪽으로 4 킬로미터 떨어진 곳이다. 경기장의 위치는 0이다.

이 도로를 따라 N개의 공공 버스 노선이 있다. 각 노선에는 매일 버스 한 대가 운행한다. i번째 버스는 Si에서 Ei까지 일정한 속력과 방향으로 달리며, 자정에 출발해 다음 날 자정에 목적지에 도착한다. 매일 자정마다 각 노선의 출발지에서 같은 목적지로 향하는 같은 버스가 출발한다. 버스의 속력은 이동해야 하는 거리에 따라 달라진다. 노선은 한 방향으로만 운행하므로 반대 방향으로 달리는 버스가 없을 수도 있다.

사람은 노선 위 어느 지점에서든, 버스가 움직이는 중에도 즉시 버스에 타고 내릴 수 있으며, 같은 위치에서 버스를 갈아탈 수도 있다.

M명의 사람이 자정에 국립 경기장을 떠났다. j번째 사람은 Pj에 산다. 각 사람이 버스로 집에 도착하는 데 걸리는 최소 시간을 구하라.

첫 줄에 버스 노선의 수 N과 사람의 수 M이 주어진다. 이어지는 N개의 줄에는 각각 i번째 버스 노선의 출발지 Si와 목적지 Ei가 주어진다. 마지막 줄에는 M개의 정수가 주어지며, j번째 정수는 j번째 사람의 집 위치다.

정확히 M개의 줄을 출력한다. j번째 줄에는 두 정수 Aj, Bj를 출력한다. $A_j / B_j$는 기약분수($\gcd(A_j, B_j) = 1$)이며, j번째 사람이 버스로 집에 도착하는 데 걸리는 최소 일수와 같아야 한다. 소수 부분이 있으면 그것까지 정확히 나타낸다. 예를 들어 가장 빨리 도착하는 시각이 4일째 정오라면 3.5일이 걸린 것이므로 답은 $7/2$이고, '7 2'를 출력한다. 모든 사람은 결국 버스로 집에 도착할 수 있음이 보장된다.

• $1 \le N \le 10^6$
• $1 \le M \le 10^6$
• 모든 $1 \le i \le N$에 대해 $-10^6 \le S_i, E_i \le 10^6$
• 모든 $1 \le j \le M$에 대해 $-10^6 \le P_j \le 10^6$
• 모든 $1 \le i \le N$에 대해 $S_i \ne E_i$
• 모든 $1 \le j \le M$에 대해 $P_j \ne 0$

임의의 정수 $x$에 대해 $\text{sign}(x)$는 $x$가 양수이면 1, 0이면 0, 음수이면 -1이다.