H. Pirate's Booty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pirates love treasure, especially gold coins.

A band of pirates has $$$N$$$ ships arranged in a line, one after the other. Assume that the ships are numbered from $$$1$$$ to $$$N$$$, from the first to the last. Each ship can store a certain number of crates filled with gold coins, with the $$$i$$$-th ship having a maximum capacity of $$$G_i$$$ such crates.

At first, all of the ships are empty. At different times, the pirates load some number of crates onto various ships. If a ship receives more crates than its maximum capacity can afford, then the remaining crates will be loaded onto the next ship in line. In other words, if the $$$i$$$-th ship has reached its maximum capacity, the remaining crates will be loaded onto the ($$$i+1$$$)-th ship. Any remaining crates from the $$$N$$$-th ship will be thrown into the ocean.

Your task is to simulate loading crates onto the ships and answer queries about the number of crates on specific ships. There are two types of queries:

  1. Load $$$C_i$$$ crates onto the $$$K_i$$$-th ship.
  2. Print out the number of crates on the $$$K_i$$$-th ship.

Assume that when you receive a query of the second type, all of the crates loaded up to that point have been properly distributed across the ships.

Input

The first line contains two integers $$$N$$$ and $$$M$$$, the number of ships and queries, respectively ($$$1 ≤ N, M ≤ 10 ^ 5$$$).

The second line contains $$$N$$$ integers $$$G_1, G_2, \ldots, G_N$$$, each ship's maximum capacity ($$$1 ≤ G_i ≤ 10^5$$$).

Each of the next $$$M$$$ lines contains the description of one query. A query of the first type is inputted as $$$1$$$ $$$K_i$$$ $$$C_i$$$, and a query of the second type is inputted as $$$2$$$ $$$K_i$$$ ($$$1 ≤ K_i ≤ N, 1 ≤ C_i ≤ 10^5$$$).

Output

For each query of the second type, print the number of crates on the corresponding ship.

Example
Input
4 6
4 8 10 6
1 1 10
1 2 6
2 1
2 2
1 4 4
2 4
Output
4
8
4