33866번: Гонка дронов

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	2048 MB	69	5	3	5.455%

문제

В Иннополисе проводятся гонки дронов.

В гонке могут принять участие $n$ дронов, $i$-й дрон пролетает единицу расстояния за $t_i$ секунд. Гонка проводится на прямой, на которой расположены $m$ ворот, пронумерованных от $1$ до $m$, $i$-е ворота находятся на расстоянии $s_i$ от стартовой позиции гонки.

В гонке примут участие первые $k$ дронов с номерами от $1$ до $k$. Величину $k$ судьи объявляют непосредственно перед гонкой, поэтому вам необходимо проанализировать гонку для всех $k$ от $1$ до $n$.

Гонка проводится следующим образом.

Дроны начинают движение из точки $0$ в сторону ворот, каждый со своей скоростью. У каждого дрона есть точка восстановления --- последние ворота, в которых он выполнял сохранение позиции. Изначально точка восстановления каждого дрона --- точка $0$. Дроны каждый раз начинают двигаться из своих точек восстановления и продолжают движение, пока один или несколько дронов не оказываются в точке, где расположены ворота (возможно, различные для разных дронов). В этот момент среди всех дронов, которые оказались в каких-либо воротах, выбирается дрон с наименьшим номером. Для этого дрона производится сохранение позиции, его точка восстановления переносится в его текущую позицию. Остальные дроны мгновенно телепортируются в свои точки восстановления. После этого гонка продолжается таким же образом.

Как только дрон сохраняет позицию в последних воротах с номером $m$, он финиширует. Не финишировавшие пока дроны, как обычно, телепортируются в свои точки восстановления и продолжают гонку. Когда все дроны финишируют, гонка завершается.

Телепортация --- очень энергоемкий процесс. Для подготовки к гонке необходимо понять, сколько суммарно телепортаций совершат все дроны до её завершения. Обозначим как $c_k$ суммарное число телепортаций, которое совершат все дроны, если в гонке будут участвовать первые $k$ дронов. Найдите значения $c_1, c_2, \ldots, c_n$.

입력

В первой строке даны два целых числа $n$ и $m$ --- количество дронов и ворот, соответственно ($2 \le n \le 150\,000$, $1 \le m \le 150\,000$).

Во второй строке даны $n$ положительных целых чисел $t_1, t_2,...,t_n$, где $t_i$ --- количество секунд, за которое $i$-й дрон пролетает единицу расстояния ($1 \le t_i \le 10^9$).

В третьей строке даны $m$ положительных целых чисел $s_1, s_2,...,s_m$, где $s_i$ --- позиция $i$-х ворот на прямой ($1 \le s_1 < s_2 < \ldots < s_m \le 150\,000$).

출력

Выведите $n$ целых чисел $c_1, c_2, \ldots, c_n$.

서브태스크

번호	배점	제한
1	5	$n = 2$, $m \le 50$, $t_i,s_i \le 100\,000$
2	7	$n \le 50$, $m \le 50$, $t_i,s_i \le 100\,000$
3	13	$n \le 1000$, $m \le 5$, $t_i,s_i \le 100\,000$
4	9	$n \le 100\,000$, $m \le 100\,000$, $t_i,s_i \le 100\,000$, $s_{i+1} - s_i = s_1$, для всех $1 \le i < m$
5	8	$n \le 100\,000$, $m \le 100\,000$, $t_i,s_i \le 100\,000$, все $t_i$ равны
6	10	$n \le 100$, $m \le 100\,000$, $t_i,s_i \le 100\,000$
7	5	$n \le 100\,000$, $m \le 100\,000$, $t_i \le 2$, $s_i \le 100\,000$
8	7	$n \le 100\,000$, $m=2$, $t_i,s_i \le 100\,000$
9	6	$n \le 10\,000$, $m \le 100\,000$, $t_i,s_i \le 100\,000$
10	6	$n \le 50\,000$, $m \le 100\,000$, $t_i,s_i \le 100\,000$
11	8	$n \le 100\,000$, $m \le 100\,000$, $t_i,s_i \le 100\,000$
12	8	$n \le 100\,000$
13	8	без дополнительных ограничений

예제 입력 1

3 3
1 2 3
1 3 6

예제 출력 1

0
4
11

예제 입력 2

3 3
3 2 1
1 3 6

예제 출력 2

0
5
13

예제 입력 3

2 5
2 1
1 3 4 6 7

예제 출력 3

0
6

노트

Рассмотрим первый пример.

Если $k = 1$, то телепортаций не происходит.

Если $k=2$, то гонка происходит следующим образом. На рисунках показаны моменты, когда дроны оказываются в воротах и происходит телепортация.



	1 телепортация

	+1 телепортация, итого 2

	+1 телепортация, итого 3
	дрон 1 финишировал
	+1 телепортация, итого 4

	дрон 2 финишировал