给定长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$，以及一个长度为 $N$ 的序列 $B$，初始时 $B_i = 0$。需要编写程序执行以下查询：

• 1 L R X：对所有 $L \le i \le R$，执行 $A_i = A_i + X$。
• 2 L R Y：对所有 $L \le i \le R$，执行 $A_i = \max(A_i, Y)$。
• 3 L R Y：对所有 $L \le i \le R$，执行 $A_i = \min(A_i, Y)$。
• 4 L R：输出 $B_L + B_{L+1} + \ldots + B_R$。

每当由第 1、2、3 号查询导致 $A_i$ 发生变化时，$B_i$ 的值增加 $1$。

输入格式

第一行包含序列大小 $N$。（$1 \le N \le 500{,}000$）

第二行包含 $A_1, A_2, \ldots, A_N$。（$-10^9 \le A_i \le 10^9$）

第三行包含查询个数 $M$。（$1 \le M \le 500{,}000$）

接下来 $M$ 行，每行给出一个查询。（$1 \le L \le R \le N$，$-2{,}000 \le X \le 2{,}000$，$-10^9 \le Y \le 10^9$）至少有一个第 4 号查询。

输出格式

对于每个第 4 号查询，输出一行结果。

样例

样例输入 1

5
1 2 3 4 5
11
4 1 5
1 1 3 3
4 1 5
2 2 5 5
4 1 5
3 1 4 5
4 1 4
2 1 5 0
4 1 5
3 1 5 1
4 1 2

样例输出 1

0
3
4
5
5
4