P. Cereal Mountains
time limit per test
7.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Agastya, the king of the Cereal Kingdom, loves to use his god powers to create cereal mountains.

More specifically, Agastya's Cereal Kingdom is described as and array length $$$n$$$ of heights $$$h_1, h_2, \dots h_n$$$.

When Agastya casts a spell at position $$$i$$$ with power $$$p$$$ and range $$$r$$$, for all indices $$$1 \leq j \leq n$$$ such that $$$|j - i| \le r$$$, $$$h_j$$$ increases by $$$p \cdot (r - |j-i|)$$$.

Larry is an over achiever, so he always wants to climb up to the tallest mountains near him. Larry is at position $$$p$$$, and wants to know the height of the tallest mountain within distance $$$d$$$ from his current position.

More specifically, Larry wants to know $$$\max(h_i)$$$ such that $$$1 \leq i \leq n$$$ and $$$|i-p| \le d$$$.

Please help Larry find the tallest of the cereal mountains.

Input

The first line contains one integer, $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.

The next line contains $$$n$$$ integers, describing $$$h_1, h_2, \dots h_n$$$ $$$(1 \leq h_i \leq 10^9)$$$.

The next line contains one integer, $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^5)$$$.

The $$$i$$$-th line of next $$$q$$$ lines first contains an integer $$$t_i$$$, describing the type of query.

If $$$t_i = 1$$$, then Agastya casts a spell. The query type is followed by $$$3$$$ integers $$$i$$$, $$$p$$$, and $$$r$$$, describing the position, power, and range of the spell $$$(1 \leq i, r \leq n)$$$, $$$(1 \leq p \leq 10^2)$$$.

If $$$t_i = 2$$$, then the query type is followed by two integers $$$p$$$ and $$$d$$$, describing the position of Larry, who wants to know the height of the tallest mountain within distance $$$d$$$ $$$(1 \leq p, d \leq n)$$$.

Output

For each query of type $$$2$$$, print out one integer $$$i$$$ followed by a newline, describing the height of the tallest mountain within distance $$$d$$$ from position $$$p$$$.

Example
Input
5
3 4 0 3 5
4
1 4 5 5
2 5 1
1 2 3 2
2 2 2
Output
25
25
Note

Initially, the $$$h$$$ = $$$[3, 4, 0, 3, 5]$$$.

When Agastya casts a spell at position $$$4$$$ with power $$$5$$$ and range $$$5$$$, the increases are $$$[10, 15, 20, 25, 20]$$$ and $$$h$$$ = $$$[13, 19, 20, 28, 25]$$$.

The tallest mountain within distance $$$1$$$ of index $$$5$$$ is $$$25$$$.

Agastya then casts a spell at position $$$2$$$ with power $$$3$$$ and range $$$2$$$. The increases are $$$[3, 6, 3, 0, 0]$$$, and $$$h$$$ = $$$[16, 25, 23, 28, 25]$$$.

The tallest mountain within distance $$$2$$$ of index $$$2$$$ is $$$25$$$.

Problem Credits: Agastya Goel