CF1214G.Feeling Good

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 \lt x_2 \leq n$, $1 \leq y_1 \lt 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.

最近，生物学家得出了一个关于如何判断变色龙情绪的有趣结论。将变色龙的身体建模为一个 $n \times m$ 的矩形表格，其中每个格子为绿色或蓝色，并可在两种颜色之间切换。我们用 $(x, y)$（$1 \leq x \leq n$，$1 \leq y \leq m$）表示第 $x$ 行、第 $y$ 列的格子。

我们将变色龙“情绪良好”的认证图案定义为表格中某个子矩形的四个角所对应的格子，满足：两组对角格子的颜色分别相同，但四个格子并非全部同色。形式化地，它是一组四个格子 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$，其中 $1 \leq x_1 < x_2 \leq n$，$1 \leq y_1 < y_2 \leq m$，且 $(x_1, y_1)$ 与 $(x_2, y_2)$ 颜色相同，$(x_1, y_2)$ 与 $(x_2, y_1)$ 颜色也相同，但四个格子并非全部同色。研究发现：只要存在这样一组四格，变色龙即处于良好情绪；反之，若不存在任何这样的四格，则变色龙处于不良情绪。

你需要帮助科学家编写一个程序，用于判定每次染色变化后变色龙的情绪状态。初始时，变色龙所有格子均为绿色。随后，变色龙的颜色可能发生若干次变化。每次变化将某一行中一个连续区间的格子颜色翻转（即绿色变蓝色，蓝色变绿色）。形式化地，每次颜色变化由三个整数 $a$、$l$、$r$（$1 \leq a \leq n$，$1 \leq l \leq r \leq m$）指定：对所有满足 $l \leq b \leq r$ 的格子 $(a, b)$，将其颜色翻转。

请编写一个程序，在每次变化后报告变色龙的情绪状态。此外，若情绪为良好，程序还需输出任意一组满足条件的四元组 $x_1$、$y_1$、$x_2$、$y_2$，使得四个格子 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$ 构成一个“情绪良好”的认证图案。

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.

输入的第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m \leq 2000$，$1 \leq q \leq 500\,000$），分别表示表格的尺寸以及修改操作的次数。

接下来的 $q$ 行中，每行包含三个整数 $a_i$、$l_i$、$r_i$（$1 \leq a_i \leq n$，$1 \leq l_i \leq r_i \leq m$），描述第 $i$ 次染色修改操作。

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 \lt x_2 \leq n$, $1 \leq y_1 \lt 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.

输出 $q$ 行。在第 $i$ 行中，报告前 $i$ 次颜色变化后变色龙的情绪状态（对所有 $1 \leq i \leq q$）。

若变色龙处于“坏心情”状态，则仅输出整数 $-1$。

否则，输出四个整数 $x_1$、$y_1$、$x_2$、$y_2$（满足 $1 \leq x_1 \lt x_2 \leq n$ 且 $1 \leq y_1 \lt y_2 \leq m$），使得四个格子 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$ 构成“好心情”的证明。若存在多种选择方式，输出任意一组合法解即可。