## Snowy Streets

View as PDF

Points: 25 (partial)
Time limit: 10.0s
Memory limit: 256M
Author:

Problem type

The North Pole is running out of funds! Santa Claus has started to work as an Oober driver in the prosperous city of Alert. For this job, Santa must drive people across Alert. The city can be seen as a grid with rows and columns. The square in the row and column is denoted as . Santa drives in a peculiar fashion: he will only drive directly down or right. To be more precise, if he is in , then he will only drive to either or .

It's been snowing in Alert a lot recently, but Santa doesn't have enough money to buy proper winter tires. Due to this, he will not go through any squares with at least millimeters of snow. Initially, all squares have millimeters of snow.

There are two operations:

1 a b c d v The levels of snow of the squares in the subrectangle with opposing corners and increase by millimeters each.

2 a b c d A query asking if it is possible for Santa to drive someone from to . You may assume that Santa can get to the starting square. Note that if the starting or ending squares have levels of snow larger than or equal to , then it is not possible.

You are given of these operations. For each of the second operation, output yes if it possible and no if it is not.

#### Constraints

for all type operations
for all type operations

for all type operations

#### Input Specification

The first line will contain four space-separated integers , , , and .
The next lines will each contain an operation in the format specified above.

#### Output Specification

For each of the second operations, output its answer on a new line, in the order which they were asked.

#### Sample Input

3 5 3 10
2 1 1 3 5
1 1 3 2 5 2
2 1 3 2 5
1 2 1 3 3 2
1 1 2 2 2 1
2 1 1 3 3
1 3 1 3 1 5
2 1 1 3 3
2 1 1 3 4
2 2 3 3 5

#### Sample Output

yes
yes
yes
no
yes
no

#### Explanation for Sample

For the first operation, all levels of snow are , so Santa can clearly get from to .
For the third operation, even though all the squares on any path from to have snow, the levels are still less than , so Santa can pass through them.
For the sixth operation, there is only one way for Santa to get from to . He has to move down twice, then right twice.
For the eighth operation, Santa cannot get from to since , , and have too much snow.
For the ninth operation, Santa can move right three times, then down twice.
For the tenth operation, the starting square has too much snow, so it is not possible.