lightsflip

Problem Description

Jianzhi is preparing Christmas lights for his annual Christmas party. To decorate his backyard, Jianzhi has arranged his lights in an N by M grid. At first, all of Jianzhi's lights are turned off.

As arranging lights are very boring, Jianzhi decides to test out his magical skills. He issues a series of Q spells, and the ith spell toggles all the lights within the rectangle bounded by (A_i, B_i) and (C_i, D_i). Jianzhi wants to know, after all spells have been casted, which lights are turned on and which lights are turned off.

Input

The first line of input will contain three integers, N, M and Q.

The next Q lines of input will contain four integers each, A_i, B_i, C_i and D_i.

Output

The output should contain N lines with M integers each, representing the configuration of the lights after Jianzhi's spells. A 0 represents a light that is off, and a 1 represents a light that is on.

Limits

For all subtasks: 1 ≤ N, M ≤ 2 000, 1 ≤ Q ≤ 3 000 000, 0 ≤ A_i ≤ C_i < N, 0 ≤ B_i ≤ D_i < M.

Subtask 1 (7%): N = 1, Q ≤ 2 000.

Subtask 2 (11%): N = 1, B_i < D_j for all i, j.

Subtask 3 (19%): N = 1.

Subtask 4 (18%): N, M ≤ 50, Q ≤ 2 000.

Subtask 5 (22%): Q ≤ 2 000.

Subtask 6 (14%): Q ≤ 100 000.

Subtask 7 (9%): No additional constraints.

Subtask 8 (0%): Sample Testcases.

Sample Input 1

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

Sample Output 1

1 1 0 0 1

Sample Input 2

3 3 2
0 1 1 2
1 0 2 1

Sample Output 2

0 1 1
1 0 1
1 1 0