题目描述

有 $n$ 个元素，第 $i$ 个元素可以用三元组 $(x_i,y_i,v_i)$ 表示。

初始有 $x_i=i,v_i=0$，而 $y_i$ 由输入给定，保证 $y$ 是一个 $1$ 到 $n$ 的排列。

你需要维护数列，以支持以下四种操作：

• 0 l r a b：$\forall x_i\in[l,r],v_i\gets v_i\times a+b$；
• 1 l r a b：$\forall y_i\in[l,r],v_i\gets v_i\times a+b$；
• 2 l r：询问 $\sum_{x_i\in[l,r]}v_i$ 的值；
• 3 l r：询问 $\sum_{y_i\in[l,r]}v_i$ 的值。

输入格式

第一行两个整数 $n,q$ 表示元素个数和操作次数。

第二行 $n$ 个整数 $y_{1\cdots n}$。

接下来 $q$ 行，每行一个操作，格式见题目描述。

输出格式

对于每次询问，输出一行一个整数表示答案。

由于答案可能很大，请输出它对 $536870912$ 取模后的结果，注意这不是一个质数。

4 4 
2 1 4 3 
0 2 3 4 5 
1 1 3 4 7 
2 1 1 
3 1 1 

7 
27 

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,q\leq 5\times 10^4$，$1\leq l\leq r\leq n$，$a,b$ 均在 $\text{int}$ 范围内。