Kilonova
Toggle theme

Rectangles

Time limit: 0.25s Memory limit: 256MB Input: Output:

You are given a matrix with nn rows and mm columns. Its entries are consecutive starting from 00 left to right, top to bottom like below:

KaTeX parse error: Unexpected character: '\' at position 2: 0\̲ KaTeX parse error: Unexpected character: '\' at position 2: 1\̲ KaTeX parse error: Unexpected character: '\' at position 2: 2\̲ KaTeX parse error: Unexpected character: '\' at position 2: 3\̲ KaTeX parse error: Unexpected character: '\' at position 2: 4\̲
KaTeX parse error: Unexpected character: '\' at position 2: 5\̲ KaTeX parse error: Unexpected character: '\' at position 2: 6\̲ KaTeX parse error: Unexpected character: '\' at position 2: 7\̲ KaTeX parse error: Unexpected character: '\' at position 2: 8\̲ KaTeX parse error: Unexpected character: '\' at position 2: 9\̲
KaTeX parse error: Unexpected character: '\' at position 3: 10\̲ KaTeX parse error: Unexpected character: '\' at position 3: 11\̲ KaTeX parse error: Unexpected character: '\' at position 3: 12\̲ KaTeX parse error: Unexpected character: '\' at position 3: 13\̲ KaTeX parse error: Unexpected character: '\' at position 3: 14\̲
KaTeX parse error: Unexpected character: '\' at position 3: 15\̲ KaTeX parse error: Unexpected character: '\' at position 3: 16\̲ KaTeX parse error: Unexpected character: '\' at position 3: 17\̲ KaTeX parse error: Unexpected character: '\' at position 3: 18\̲ KaTeX parse error: Unexpected character: '\' at position 3: 19\̲

There are qq operations which modify the matrix in the following way: a submatrix is chosen inside the matrix and it will be inverted horizontally and vertically. For example if the submatrix with the top-left coordinate (1,3)(1, 3) and bottom-right coordinate (3,5)(3, 5) is inverted on the one above it will look like this:

KaTeX parse error: Unexpected character: '\' at position 2: 0\̲ KaTeX parse error: Unexpected character: '\' at position 2: 1\̲ KaTeX parse error: Unexpected character: '\' at position 3: 14\̲ KaTeX parse error: Unexpected character: '\' at position 3: 13\̲ KaTeX parse error: Unexpected character: '\' at position 3: 12\̲
KaTeX parse error: Unexpected character: '\' at position 2: 5\̲ KaTeX parse error: Unexpected character: '\' at position 2: 6\̲ KaTeX parse error: Unexpected character: '\' at position 2: 9\̲ KaTeX parse error: Unexpected character: '\' at position 2: 8\̲ KaTeX parse error: Unexpected character: '\' at position 2: 7\̲
KaTeX parse error: Unexpected character: '\' at position 3: 10\̲ KaTeX parse error: Unexpected character: '\' at position 3: 11\̲ KaTeX parse error: Unexpected character: '\' at position 2: 4\̲ KaTeX parse error: Unexpected character: '\' at position 2: 3\̲ KaTeX parse error: Unexpected character: '\' at position 2: 2\̲
KaTeX parse error: Unexpected character: '\' at position 3: 15\̲ KaTeX parse error: Unexpected character: '\' at position 3: 16\̲ KaTeX parse error: Unexpected character: '\' at position 3: 17\̲ KaTeX parse error: Unexpected character: '\' at position 3: 18\̲ KaTeX parse error: Unexpected character: '\' at position 3: 19\̲

You are also given the coordinates (x,y)(x, y) of a cell, type the value of that cell after all qq operations.

Input

The first line will contain 55 integers, n,m,q,xn, m, q, x and y(1≤n,m≤109),(1≤q≤3⋅105),(1≤x,y≤n)y (1 ≤ n, m ≤ 10^9), (1 ≤ q ≤ 3 \cdot 10^5), (1 ≤ x, y ≤ n).

The following qq lines will contain x1,y1,x2x_1, y_1, x_2 and y2y_2 which describe the top-left, bottom-right coordinates of the submatrix (1≤x1≤x2≤n),(1≤y1≤y2≤n)(1 ≤ x_1 ≤ x_2 ≤ n), (1 ≤ y_1 ≤ y_2 ≤ n).

For tests worth 2020 points it is guaranteed that (1≤n,m≤100),(1≤q≤100)(1 ≤ n, m ≤ 100), (1 ≤ q ≤ 100)

Example

stdin

4 5 1 1 3
1 3 3 5

stdout

14

Log in or sign up to be able to send submissions!