「yyOI R1」youyou 的序列

给定一个长度为 $n$ 的序列 $a_{1\dots n}$，以及 $q$ 次操作。 定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并**立即**询问所有以 $a_i \;( i\in [1,n])$ 为峰的[子序列](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97)数量之和，对 $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>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$ 值由如下方法得到： ```cpp 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$。