403181: GYM101061 J Cola

At Cola factory there is N bottles on a line. Also, there is a machine that pour cola in these bottles one by one. Every thing was working well. Suddenly, the machine started acting in a strange way !!

It started choosing a random bottle and pour a random quantity of cola in this bottle.

When a bottle is full, the rest of the cola goes to the bottle on the right of it, and if it was the last bottle, then the rest of the cola will be wasted .

As an engineer in this factory, you were given the capacity of every bottle in Litters. Also, you know the record of machine moves because it is stored in the Microcontroller memory of the machine. You are asked to compute the amount of wasted cola, and the amount of cola every bottle has at the end.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T the number of test cases. Followed by the test cases.

Every test case starts with two numbers N and M (1 ≤ N ≤ 10⁵), (1 ≤ M ≤ 10⁵) denoting the number of bottles, and the number of moves the machine had did.

Then follow N integers on a line separated by spaces. The integer C_i denotes the capacity of the i^th bottle (1 ≤ C_i ≤ 10⁹) where (1 ≤ i ≤ N).

M lines follow denoting the moves. Each line contains two integers X and Y (1 ≤ X ≤ N), (1 ≤ Y ≤ 10⁹) means that the machine poured Y liters of cola in the X^th bottle .

For each test case print two lines.

First line contains the amount of wasted cola.

The second line contains N integers separated by spaces denoting the amount of cola in every bottle at the end.

2
5 3
5 4 3 2 1
3 4
4 4
1 2
6 3
3 4 5 5 6 7
3 3
1 8
5 9

2
2 0 3 2 1
0
3 4 4 0 6 3