A company is designing a conveyer belt for loading the items from warehouse to the delivery trucks. The conveyer belt is of length N with N being the end of the conveyer belt and used for putting the items directly into the truck. The conveyer belt moves 1 unit at a time. The workers of the warehouse can put any number of items at any position of the conveyer belt. Before the conveyer belt is launched for use, the auditors need calculate total number of items at position i after the conveyer belt has started working. In a day, Q operations are performed in total by workers and auditors of the type:

• 1 i u- Put u items at index i at that instant.

• 2 i - Find the total number of items at index i at that instant.

The conveyer belt moves one unit after each operation is performed. When items reach the end of the conveyer belt, the items are removed from the conveyer belt by the workers and loaded into the truck. The conveyer starts at instant 0 and operations are performed from instant 1.

Input Format

• First line contains a single integer T denoting the number of test cases.
• The first line of each test case contains two integers N and Q denoting the total length of the conveyer belt and the total number of queries performed in total.
• The next Q lines contains the queries of the two types
  • If it is of query type 1, it will contain 3 space separated integers 1 i u, where i is the index and u is the number of items.
  • If it is of query type 2, it will contain 2 space separated integers 2 i, where i is the index where you need to calculate the total number of items.

Output Format

For every query of type 2, print the total number of items in the conveyer belt in that specified index.

Constraints

• 1 ≤ T ≤ 50
• 1 ≤ N, Q ≤ 3 • 105
• 1 ≤ u ≤ 109
• Sum of N over all test cases does not exceed 3 • 105
• Sum of Q over all test cases does not exceed 3 • 105

Subtasks

• Subtask #1 (20 points): It is guaranteed that sum of N, Q over all test cases does not exceed 2000 in the first subtask.
• Subtask #2 (80 points): Original constraints.

Sample 0

Input

1
5 10
1 1 2
1 2 4
2 3
1 2 5
2 5
2 3
1 4 10
2 5
1 2 10
2 2

Output

6
6
0
10
0

Explanation

• Initially the conveyer belt is empty.
• In the first query we add 2 to the conveyer belt at index 1, so current conveyer belt looks like [2, 0, 0, 0, 0].
• The belt moved by 1 unit, so now we have [0, 2, 0, 0, 0].
• In the next query, we add 4 to the conveyer belt at index 2, so current conveyer belt looks like [0, 6, 0, 0, 0].
• The belt moved by 1 unit, so now we have [0, 0, 6, 0, 0].
• In the next query, we need to report the total units at index 3 which is 6.
• The belt moved by 1 unit, so now we have [0, 0, 0, 6, 0].
• In the next query, 5 items are added at index 2, so now the belt looks like [0, 5, 0, 6, 0].
• The belt moved by 1 unit, so now belt looks like [0, 0, 5, 0, 6].
• In the next query, we need to report the total units at index 5 which is 6.
• The belt moves by 1 unit, so now we have [0, 0, 0, 5, 0] and 6 items were loaded into the truck since it reached the end of the conveyer belt.
• In the next query, we need to report the total units at index 3 which is 0.
• The belt moves by 1 unit, so now we have [0, 0, 0, 0, 5].
• In the next query, we add 10 units at index 4, so now the belt looks like [0, 0, 0, 10, 5].
• The belt moves by 1 unit, so now we have [0, 0, 0, 0, 10] and 5 items were loaded into the truck.
• In the next query, we need to report the total number of units at index 5 which is 10.
• The belt moves by 1 unit, so now we have [0, 0, 0, 0, 0] and 10 items were loaded into the truck.
• In the next query, we add 10 items at index 2 so now the belt looks like [0, 10, 0, 0, 0].
• The belt moves by 1 unit, so now we have [0, 0, 10, 0, 0].
• In the next query, we need to report the total number of units at index 2 which is 0.
• The belt moves by 1 unit, so now we have [0, 0, 0, 10, 0].