← 返回题目列表

Codeforces · 1214/G

G. 感觉良好

中文机器翻译题面 查看原题

最近,生物学家就如何找到变色龙的情绪得出了一个令人着迷的结论。将变色龙的身体视为一个矩形桌子 $$$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$$$) 定义。在这种情况下,所有单元格 $$$(a, b)$$$ 的颜色发生变化,使得 $$$l \leq b \leq r$$$ 被替换为相反的颜色。

编写一个程序,报告每次变化后变色龙的情绪。另外,如果变色龙心情好,程序应该找出任意四个数字 $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ 使得四个单元格 $$$(x_1, y_1)$$$, $$$(x_1, y_2)$$$, $$$(x_2, y_1)$$$, $$$(x_2, y_2)$$$ 是好心情证书。

输入

输入的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m \leq 2000$$$, $$$1 \leq q \leq 500\,000$$$),分别是表格的大小和更改的次数。

以下 $$$q$$$ 行包含 3 个整数 $$$a_i$$$、$$$l_i$$$、$$$r_i$$$ ($$$1 \leq a_i \leq n$$$、$$$1 \leq l_i \leq r_i \leq m$$$),描述第 $$$i$$$ 颜色变化。

输出

打印 $$$q$$$ 行。在第 $$$i$$$ 行中,报告所有 $$$1 \leq i \leq q$$$ 第一次 $$$i$$$ 颜色变化后变色龙的情绪。

如果变色龙心情不好,则打印唯一的整数 $$$-1$$$。

否则,打印四个整数 $$$x_1$$$, $$$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_1, y_2)$$$、$$$(x_2, y_1)$$$、$$$(x_2, y_2)$$$ 是好心情证书。如果有多种方法可以选择这四个整数,则打印任何有效的一个。

示例

输入 #1

2 2 6
1 1 1
2 2 2
2 1 1
1 2 2
2 2 2
1 1 1

输出 #1

-1
1 1 2 2
-1
-1
-1
1 1 2 2

输入 #2

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

输出 #2

-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