Description

Bob 需要一个程序来监视 CPU 使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob 会慢慢列出今天会在用计算机时做什么事。

Bob 会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内 CPU 使用率增加或减少一个值；有的事还会直接让 CPU 使用率变为一个值。

当然 Bob 会询问：在之前给出的事件影响下，CPU 在某段时间内，使用率最高是多少。有时候 Bob 还会好奇地询问，在某段时间内 CPU 曾经的最高使用率是多少。

为了使计算精确，使用率不用百分比而用一个整数表示。

不保证 Bob 的事件列表没有出莫名的问题，使得使用率为负………………

Input Format

第一行一个正整数 $T$，表示 Bob 需要监视 CPU 的总时间。

然后第二行给出 $T$ 个数表示在你的监视程序执行之前，Bob 干的事让 CPU 在这段时间内每个时刻的使用率达已经达到了多少。

第三行给出一个整数 $E$，表示 Bob 需要做的事和询问的总数。

接下来 $E$ 行每行表示给出一个询问或者列出一条事件：

• Q X Y：询问从 $X$ 到 $Y$ 这段时间内 CPU 最高使用率。
• A X Y：询问从 $X$ 到 $Y$ 这段时间内之前列出的事件使 CPU 达到过的最高使用率。
• P X Y Z：列出一个事件这个事件使得从 $X$ 到 $Y$ 这段时间内 CPU 使用率增加 $Z$。
• C X Y Z：列出一个事件这个事件使得从 $X$ 到 $Y$ 这段时间内 CPU 使用率变为 $Z$。

时间的单位为秒，使用率没有单位。

$X$ 和 $Y$ 均为正整数（$X\le Y$），$Z$ 为一个整数。

从 $X$ 到 $Y$ 这段时间包含第 $X$ 秒和第 $Y$ 秒。

保证必要运算在有符号 32 位整数以内。

Output Format

对于每个询问，输出一行一个整数回答。

10
-62 -83 -9 -70 79 -78 -31 40 -18 -5 
20
A 2 7
A 4 4
Q 4 4
P 2 2 -74
P 7 9 -71
P 7 10 -8
A 10 10
A 5 9
C 1 8 10
Q 6 6
Q 8 10
A 1 7
P 9 9 96
A 5 5
P 8 10 -53
P 6 6 5
A 10 10
A 4 4
Q 1 5
P 4 9 -69

79
-70
-70
-5
79
10
10
79
79
-5
10
10

Hint

数据分布如下：

第 $1,2$ 个数据保证 $T$ 和 $E$ 均小于等于 $10^3$。

第 $3,4$ 个数据保证只有 Q 类询问。

第 $5,6$ 个数据保证只有 C 类事件。

第 $7,8$ 个数据保证只有 P 类事件。

对于 $100\%$ 的数据，$1\le T,E\le 10^5$，$1\le X\le Y\le T$，$-2^{31}\leq Z\lt 2^{31}$。