一个整数寄存器的值只能处于 [0,M] 内。执行调整 a 时，先将寄存器加上 a，再把结果限制在 [0,M] 内：小于 0 的结果变成 0，大于 M 的结果变成 M。

现有 n 条按顺序排列的调整，数值为 a_1,a_2,…,a_n。你需要处理 q 次操作：

• 1 p v：把第 p 条调整改为 v；
• 2 l1 r1 l2 r2：分别取当前日志的两个连续段 [l1,r1]、[l2,r2]。对两个寄存器设置相同的整数初值 x，分别从左到右执行这两个段。求使两个最终值不同的最小 x，其中 0≤x≤M。如果对所有允许的初值，两个最终值都相同，输出 −1。

每次询问都独立设置寄存器初值，不继承之前询问的执行结果。两个查询段可以重叠，也不必等长。

输入格式

本题只有一组输入数据。

第一行包含 n、q、M。

第二行包含 n 个整数 a_1,a_2,…,a_n。

接下来 q 行，每行描述一次上述操作。

输出格式

对每次类型为 2 的操作，输出一行答案。

数据范围

• 1 ≤ n,q ≤ 200000；
• 1 ≤ M ≤ 10^9；
• 初始 a_i 和修改值 v 都在 [−10^9,10^9] 内；
• 1 ≤ p ≤ n；
• 1 ≤ l1 ≤ r1 ≤ n，1 ≤ l2 ≤ r2 ≤ n；
• 至少有一次类型为 2 的操作。

样例

6 6 10
-2 4 -2 4 -2 15
2 1 3 2 3
2 2 3 4 5
2 6 6 1 6
1 4 -2
2 1 3 4 5
2 6 6 2 2

1
-1
-1
0
0

说明：第一次询问比较 −2,+4,−2 与 +4,−2。初值为 0 时，两者都得到 2；初值为 1 时，两者分别得到 2 和 3。因此答案为 1。

第三次询问中，两段的最后一条调整都是 +15，执行后一定得到 10。

下载样例数据