Саша có $n$ quả táo với trọng lượng nguyên $w_1, w_2, \ldots, w_n$ đang nằm trên bàn, cùng với hai chiếc giỏ có sức chứa lớn.
Саша chọn một số nguyên $k$ và xét các quả táo có trọng lượng không lớn hơn $k$. Sau đó, cô có thể đặt mỗi quả táo có trọng lượng $w_i \le k$ vào một trong hai giỏ, hoặc để nó trên bàn. Các quả táo có trọng lượng $w_i > k$ luôn được để lại trên bàn.
Gọi một cặp số $(x, y)$ là đạt được với $k$ nếu Саша có thể đặt một số quả táo có trọng lượng không lớn hơn $k$ vào các giỏ sao cho tổng trọng lượng táo trong giỏ thứ nhất bằng $x$ và tổng trọng lượng táo trong giỏ thứ hai bằng $y$. Gọi một cặp số $(a, b)$ là lý tưởng với $k$ nếu với mọi $x$ và $y$ thỏa mãn $0 \le x \le a$ và $0 \le y \le b$, cặp $(x, y)$ đều đạt được với $k$.
Саша xét $q$ bộ ba số $k, a, b$ và với mỗi bộ ba, cô muốn biết cặp $(a, b)$ có lý tưởng với $k$ hay không.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n$ và $q$, là số quả táo mà Саша có và số truy vấn bạn cần xử lý ($1 \le n, q \le 300\,000$).
Dòng thứ hai chứa $n$ số nguyên $w_1, w_2, \ldots, w_n$, là trọng lượng của các quả táo mà Саша có ($1 \le w_i \le 10^{12}$).
Dòng thứ ba chứa số nguyên $z$, được dùng để tạo các truy vấn cần trả lời ($0 \le z \le 10^6$).
Trong $q$ dòng tiếp theo là mô tả các truy vấn. Các truy vấn được đánh số từ $1$ đến $q$. Mỗi dòng chứa ba số nguyên $j, c, d$ ($0 \le j, c, d \le 10^{18}$). Truy vấn được tạo từ các số trên dòng đó theo quy tắc sau. Tính $v$ là tổng các số thứ tự của những truy vấn trước truy vấn hiện tại mà cặp $(a, b)$ trong truy vấn đó là lý tưởng với $k$. Khi đó, trong truy vấn hiện tại, $k = j - v \cdot z$; $a = c - v \cdot z$; $b = d - v \cdot z$. Đảm bảo rằng $k, a, b \ge 0$.
Lưu ý rằng khi $z = 0$ (điều này đúng trong phần lớn các nhiệm vụ con), các giá trị $k, a, b$ lần lượt bằng $j, c, d$. Nghĩa là các tham số của truy vấn không phụ thuộc vào câu trả lời cho các truy vấn trước đó và được cho tường minh trong dữ liệu vào.
Dữ liệu ra
Với mỗi truy vấn, in Yes nếu cặp $(a, b)$ trong truy vấn đó là lý tưởng với $k$; ngược lại, in No.
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn bổ sung: $n, q$ | Giới hạn bổ sung: $a, b$ | Giới hạn bổ sung: $k$ | Giới hạn bổ sung: $z$ | Nhiệm vụ con cần thiết |
|---|---|---|---|---|---|---|
| 1 | 9 | $n, q \le 10$ | $z = 0$ | |||
| 2 | 6 | $n \le 100$ | $a \le 100\,000$, $b = 0$ | $k = 10^{18}$ | $z = 0$ | |
| 3 | 3 | $b = 0$ | $k = 10^{18}$ | $z = 0$ | 2 | |
| 4 | 6 | $n, q \le 100$ | $a, b \le 300$ | $k = 10^{18}$ | $z = 0$ | |
| 5 | 6 | $n \le 100$ | $a, b \le 300$ | $k = 10^{18}$ | $z = 0$ | 4 |
| 6 | 2 | $n \le 1500$ | $a, b \le 1500$ | $k = 10^{18}$ | $z = 0$ | 4–5 |
| 7 | 6 | $n \le 5000$ | $a, b \le 5000$ | $k = 10^{18}$ | $z = 0$ | 4–6 |
| 8 | 2 | $a, b \le 200\,000$ | $k = 10^{18}$ | $z = 0$ | 2, 4–7 | |
| 9 | 9 | $k = 10^{18}$ | $z = 0$ | 2–8 | ||
| 10 | 3 | $b = 0$ | $z = 0$ | 2–3 | ||
| 11 | 6 | $n, q \le 100$ | $a, b \le 300$ | $z = 0$ | 4 | |
| 12 | 6 | $n \le 100$ | $a, b \le 300$ | $z = 0$ | 4–5, 11 | |
| 13 | 2 | $n, q \le 1500$ | $a, b \le 1500$ | $z = 0$ | 4, 11 | |
| 14 | 2 | $n \le 1500$ | $a, b \le 1500$ | $z = 0$ | 4–6, 11–13 | |
| 15 | 6 | $n \le 5000$ | $a, b \le 5000$ | $z = 0$ | 4–7, 11–14 | |
| 16 | 2 | $a, b \le 200\,000$ | $z = 0$ | 4–8, 11–15 | ||
| 17 | 6 | $z = 0$ | 1–16 | |||
| 18 | 18 | Ví dụ, 1–17 |
Ví dụ
Dữ liệu vào 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
Dữ liệu ra 1
Yes No No Yes No
Dữ liệu vào 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
Dữ liệu ra 2
Yes No No Yes No