Rikka 正全力奔向比赛场地。

EC Final 的规模越来越大……因此，越来越多的计算机被连接到脆弱的 2000W 主电线上，每一排都在积聚热量。

当 Rikka 进入大厅时，她发现 LCR 正在和志愿者们一起重新布置电线。然而，她除了观察之外，似乎帮不上什么忙。

“听着，我们没有时间计算新电路的参数了。你擅长数据结构吗？请帮帮我们……”

电路是一个包含 $n$ 个节点的序列，总共有 $m$ 个可能的节点等级，编号从 $1$ 到 $m$。由于一个 $k$ 级节点的功率限制是 $(k-1)$ 级节点的两倍，Rikka 可以将两个相邻的 $k$ 级节点合并为一个 $(k+1)$ 级节点（前提是 $k < m$）。她也可以在任何时候从电路中移除任何节点，同时保持其余节点的顺序不变。

志愿者们总共有 $q$ 次询问。每次询问包含一个区间 $[l, r]$ 和一个整数等级 $k$。Rikka 需要计算指定区间内有多少个子区间（即满足 $l \le x \le y \le r$ 的区间 $[x, y]$）可以提供一个 $k$ 级节点。这意味着可以通过合并相同等级的相邻节点并移除节点，将电路序列 $[x, y]$ 转化为一个单一的 $k$ 级节点，其中这两种操作可以以任意顺序执行多次。注意，最终节点的等级必须恰好为 $k$，不能更高或更低。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 2 \times 10^5$)，分别表示电路序列的长度、最大等级和询问次数。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$ ($1 \le A_i \le m$)，表示节点的等级序列。

接下来的 $q$ 行，每行包含三个整数 $l, r, k$ ($1 \le l \le r \le n, 1 \le k \le m$)，描述一个询问。

同一行中的多个整数由空格分隔。

输出格式

输出 $q$ 行，每行包含一个整数，即该询问的答案。

样例

样例输入 1

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

样例输出 1

15
10
3
0
0

样例输入 2

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

样例输出 2

9
10
9
6
1