给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。请编写程序处理以下查询：

• 1 x y v: 执行 $A_i = (A_i + v) \% MOD$，其中 $x \le i \le y$。
• 2 x y v: 执行 $A_i = (A_i \times v) \% MOD$，其中 $x \le i \le y$。
• 3 x y v: 执行 $A_i = v$，其中 $x \le i \le y$。
• 4 x y: 输出 $(\sum A_i) \% MOD$，其中 $x \le i \le y$。

这里 $MOD$ 恒为 $10^9+7$，$\%$ 表示取模运算。

输入格式

第一行包含序列的长度 $N$。($1 \le N \le 100{,}000$)

第二行包含 $A_1, A_2, \ldots, A_N$。($1 \le A_i \le 10^9$)

第三行包含查询的个数 $M$。($1 \le M \le 100{,}000$)

接下来 $M$ 行，每行包含一个查询。($1 \le x \le y \le N$，$1 \le v \le 10^9$)

输出格式

对于第 $4$ 种查询，按顺序每行输出一个答案。

样例

输入格式 1

4
1 2 3 4
4
4 1 4
1 1 3 10
2 2 4 2
4 1 4

输出格式 1

10
69