大战水魔兽

题号：NC231906
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

李逍遥终于迎来与拜月教主的决战，只见拜月教主召唤出了 $n$ 只水魔兽，第 $i$ 只的水魔兽的体力值为 $a[i]$ .

李逍遥在寻找水魔兽的弱点，由于御剑术威力过大会消耗掉全身真气，因此他每次会选择一个区间 $[l, r]$ 假想发动御剑术来查询此次造成的伤害值（并不会对水魔兽造成实质伤害）.

对于区间 $[l, r]$ 的水魔兽，御剑术的伤害值计算规则为：构造非空正整数序列 $s$ 满足 $\begin{aligned} \prod{s} = \prod_{i=l}^{r}{a[i]} \end{aligned}$ ，则伤害值为 $min\left\{\sum{s}\right\}$ .

拜月教主也不甘示弱，他每次会挑选一个区间 $[l, r]$ 和整数 $x$ ，使得区间 $[l, r]$ 水魔兽的体力值变成 $x$ 倍，即 $\forall_{i \in [l, r]}{a[i] \leftarrow a[i] \times x}$ .

由于李逍遥正忙着对付拜月教主，所以请你帮他计算伤害值。

输入描述:

第一行输入两个整数  表示有  只水魔兽和  次操作.

第二行有  个整数 ，其中  表示第  只水魔兽的体力值.

接下来  行，每行第一个整数  表示操作类型. 

若  则后面有两个整数  表示李逍遥对区间  的水魔兽假想发动御剑术的伤害值.

若  则后面有三个整数  表示拜月教主把区间  水魔兽的体力值变成  倍.

输出描述:

对于每次御剑术操作，输出一个整数表示此次伤害值，由于结果可能很大，所以你只需要输出答案对  取模后的值.

示例1

输入

复制

10 10
3 2 4 8 8 7 8 4 8 10
1 1 7
1 1 3
1 6 10
2 1 2 2
1 5 6
1 1 7
2 1 2 2
1 1 1
1 2 10
1 1 7

输出

复制