KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다.

이 중 i (1 ≤ i ≤ 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₁ × |x₁ − x| + a₂ × |x₂ − x| + · · · + a_n × |x_n − x| = ∑^N_i=1a_i× |x_i− x|_이다.

예를 들어 마을의 위치가 x₁ = 1, x₂ = 3, x₃ = 6이고,

각 마을에 거주하는 사람들의 수가 a₁ = 2, a₂= 1, a₃ = 3이라고 하면,

모임 장소가 x = 4일 때의 누적 거리는 f(4) = 2×|1−4|+ 1×|3−4|+ 3×|6−4| = 13 이다.

KOI 나라는 모임이 개최될 장소의 후보를 Q개 준비해 두었다.

이 때 j (1 ≤ j ≤ Q)번째 후보 장소의 위치는 q_j이다.

이 때 서로 다른 두 후보 장소의 위치가 같은 경우는 없으나 마을의 위치와 후보 장소의 위치가 같을 수 있다.

각각의 후보 장소에 대해 누적 거리를 계산하는 프로그램을 작성하라.

참고

|x|는 x < 0이면 −x, x ≥ 0이면 x인 절댓값 기호이다.

제약 조건

• 1 ≤ N ≤ 200 000

• 모든 i (1 ≤ i ≤ N)에 대해, 1 ≤ a_i ≤ 1 000

• 모든 i (1 ≤ i ≤ N)에 대해, −10⁹ ≤ x_i ≤ 10⁹

• 1 ≤ Q ≤ 200 000

• 모든 j (1 ≤ j ≤ Q)에 대해, −10⁹ ≤ q_j ≤ 10⁹

• 1 ≤ i₁ < i₂ ≤ N에 대해 x_i1 ≠ x_i2

• 즉, 모든 마을의 위치는 서로 다르다.

• 1 ≤ j₁ < 2 ≤ Q에 대해 q_j1 ≠ q_j2

• 즉, 모든 후보 장소의 위치는 서로 다르다.

• 주어지는 모든 수는 정수이다.

부분문제

1. (9점) N, Q ≤ 5 000

2. (21점)

• 모든 i (1 ≤ i ≤ N)에 대해 1 ≤ x_i ≤ 200 000

• 모든 j (1 ≤ j ≤ Q)에 대해 1 ≤ q_j ≤ 200 000

3. (25점) 모든 i (1 ≤ i ≤ N)에 대해 a_i = 1

4. (45점) 추가 제약 조건 없음.

누적 거리 timer 3초 memory 1024MB

누적 거리 3초 1024MB