AT_past202004_m.食堂

一些公司自助餐厅的菜单是以 $d$ 日为周期的。它的菜肴由整数表示，在第 $i$ 天、第 $i+d$ 天、第 $i+2d$ 天等时间供应菜肴 $c_i$，今天是第 $1$ 天。

使用这家自助餐厅的 $n$ 名员工对食物很挑剔，员工 $j$ 喜欢第 $k_j$ 道菜。每个员工都会在上桌并拿到最喜欢的菜的那一天使用自助餐厅。在其他日子里，员工只有在最后一天使用时是 $l$ 天前才使用自助餐厅。但是，当他/她第一次使用时，上述规定不适用（如下所述）。

对于每个满足 $1≤j≤n$ 的整数 $j$ ，回答以下问题：

假设员工 $j$ 在第 $f_j$ 天第一次使用自助餐厅。（仅限于这一天，即使提供的菜不是他/她最喜欢的，他/她也会使用。此外，假设他/她在这一天之前不能使用自助餐厅，即使提供了他/她喜欢的菜。）计算员工 $j$ 在使用 $t_j$ 次自助餐厅之前获得最喜欢的菜的次数。

第一行：$d,l,n$

第二行：$c_1,c_2,...,c_d$

接下来 $n$ 行：第 $i$ 行为 $k_i,f_i,t_i$

$n$ 行，第 $j$ 行为员工 $j$ 在使用 $t_j$ 次自助餐厅之前获得最喜欢的菜的次数。

输入输出样例 #1 说明

自助餐厅以 $4$ 天为周期供应菜肴：$\{2,3,1,3\}$。

员工 $1$ 喜欢第 $1$ 道菜。他在第 $2$ 天先吃第 $3$ 道菜，然后在第 $3$ 天吃第 $1$ 道菜。因此，他得到了他最喜欢的一道菜，我们应该输出 $1$。

员工 $2$ 喜欢第 $3$ 道菜。他只在第 $3$ 天吃了第 $1$ 道菜。因此，他得到了他最喜欢的菜 $0$ 次，我们应该输出 $0$。

员工 $3$ 喜欢第 $3$ 道菜。他先在第 $4$ 天吃第 $3$ 道菜，然后在第 $6$ 天吃第 $3$ 道菜，最后在第 $8$ 天吃第 $3$ 道菜。因此，我们应该输出 $3$。

输入输出样例 #2 说明

自助餐厅每天都提供菜肴 $1$。

员工 $1$ 喜欢第 $2$ 道菜。他首先在第 $1$ 天吃了菜肴 $1$，然后又由于 $l=1$，他在第 $2$ 天和第 $3$ 天都吃的是菜肴 $1$。餐厅从不提供他最爱吃的菜，所以输出 $0$。

员工 $2$ 和员工 $3$ 喜欢第 $1$ 道菜。他们每天都能吃到他们最喜欢吃的菜，所以都输出 $3$。

数据规模与约定

$1 \le n,d,c_i,k_j \le 10^5$；

$1 \le l,t_j \le 10^9$，$1 \le f_j \le d$；

输入的数值均为整数。