Bullets and Enemies ~ Multiplex Coder

There are

N

enemies standing from left to right with strengths

S_{1}, S_{2}, \dots, S_{N}

$M$

bullets are to be fired from the left side such that only one bullet is fired at a time. The

i^{t h}

bullet

(1 \leq i \leq M)

has power

P_{i}

and capacity

C_{i}

.
This means that the

i^{t h}

bullet affects the first

C_{i}

alive enemies from the left side and decreases the strength of each of those

C_{i}

enemies by

P_{i}

Once an enemy’s strength becomes less than or equal to $0$

, the enemy dies and its strength becomes

0

Find the strength of all the enemies after all $M$

bullets are fired.

Input Format

First line will contain $T$

, the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers

N

and

M

The second line contains

N

space-separated integers

S_{1}, S_{2}, \dots, S_{N}

, denoting strength of the enemies.

The third line contains

M

space-separated integers

P_{1}, P_{2}, \dots, P_{N}

, denoting the power of the

i^{t h}

bullet.

The fourth line contains

M

space-separated integers

C_{1}, C_{2}, \dots, C_{N}

, denoting the capacity of the

i^{t h}

bullet.

Output Format

For each test case, output $N$

space-separated integers denoting the final strength of the enemies.

Constraints

$1 \leq T \leq 10^{3}$

1 \leq N, M \leq 3 \cdot 10^{5}

1 \leq S_{i}, P_{i} \leq 10^{9}

1 \leq C_{i} \leq N

Sum of

N

over all the test cases does not exceed

3 \cdot 10^{5}

Sum of

M

over all the test cases does not exceed

3 \cdot 10^{5}

Sample Input 1

2
7 4
51 84 24 19 77 10 34
3 6 3 10
2 2 6 2
4 3
10 5 4 8
4 2 3
2 4 2

Sample Output 1

29 62 21 16 74 7 34
1 0 0 6

Explanation

Test case $1$

: Initial strength of the enemies is

[51, 84, 24, 19, 77, 10, 34]

The power of the first bullet is $3$

and the capacity is

2

. This means that the first bullet reduces the strength of the first and second enemies by

3

. The strength of the enemies after the first bullet is fired:

[48, 81, 24, 19, 77, 10, 34]

The power of the second bullet is

6

and the capacity is

2

. This means that the second bullet reduces the strength of first and second enemies by

6

. The strength of the enemies after the second bullet is fired:

[42, 75, 24, 19, 77, 10, 34]

The strength of enemies after third bullet is fired:

[39, 72, 21, 16, 74, 7, 34]

The strength of enemies after fourth bullet is fired:

[29, 62, 21, 16, 74, 7, 34]

Test case $2$

: Initial strength of the enemies is

[10, 5, 4, 8]

The power of the first bullet is $4$

and the capacity is

2

. This means that the first bullet reduces the strength of the first and second enemies by

4

. The strength of the enemies after the first bullet is fired:

[6, 1, 4, 8]

The power of the second bullet is

2

and the capacity is

4

. This means that the second bullet reduces the strength of the first four enemies by

2

. The strength of the enemies after the second bullet is fired:

[4, 0, 2, 6]

. Note that due to this bullet, the second enemy dies and its strength becomes

0

The power of the third bullet is

3

and the capacity is

2

. This means that the third bullet reduces the strength of the first two alive enemies by

3

. The strength of the enemies after the third bullet is fired:

[1, 0, 0, 6]

. Note that since the second enemy is already dead, enemies

1

and

3

are affected by this bullet.