Get to Work, Lute!

Lute, who works at Didipos Inc., was assigned the task of writing problems for the company's coding test. He wrote a problem called "Cat Dating," but because he found working tiresome he never wrote a reference solution[1], and Diddy fired him. Having lost his job, Lute moved to Russia to look for new work.

After many twists and turns, Lute found a job at a Russian chemical engineering company, and he wants to move various chemicals from Vladivostok to Moscow through several pipes. To transport a chemical from Vladivostok to Moscow through pipes, it must pass through M pipes P1, P2, ..., PM in order. For each i = 1, 2, ..., M, the length of Pi is Li.

There are N kinds of chemicals that Lute wants to move. For convenience, number them 1, 2, 3, ..., N. Note that for each 1 ≤ i < j ≤ N, chemical i must be transported before chemical j.

For each i = 1, 2, ..., N, the viscosity coefficient of chemical i is ri. If a chemical with viscosity coefficient r starts flowing into a pipe of length L at time t, the chemical leaves the pipe completely just before time t+rl. In other words, it passes through the pipe during [t, t+rl).

Lute worries that the chemicals will mix, so for each i = 1, 2, ..., M, he wants to ensure that after one chemical passes through Pi, no other chemical enters Pi before Ci time has passed. (These Ci are values Lute set by his own standards, and they are given in the input.)

Also, for i = 1, 2, ..., M-1, a chemical must enter Pi+1 immediately after leaving Pi. In other words, a chemical must not stop while flowing through the pipes.

Suppose Lute starts sending chemicals through the pipes starting at time 0. Lute wants to finish the transport work in the minimum amount of time. If Lute finishes the transport work in the minimum amount of time, let Ti be the time at which chemical i leaves PN, for i = 1, 2, ..., N. Find T1, T2, ..., TN.

[1] He really did not write a reference solution.😡 Diddy took pity on him and solved it instead, so Lute does not even know the solution.

The first line of the input gives N and M separated by a space.

The second line of the input gives L1, L2, ..., LM separated by spaces.

The third line of the input gives C1, C2, ..., CM separated by spaces.

The fourth line of the input gives r1, r2, ..., rN separated by spaces.

On the first line of the output, print T1, T2, ..., TN separated by spaces.

• 1 ≤ N ≤ 2,000,000
• 1 ≤ M ≤ 2,500
• For each i = 1, 2, ..., N, 1 ≤ ri ≤ 100
• For each i = 1, 2, ..., M, 1 ≤ Li ≤ 10,000 and 1 ≤ Ci ≤ 100
• All values in the input are integers.