题目描述

对于一个序列 $A$ 和正整数 $k$，定义 $f(A,k)$ 为下面算法的输出：

算法流程

• 初始化空序列 $T$，计数器 $m=0$。
• 遍历 $i=1,2,\cdots,|A|$：
  • 重复执行以下操作，直到 $T$ 为空或者 $A_{T_{|T|}} < A_i$：
    • 删除 $T$ 的末尾元素 $T_{|T|}$。
  • 重复执行以下操作，直到 $T$ 为空或者 $T_1 > i-k$：
    • 删除 $T$ 的开头元素 $T_{1}$。
  • 向 $T$ 的末尾加入 $i$。
  • $m \gets m+|T|$。
• 输出 $m$ 的值。

给定一个序列 $X=[X_1,X_2,\cdots,X_n]$。

现在有 $q$ 次询问，第 $i$ 次给定 $l_i,r_i,k_i$，请求出 $f([X_{l_i},X_{l_i+1},\cdots,X_{r_i}],k_i)$ 的值。

输入格式

第一行 $2$ 个整数 $n,q$。

第二行 $n$ 个整数 $X_1,X_2,\cdots.X_n$。

接下来 $q$ 行，第 $i$ 行 $3$ 个整数 $l_i,r_i,k_i$。

输出格式

设第 $i$ 次询问的答案为 $f_i$。

由于一些特别的原因，请输出 $\displaystyle \bigoplus_{i=1}^{n} (i^2+f_i)$ 的值。

样例

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

9

说明/提示

对于 $100\%$ 的数据：

• $1 \le n,q \le 2 \times 10^5$；
• $X$ 为 $1 \sim n$ 的排列；
• $1 \le l_i \le r_i \le n,1 \le k_i \le n$。

本题开启捆绑测试。

• Subtask #1（$10 \ \text{pts}$）：$n,q \le 3000$。
• Subtask #2（$5 \ \text{pts}$）：$k_i=1$。
• Subtask #3（$5 \ \text{pts}$）：$k_i=2$。
• Subtask #4（$5 \ \text{pts}$）：$X_i=i$。
• Subtask #5（$5 \ \text{pts}$）：$X_i=n-i+1$。
• Subtask #6（$10 \ \text{pts}$）：$n \le 3000$。
• Subtask #7（$15 \ \text{pts}$）：每次询问 $r_i=n$。
• Subtask #8（$15 \ \text{pts}$）：$k_i \ge r_i-l_i+1$。
• Subtask #9（$10 \ \text{pts}$）：$|X_i-i| \le 3$。
• Subtask #10（$20 \ \text{pts}$）：无特殊限制。