循环位移

题目描述

小七给奶龙一个长度为 $n$ 的数组 $a_0,a_1,\cdots,a_{n-1}$, ($0 \le a_i<p$)，奶龙不喜欢数组死气沉沉的样子，于是他决定进行 $m$ 次操作让数组动起来。每次操作有两种形式：

1. 把当前的数组向右循环位移 $x$ 位，即 $a_{(i+x)\bmod n}:= a_i$

2. 令 $a_i=(a_i+x)\bmod p$（$p$ 事先给定）。

充满好奇心的奶龙想要知道每次操作后整个数组的逆序对数，你能帮帮他吗？

输入格式

第一行包含两个正整数 $n,m,p$，分别为数组大小和操作次数，以及事先给定的参数 $p$。

第二行包含 $n$ 个整数，依次为 $a_0,a_1,\cdots,a_n$。

接下来 $m$ 行，每行包含两个整数 $o,x(o\in\{0,1\},0\le x< p)$ 描述一次操作。若 $o$ 为 $0$ 表示这是第一种操作，否则为第二种操作。

输出格式

共 $m$ 行，每行一个整数表示当前数组的逆序对数。

样例 #1

样例输入 #1

4 2 10
0 4 2 8
0 2
1 9

样例输出 #1

3
2

样例 #2

样例输入 #2

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

样例输出 #2

4
6
4

数据范围

对于所有数据，保证 $1\le n,m\le 10^6,2\le p\le 10^9,0\le a_i<p$。