Drone racing is held in Innopolis. There are $n$ drones that can participate in the race, and the $i$-th drone travels one unit of distance in $t_i$ seconds. The race takes place on a straight line where $m$ gates are located, numbered from $1$ to $m$. The $i$-th gate is located at a distance $s_i$ from the starting position of the race. The first $k$ drones with numbers from $1$ to $k$ will participate in the race. The value of $k$ is announced by the judges immediately before the race, so you need to analyze the race for all $k$ from $1$ to $n$. The race is conducted as follows. Drones start moving from point $0$ towards the gates, each at its own speed. Each drone has a recovery point — the last gate where it performed a position save. Initially, the recovery point for each drone is point $0$. Drones start moving from their recovery points each time and continue moving until one or more drones reach a point where a gate is located (possibly different gates for different drones). At this moment, among all drones that have reached any gate, the drone with the smallest number is selected. For this drone, a position save is performed, and its recovery point is moved to its current position. The remaining drones are instantly teleported back to their recovery points. After this, the race continues in the same way. As soon as a drone saves its position at the last gate with number $m$, it finishes. Drones that have not yet finished are teleported to their recovery points as usual and continue the race. When all drones have finished, the race ends. Teleportation is a very energy-intensive process. To prepare for the race, it is necessary to understand the total number of teleportations all drones will perform before it ends. Let $c_k$ be the total number of teleportations that all drones will perform if the first $k$ drones participate in the race. Find the values $c_1, c_2, \dots, c_n$.
Input
The first line contains two integers $n$ and $m$ — the number of drones and gates, respectively ($2 \le n \le 150\,000$, $1 \le m \le 150\,000$). The second line contains $n$ positive integers $t_1, t_2, \dots, t_n$, where $t_i$ is the number of seconds it takes for the $i$-th drone to travel one unit of distance ($1 \le t_i \le 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 on the line ($1 \le s_1 < s_2 < \dots < s_m \le 150\,000$).
Output
Output $n$ integers $c_1, c_2, \dots, c_n$.
Subtasks
| Subtask | Points | Constraints | Additional Constraints | Required Subtasks |
|---|---|---|---|---|
| 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$ | 1 |
| 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$ for all $1 \le i < m$ | |
| 5 | 8 | $n \le 100\,000$ | $m \le 100\,000$, $t_i, s_i \le 100\,000$, all $t_i$ are equal | |
| 6 | 10 | $n \le 100$ | $m \le 100\,000$, $t_i, s_i \le 100\,000$ | 1, 2 |
| 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$ | 1, 2, 3, 6 |
| 10 | 6 | $n \le 50\,000$ | $m \le 100\,000$, $t_i, s_i \le 100\,000$ | 1, 2, 3, 6, 9 |
| 11 | 8 | $n \le 100\,000$ | $m \le 100\,000$, $t_i, s_i \le 100\,000$ | 1 – 10 |
| 12 | 8 | $n \le 100\,000$ | 1 – 11 | |
| 13 | 8 | no additional constraints | 1 – 12 |
Examples
Input 1
3 3 1 2 3 1 3 6
Output 1
0 4 11
Input 2
3 3 3 2 1 1 3 6
Output 2
0 5 13
Input 3
2 5 2 1 1 3 4 6 7
Output 3
0 6
Note
Consider the first example. If $k = 1$, no teleportations occur. If $k = 2$, the race proceeds as follows. The figures show the moments when drones reach the gates and teleportation occurs.
If $k = 3$, the race proceeds as follows. The figures show the moments when drones reach the gates and teleportation occurs.
