Range Max Query

Problem Description

Coco the Monkey has an array of N integers. Initially, the ith integer has the value Ai.

Coco the Monkey wants you to answer queries and updates, there will be a total of M queries and updates, in order.

For each query, Coco the Monkey will provide you with two integers x and y where 0 ≤ xyN. You are to respond with the maximum value of the integers from A[x] to A[y] inclusive.

For each update, Coco the Monkey will provide you with three integers, a, b and c. This means you have to add c to every integer from A[a] to A[b].

Limits

For all testcases, -(103) ≤ Ai, c ≤ 103, 0 ≤ x ≤ y < N, 0 ≤ a ≤ b < N.

Subtask 1 (57%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. For all update commands, a = b.

Subtask 2 (43%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. No further restrictions.

Subtask 3 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array A.

The next line will contain a single integer, M.

M lines will follow. The first character of each line will be T.

If T is 0, then it represents a query. 2 integers will then follow, x and y.

If T is 1, then it represents a update. 3 integers will then follow, a, b followed by c.

Output

For each line of query, you are to output the maximum value of A[x] to A[y] inclusive, on a single line.

Sample Testcase 1

Input

10
1 2 9 5 7 6 3 4 2 2
5
0 0 1
0 0 9
1 1 8 7
0 0 9
0 5 7

Output

2
9
16
13

Submitting to 'Range Max Query'


You're not logged in! Click here to login


Submitting to 'Range Max Query'


You're not logged in! Click here to login


Submitting .cpp to 'Range Max Query'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 98
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 57
2 43
3 0