Denny 正在为班级旅行做准备。Denny 计划带上几件物品。他将这些物品排成一行，并从 $1$ 到 $n$ 进行编号。对于每件物品，Denny 都知道它的重量 $w_i$。Denny 准备带去的背包容量为 $c$，因此 Denny 可以带上总重量不超过 $c$ 的若干件物品。

不幸的是，Denny 在做决定方面非常糟糕。他无法决定旅行中哪些物品更有用。此外，他不喜欢携带太多东西，所以他可能不会把背包完全装满。为了帮助自己做出选择，Denny 决定对要选择的物品设置额外的约束。

现在 Denny 生成了各种约束计划。每个计划都是一个三元组 $(l_j, r_j, t_j)$，其中 $1 \le l_j \le r_j \le n$ 且 $0 \le t_j \le c$。为了满足计划的约束，Denny 必须选择编号在 $l_j$ 到 $r_j$（包含边界）之间的若干件物品，使得它们的总重量恰好等于 $t_j$。对于每个计划，Denny 都想立即知道它是否可以被满足。请帮帮他！

输入格式

输入文件包含多个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2000$)。每个测试用例的第二行包含 $n$ 个整数 $w_i$ ($1 \le w_i \le 100$)。第三行包含背包的容量 $c$ ($1 \le c \le 1000$)。第四行包含 $q$ —— Denny 计划提出的方案数量 ($1 \le q \le 300\,000$)。接下来的 $q$ 行描述了这些计划。

第 $j$ 个计划由三个整数 $a_j, b_j, c_j$ 描述 ($0 \le a_j < n, 1 \le b_j \le n, 0 \le c_j \le c$)。设在该测试用例中，第 $j$ 个计划之前已经有 $k$ 个计划是可以被满足的。使用以下公式计算该计划的参数：$l_j = (a_j + k) \pmod{n - b_j + 1} + 1$，$r_j = l_j + b_j - 1$，以及 $t_j = (c_j + k) \pmod{c + 1}$。

最后一个测试用例之后会有一行包含单个数字 $0$，该行不应被处理。所有测试用例的 $n$ 之和不超过 $2000$。所有测试用例的 $q$ 之和不超过 $300\,000$。

输出格式

对于每个测试用例，输出一行字符 'Y' 和 'N'。对于每个计划，如果可以满足则输出 'Y'，否则输出 'N'。

样例

输入 1

5
2 3 4 5 9
10
5
0 3 5
0 2 4
0 3 4
0 4 6
2 3 5
0

输出 1

YNYYN

说明 1

在给定的样例中，计划分别为 $(1, 3, 5), (2, 3, 5), (2, 4, 5), (1, 4, 8), (3, 5, 8)$。