题目描述

译自 ROI 2023 Day2 T3. Яблоки по корзинам

桌子上有萨沙的 $n$ 个苹果，它们的重量分别是整数 $w_1, w_2, \ldots, w_n$。她还有两个容量很大的篮子。

萨沙选择一个整数 $k$，然后只考虑重量不超过 $k$ 的苹果。之后，她可以把每个重量 $w_i \leq k$ 的苹果放到两个篮子中的一个，或者留在桌子上。重量 $w_i > k$ 的苹果无论如何都要留在桌子上。

如果萨沙能把一些重量不超过 $k$ 的苹果放到篮子里，使得第一个篮子里的苹果总重为 $x$，第二个篮子里的苹果总重为 $y$，那么我们就称数对 $(x, y)$ 是 $k$-可达的。如果对于所有满足 $0 \leq x \leq a$ 和 $0 \leq y \leq b$ 的 $x$ 和 $y$，数对 $(x, y)$ 都是 $k$-可达的，那么我们就称数对 $(a, b)$ 是 $k$-完美的。

萨沙有 $q$ 组数 $k, a, b$，对于每一组，她想知道数对 $(a, b)$ 是否是 $k$-完美的。

输入格式

第一行有两个整数 $n, q$（$1 \leq n, q \leq 3 \times 10^5$），表示萨沙有多少个苹果，以及你需要处理的查询的数量。

第二行有 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \leq w_i \leq 10^{12}$），表示萨沙的苹果的重量。

第三行有一个整数 $z$（$0 \leq z \leq 10^6$），用于生成需要回答的查询。

接下来的 $q$ 行是描述了 $q$ 个查询。查询从 $1$ 到 $q$ 编号。每行包含三个整数 $j, c, d$（$0 \leq j, c, d \leq 10^{18}$）。查询的参数根据这些数字按照以下规则生成。我们令 $v$ 表示在当前查询之前，满足查询中给定的数对 $(a, b)$ 是 $k$-完美的查询的编号之和。那么在当前查询中，$k = j - v \cdot z$，$a = c - v \cdot z$，$b = d - v \cdot z$。保证 $k, a, b \geq 0$。

注意，当 $z=0$ 时，$k, a, b$ 的值就分别等于 $j, c, d$。也就是说，查询的参数不依赖于之前查询的答案，而是在输入数据中明确给出的。

输出格式

对于每个查询，如果数对 $(a, b)$ 是 $k$-完美的，输出 Yes，否则输出 No。

样例 1

输入

8 5
17 1 3 2 100 5 6 1
0
6 15 3
9 4 4
5 15 3
17 34 1
16 33 2

输出

Yes
No
No
Yes
No

样例 2

输入

8 5
17 1 3 2 100 5 6 1
1
6 15 3
10 5 5
6 16 4
18 35 2
21 38 7

输出

Yes
No
No
Yes
No

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。