Гонка дронов

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

В гонке могут принять участие $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$.

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

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

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

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

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

	2 телепортации
	+2 телепортации, итого 4
дрон 1 финишировал	+2 телепортации, итого 6
	+2 телепортации, итого 8
	+1 телепортация, итого 9
	+1 телепортация, итого 10
дрон 2 финишировал	+1 телепортация, итого 11
	дрон 3 финишировал