由于 Sonya 刚刚学习了矩阵的基础知识,她决定稍微玩一下它们。
索尼娅想象了一种新型矩阵,她称之为菱形矩阵。这些矩阵恰好有一个零,而所有其他单元都具有到包含零的单元的曼哈顿距离。数量相等的细胞呈菱形,这就是索尼娅如此称呼这种类型的原因。
两个像元 ($$$x_1$$$, $$$y_1$$$) 和 ($$$x_2$$$, $$$y_2$$$) 之间的曼哈顿距离定义为 $$$|x_1 - x_2| + |y_1 - y_2|$$$。例如,像元 $$$(5, 2)$$$ 和 $$$(7, 1)$$$ 之间的曼哈顿距离等于 $$$|5-7|+|2-1|=3$$$。
菱形矩阵的示例。
请注意,菱形矩阵由 $$$n$$$、$$$m$$$ 以及包含零的单元格的坐标唯一定义。
她画了一个 $$$n\times m$$$ 菱形矩阵。她认为,如果她只以某种任意顺序(即 $$$n\cdot m$$$ 数字的序列)为您提供该矩阵的元素,您就无法重新创建该矩阵。请注意,Sonya 不会给您 $$$n$$$ 和 $$$m$$$,因此您只能使用此矩阵中的数字序列。
编写一个程序,找到这样一个 $$$n\times m$$$ 菱形矩阵,其元素与序列中的元素按某种顺序相同。
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^6$$$) — 矩阵中的单元格数量。
第二行包含 $$$t$$$ 整数 $$$a_1, a_2, \ldots, a_t$$$ ($$$0\leq a_i< t$$$) - 单元格中的值以任意顺序排列。
输出
在第一行中,打印两个正整数 $$$n$$$ 和 $$$m$$$ ($$$n \times m = t$$$) — 矩阵的大小。
在第二行中,打印两个整数 $$$x$$$ 和 $$$y$$$ ($$$1\leq x\leq n$$$, $$$1\leq y\leq m$$$)——$$0$$$ 所在单元格所在的行号和列号。
如果有多个可能的答案,请打印其中任何一个。如果无解,则打印单个整数 $$$-1$$$。
示例
输入 #1
20 1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4
输出 #1
4 5 2 2
输入 #2
18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1
输出 #2
3 6 2 3
输入 #3
6 2 1 0 2 1 2
输出 #3
-1
注意
您可以在图例中看到第一个示例的解决方案。您还可以选择单元格 $$$(2, 2)$$$ 作为 $$$0$$$ 所在的单元格。您还可以选择 $$$5\times 4$$$ 矩阵,在 $$$(4, 2)$$$ 处为零。
在第二个示例中,有一个 $$$3\times 6$$$ 矩阵,其中零位于 $$$(2, 3)$$$ 处。
在第三个示例中,不存在解。