Background

Translated from ROI 2024 D2T3.

There are $n$ drones registered to participate in a drone race. The $i$-th drone needs $t_i$ seconds to fly one unit of distance.

The race is held on a straight line with $m$ gates, numbered from $1$ to $m$. The $i$-th gate is located at distance $s_i$ from the start of the race.

Due to the limited size of the track, only the first $k$ drones will participate in the first race, numbered from $1$ to $k$. The value of $k$ will be announced by the judges before the race starts, so you need to analyze the race outcome for all $k$ from $1$ to $n$.

The race proceeds as follows:

The drones move from point $0$ toward the gates, and each drone has a different speed. Each drone has a checkpoint, which is the last gate where it performed a save operation. Initially, every drone’s checkpoint is point $0$.

During the race, all drones start moving from their checkpoints, until one or more drones reach a gate (it is possible that different drones reach different gates at the same time). At that moment, among all drones that have reached a gate, choose the drone with the smallest index and perform a save operation for it, setting its checkpoint to the current position. All other drones are immediately teleported back to their checkpoints. Then the race continues.

If a drone performs a save operation at the last gate, numbered $m$, then it finishes the race. The drones that have not yet finished will be teleported back to their checkpoints and continue racing. When all drones finish, the race ends.

Problem Description

Teleportation is a very energy-consuming process. To prepare for the race, you need to know how many times in total all drones will teleport before the race ends. Let $c_k$ denote the total number of teleports made by all drones when the first $k$ drones participate in the race. You need to compute $c_1, c_2, \dots, c_n$.

Input Format

The first line contains two integers $n$ and $m$, representing the number of drones and the number of gates, respectively ($2 \leq n \leq 150000$，$1 \leq m \leq 150000$).

The second line contains $n$ positive integers $t_1, t_2, \dots, t_n$, where $t_i$ is the number of seconds the $i$-th drone needs to fly one unit of distance ($1 \leq t_i \leq 10^9$).

The third line contains $m$ positive integers $s_1, s_2, \dots, s_m$, where $s_i$ is the position of the $i$-th gate ($1 \leq s_1 < s_2 < \dots < s_m \leq 150000$).

Output Format

Output $n$ integers $c_1, c_2, \dots, c_n$, as described above.

3 3
1 2 3
1 3 6

0
4
11

3 3
3 2 1
1 3 6

0
5
13

2 5
2 1
1 3 4 6 7

0
6

Hint

Sample $1$ explanation:

When $k=1$, no teleportation is needed, because only one drone participates, and only it keeps saving all the time.

When $k=2$, the whole race process is shown in the figure below.

When $k=3$, the whole race process is shown in the figure below.

Special properties table for subtasks:

Translated by ChatGPT 5