线段树
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

现在给你一串数字，a1,a2,a3…an，你需要进行m次如下几种操作：
1 l r v，区间a[l]到a[r]的所有数字全部加v。
2 l r v，区间a[l]到a[r]的所有数字全部乘v。
3 l r，求区间a[l]到a[r]之间两两之间数字的乘积和(例如：2，3，4，5两两之间乘积和为 2*3+2*4+2*5+3*4+3*5+4*5)
现在给出你操作的顺序，按照要求操作或者输出。

输入描述:

第一行,一个数字T，表示有T组数据。
每组数据，第一行三个数值，n，m，p，表示有n个数字，有m个操作，p为模数，所有算术操作均要取模。
第二行，n个数字，表示初始序列
接下来m行，每行第一个数为操作方法opt，
若opt=1或者2，则后面跟着三个数l，r，v，若opt=3，则后面跟着两个数字l，r其含义如题所示

 

保证所有输入均在int范围内，所有数字均为整数，其中p为素数，保证数据合法。

输出描述:

对于每次操作3，输出一行一个数字ans（mod p），表示答案。
示例1

输入

复制 
1
5 6 1000000007
0 0 0 0 0
1 1 5 1
3 1 5
2 2 4 2
2 3 3 2
3 1 3
3 1 1

输出

复制 
10
14
0

备注: