[Solution] Rorororobot solution codeforces

Rorororobot solution codeforces – There is a grid, consisting of 𝑛n rows and 𝑚m columns. The rows are numbered from 11 to 𝑛n from bottom to top. The columns are numbered from 11 to 𝑚m from left to right. The 𝑖i-th column has the bottom 𝑎𝑖ai cells blocked (the cells in rows 1,2,,𝑎𝑖1,2,…,ai), the remaining 𝑛𝑎𝑖n−ai cells are unblocked.

Table of Contents

[Solution] Rorororobot solution codeforces

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?

Input

The first line contains two integers 𝑛n and 𝑚m (1𝑛1091≤n≤1091𝑚21051≤m≤2⋅105) — the number of rows and columns of the grid.

The second line contains 𝑚m integers 𝑎1,𝑎2,,𝑎𝑚a1,a2,…,am (0𝑎𝑖𝑛0≤ai≤n) — the number of blocked cells on the bottom of the 𝑖i-th column.

The third line contains a single integer 𝑞q (1𝑞21051≤q≤2⋅105) — the number of queries.

Each of the next 𝑞q lines contain five integers 𝑥𝑠,𝑦𝑠,𝑥𝑓,𝑦𝑓xs,ys,xf,yf and 𝑘k (𝑎[𝑦𝑠]<𝑥𝑠𝑛a[ys]<xs≤n1𝑦𝑠𝑚1≤ys≤m𝑎[𝑦𝑓]<𝑥𝑓𝑛a[yf]<xf≤n1𝑦𝑓𝑚1≤yf≤m1𝑘1091≤k≤109) — 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.

[Solution] Rorororobot solution codeforces

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

Example
input

Copy
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
output

Copy
YES
NO
NO
NO
YES
YES

 

For Solution

Click Here

Leave a Comment