注意：修改过程中没有取模。

为了避免没有任何得分，我们将数据点1的数据模数改为2。

题目背景

这题不是数学题。但是这题可能很难。

题目描述

给你一个长度为 $n$ 的序列 $a$

进行 $q$ 次两个操作

1 l r ，求$\sum_{i=l}^ra_i\pmod p$

2 l r ，$\forall l\le i\le r,k^{a_i} ->a_i$

对于操作1，输出求出答案

输入格式

第一行四个整数 $n,q,p,k$

第二行 $n$ 个整数表示 $a$

接下来 $q$ 行输入opt,l,r

输出格式

对于每个 $1$ 操作，输出询问的答案

样例输入

4 4 7 2
1 2 3 4
2 1 4
1 2 4
2 1 4
1 1 3

样例输出

0
3

样例解释

第一次修改后，数组变成

$2,4,8,16$

第二次修改后，数组变成

$4,16,256,65536$

数据范围和提示

$n,q\le 10^5,a_i,k\le p\le 10^8$

不保证 $p$ 是质数

$n^2log p$ 20分

$n^2$ 40分

相信现代计算机的速度。

目前数据可能有点水，过后有可能修改数据