$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1038}$

$\texttt{L}\color{red}\texttt{enstar}\color{black}\texttt{'s Problem}$

给定一个长度为 $n$ 的数列 $a$ ，和 $q$ 个询问，每次询问给定两个数 $l,r$ 。

定义一个区间的 $[l,r]$ 的权值 $val_{l,r}$ 为：

val_{l,r}=(\max\limits^r_{i=l}a_i)\times(\prod\limits^{r}_{i=l}a_i)

即 $val_{l,r}$ 的值等于 $[l,r]$ 的区间积乘上 $[l,r]$ 的区间最大值。

对于每个询问，你需要回答下面这个式子的值：

(\sum\limits^r_{i=l}\sum\limits^{r}_{j=i}val_{i,j})\ \text{mod}\ p

同时题目会给定一个 $type$ ，对于给定的询问 $l,r$ ，你需要做出如下转化：

l=(lastans\times type+l)\ \text{mod}\ n+1\\ r=(lastans\times type+r)\ \text{mod}\ n+1

其中 $lastans$ 表示上一次询问的答案。特别地，对于第一个询问，令 $lastans=0$ 。

第一行给定一个正整数 $num$ 表示该测试点编号。特别地，样例中的 $num$ 表示该样例符合第 $num$ 个测试点的范围。

第二行给定四个整数 $n,q,p,type$ 。

第三行给定 $n$ 个整数，表示数列 $a$ 。

接下来 $q$ 行，每行给定两个整数 $l,r$ 。

对于每个询问，每行给出一个答案。


xxxxxxxxxx
1
4

对于样例，取模之前的答案分别为 $31$ 和 $19$ 。

本题的数据范围参见下表：

测试点编号	$n$	$q$	$\|a_i\|$	特殊性质
$1$	$\leq10$	$\leq10$	$\leq10$	$\text{A,B}$
$2$	$\leq100$	$\leq100$	$\leq100$	$\text{A,B}$
$3$	$\leq100$	$\leq100$	$\leq100$	$\text{A}$
$4$	$\leq10^3$	$\leq10^3$	$\leq{10^3}$	$\text{A,B}$
$5$	$\leq10^3$	$\leq10^3$	$\leq{10^3}$	$\text{A}$
$6$	$\leq10^3$	$\leq10^3$	$\leq{10^3}$	$\text{B}$
$7$	$\leq2\times10^4$	$\leq2\times10^4$	$\leq2\times10^4$	$\text{A,B}$
$8$	$\leq5\times10^4$	$\leq2\times10^4$	$\leq5\times10^4$	$\text{B}$
$9$	$\leq10^5$	$\leq10^5$	$\leq10^5$	无
$10$	$\leq10^5$	$\leq10^5$	$\leq10^5$	无

同时，对于 $100\%$ 的数据，满足 $2\leq p\leq 2\times 10^9,1\leq l\leq r\leq n,0\leq type\leq 100$ 。