My little brother very much talented to play marble. He has never been defeated. But our family member do not like it. My Mother always finds his marbles and throws them into pond. One day, my little brother thought he store his marble in N bag [1.2,3,….,N] initially there will be some marble and hide them in a secret place. If my mother found a bag then other bag will be save.

Every day he plays marble and wins. He puts the won marble into u to v bag, exactly k pieces for each bag. And if my mother found a bag then thows all marble in the bag into the pond. That mean the founded bag will be empty.

Now my little brother want  to know how many pieces of marble are there in the bag now?

Input:

Input starts with an integer T (≤ 10), denoting the number of test cases.

 Next line contains the integers N,Q 1≤N, Q≤10^5,  N is number of bag and Q is total work my brother and mother.

 Next line there will be N integer A the initially pieces of marble put into bag. (0 ≤ A_i ≤ 10^9)

 m following lines, each forms:

w u v k that mean today my brother put u to v bag exactly k pieces of marble.

1≤u,v≤N, 0 ≤k≤ 10^9

m p that mean mother found p no bag, then the bag will be empty.

f p that mean my brother want to know how many pieces of marble are in p no bag.

Output:

For each test case, print the case number and print the prices of marble when my brother want to know.

Sample: