누적 거리

KOI 나라는 수직선 위에 놓인 $N$개의 마을로 구성되어 있다. 이 중 $i$ ($1 \le i \le N$)번째 마을은 $x_i$ 위치에 놓여 있으며 $a_i$명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다.

KOI 나라는 모든 국민이 참여하는 모임을 개최하려고 한다. 모든 사람들이 모임 장소에 도착하기 위해 이동해야 하는 거리의 합을 누적 거리라고 부르고, 모임 장소가 $x$일 때의 누적 거리를 $f(x)$로 나타내자.

$i$번째 마을에 사는 사람이 $x$ 위치에서 열리는 모임에 참가하기 위해서 이동해야 하는 거리는 $|x_i - x|$이다. $i$번째 마을에는 $a_i$명이 거주 중이므로 $i$번째 마을에 사는 사람들의 이동 거리의 합은 $a_i|x_i - x|$가 된다. 이 값을 모든 마을에 대해 합한 값이 모임 장소가 $x$일 때의 누적 거리가 될 것이다. 즉, $f(x) = a_1 \times |x_1 - x| + a_2 \times |x_2 - x| + \cdots + a_n \times |x_n - x|$이다.

예를 들어 마을의 위치가 $x_1 = 1$, $x_2 = 3$, $x_3 = 6$이고, 각 마을에 거주하는 사람들의 수가 $a_1 = 2$, $a_2 = 1$, $a_3 = 3$이라고 하면, 모임 장소가 $x = 4$일 때의 누적 거리는 $f(4) = 2 \times |1 - 4| + 1 \times |3 - 4| + 3 \times |6 - 4| = 13$ 이다.

KOI 나라는 모임이 개최될 장소의 후보를 $Q$개 준비해 두었다. 이 때 $j$ ($1 \le j \le Q$)번째 후보 장소의 위치는 $q_j$이다. 이 때 서로 다른 두 후보 장소의 위치가 같은 경우는 없으나 마을의 위치와 후보 장소의 위치가 같을 수 있다. 각각의 후보 장소에 대해 누적 거리를 계산하는 프로그램을 작성하라.

첫 번째 줄에 $N$과 $Q$가 공백을 사이에 두고 차례로 주어진다.

다음 $N$개의 줄에는 마을에 대한 정보가 주어진다. 이 중 $i$ ($1 \le i \le N$)번째 줄에는 $a_i$와 $x_i$가 공백을 사이에 두고 차례로 주어진다.

다음 $Q$개의 줄에는 모임 장소 후보에 대한 정보가 주어진다. 이 중 $j$ ($1 \le j \le Q$)번째 줄에는 $q_j$가 주어진다.

$j$ ($1 \le j \le Q$)번째 줄에 모임 장소가 $j$번째 후보 모임 장소인 $q_j$일 때의 누적 거리, 즉 $f(q_j)$의 값을 출력한다.

• $1 \le N \le 200\,000$
• 모든 $i$ ($1 \le i \le N$)에 대해, $1 \le a_i \le 1\,000$
• 모든 $i$ ($1 \le i \le N$)에 대해, $-10^9 \le x_i \le 10^9$
• $1 \le Q \le 200\,000$
• 모든 $j$ ($1 \le j \le Q$)에 대해, $-10^9 \le q_j \le 10^9$
• $1 \le i_1 < i_2 \le N$에 대해 $x_{i_1} \ne x_{i_2}$. 즉, 모든 마을의 위치는 서로 다르다.
• $1 \le j_1 < j_2 \le Q$에 대해 $q_{j_1} \ne q_{j_2}$. 즉, 모든 후보 장소의 위치는 서로 다르다.
• 주어지는 모든 수는 정수이다.

$|x|$는 $x < 0$이면 $-x$, $x \ge 0$이면 $x$인 절댓값 기호이다.