题目描述

奥利姆银行会预测未来每小时的利润，并不时对这些预测进行修正。银行分析师会研究不同的时间区间。对于每个给定区间，分析师关心其中最大的平均每小时利润。

也就是说，需要在查询区间内部选择一个长度至少为 $2$ 小时的连续时间段，使该时间段内利润值的算术平均值尽可能大。

此外，不同分析师关心的时间区间不同。

任务

给定初始的每小时利润预测，以及之后的若干次修正和询问，回答每个询问中达到最大平均利润的时间段端点。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示可用预测的小时数，以及操作总数，满足 $2\le N,M\le 50000$。

第二行包含 $N$ 个整数，第 $i$ 个数 $A_i$ 表示第 $i$ 小时的初始利润预测，满足 $-10^8\le A_i\le 10^8$。正数表示盈利，负数表示亏损。

接下来 $M$ 行，每行描述一个操作。每行第一个整数表示操作类型：

• 1：修正预测；
• 2：分析师询问。

若为修正操作，则接下来给出三个整数 $L,R,X$，表示对区间 $[L,R]$ 中所有预测值加上 $X$。满足 $1\le L\le R\le N$，$-10^3\le X\le 10^3$，且 $X e 0$。

若为询问操作，则接下来给出两个整数 $L,R$，表示查询区间 $[L,R]$，满足 $1\le L<R\le N$。

保证输入中至少有一次分析师询问。

输出格式

对于每个询问，输出一行两个整数 $L_M$ 和 $R_M$，表示达到最大平均值的时间段两端，要求：

若有多个合法答案，输出任意一个。

样例输入

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

子任务

额外保证：

1. 15 分：$2\le N,M\le 100$；
2. 50 分：$2\le N,M\le 3000$。