건초 무게

농부 Bajtazar는 넓이 $n$ 아르의 밭을 사서 그곳에 풀을 심으려 한다. 벤 뒤 말린 풀은 Bajtazar의 농장에서 기르는 가축의 사료가 된다.

밭에는 $n$ 종류의 풀을 섞어 심는다. 각 종류는 합쳐서 1 아르를 차지한다. $i$번째 종류에 대해, 이 종류의 풀 한 포기는 날씨와 토양 비옥도에 관계없이 하루에 $a_i$ 센티미터씩 자란다. 또한 1 아르 넓이에서 1 센티미터의 풀을 베면 정확히 1 킬로그램의 건초를 얻는다.

Bajtazar에게는 예초기가 있고, 이 예초기는 풀을 임의의 높이 $b$로 자를 수 있게 설정할 수 있다. 이렇게 설정하면 $b$ 센티미터보다 높은 모든 풀 포기는 정확히 $b$ 센티미터 높이로 잘린다.

Bajtockie 법에 따르면 풀을 벨 때마다 벤 풀에서 얻은 건초의 양을 기록해야 한다. Bajtazar는 저울을 사거나, 예초 날짜와 예초기 설정을 바탕으로 각 예초 후 얻은 건초의 무게를 계산하는 프로그램을 작성하는 것 중 하나를 골라야 한다. 그는 두 번째 선택이 더 편리하고 저렴하다고 판단했다.

풀은 0일 자정에 심고, 항상 자정에 벤다고 가정한다. 또한 밭을 임의의 높이 $b$로 베는 데 걸리는 시간은 무시할 수 있을 만큼 작다고 가정한다.

입력의 첫째 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 500\,000$)이 주어진다. 이는 각각 Bajtazar의 밭 넓이(아르)이자 심은 풀 종류의 수, 그리고 예초 횟수이다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$)이 주어지며, 이는 각 풀 종류의 성장 속도이다.

다음 $m$개의 줄에는 Bajtazar가 한 예초를 설명하는 정보가 주어진다. $i$번째 예초는 $i$번째 줄에 있는 두 정수 $d_i$와 $b_i$ ($1 \le d_i \le 10^{12}$, $0 \le b_i \le 10^{12}$)로 설명되며, 이는 $d_i$일에 Bajtazar가 풀을 $b_i$ 센티미터 길이로 잘랐다는 뜻이다. 예초 설명은 시간 순서대로 주어지며, $d_1 < d_2 < \ldots < d_m$이다.

또한 Bajtazar는 밭의 어떤 곳에서도 풀의 높이가 $10^{12}$ 센티미터를 넘지 않게 한다.

정확히 $m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 예초 후 얻은 건초의 총 무게(킬로그램)를 출력한다.

1, 2, 3, 4번 풀 종류의 포기 높이를 각 예초 전후로 나타낸 표는 다음과 같다.