题目描述

题目译自 Ukrainian Olympiads in Informatics 2017 Stage 4 Day1 T4. Шафа-купе

奥林银行（Olymbank）会预测其未来的每小时利润，并时常更新这些信息。银行的分析师会研究有每小时预测的各种时间段。对于每个这样的时间段，分析师们感兴趣的是该时段内最大的平均每小时利润是多少。也就是说，要找到一个长度为两小时或更长、完全位于给定时间段内的时间区间，使得该区间内利润的算术平均值尽可能大。此外，不同的分析师对不同的时间段感兴趣。

请编写一个程序，根据奥林银行的每小时利润预测信息及其更新，来回答银行分析师关于在给定时间段内最大平均每小时利润的查询。

输入格式

输入文件的第一行包含两个整数 $N$ 和 $M$ $(2 \leq N, M \leq 50000)$，分别是可预测的小时数，以及两种类型操作的总次数：预测更新和分析师查询。

第二行包含 $N$ 个整数：第 $i$ 个数 $A_i$ $(-10^8 \leq A_i \leq 10^8)$ 表示第 $i$ 小时的初始预测（正值对应利润，负值对应亏损）。

接下来的 $M$ 行描述了操作。每行的第一个数字表示操作类型：$1$ 表示预测更新，$2$ 表示分析师查询。

• 如果操作类型是预测更新，则该行接下来是三个整数 $L, R, X$ $(1 \leq L \leq R \leq N, -10^3 \leq X \leq 10^3, X \neq 0)$，表示预测区间的边界，需要将该区间（包括端点）内所有预测值都加上 $X$。
• 如果操作类型是分析师查询，则该行接下来是两个整数 $L, R$ $(1 \leq L < R \leq N)$，表示查询区间的边界（包括端点）。

保证输入数据中至少有一次分析师查询。

输出格式

对于每个分析师的查询，在单独的一行中向输出文件输出两个整数 $L_M$ 和 $R_M$，表示获得最大平均利润的区间的端点（包含端点），该区间必须满足关系 $L \leq L_M < R_M \leq R$，其中 $L, R$ 是相应查询的边界。如果存在多个这样的区间，输出任意一个即可。

5 4
1 2 3 4 5
2 1 5
1 1 3 3
2 1 5
2 3 5

4 5
2 3
3 5

数据范围与提示

• 对于 $15\%$ 的数据，$2 \leq N, M \leq 100$。
• 对于 $50\%$ 的数据，$2 \leq N, M \leq 3000$。