A village has a reservoir with a capacity of $c$. The daily water consumption of the village is known to be $a[1 \dots n]$ (for simplicity, assume water consumption occurs at noon each day). There are $q$ operations:

• $1 \ x \ y$: Inject $y$ amount of water into the reservoir on the morning of day $x$ (injection occurs before the day's water consumption). Note that the amount of water in the reservoir cannot exceed $c$.
• $2 \ x \ y$: Change the water consumption of day $x$ to $y$.
• $3 \ x$: Query the amount of water in the reservoir on the evening of day $x$ (the query occurs after the day's water consumption).

Please simulate the entire process and output the result of each query operation in order.

Input

The first line contains three integers $n, q, c$. The second line contains $n$ integers $a[1 \dots n]$. The next $q$ lines each represent an operation.

Output

Output several lines, representing the results of each query operation.

Constraints

• For 30% of the data, $n \le 2000$.
• For another 20% of the data, $c = 10^9$.
• For 100% of the data, $1 \le n, q \le 10^5, 1 \le c \le 10^9, 0 \le y, a[i] \le 10^4, 1 \le x \le n$.

Examples

Input 1

10 10 100
5 3 1 7 6 4 7 8 3 9
1 5 12
1 2 5
3 3
2 2 1
2 8 30
3 3
2 4 18
1 3 30
2 3 3
3 4

Output 1

1
3
13

Input 2

10 10 20
7 9 3 9 2 2 10 7 9 7
1 4 30
2 9 9
3 2
1 10 24
2 1 17
3 6
1 10 11
2 9 28
3 5
3 1

Output 2

0
7
9
0