U23100.流水线

有一家工厂 $A$，里面有一条“流水线”。是的，真的是有“流水”。这条流水线上有 $n$ 个产品，每个产品有一个“合格程度”，$a_i$ 代表第 $i$ 个产品的合格程度。当然，$i \in [1,n]$。一段产品的合格指数 $S$ 为这段产品里的合格程度最大的与最小的之差。
工厂 $A$ 的老板现在要视察工作，他想知道 $q$ 个区间的合格指数。哦对了，前面说过，这是一条流水线，所以流水线上的所有产品都会以每秒 $k$ 个单位长度的速度向右流去。第 $0$ 秒时，第 $i$ 个产品处于位置 $i$ 上。现在，你作为新被提拔上来的人，自然是要回答老板的问题了。

第一行是三个正整数 $n,q,k$，分别表示产品的数量、老板的问题个数 $-1$ 以及流水的速度。
第二行是 $n$ 个正整数，第 $i$ 个数是 $a_i$，代表第 $i$ 个产品的合格程度。
接下来 $q-1$ 行，每行三个正整数 $l,r,t$，$l,r$ 表示老板想要知道的合格指数的位置的区间，而 $t$ 表示老板问问题的时间。

有 $q-1$ 行输出， 第 $i$ 行代表第 $i$ 个问题的答案。当然，$i \in [1,q)$。

样例解释

对于询问 $1$，此时位置 $1$ ~ $4$ 的产品的合格程度为 $1\ 4\ 2\ -3$。该区间的合格指数为 $4-(-3)=7$。
对于询问 $2$，此时位置 $3$ ~ $4$ 的产品的合格程度为 $1\ 4$。该区间的合格指数为 $4-1=3$。
对于询问 $3$，此时位置 $100$ ~ $104$ 的产品的合格程度为 $1\ 4\ 2\ -3\ 5$。该区间的合格指数为 $5-(-3)=8$。
故答案为 $7\ 3\ 8$。

---

数据范围

对于 $40\%$ 的数据，$1 \leq n,q \leq 10^3$。
对于 $100\%$ 的数据，$1 \leq n,q \leq 5 \times 10^5$，$0 \leq k,t \leq 10^7$，$|a_i| \leq 10^8$，$l,r$ 不会超出产品的位置的最大值与最小值。
请注意巨大的读入读出对程序所造成的影响。