题目描述

克拉克有一个长度为 $n$ 的数列 $\left\{a_1,a_2,\dots,a_n\right\}$。对这个数列，克拉克会进行 $q$ 次询问。每一次询问他都会从数列取出一个子串；对于这个子串，他想知道这个子串的最长上升子序列是多长。

子串是指数列中连续的一部分构成的数列。我们用参数 $l,r$ 来表示子串 $\left\{a_l,a_{l+1},\dots,a_r\right\}$。

子序列是指数列中抽取若干个元素，按照原数列的顺序排列得到的新数列。例如 $\left\{a_3,a_4,a_6,a_8\right\}$ 就是数列 $\left\{a_2,a_3,a_4,a_5,a_6,a_7,a_8\right\}$ 的一个子序列。

上升数列是指除第一个元素外，其他每个元素都比前一个元素严格更大的数列。例如 $\left\{2,3,5,8\right\}$ 就是一个上升序列，而 $\left\{2,3,5,5\right\}$ 不是。

数列的长度是指数列的元素个数。

最长上升子序列是指一个数列所有可能的子序列中，是上升数列的最长的一个或若干个。

输入格式

第一行包含三个非负整数 $n,q,v$ 表示数列的长度，询问的个数和是否强制在线。其中 $v\in \{0,1\}$，分别表示不强制在线和强制在线。

接下来一行 $n$ 个正整数表示数列 $\left\{a_1,a_2,\dots,a_n\right\}$。对于 $1 \le i \le n$

保证 $1 \le a_i \le {{ args['a'] }}$。

接下来一行，包含 $8$ 个整数 $A,B,C,D,E,F,x_0, y_0$，表示生成询问的一些参数，保证 $1 \le A,B,C,D,E,F,x_0, y_0 \le n$。

对于 $1\le i \le q$，我们用这样的方式给出每组询问的子串：首先设 $s_i$ 为第 $i$ 个询问的答案，也就是最长上升子序列的长度；并设 $s_0=0$。然后令

$$x_i=Ax_{i-1}+By_{i-1}+C$$ $$y_i=Dx_{i-1}+Ey_{i-1}+F$$ $$l_i=\min\left\{\left(x_i+vs_{i-1}-1\right)\bmod n + 1, \left(y_i+vs_{i-1}-1\right)\bmod n + 1\right\} $$$$r_i=\max\left\{\left(x_i+vs_{i-1}-1\right)\bmod n + 1, \left(y_i+vs_{i-1}-1\right)\bmod n + 1\right\} $$

第 $i$ 个询问表示求 $\left\{a_{l_i},a_{ {l_i}+1},\dots,a_{r_i}\right\}$ 的最长上升序列长度。

输出格式

输出一行一个整数，表示 $\sum_{i=1}^{q}{i s_i} \bmod {{ args['Q'] }}$。

样例

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

13

10 10 0
145 902 747 599 493 789 49 310 831 667
5 2 2 5 5 3 2 2

14

子任务

- args: {n: 100, q: 30000}
  cases: [1, 2]
- args: {n: 3000, q: 30000}
  cases: [3, 4]
- args: {n: 50000, q: 30000}
  cases: [5, 6]
- args: {n: 3000, q: 1000000}
  cases: [7, 8]
- args: {n: 50000, q: 1000000}
  cases: [9, 10]
- args: {n: 50000, q: 3000000}
  cases: [11, 12]
- args: {n: 50000, q: 5000000}
  cases: [13, 14]
- args: {n: 100000, q: 5000000}
  cases: [15, 16]
- args: {n: 50000, q: 10000000}
  cases: [17, 18]
- args: {n: 100000, q: 10000000}
  cases: [19, 20]

此外，对于编号为奇数的测试点，满足 $v=0$；对于编号为偶数的测试点，满足 $v=1$。

在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 ${{ tl.len(prob.pre_cases) }}$ 个测试点，每个测试点的数据规模限制与对应编号的最终测试点相同。

注意：预测试数据的评测结果与最终评测结果没有关系。

提示

注意时间限制。