U229959 线段树大集合

共有 $n$ 个数，$m$ 种操作，请设计一种算法，它支持以下几种操作： `1 x y t`：将处于 $x\sim y$ 区间的所有的数都加上 $t$。 `2 x y`：查询处于 $x\sim y$ 区间的每个数的阶乘的和，并对 $10^9$ 取模。 `3 x y`：查询处于 $x\sim y$ 区间的每个数的$\texttt{gcd}$。 `4 x y`：查询处于 $x\sim y$ 区间的每个数的最大值。 `5 x y`：查询处于 $x\sim y$ 区间的数的总和，并对 $10^9$ 取模。

第一行两个整数 $n,m$，表示 $n$ 个数，$m$ 个操作。 接下来一行 $n$ 个整数 $a_i$ 接下来的 $m$ 行每行若干个整数，第一个数为操作的编号 $opt$（$1 \leq opt \leq 5$），以**题目描述**为准。

对于所有查询操作，输出对应的答案。

$\texttt{Sub0}(25pts)：$ $1\le n,m,t\le 1000$ $\texttt{Sub1}(25pts)：$ 只包含修改和一种查询操作。 $\texttt{Sub2}(40pts)：$ 无特殊限制。 $\texttt{Sub3}(10pts)：$ 可通过神奇的优化方法暴力过。 对于 $100\%$ 的数据，$1\le n,m,t\le 100000$，$1\le opt\le 5$，$1\le x\le y\le n，1\le a_i\le 1000000000$