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 safe.

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

Now my little brother want to know how many marbles 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 bags and Q is total work my brother and mother.

Next line there will be N integers A_i the initial number of marbles in each bag. (0 ≤ A_i ≤ 10^9)

m following lines, each forms:

• w u v k means my brother added exactly k marbles to bags u to v. (1 ≤ u, v ≤ N, 0 ≤ k ≤ 10^9).
• m p means mother found bag p, and so the bag will be empty.
• f p means my brother want to know how many marbles are in bag p.

Output

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

Sample

Input:
2
5 3
1 2 3 4 5
w 2 3 4
f 2
f 1
2 2
4 5
f 1
f 2

Output:
Case 1:
6
1
Case 2:
4
5