Đại lộ JOI là một con đường dài \(L\) mét theo hướng đông-tây. Điểm trên đường cách đầu phía tây \(l\) mét (\(0 \le l \le L\)) được gọi là vị trí \(l\).

Năm nay, cuộc thi marathon đầu tiên trên đại lộ JOI sẽ được tổ chức. Cuộc thi có luật khác với marathon thông thường:

• Trước cuộc thi, có \(N\) quả bóng được đặt trên đường. Quả bóng thứ \(i\) (\(1 \le i \le N\)) nằm tại vị trí \(X_i\). Nhiều quả bóng có thể nằm ở cùng một vị trí.
• Người tham gia xuất phát tại vị trí được chỉ định.
• Người tham gia phải thu nhặt đủ \(N\) quả bóng và mang tất cả chúng đến vị trí đích được chỉ định trong thời gian cho phép để hoàn thành cuộc thi. Sau khi nhặt một quả bóng, nếu đặt nó xuống đường thì người tham gia sẽ bị loại.

Vị trí xuất phát, vị trí đích và thời gian cho phép chưa được công bố, nhưng đã biết chúng sẽ được chọn trong \(Q\) kịch bản. Ở kịch bản thứ \(j\) (\(1 \le j \le Q\)), người tham gia xuất phát tại vị trí \(S_j\), về đích tại vị trí \(G_j\), với thời gian cho phép là \(T_j\) giây.

Rie sẽ tham gia cuộc thi. Cô mất \(1\) giây để nhặt một quả bóng. Khi đang mang \(x\) quả bóng, cô mất \(x+1\) giây để di chuyển \(1\) mét trên đường.

Cho thông tin về đại lộ JOI, các quả bóng và các kịch bản, hãy xác định với từng kịch bản liệu có cách để Rie hoàn thành cuộc thi hay không.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N L
X_1 X_2 ... X_N
Q
S_1 G_1 T_1
S_2 G_2 T_2
...
S_Q G_Q T_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu tồn tại cách để Rie hoàn thành cuộc thi ở kịch bản thứ \(j\), hoặc No nếu không tồn tại.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le L \le 500\,000\).
• \(0 \le X_i \le L\) (\(1 \le i \le N\)).
• \(1 \le Q \le 500\,000\).
• \(0 \le S_j \le L\) (\(1 \le j \le Q\)).
• \(0 \le G_j \le L\) (\(1 \le j \le Q\)).
• \(1 \le T_j \le 500\,000\) (\(1 \le j \le Q\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 7 điểm: \(N \le 7\), \(Q \le 10\), \(S_j=0\) và \(G_j=0\) với mọi \(1 \le j \le Q\).
2. 7 điểm: \(N \le 7\), \(Q \le 10\).
3. 10 điểm: \(N \le 14\), \(Q \le 10\).
4. 28 điểm: \(N \le 100\), \(Q \le 10\).
5. 10 điểm: \(N \le 2\,000\), \(Q \le 10\).
6. 19 điểm: \(N \le 2\,000\).
7. 19 điểm: Không có ràng buộc bổ sung.

Ví dụ

3 100
30 80 30
3
0 100 403
0 100 300
0 100 262

Yes
Yes
No

3 100
30 80 30
3
0 0 403
0 0 300
0 0 262

Yes
No
No

6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600

No
Yes
No
Yes

Nguồn

Marathon Race 2, JOI 2024, vòng chung kết quốc gia, bài 3 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.