题目背景

翻译自 ROI 2023 D2T3。

淘淘有 $n$ 个整数重量的苹果，它们分别为 $w_1,w_2,\dots,w_n$，这些苹果放在桌子上，同时有两个容量足够大的篮子。

淘淘选择一个整数 $k$，他可以将每个重量 $w_i \le k$ 的苹果放入其中一个篮子，也可以将其留在桌子上。重量大于 $k$ 的苹果将始终留在桌子上。

如果淘淘能够将重量不超过 $k$ 的苹果放入篮子中，使得第一个篮子中苹果的重量之和等于 $x$，而第二个篮子中苹果的重量之和等于 $y$，则称 $(x, y)$ 是 $k$ 的可达到对。如果对于所有满足 $0 \le x \le a$ 和 $0 \le y \le b$ 的 $x$ 和 $y$，$(x, y)$ 都是 $k$ 可达到的，则称 $(a, b)$ 是 $k-\!$ 完美的。

题目描述

淘淘会询问你 $q$ 次，请你判断对于每个 $(k,a,b)$ 三元组，$(a, b)$ 是否是 $k-\!$ 完美的。

输入格式

第一行给出两个整数 $n$ 和 $q$，表示淘淘拥有的苹果数量和要处理的查询数量（$1 \le n, q \le 300,000$）。

第二行给出 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示陶陶拥有的苹果的重量（$1 \le w_i \le 10^{12}$）。

第三行给出一个整数 $z$，在接下来的输入中会用到（$0 \le z \le 10^6$）。

接下来的 $q$ 行给出查询的描述。查询编号从 $1$ 到 $q$。每行包含三个整数 $j,c,d$（$0 \le j, c, d \le 10^{18}$），表示这个查询中的 $k = j - v \times z,a = c - v \times z,b = d - v \times z$，其中 $v$ 是在这个查询前答案为 Yes 的询问的编号和。保证 $k,a,b \ge 0$。

在本题中，大多数测试点的 $z$ 都等于 $0$，此时 $k,a,b$ 的值分别等于 $j,c,d$。

输出格式

对于每个查询，如果在该查询中 $(a, b)$ 对是 $k-\!$ 完美的，则输出 Yes，否则输出 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

提示