← 返回题目列表

Codeforces · 1709/D

D. 滚滚滚滚机器人

中文机器翻译题面 查看原题

有一个网格,由 $$$n$$$ 行和 $$$m$$$ 列组成。行从下到上编号为 $$$1$$$ 到 $$$n$$$。这些列从左到右编号为 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 列的底部 $$$a_i$$$ 单元格已被阻止($$$1, 2, \dots, a_i$$$ 行中的单元格),其余 $$$n - a_i$$$ 单元格未被阻止。

一个机器人正在该网格上行进。您可以向它发送命令 - 向上、向右、向下或向左移动。如果机器人试图进入被封锁的单元格或网格外,它就会爆炸。

然而,机器人坏了——它执行每个收到的命令 $$$k$$$ 次。因此,例如,如果您告诉它向上移动,它将向上移动 $$$k$$$ 次($$$k$$$ 单元格)。当机器人执行当前命令时,您无法向它发送命令。

系统会向您询问有关机器人的 $$$q$$$ 个问题。每个查询都有一个起始单元格、一个结束单元格和一个值 $$$k$$$。您能否向机器人发送任意数量的命令(可能为零),以便它从起始单元到达结束单元,假设它执行每个命令 $$$k$$$ 次?

机器人必须停在终点单元中。如果它在执行命令的同时访问完成单元,则不算数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — 网格的行数和列数。

第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \dots, a_m$$$ ($$$0 \le a_i \le n$$$) — 第 $$$i$$$ 列底部被阻止的单元格数量。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含五个整数 $$$x_s、y_s、x_f、y_f$$$ 和 $$$k$$$ ($$$a[y_s] < x_s \le n$$$; $$$1 \le y_s \le m$$$; $$$a[y_f] < x_f \le n$$$; $$$1 \le y_f \le m$$$; $$$1 \le k \le 10^9$$$) — 起始单元格的行和列、结束单元格的行和列以及每个命令的执行次数。每个查询的开始和结束单元格都被解锁。

输出

对于每个查询,如果您可以向机器人发送任意数量的命令(可能为零),以便它从起始单元格到达结束单元格(假设它执行每个命令 $$$k$$$ 次),则打印“YES”。否则,打印“NO”。

示例

输入 #1

11 10
9 0 0 10 3 4 8 11 10 8
6
1 2 1 3 1
1 2 1 3 2
4 3 4 5 2
5 3 11 5 3
5 3 11 5 2
11 9 9 10 1

输出 #1

YES
NO
NO
NO
YES
YES