题目描述

鸽子在下飞行棋。众所周知，一般来说，在飞行棋中，你掷到的点数在 $6$ 以内越大，对你越有利。现在，我们定义鸽子掷到的点数：在一条 $n$ 个节点的链上，每条边都有一个点数，鸽子将在 $k$ 步内从节点 $x$ 走到 $y$，每步只能走一条边，一条边可以经过多次，一个节点也可以经过多次。而在飞行棋中，你所掷到的点数不能超过一个定值。所以这个点数为路径上点数之和对 $mod$ 取模后的值。由于一些原因，在一盘棋中，链都是一样的。鸽子将每次给定三个数 $x,y,k$，询问你鸽子能掷到的最大的点数。

输入格式

第一行三个整数 $n,m,mod$ 分别表示链上节点数、询问数和模数。

接下来一行 $n-1$ 个整数 $a_i$ 表示节点 $i$ 和 $i+1$ 之间有一条点数为 $a_i$ 的边。

接下来 $m$ 行，每行三个整数 $x,y,k$，表示一次询问。

输出格式

$m$ 行，每行一个整数，表示答案。如果无解，输出 $-1$。

样例一

input

4 2 111
97 70 84
4 1 6
2 1 4

output

86
97

下发样例二到六分别对应子任务一到五。 下发样例

限制与约定

对于所有数据，满足 $1 \le n \le 500,1 \le m,mod \le 200,0 \le a_i < mod,1 \le x,y \le n,1 \le k \le 10^9$。