## codeforces 495D Sonya and Matrix 转

o
osc_odyg6b92

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 (x1,y1) and (x2,y2)is defined as |x1-x2|+|y1-y2|.For example For example, the Manhattan distance between the cells (5,2) and (7,1) equals to |57|+|21|=3.

Note that rhombic matrices are uniquely defined by n, m, and the coordinates of the cell containing the zero.

She drew a n×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 nm 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 ann×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≤t≤106) — the number of cells in the matrix.
The second line contains tintegers a1,a2,…,at (0≤ai<t) — the values in the cells in arbitrary order.
Output
In the first line, print two positive integers n and m (n×m=t) — the size of the matrix.
In the second line, print two integers xand y (1≤x≤n, 1≤y≤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.
Examples
Input

20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4

Output

4 5
2 2

Input

18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1

Output

3 6
2 3

Input

6
2 1 0 2 1 2
Output
-1
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×4 matrix with zero at (4,2).

In the second example, there is a 3×6 matrix, where the zero is located at (2,3) there.

In the third example, a solution does not exist.

``````#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef unsigned long long ull;
typedef long long ll;
//设0的坐标为(x,y)
//左上角的值为a=x+y-2;
//右下角的值为b=n+m-x-y;
//a+b=n+m-2
//b为最大值
//所以有y=n+m-b-x;
//n,m暴力求解x为最小的i使得a[i]!=i*4;
int t,n,m,a[1000006],dp[1000006],x,pos=-1,val_x,val_y;
int main()
{
scanf("%d",&t);
for(int i=0;i<t;i++)
{
scanf("%d",&x);
pos=max(pos,x);
a[x]++;
}
printf("\n");
int flag=0;
for(int i=1;;i++)
if(a[i]!=4*i){val_x=i;break;}
for(int i=1;i<=t;i++)
{
if(t%i) continue;
n=i,m=t/i;
val_y=n+m-pos-val_x;
memset(dp,0,sizeof(dp));
for(int row=1;row<=n;row++)
for(int col=1;col<=m;col++)
dp[abs(row-val_x)+abs(col-val_y)]++;
for(int j=0;j<=pos;j++)
if(a[j]!=dp[j]) goto eg;
flag=1;
eg:;
if(flag) break;
}
if(flag) printf("%d %d\n%d %d\n",n,m,val_x,val_y);
else printf("-1\n");
return 0;
}``````

o

### osc_odyg6b92

MATPaint 是 MATrix Paint 的缩写，用于设计点阵字符，最高支持 32x32 像素。 该工具的功能： 新建、打开和保持文件 记住上次状态 保持模式为 PNG 图像 为微控制器生成十六进制码 打印预览和...

2012/11/26
750
0

wyh817
2016/04/26
407
2

MrZhangKe
2016/08/08
3.1K
2
Pure 编程语言

Pure 是一个高级的函数式编程语言. It offers equational definitions with pattern matching, full symbolic rewriting capabilities, dynamic typing, eager and lazy evaluation, lexica......

2010/06/10
1.7K
0

MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据 分析以及数值计算的高级技术计算语言和交互式环境，主要包括MAT...

2010/04/28
5.2W
2

SQL 语句大全

GeneralMa

0
0

osc_qv1fwke0
30分钟前
14
0

zhang_rick

1
0

osc_anefoz50
31分钟前
0
0

31分钟前
21
0