Bank
Olimbank is projecting its hourly profits for the future and occasionally updates this information. The bank's analysts examine various time intervals for which hourly forecasts are available. For each interval, they are interested in finding the segment of two or more consecutive hours within that interval that has the highest average hourly profit. Different analysts may focus on different time intervals.
Task
Develop a program that, using Olimbank's hourly profit forecasts and any updates to these forecasts, can respond to analysts' queries about the maximum average hourly profit over specified time intervals.
Input Data
The first line of the input contains two integers, N and M. N is the number of hours for which forecasts are available, and M is the total number of operations, which include both analysts' queries and forecast updates. The second line contains N integers: the i-th integer A[i] (–10^8 ≤ A[i] ≤ 10^8) represents the initial forecast for the i-th hour (positive values indicate profit, while negative values indicate expenses). The following M lines describe the operations. Each line begins with a number indicating the type of operation: 1 for a forecast update or 2 for an analyst's query.
For a forecast update operation, the line contains three integers L, R, X (1 ≤ L ≤ R ≤ N, –
10^3≤ X ≤10^3, X ≠ 0). This specifies the segment of the forecast that needs to be adjusted by X (inclusive of the endpoints).For an analyst's query, the line contains two integers L, R (1 ≤ L < R ≤ N), which define the segment of interest (inclusive of the endpoints).
It is guaranteed that there is at least one analyst's query in the input data.
Output Data
For each analyst's query, output two integers L[M] and R[M] on a separate line. These integers represent the endpoints of the segment (inclusive) where the maximum average profit is achieved. The condition L ≤ L[M] < R[M] ≤ R must be satisfied, where L and R are the boundaries of the respective query. If multiple segments yield the same maximum average, any one of them can be output.
Evaluation
The problem will be evaluated under the following conditions:
2 ≤ N, M ≤ 100 — 15% of tests;
2 ≤ N, M ≤ 1000 — 35% of tests;
2 ≤ N, M ≤ 60000 — 50% of tests.