Feeling Good
Contest: Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)
Difficulty rating: 3200
Tags: bitmasks, data structures

Recently biologists came to a fascinating conclusion about how to find a chameleon mood. Consider chameleon body to be a rectangular table $$$n \times m$$$, each cell of which may be green or blue and may change between these two colors. We will denote as $$$(x, y)$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$) the cell in row $$$x$$$ and column $$$y$$$.

Let us define a chameleon good mood certificate to be four cells which are corners of some subrectangle of the table, such that colors in opposite cells among these four are similar, and at the same time not all of the four cell colors are similar. Formally, it is a group of four cells $$$(x_1, y_1)$$$, $$$(x_1, y_2)$$$, $$$(x_2, y_1)$$$, $$$(x_2, y_2)$$$ for some $$$1 \leq x_1 < x_2 \leq n$$$, $$$1 \leq y_1 < y_2 \leq m$$$, that colors of $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ coincide and colors of $$$(x_1, y_2)$$$ and $$$(x_2, y_1)$$$ coincide, but not all of the four cells share the same color. It was found that whenever such four cells are present, chameleon is in good mood, and vice versa: if there are no such four cells, chameleon is in bad mood.

You are asked to help scientists write a program determining the mood of chameleon. Let us consider that initially all cells of chameleon are green. After that chameleon coloring may change several times. On one change, colors of contiguous segment of some table row are replaced with the opposite. Formally, each color change is defined by three integers $$$a$$$, $$$l$$$, $$$r$$$ ($$$1 \leq a \leq n$$$, $$$1 \leq l \leq r \leq m$$$). On such change colors of all cells $$$(a, b)$$$ such that $$$l \leq b \leq r$$$ are replaced with the opposite.

Write a program that reports mood of the chameleon after each change. Additionally, if the chameleon mood is good, program should find out any four numbers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ such that four cells $$$(x_1, y_1)$$$, $$$(x_1, y_2)$$$, $$$(x_2, y_1)$$$, $$$(x_2, y_2)$$$ are the good mood certificate.

Input format:
The first line of input contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m \leq 2000$$$, $$$1 \leq q \leq 500\,000$$$), the sizes of the table and the number of changes respectively.

Each of the following $$$q$$$ lines contains 3 integers $$$a_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$1 \leq a_i \leq n$$$, $$$1 \leq l_i \leq r_i \leq m$$$), describing $$$i$$$-th coloring change.

Output format:
Print $$$q$$$ lines. In the $$$i$$$-th line report the chameleon mood after first $$$i$$$ color changes for all $$$1 \leq i \leq q$$$.

If chameleon is in bad mood, print the only integer $$$-1$$$.

Otherwise, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1 < x_2 \leq n$$$, $$$1 \leq y_1 < y_2 \leq m$$$) such that four cells $$$(x_1, y_1)$$$, $$$(x_1, y_2)$$$, $$$(x_2, y_1)$$$, $$$(x_2, y_2)$$$ are the good mood certificate. If there are several ways to choose such four integers, print any valid one.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
2 2 6
1 1 1
2 2 2
2 1 1
1 2 2
2 2 2
1 1 1

Example output:
-1
1 1 2 2
-1
-1
-1
1 1 2 2

Example input:
4 3 9
2 2 3
4 1 2
2 1 3
3 2 2
3 1 3
1 2 2
4 2 3
1 1 3
3 1 3

Example output:
-1
2 1 4 3
-1
2 1 3 2
3 2 4 3
1 1 2 2
1 1 2 2
-1
2 1 3 2

Editorial:
Let's define the set $$$A_i$$$ for each $$$1 \leq i \leq n$$$ as a set of columns $$$j$$$, such that the color of the cell $$$(i, j)$$$ is blue. If there exists two rows $$$1 \leq x_1 < x_2 \leq n$$$, such that $$$A_{x_1} \not\subset A_{x_2}$$$ and $$$A_{x_2} \not\subset A_{x_1}$$$ the good mood certificate exists. It's easy to see, because if $$$A_{x_1} \not\subset A_{x_2}$$$ there exists some $$$y_1$$$, such that $$$y_1 \in A_{x_1}$$$ and $$$y_1 \not\in A_{x_2}$$$ and if $$$A_{x_2} \not\subset A_{x_1}$$$ there exists some $$$y_2$$$, such that $$$y_2 \in A_{x_2}$$$ and $$$y_2 \not\in A_{x_1}$$$. Four cells $$$(x_1, y_1)$$$, $$$(x_1, y_2)$$$, $$$(x_2, y_1)$$$, $$$(x_2, y_2)$$$ will be the good mood certificate. Otherwise, if for any two rows $$$1 \leq x_1 < x_2 \leq n$$$ $$$A_{x_1} \subset A_{x_2}$$$ or $$$A_{x_2} \subset A_{x_1}$$$, there is no good mood certificate.
Let's use bitset $$$a_i$$$ for each row, such that $$$a_{{i}{j}} = 1$$$, if the color of the cell $$$(i, j)$$$ is blue. For two rows $$$1 \leq x_1 < x_2 \leq n$$$ it's easy to check that $$$A_{x_1} \subset A_{x_2}$$$ or $$$A_{x_2} \subset A_{x_1}$$$ and find any good mood certificate if it is false using simple operations with two bitsets $$$a_{x_1}$$$ and $$$a_{x_2}$$$ in time $$$O(\frac{m}{w})$$$. Let's sort rows by the size of $$$A_i$$$. If for every two adjacent rows in this order one of them was a subset of other it is true for every pair of rows. So, we can check only pairs of adjacent rows in the sorted order. Let's keep a set of rows, sorting them by the size of $$$A_i$$$. And let's keep set of any good mood certificate for every two adjacent rows in the first set, if it exists. Now, if some row $$$x$$$ changes, we can change bitset $$$a_x$$$ in time $$$O(\frac{m}{w})$$$ and make $$$O(1)$$$ changes with our two sets.
Time complexity: $$$O((\log{n} + \frac{m}{w})q)$$$, there $$$w=32$$$ or $$$w=64$$$.