#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

**Note: this is a version of binarybomb with larger test data and tighter constraints.**

## Problem Description

An evil villain, Diamond Bomber, is attacking BinaryLand with bombs! Fortunately, of the *10* residents of BinaryLand, only one was killed and the other resident, Mr B, managed to take shelter underground before the attack. When he emerged above ground, he found that BinaryLand was blown to *bits* (well, it was in bits before the attack but you get the idea).

It is your job as a member of the rescue team to code a program to work out the shortest path for Mr B to take to get to the rescue zone from his shelter (he can only travel left, right, up or down). However, there are a few problems:

1. You do not know what the current layout of BinaryLand is, but you know about the bombs that have exploded.

2. There are three type of bombs:

Type 1: Changes all values caught in bomb's radius to 1

Type 2: Changes all values caught in bomb's radius to 0

Type 3: FLIPS all values caught in bomb's radius (1 becomes 0, 0 becomes 1)

3. The Diamond Bomber's bombs explode in a diamond pattern (surprise!)

E.g. Bomb of Radius 2 Type 1

000010000 000111000 001111100 000111000 000010000

4. Distances in BinaryLand are calculated through Binary, so the shortest path has the shortest distance when the path is converted from binary to a base 10 integer

E.g. If the path from the shelter to the rescue area is 0 -> 1 -> 0 -> 1, the binary number is 1010 (with the starting point as last digit) and the distance will be 10 after converting to integer.

The fate of Mr B lies in your hands, Good Luck!

**Note: **The default layout of BinaryLand is all 0s and all coordinates are **0-indexed**. The value at the shelter and the rescue location must also be considered when working out the shortest path.

## Input

The first line of input has 3 integers: **H**, **W** and **B** (representing the height and width of BinaryLand, and the number of bombs respectively)

The next line of input has 4 integers: **S _{x}**,

**S**,

_{y}**R**,

_{x}**R**(representing the coordinates of the shelter and the rescue area respectively)

_{y }The next **B **lines contain 4 integers each: **B _{T}**,

**B**,

_{x}**B**,

_{y}**B**(representing the type of bomb, the coordinates of the centre of the bomb, and the bomb radius respectively)

_{R}## Output

A single integer stating the shortest distance from the shelter to the rescue area **mod 13371337**.

This is because numbers may become too large to fit in an integer or a long long.

## Limits

Subtask 1 (9%): 1 < **H**, **W** ≤ 100, 1 < **B** ≤ 500, 1 < **B _{R} **≤ 50

Subtask 2 (21%): 1 < **H**, **W** ≤ 1000, 1 < **B **≤ 1000, 1 < **B _{R} **≤ 100

Subtask 3 (70%): 1 < **H**, **W** ≤ 4000, 1 < **B **≤ 4000, 1 < **B _{R} **≤ 1000

Subtask 4 (0%): Sample testcases

## Sample Testcase 1

### Input

5 5 2 0 0 4 4 1 2 2 2 2 2 2 1

### Output

68

### Explanation

After the bombs exploded, this is the layout of BinaryLand:

00100 01010 10001 01010 00100

The shortest distance from shelter *(0, 0)* to rescue zone *(4, 4)* is through (shelter) 0 -> 0 -> 1 -> 0 -> 0 -> 0 -> 1 -> 0 -> 0 (rescue). The binary number is 001000100, which converts to 68.

## Sample Testcase 2

### Input

25 25 5 3 8 24 24 1 15 17 6 3 6 24 4 3 23 11 7 2 18 20 4 1 22 17 5

### Output

0

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 9 | 30 | 2s | 32MB | Minimum |

2 | 21 | 30 | 2s | 32MB | Minimum |

3 | 70 | 32 | 2s | 32MB | Minimum |

4 | 0 | 2 | 2s | 32MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o binarybomb_ex -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512