English · Original
Chinese · Translation
Formal · Original
Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.
Sonya imagined a new type of matrices that she called _rhombic matrices_. These matrices have exactly one zero, while all other cells have the Manhattan distance to the cell containing the zero. The cells with equal numbers have the form of a rhombus, that is why Sonya called this type so.
The Manhattan distance between two cells ($x_1$, $y_1$) and ($x_2$, $y_2$) is defined as $|x_1 - x_2| + |y_1 - y_2|$. For example, the Manhattan distance between the cells $(5, 2)$ and $(7, 1)$ equals to $|5-7|+|2-1|=3$.
<center> Example of _a rhombic matrix_.</center>Note that _rhombic matrices_ are uniquely defined by $n$, $m$, and the coordinates of the cell containing the zero.
She drew a $n\times m$ _rhombic matrix_. She believes that you can not recreate the matrix if she gives you only the elements of this matrix in some arbitrary order (i.e., the sequence of $n\cdot m$ numbers). Note that Sonya will not give you $n$ and $m$, so only the sequence of numbers in this matrix will be at your disposal.
Write a program that finds such an $n\times m$ _rhombic matrix_ whose elements are the same as the elements in the sequence in some order.
## Input
The first line contains a single integer $t$ ($1\leq t\leq 10^6$) — the number of cells in the matrix.
The second line contains $t$ integers $a_1, a_2, \ldots, a_t$ ($0\leq a_i< t$) — the values in the cells in arbitrary order.
## Output
In the first line, print two positive integers $n$ and $m$ ($n \times m = t$) — the size of the matrix.
In the second line, print two integers $x$ and $y$ ($1\leq x\leq n$, $1\leq y\leq m$) — the row number and the column number where the cell with $0$ is located.
If there are multiple possible answers, print any of them. If there is no solution, print the single integer $-1$.
[samples]
## Note
You can see the solution to the first example in the legend. You also can choose the cell $(2, 2)$ for the cell where $0$ is located. You also can choose a $5\times 4$ matrix with zero at $(4, 2)$.
In the second example, there is a $3\times 6$ matrix, where the zero is located at $(2, 3)$ there.
In the third example, a solution does not exist.
由于索尼娅刚刚学习了矩阵的基础知识，她决定稍微玩一玩矩阵。
索尼娅想象了一种她称为 _菱形矩阵_ 的新类型矩阵。这些矩阵恰好包含一个零，而其他所有单元格的值等于该单元格到包含零的单元格的曼哈顿距离。具有相同数值的单元格形成菱形，因此索尼娅称其为这种类型。
两个单元格 ($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$ 个数字的序列），你就无法重建该矩阵。注意，索尼娅不会告诉你 $n$ 和 $m$，因此你只能获得矩阵中数字的序列。
编写一个程序，找出一个 $n \times m$ 的 _菱形矩阵_，其元素与给定序列中的元素相同（顺序任意）。
第一行包含一个整数 $t$ ($1 \leq t \leq 10^6$) — 矩阵中的单元格数量。
第二行包含 $t$ 个整数 $a_1, a_2, \dots, 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$) — 包含零的单元格所在的行号和列号。
如果有多个可能的答案，输出任意一个即可。如果没有解，输出单个整数 $-1$。
第一个示例的解法见题面图示。你也可以选择单元格 $(2, 2)$ 作为零的位置，也可以选择一个 $5 \times 4$ 的矩阵，零位于 $(4, 2)$。
在第二个示例中，存在一个 $3 \times 6$ 的矩阵，零位于 $(2, 3)$。
在第三个示例中，无解。
## Input
第一行包含一个整数 $t$ ($1 \leq t \leq 10^6$) — 矩阵中的单元格数量。第二行包含 $t$ 个整数 $a_1, a_2, \dots, a_t$ ($0 \leq a_i < t$) — 按任意顺序给出的单元格中的值。
## Output
第一行输出两个正整数 $n$ 和 $m$ ($n \times m = t$) — 矩阵的尺寸。第二行输出两个整数 $x$ 和 $y$ ($1 \leq x \leq n$, $1 \leq y \leq m$) — 包含零的单元格所在的行号和列号。如果有多个可能的答案，输出任意一个即可。如果没有解，输出单个整数 $-1$。
[samples]
## Note
第一个示例的解法见题面图示。你也可以选择单元格 $(2, 2)$ 作为零的位置，也可以选择一个 $5 \times 4$ 的矩阵，零位于 $(4, 2)$。在第二个示例中，存在一个 $3 \times 6$ 的矩阵，零位于 $(2, 3)$。在第三个示例中，无解。
**Definitions**
Let $ t \in \mathbb{Z}^+ $ be the total number of cells in the matrix.
Let $ A = \{a_1, a_2, \dots, a_t\} $ be a multiset of non-negative integers with $ 0 \leq a_i < t $, representing the multiset of values in the rhombic matrix in arbitrary order.
A *rhombic matrix* of size $ n \times m $ (with $ n \cdot m = t $) with zero at position $ (x, y) $ is defined such that for each cell $ (i, j) $, its value is the Manhattan distance to $ (x, y) $:
$$
v(i,j) = |i - x| + |j - y|
$$
**Constraints**
1. $ t \leq 10^6 $
2. $ a_i \in \mathbb{Z}_{\geq 0} $, $ a_i < t $ for all $ i \in \{1, \dots, t\} $
3. $ n, m \in \mathbb{Z}^+ $, $ n \cdot m = t $
4. $ 1 \leq x \leq n $, $ 1 \leq y \leq m $
**Objective**
Find integers $ n, m, x, y $ such that:
- $ n \cdot m = t $,
- The multiset of Manhattan distances $ \{ |i - x| + |j - y| \mid 1 \leq i \leq n,\ 1 \leq j \leq m \} $ is equal to the multiset $ A $.
If no such $ n, m, x, y $ exist, output $ -1 $.
If multiple solutions exist, output any one.
API Response (JSON)
{
"problem": {
"name": "D. Sonya and Matrix",
"description": {
"content": "Since Sonya has just learned the basics of matrices, she decided to play with them a little bit. Sonya imagined a new type of matrices that she called _rhombic matrices_. These matrices have exactly ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1004D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.\n\nSonya imagined a new type of matrices that she called _rhombic matrices_. These matrices have exactly ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "由于索尼娅刚刚学习了矩阵的基础知识，她决定稍微玩一玩矩阵。\n\n索尼娅想象了一种她称为 _菱形矩阵_ 的新类型矩阵。这些矩阵恰好包含一个零，而其他所有单元格的值等于该单元格到包含零的单元格的曼哈顿距离。具有相同数值的单元格形成菱形，因此索尼娅称其为这种类型。\n\n两个单元格 ($x_1$, $y_1$) 和 ($x_2$, $y_2$) 之间的曼哈顿距离定义为 $| x_1 -x_2 | + | y_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z}^+ $ be the total number of cells in the matrix. \nLet $ A = \\{a_1, a_2, \\dots, a_t\\} $ be a multiset of non-negative integers with $ 0 \\leq a_i < t $, represen...",
"is_translate": false,
"language": "Formal"
}
]
}