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 types 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 \to 1 \to 0 \to 1~, the binary number is ~1010~ (with the starting point as last digit) and the distance will be ~10~ after converting to a base ~10~ integer.

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

Note: The default layout of BinaryLand is all ~0~s 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 Specification

The first line of input has 3 integers: ~H~, ~W~, ~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_y~ (representing the coordinates of the shelter and the rescue area respectively)

The next ~B~ lines contain 4 integers each: ~B_T~, ~B_x~, ~B_y~, ~B_R~ (representing the type of bomb, the coordinates of the centre of the bomb, and the bomb radius respectively)

Output Specification

A single integer stating the shortest distance from the shelter to the rescue area ~\bmod 13\,371\,337~.

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

Constraints

Subtask 1 [30%]

~1 < H, W \le 100~

~1 < B \le 500~

~1 < B_R \le 50~

Subtask 2 [70%]

~1 < H, W, B \le 1\,000~

~1 < B_R \le 100~

Subtask 3 [0%]

Sample test cases.

Sample Input 1

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

Sample Output 1

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 \to 0 \to 1 \to 0 \to 0 \to 0 \to 1 \to 0 \to 0~ (rescue). The binary number is ~001000100~, which converts to ~68~.

Sample Input 2

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

Sample Output 2

0