时空限制

1S/256M

题目描述

有一个正方形水池，可以被划分为 $n\times n$ 个网格，网格的行和列均从 $1$ 开始编号。水池中生活着 $m$ 条活泼的小鱼，它们每天都会沿着各自固定的路线来回游动：

• 行小鱼：始终在某一行的第 $1$ 列至第 $n$ 列之间来回游动；
• 列小鱼：始终在某一列的第 $1$ 行至第 $n$ 行之间来回游动。

多条小鱼可以在同一行或同一列游动。

水池中还有一条爱吃白饭的大肥鱼，它体型庞大，占据了 $3\times3$ 的网格区域。它虽然很贪吃，却非常懒惰，因此只愿意选择一块 $3\times3$ 的网格区域待着始终不移动。

用 $(x,y)$ 表示这块区域左上角网格的坐标，其中 $1\le x,y\le n-2$。这块区域覆盖第 $x$ 至第 $x+2$ 行，以及第 $y$ 至第 $y+2$ 列。

由于小鱼会不断来回游动，若一条行小鱼所在的行被覆盖，或者一条列小鱼所在的列被覆盖，它最终就会游入大肥鱼所在的区域并被吃掉。

求使大肥鱼吃到的小鱼数量最多的 $(x,y)$。若存在多个满足条件的位置，优先选择 $x$ 较小的位置，在 $x$ 相同时选择 $y$ 较小的位置。

格式

输入格式

第一行输入两个正整数 $n,m$，分别表示水池的边长和小鱼的数量。

接下来 $m$ 行，每行输入两个正整数 $op,k$，描述一条小鱼：

• 若 $op=1$，表示这是一条在第 $k$ 行游动的行小鱼；
• 若 $op=2$，表示这是一条在第 $k$ 列游动的列小鱼。

输出格式

输出一行两个正整数 $x,y$，表示最优的 $3\times3$ 区域左上角网格的行坐标和列坐标。

样例

样例输入 #1

7 10
1 2
1 3
1 3
1 5
1 7
2 1
2 4
2 4
2 6
2 7

样例输出 #1

1 4

样例解释 #1

选择 $(1,4)$ 时，大肥鱼会吃到三条行小鱼和三条列小鱼，共吃到六条小鱼，没有其他更优的选择。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，满足 $3\le n\le500$，$1\le m\le500$，$op\in\{1,2\}$，$1\le k\le n$。