누적 거리

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| = \sum_{i=1}^N a_i \times |x_i - 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 $이다. 이 때 서로 다른 두 후보 장소의 위치가 같은 경우는 없으나 마을의 위치와 후보 장소의 위치가 같을 수 있다. 각각의 후보 장소에 대해 누적 거리를 계산하는 프로그램을 작성하라.

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

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

1. (9점) $ N, Q \leq 5\,000 $

2. (21점)

   • 모든 $ i $ ($ 1 \le i \le N $)에 대해 $ 1 \leq x_i \leq 200\,000 $

     • 모든 $ j $ ($ 1 \le j \le Q $)에 대해 $ 1 \leq q_j \leq 200\,000 $
3. (25점) 모든 $ i $ ($ 1 \le i \le N $)에 대해 $ a_i = 1 $
4. (45점) 추가 제약 조건 없음.

첫 번째 줄에 $ 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) $의 값을 출력한다.