题目描述

给定一个长度为 $n$ 的序列 $a_{1\dots n}$，以及 $q$ 次操作。

定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并立即询问所有以 $a_i \;( i\in [1,n])$ 为峰的子序列数量之和，对 $4294967296$ 取模。这里的交换是暂时的，也就是说，它仅在下一次操作前有效。

在此我们认为，一个长度至少为 $1$ 的序列 $[a_1,a_2 ,\cdots,a_{s-1},a_s,a_{s+1},\cdots,a_{n-1},a_n ]$，满足 $a_1<a_2<\cdots<a_{s-1}a_{s+1}>\cdots >a_{n-1}>a_n$，则称此序列为以 $a_s$ 为峰的序列。

你的任务是回答出所有操作的答案。

输入格式

第一行输入两个整数 $n,q$。

第二行输入 $n$ 个正整数，表示一开始的序列 $a_{1\dots n}$。

第三行，输入一个整数 $k$，表示进行第一次操作（定义见上），保证 $1\le k <n$。

---

第 $2$ 到第 $q$ 次操作的 $k$ 值由如下方法得到：

int Answer(unsigned int ans)
{
    unsigned int BASE=998244353ll*ans+ans*ans+ans/9991+ans%2159;
    BASE^=9810;
    BASE^=51971;
    BASE=BASE>>7;
    BASE=BASE<<11;
    BASE^=751669;
    BASE^=23465695622566ll;
    return BASE%(n-1)+1;
}

当你每完成一次询问后，将你这次询问的答案 $ans$ 作为参数，恰好调用一次 Answer(ans) 。

得到的返回值即为下一次操作的 $k$。

注意：本输入方式仅用于减少输入量，标准算法不依赖于此输入方式。

输出格式

你需要输出所有操作的答案，每个答案输出一行。

4 3
1 5 7 3
1

12
13
13

5 5
7 7 7 7 6
1

9
9
9
9
9

提示

样例解释 #1

第一次操作的 $k$ 为 $1$。

此时序列为 $[5,1,7,3]$。

峰为 $a_1$：$[5]$，$[5,1]$，$[5,3]$。

峰为 $a_2$：$[1]$。

峰为 $a_3$：$[7]$，$[5,7]$，$[1,7]$，$[7,3]$，$[5,7,3]$，$[1,7,3]$。

峰为 $a_4$：$[3]$，$[1,3]$。

共计 $12$ 个不同的子序列，答案输出 $12$。

第二次和第三次操作的 $k$ 均为 $3$ ，此时有 $13$ 个不同的序列满足条件。

样例解释 #2

第一次操作的 $k$ 为 $1$。

此时序列为 $[7,7,7,7,6]$。

峰为 $a_1$：$[7]$，$[7,6]$。

峰为 $a_2$：$[7]$，$[7,6]$。

峰为 $a_3$：$[7]$，$[7,6]$。

峰为 $a_4$：$[7]$，$[7,6]$。

峰为 $a_5$：$[6]$。

共计 $9$ 个不同的子序列，答案输出 $9$。

后四次操作同理。

---

数据范围

本题采用捆绑测试。

子任务编号	$n$	$q$	分数
$1$	$\le 500$	$\le 100$	$10$
$2$	$\le2\times10^3$	$\le 5\times10^3$	$20$
$3$	$\le3\times10^4$	$\le 10^4$	$30$
$4$	$\le10^6$	$\le10^6$	$40$

对于 $100\%$ 的数据，$2\le n\le10^6$，$1\le q\le10^6$，$1\le a_i\le10^4$。