题目描述

译自 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\cdot 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$-完美的，输出 Үеs，否则输出 No。

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

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$ 是样例。