CF1709D.Rorororobot

There is a grid, consisting of $n$ rows and $m$ columns. The rows are numbered from $1$ to $n$ from bottom to top. The columns are numbered from $1$ to $m$ from left to right. The $i$-th column has the bottom $a_i$ cells blocked (the cells in rows $1, 2, \dots, a_i$), the remaining $n - a_i$ cells are unblocked.

A robot is travelling across this grid. You can send it commands — move up, right, down or left. If a robot attempts to move into a blocked cell or outside the grid, it explodes.

However, the robot is broken — it executes each received command $k$ times. So if you tell it to move up, for example, it will move up $k$ times ($k$ cells). You can't send it commands while the robot executes the current one.

You are asked $q$ queries about the robot. Each query has a start cell, a finish cell and a value $k$. Can you send the robot an arbitrary number of commands (possibly, zero) so that it reaches the finish cell from the start cell, given that it executes each command $k$ times?

The robot must stop in the finish cell. If it visits the finish cell while still executing commands, it doesn't count.

有一个由 $n$ 行 $m$ 列组成的网格。行从下到上编号为 $1$ 至 $n$，列从左到右编号为 $1$ 至 $m$。第 $i$ 列的底部 $a_i$ 个单元格被阻塞（即第 $1, 2, \dots, a_i$ 行中的单元格），其余 $n - a_i$ 个单元格未被阻塞。

一个机器人在该网格中移动。你可以向它发送指令：向上、向右、向下或向左移动。如果机器人试图移入一个被阻塞的单元格或移出网格边界，它将爆炸。

然而，该机器人已损坏——它会将每条接收到的指令执行 $k$ 次。例如，若你命令它向上移动，它将连续向上移动 $k$ 次（即跨越 $k$ 个单元格）。在机器人执行当前指令期间，你无法发送新的指令。

你需要处理 $q$ 个关于该机器人的查询。每个查询包含一个起始单元格、一个目标单元格以及一个参数值 $k$。是否存在一个（可能为空）指令序列，使得机器人能从起始单元格出发，恰好停在目标单元格上（注意：机器人必须最终停止于目标单元格；若其在执行某条指令的过程中途经目标单元格，不视为成功到达）？

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^9$; $1 \le m \le 2 \cdot 10^5$) — the number of rows and columns of the grid.

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($0 \le a_i \le n$) — the number of blocked cells on the bottom of the $i$-th column.

The third line contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines contain five integers $x_s, y_s, x_f, y_f$ and $k$ ($a[y_s] \lt x_s \le n$; $1 \le y_s \le m$; $a[y_f] \lt x_f \le n$; $1 \le y_f \le m$; $1 \le k \le 10^9$) — the row and the column of the start cell, the row and the column of the finish cell and the number of times each your command is executed. The start and the finish cell of each query are unblocked.

第一行包含两个整数 $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] \lt x_s \le n$；$1 \le y_s \le m$；$a[y_f] \lt x_f \le n$；$1 \le y_f \le m$；$1 \le k \le 10^9$）—— 分别表示起点单元格的行号与列号、终点单元格的行号与列号，以及每次指令执行的次数。每个查询的起点与终点单元格均未被封锁。

For each query, print "YES" if you can send the robot an arbitrary number of commands (possibly, zero) so that it reaches the finish cell from the start cell, given that it executes each command $k$ times. Otherwise, print "NO".

对于每个查询，如果可以向机器人发送任意数量（可能为零）的指令，使得它从起始单元格出发，在执行每条指令 $k$ 次后恰好到达终点单元格，则输出 "YES"；否则输出 "NO"。