题目描述

沿国境修建墙体并不是现代才有的做法。在漫长的历史中，国家 X 一直沿着与国家 Y 的边界维护一堵墙。墙的总长度始终为 N 米，但其高度经常发生变化。

沿墙长度方向连续的每个 1 米区段称为一个段（segment），这些段依次编号为 1 到 N。我们用 [L, R] 表示一段墙区间，即所有编号 p 满足 L ≤ p ≤ R 的墙段。

历史上的每次改造都由三个整数决定：1 ≤ L ≤ R ≤ N，以及一个高度变化量 dh。这次改造会将区间 [L, R] 内每一段墙的高度同时增加 dh。在不同改造中，dh 可以不同。它既可能是正数（表示增高），也可能是负数（表示降低）。并且每次所选的 dh 都保证不会使任何一段墙的高度变成负数。

最开始并没有墙，也就是说所有墙段的高度都为 0。

当然，统治者身边总少不了喜欢提问的学者。他们最常问的问题是：

在过去的所有年份中，区间 [L, R] 内曾出现过的墙段最大高度是多少？

任务

编写函数 init()、change_wall() 和 get_wall_h()。这些函数将与评测程序一起编译，并由评测程序调用，用来模拟墙体高度的变化，并回答学者们的提问。

实现细节

你需要提交一个名为 wall.cpp 的源文件，其中包含以下函数：

void init(int N);
void change_wall(int L, int R, int dh);
long long get_wall_h(int L, int R);

• init 在程序开始时调用一次，通过参数 N 给出墙的长度。你可以在其中初始化后续需要使用的数据结构。
• change_wall 在需要修改某个区间的墙高时调用。
• get_wall_h 在需要回答学者提问时调用。

各参数含义如下。

对于 init

• N：墙的长度（即一米长墙段的数量）。

对于 change_wall

• L：要修改高度的区间左端点；
• R：要修改高度的区间右端点；
• dh：区间 [L, R] 内每一段墙高度的变化量。

对于 get_wall_h

• L：提问区间的左端点；
• R：提问区间的右端点。

函数 get_wall_h 应返回：在本次调用之前的历史中，区间 [L, R] 内任意墙段曾达到过的最大高度。

wall.cpp 不应包含 main() 函数，但可以包含完成 change_wall 和 get_wall_h 所需的声明和辅助函数。

限制

若用 K 表示函数 change_wall 与 get_wall_h 的总调用次数，则有：

• 1 ≤ N ≤ 200 000
• 1 ≤ K ≤ 200 000
• -10^9 ≤ dh ≤ 10^9

样例

子任务

本地测试

为了在本地测试你编写的 init()、change_wall() 和 get_wall_h()，题目提供文件 Lgrader.cpp 和 wall.h。请将它们与 wall.cpp 放在同一目录下，编译 Lgrader.cpp 后即可得到用于本地测试的程序。

该本地测试程序从标准输入读取如下数据：

第一行输入两个正整数，以空格分隔：

• N：墙的长度；
• K：函数 change_wall 与 get_wall_h 的调用总次数。

接下来有 K 行，每行描述一次函数调用。每行第一个数表示调用的是哪一个函数：

• 1：表示调用 change_wall，即修改某段墙的高度；
• 2：表示调用 get_wall_h，即提出一个询问。

之后输入两个正整数 L 和 R（L ≤ R），表示本次操作或询问对应的区间 [L, R]。

如果本次操作是修改高度，那么在其后还会再输入一个整数 dh，表示区间 [L, R] 内每段墙高度都要增加的值。