平面上有 $n$ 个点，第 $i$ 个点的横坐标为 $i$，纵坐标为 $Y_i$。每个点可以平行于 $y$ 轴向上或向下移动任意的距离。

现在有 $q$ 个指令，每个指令形如 $(a, l, r)$，表示要将横坐标在 $[l, r]$ 中的点，经过一系列移动移动后，与点 $(a, Y_a)$ 同在斜率为 $k$ 的直线上。

对于每个指令，你需要回答最小的移动距离总和。

注意：对于每个指令，$k$ 是固定的，且每个指令执行后重置为初始状态。

输入格式

第一行三个正整数 $n, q, k$。

第二行 $n$ 个正整数，第 $i$ 个数表示 $Y_i$。

接下来 $q$ 行，每行三个正整数 $a, l, r$。

输出格式

输出 $q$ 行，每行一个非负整数，表示最小的移动距离总和。

样例一

input

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

output

0
7
9

样例二

见样例数据下载

限制与约定

对于 $20\texttt{%}$ 的数据，$n, q \le 1000$

对于另外 $10\texttt{%}$ 的数据，有 $Y_1 = Y_2 = Y_3 = ⋯ = Y_n$

对于另外 $10\texttt{%}$ 的数据，所有指令中 $a = 1$

对于另外 $40\texttt{%}$ 的数据，$k = 0$

对于 $100\texttt{%}$ 的数据，$1 \le n, q \le 10^5$，$1 \le l \le r \le n$，$1 \le a \le n$，$0 \le k, Y_i \le 10^6$

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载