/*#include <stdio.h>
int arr[100]={};
int a, cnt=0;
void dab()
{
int brr[100];
int i, j, p=0;
brr[a-1]=arr[a];
for(i=a-3;i>1;i-=2)
{
brr[i]=arr[i+1]-brr[i+2];
}
if(a%2==1)
{
brr[1]=arr[1]-brr[2];
for(j=3;j<=a;j+=2)
brr[j]=arr[j-1]-brr[j-2];
}
else
{
brr[2]=arr[1]-brr[1];
for(j=4;j<=a;j+=2)
brr[j]=arr[j-1]-brr[j-2];
}*/
/*brr[4]=arr[5]
brr[2]=arr[3]-brr[4]=arr[3]-arr[5]
brr[1]=arr[1]-brr[2]=arr[1]-arr[3]+arr[5]
brr[3]=arr[2]-brr[1]=arr[2]-arr[1]+arr[3]-arr[5]
brr[5]=arr[4]-brr[3]=arr[4]-arr[2]+arr[1]-arr[3]+arr[5]*/
/*cnt++;
for(i=1;i<=a;i++)
{
printf("%d ",brr[i]);
}
printf("\n");
for(i=0;i<=a;i++)
if(brr[i]<0)
p=1;
if(p==1&&cnt>1){
printf("%dtimes divided\n", cnt-1);
return ;}
if(p==1&&cnt<=1){
printf("-1times divided\n");
return ;}
for(i=1;i<=a;i++)
arr[i]=brr[i];
dab();
}
int main()
{
int n, i, j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d", &a);
for(j=1;j<=a;j++)
scanf("%d", &arr[j]);
dab();
cnt=0;
}
}
*/
/*
2
5
1 3 0 3 0
5
1 2 3 4 5
*/
/*
#include <stdio.h>
int n, m, x, a, b, cnt=-1, dab=10000000;
char arr[100][100];
int queue[100][2], hehehe[1000], d=1, l=1, visited[100][100]={}, visit[10000];
int front=0, rear=0;
void bfs(int p, int q)
{
if(p==a&&q==b)
{
if(cnt+1<dab)
dab=cnt+1;
return ;
}
printf("%d %d %d\n\n\n",p,q,cnt);
visited[p][q]=1;
if(arr[p+1][q]!='F'&&visited[p+1][q]==0&&p+1>=0&&q>=0&&p+1<n&&q<m)
{
queue[rear][0]=p+1;
queue[rear++][1]=q;
}
if(arr[p-1][q]!='F'&&visited[p-1][q]==0&&p-1>=0&&q>=0&&p-1<n&&q<m)
{
queue[rear][0]=p-1;
queue[rear++][1]=q;
}
if(arr[p][q+1]!='F'&&visited[p][q+1]==0&&p>=0&&q+1>=0&&p<n&&q+1<m)
{
queue[rear][0]=p;
queue[rear++][1]=q+1;
}
if(arr[p][q-1]!='F'&&visited[p][-1]==0&&p>=0&&q-1>=0&&p<n&&q-1<m)
{
queue[rear][0]=p;
queue[rear++][1]=q-1;
}
}
void fire()
{
int i, j, brr[100][2], g=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(arr[i][j]=='F')
{
brr[++g][0]=i;
brr[g][1]=j;
}
}
}
for(int i=1;i<=g;i++)
{
arr[brr[i][0]+1][brr[i][1]]='F';
arr[brr[i][0]][brr[i][1]+1]='F';
arr[brr[i][0]-1][brr[i][1]]='F';
arr[brr[i][0]][brr[i][1]-1]='F';
}
}
int main()
{
scanf("%d %d %d\n", &n, &m, &x);
int i, j;
for(i=0;i<n;i++)
scanf("%s",arr[i]);
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(arr[i][j]=='Y')
{
queue[++rear][0]=i;
queue[rear][1]=j;
}
if(arr[i][j]=='E')
{
a=i;
b=j;
}
}
}*/
/*printf("%d %d\n", queue[1][0], queue[1][1]);
for(i=0;i<n;i++){
for(j=0;j<m;j++)
{
printf("%c ",arr[i][j]);
}
printf("\n");
}*/
/*
hehehe[d++]=1;
while(front!=rear)
{
int r=queue[++front][0];
int t=queue[front][1];
if(front==hehehe[l])
{
cnt++;
l++;
}
if(visit[cnt]==0&&cnt%x==0&&cnt!=0)
{
visit[cnt]=1;
fire();
}
bfs(r, t);
hehehe[d++]=rear;
}
printf("%d\n", dab);
}*/
/*
5 5 2
FOOOE
OOOOO
OOOOO
OOOOO
YOFFO
*/
/*
#include <stdio.h>
#include <stdlib.h>
#define MAX_for(i=0;i<4;i++)
{
yy=y1+dir[i][0];
xx=x1+dir[i][1];
if(out(yy, xx)||yy=y2&&xx==x2)
continue;
if(!Result[yy][xx])
decrease(Board[y1][x1], Board[yy][xx]);
}
for(i=0;i<4;i++)
{
yy=y2+dir[i][0];
xx=x2+dir[i][1];
if(out(yy, xx)||yy=y1&&xx==x1)
continue;
if(!Result[yy][xx])
decrease(Board[y2][x2], Board[yy][xx]);
}N 100
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"
#define true 1
#define false 0
typedef struct _pList
{
int x1;
int x2;
int y1;
int y2;
struct _pList* next;
}pList;
int n;
int Board[MAX_N][MAX_N+1];
int CounterBoard[MAX_N+1][MAX_N+1];
int visited[MAX_N+1][MAX_N+1];
pList* PositionList[MAX_N+1][MAX_N+1];
pList* header[MAX_N+1][MAX_N+1];
int dir[4][2]={{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
int Result[MAX_N][MAX_N+1];
int res_n;
int found=false;
int RC=0;
void Input_data();
void AddpositionList(int, int, int, int, int, int);
void preprocess(void);
int out(int, int);
void decrease(int, int);
void increase(int, int);
void Output_result(void);
void find_solution(void);
void Solve(void);
void Input_data()
{
int i, j;
FILE *inf;
inf=fopen(INPUT_FILE, "r");
fscanf(inf, "%d", &Board[i][j]);
fclose(inf);
}
void AddPositionList(int p, int q, int y1, int x1, int y2, int x2)
{
int temp;
if(q<p)
{
temp=p;
p=q;
q=temp;
}
CounterBoard[p][q]++;
PositionList[p][q]->next=(pList*)malloc(sizeof(pList));
PositionList[p][q]=PositionList[p][q]->next;
PositionList[p][q]->y1=y1;
PositionList[p][q]->x1=x1;
PositionList[p][q]->y2=y2;
PositionList[p][q]->x2=x2;
PositionList[p][q]->next=NULL;
}
void preprocess(void)
{
int i, j;
int p, q;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
PositionList[i][j]=(pList*)malloc(sizeof(pList));
PositionList[i][j]->next=NULL;
header[i][j]=PositionList[i][j];
}
}
for(i=0;i<n;i++)
{
p=Board[i][0];
for(j=1;j<n+1;j++)
{
q=Board[i][j];
AddPositionList(p, q, i, j-1, i, j);
p=q;
}
}
for(i=0;i<n+1;i++)
{
p=Board[0][i];
for(j=1;j<n;j++)
{
q=Board[j][i];
AddPositionList(p, q, j-1, i, j, i);
p=q;
}
}
}
int out(int y, int x)
{
if(y<0||x<0||y>=n||x>n)
return true;
else
return false;
}
void increase(int n1, int n2)
{
if(n1<n2)
CounterBoard[n1][n2]++;
else
CounterBoard[n2][n1]++;
}
void decrease(int n1, int n2)
{
if(n1<n2)
CounterBoard[n1][n2]--;
else
CounterBoard[n2][n1]--;
}
void Output_result(void)
{
int i, j;
FILE *ouf;
ouf=fopen(OUTPUT_FILE, "w");
if(!found)
fprintf(ouf, "Impossible\n");
else
{
for(i=0;i<n;i++)
{
for(j=0;j<n+1;j++)
fprintf(ouf, "%d", Result[i][j]);
fprintf(ouf, "\n");
}
}
}
void find_solution(void)
{
int i, j;
int p, q, min;
pList* PositionList;
int y1, x1, y2, x2;
int yy, xx;
RC++;
p=q=-1;
if(RC==MAX_N*(MAX_N+1)/2)
{
found=true;
Output_result();
exit(0);
}
min=MAX_N*(MAX_N+1)*2+1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(!visited[i][j]&&CounterBoard[i][j]<min)
{
min=CounterBoard[i][j];
p=i;
q=j;
}
}
}
if(min==0)
return ;
if(p<0||q<0)
{
found=true;
Output_result();
exit(0);
}
PositionList=header[p][q];
visited[p][q]=true;
while(PositionList->next!=NULL)
{
PositionList=PositionList->next;
x1=PositionList->x1;
y1=PositionList->y1;
x2=PositionList->x2;
y2=PositionList->y2;
if(Result[y1][x1]||Result[y2][x2])
continue;
for(i=0;i<4;i++)
{
yy=y1+dir[i][0];
xx=x1+dir[i][1];
if(out(yy, xx)||yy==y2&&xx==x2)
continue;
if(!Result[yy][xx])
decrease(Board[y1][x1], Board[yy][xx]);
}
for(i=0;i<4;i++)
{
yy=y2+dir[i][0];
xx=x2+dir[i][1];
if(out(yy, xx)||yy==y1&&xx==x1)
continue;
if(!Result[yy][xx])
decrease(Board[y2][x2], Board[yy][xx]);
}
res_n++;
Result[y1][x1]=res_n;
Result[y2][x2]=res_n;
find_solution();
res_n--;
Result[y1][x1]=0;
Result[y2][x2]=0;
for(i=0;i<4;i++)
{
yy=y1+dir[i][0];
xx=x1+dir[i][1];
if(out(yy, xx)||yy==y2&&xx==x2)
continue;
if(!Result[yy][xx])
increase(Board[y1][x1], Board[yy][xx]);
}
for(i=0;i<4;i++)
{
yy=y2+dir[i][0];
xx=x2+dir[i][1];
if(out(yy, xx)||yy==y1&&xx==x1)
continue;
if(!Result[yy][xx])
increase(Board[y2][x2], Board[yy][xx]);
}
}
visited[p][q]=false;
}
void Solve(void)
{
preprocess();
find_solution();
Output_result();
}
void main()
{
Input_data();
Solve();
}*/
/*
#include <stdio.h>
int main()
{
int arr[32002];
int t;
scanf("%d", &t);
int i;
for(i=0;i<t;i++)
{
int n;
scanf("%d", &n);
int j;
for(j=1;j<=n;j++)
scanf("%d", &arr[j]);
int avg;
int total=0;
for(j=1;j<=n;j++)
total+=arr[j];
if(total%n!=0)
{
printf("-1");
continue;
}
else
{
avg=total/n;
}
int ans=0;
for(j=1;j<=n;j++)
{
if(arr[j]>avg)
ans+=arr[j]-avg;
}
printf("%d\n", ans);
}
}*/
/*
#include <stdio.h>
int arr[10000];
int top=-1;
int temp;
int next(int x, int y)
{
int l, i=0, ret=0, keke=10, k;
l=x;
while(l!=0)
{
i++;
l/=10;
}
int j;
for(j=1;j<=i;j++)
{
int a=x%keke;
int p=a;
keke=10;
x/=10;
for(k=1;k<=y-1;k++)
a=a*p;
ret+=a;
}
return ret;
}
int check(int x)
{
int i, j, cnt=1, keke=0;
for(i=x-1;i>0;i--)
{
if(arr[x]==arr[i])
{
keke=1;
break;
}
cnt++;
}
if(keke==1)
return cnt;
else
return 0;
}
int main()
{
int t;
scanf("%d", &t);
int i;
for(i=0;i<t;i++)
{
top=0;
int a, b;
int ans;
scanf("%d %d", &a, &b);
arr[++top]=a;
temp=a;
for(;;)
{
int k=next(temp, b);
temp=k;
arr[++top]=k;
if(check(top)!=0)
{
ans=check(top);
break;
}
//printf("%d\n", k);
}
printf("%d\n",top-ans-1);
}
}
*/
/*
#include <stdio.h>
int kekeke(int x, int y)
{
int arr[100];
int top=0;
while(x)
{
arr[++top]=x%y;
x=x/y;
}
int k=0;
int i;
for(i=top;i>=1;i--)
k=k*10+arr[i];
return k;
}
int hahaha(int x, int y, int p)
{
int k=kekeke(x, p);
int ret=0;
while(k)
{
ret=(ret*y+(k%y));
k/=y;
}
return ret;
}
int main()
{
int t;
scanf("%d", &t);
int i;
for(i=0;i<t;i++)
{
int a, cnt=0;
scanf("%d", &a);
int j;
for(j=1;j<=300;j++)
{
if(kekeke(j*j, a)==hahaha(j*j, 10, a))
cnt++;
}
printf("%d\n", cnt);
}
}
*/
/*
#include <stdio.h>
int n;
int dp[10002];
int ans(int x)
{
if(x==1)
return 1;
if(x==2)
return 2;
if(dp[x]!=0)
return dp[x];
long long ret;
ret=(ans(x-1)+ans(x-2))%100000007;
return dp[x]=ret;
}
int main()
{
scanf("%d", &n);
printf("%d", ans(n));
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int n;
int memo[10002];
int ans(int x)
{
if(x==1)
return 0;
if(x==2)
return 0;
if(x==3)
return 2;
if(memo[x]!=-1)
return memo[x];
int ret=(ans(x-3)+ans(x-3))%100000007;
return memo[x]=ret;
}
int main()
{
memset(memo, -1, sizeof(memo));
scanf("%d", &n);
printf("%d", ans(n));
}*/
/*
#include <stdio.h>
int n;
int memo[10002];
int ans(int x)
{2
12 21 31 40 49 58 69 79 90 101
if(x==1)
return 1;
if(x==2)
return 5;
if(x==3)
return 1+1+8;
if(memo[x]!=0)
return memo[x];
long long ret;
ret=ans(x-1)+4*ans(x-2)+2*ans(x-3);
return memo[x]=ret;
}
int main()
{
scanf("%d", &n);
printf("%d", ans(n));
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int dp[50];
int arr[11];
int main()
{
int t;
scanf("%d", &t);
int i;
for(i=1;i<=t;i++)
{
int j;
for(j=1;j<=10;j++)
scanf("%d", &arr[j]);
memset(dp, 9876543, sizeof(dp));
for(j=1;j<=10;j++)
dp[j]=arr[j];
int o;
scanf("%d", &o);
for(j=1;j<o;j++)
{
int k;
for(k=1;k+j<=o;k++)
{
if(dp[j+k]>dp[k]+dp[j])
{dp[j+k]=dp[k]+dp[j];*/
/*printf("%d %d %d %d %d %d\n", j+k, dp[j+k], j, k, dp[j], dp[k]);*///}
/*}
}
printf("%d\n", dp[o]);
}
}*/
/*
#include <stdio.h>
int n;
int arr[1002][1002];
int sum;
int max(int x, int y)
{
if(x>y)
return x;
else
return y;
}
int ans(int k, int x, int y)
{
if(x<y)
return 0;
if(x==n+1)
return sum=max(sum, k);
return max(ans(k+arr[x][y], x+1, y), ans(k+arr[x][y+1], x+1, y+1));
}
int main()
{
int t;
scanf("%d", &t);
for(int i=0;i<t;i++)
{
scanf("%d", &n);
for(int j=1;j<=n;j++)
{
for(int k=1;k<=j;k++)
scanf("%d", &arr[j][k]);
}
sum=0;
printf("%d", ans(0, 1, 1));
}
}*/
#include <Stdio.h>
int main()
{
int t;
scanf("%d", &t);
for(int i=0;i<t;i++)
{
int n;
scanf("%d", &n);
float arr[505][2];
for(int j=1;j<=n;j++)
scanf("%f %f", &arr[j][0], &arr[j][1]);
}
}