Rorororobot

题意翻译

有一个 $n\times m$ 的网格，第 $i(i\in[1,m])$ 列的 $[1,a_i]$ 行被锁定了。 你有个机器人，你可以给它发命令，让它向上下左右移动一格，但是机器人有 Bug，你发的每个命令都会被执行 $k$ 次**不是瞬移 $k$ 格，而是走 $k$ 次，每次一格**。在**任何一个时刻**，机器人都不能处于被锁定的格子或者网格外。 给定 $q$ 组询问，每组询问给定五个参数 $x_s,y_s,x_f,y_f,k$，代表起点终点坐标和参数 $k$，问能否从起点到终点，能输出 `YES`，不能输出 `NO`。 第一行输入 $n,m$。 第二行输入一个长度为 $m$ 的数组表示 $a$。 第三行一个整数 $q$ 接下来 $q$ 行每行 $5$ 个整数 $x_s,y_s,x_f,y_f,k$ 描述一个询问。 $ 1 \le n \le 10^9 ; 1 \le m \le 2 \cdot 10^5 ; 1\le q \le 2\times 10^5$ $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$

题目描述

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.

输入输出格式

输入格式

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] < 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 $ ) — 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.

输出格式

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".

输入输出样例

输入样例 #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

**题目大意：**
有一个由n行m列组成的网格。第i列的底部有a_i个单元格被封锁，其余的n-a_i个单元格未被封锁。机器人可以在网格上移动，每次可以向上、右、下或左移动一格，但由于机器人出现故障，每个接收到的命令会被执行k次。你需要回答q个关于机器人的查询，每个查询包含一个起始单元格、一个结束单元格和一个值k。询问是否能通过任意次数的命令（可能为零次）使机器人从起始单元格到达结束单元格，假定每次命令执行k次。机器人必须在结束单元格停止。如果机器人在执行命令时经过结束单元格，则不计入。

**输入数据格式：**
- 第一行包含两个整数n和m（1≤n≤10^9; 1≤m≤2×10^5），表示网格的行数和列数。
- 第二行包含m个整数a_1, a_2, …, a_m（0≤a_i≤n），表示第i列底部被封锁的单元格数量。
- 第三行包含一个整数q（1≤q≤2×10^5），表示查询的数量。
- 接下来的q行，每行包含五个整数x_s, y_s, x_f, y_f和k（a[y_s]
**输出数据格式：**
- 对于每个查询，如果机器人能从起始单元格到达结束单元格，则输出“YES”，否则输出“NO”。**题目大意：** 有一个由n行m列组成的网格。第i列的底部有a_i个单元格被封锁，其余的n-a_i个单元格未被封锁。机器人可以在网格上移动，每次可以向上、右、下或左移动一格，但由于机器人出现故障，每个接收到的命令会被执行k次。你需要回答q个关于机器人的查询，每个查询包含一个起始单元格、一个结束单元格和一个值k。询问是否能通过任意次数的命令（可能为零次）使机器人从起始单元格到达结束单元格，假定每次命令执行k次。机器人必须在结束单元格停止。如果机器人在执行命令时经过结束单元格，则不计入。 **输入数据格式：** - 第一行包含两个整数n和m（1≤n≤10^9; 1≤m≤2×10^5），表示网格的行数和列数。 - 第二行包含m个整数a_1, a_2, …, a_m（0≤a_i≤n），表示第i列底部被封锁的单元格数量。 - 第三行包含一个整数q（1≤q≤2×10^5），表示查询的数量。 - 接下来的q行，每行包含五个整数x_s, y_s, x_f, y_f和k（a[y_s]