UOJ Logo Zijian Online Judge

ZOJ

Statistics

平面上有 $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}$

下载

样例数据下载