#include <bits/stdc++.h> using namespace std; long long int A, B, c, r[100001], a[100001], b[100001], q[100001]; long long int gcd(long long int x, long long int y) { if(x%y==0) return y; return gcd(y, x%y); } int main() { printf("Ax+By=C 형태로 정리한 부정방정식의 A, B, C값을 차례로 입력하십시오."); scanf("%lld %lld %lld", &A, &B, &c); long long int w, e, m; w=abs(A); e=abs(B); if(A==0&&B!=0) { if(c%B==0) { printf("x=1, y=%lld", c/B); return 0; } printf("정수해가 존재하지 않습니다."); return 0; } else if(A!=0&&B==0) { if(c%A==0) { printf("x=%lld, y=1", c/A); return 0; } printf("정수해가 존재하지 않습니다."); return 0; } else if(A==0&&B==0) { if(c==0) { printf("x=1, y=1"); return 0; } printf("정수해가 존재하지 않습니다."); return 0; } if(w<e) { m=w; w=e; e=m; } long long int t; t=gcd(w, e); if(c%t!=0) { printf("정수해가 존재하지 않습니다."); return 0; } long long int p=c/t; if(A>B&&B>0) { long long int k; r[0]=A; r[1]=B; for(int i=2;; i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1; i<=k; i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1; i>=1; i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", a[1]*p, B/t, b[1]*p, A/t); } else if(A>B&&B<0&&A>0) { int k; r[0]=A; r[1]=-B; for(int i=2;; i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1; i<=k; i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1; i>=1; i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", a[1]*p, B/t,-b[1]*p, A/t); } else if(A>B&&A<0) { int k; r[0]=-A; r[1]=-B; for(int i=2;; i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1; i<=k; i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1; i>=1; i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", -a[1]*p, B/t, -b[1]*p, A/t); } else if(A<B&&A>0) { int k; r[0]=B; r[1]=A; for(int i=2;; i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1; i<=k; i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1; i>=1; i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", b[1]*p, B/t, a[1]*p, A/t); } else if(A<B&&A<0&&B>0) { int k; r[0]=B; r[1]=-A; for(int i=2;; i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1; i<=k; i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1; i>=1; i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", -b[1]*p, B/t, a[1]*p, A/t); } else if(A<B&&B<0) { int k; r[0]=-B; r[1]=-A; for(int i=2;;i++) { r[i]=r[i-2]%r[i-1]; if(r[i]==0) { k=i-1; break; } } for(int i=1;i<=k;i++) { q[i]=r[i-1]/r[i]; } a[k]=-q[k-1]; b[k]=1; for(int i=k-1;i>=1;i--) { a[i]=-(a[i+1]*q[i-1])+b[i+1]; b[i]=a[i+1]; } printf("x=%lld+%lldk, y=%lld-%lldk", -b[1]*p, B/t, -a[1]*p, A/t); } }

/*#include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); for(int i=0;i<s.length();i++) { if(s[i]==' ') { printf(" "); continue; } if(s[i]=='a'||s[i]=='b'||s[i]=='c') { printf("%c", 23+s[i]); continue; } printf("%c", s[i]-3); } } *//* 1. 생명이 없는 칸의 주위 8칸에 정확히 3마리의 생명이 존재하는 경우 다음 세대에 그 칸에서 생명이 탄생한다. 2. 생명이 있는 칸의 주위 8칸에 4마리 이상 또는 1마리 이하의 생명이 존재하는 경우 다음 세대에 그 칸의 생명은 죽는다. 3. 생명이 있는 칸의 주위 8칸에 2마리 또는 3마리의 생명이 존재하는 경우 다음 세대에 그 칸의 생명은 생존한다.*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[172][172]={}; int temp[172][172]={}; int n, m; scanf("%d %d", &n, &m); int a, b, c; scanf("%d %d %d", &a, &b, &c); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)scanf("%d", &arr[i][j]); } int k; scanf("%d", &k); int dx[8]={-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8]={-1, 0, 1, -1, 1, -1, 0, 1}; int cnt; while(k--) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cnt=0; for(int p=0;p<=7;p++) { if(arr[i+dx[p]][j+dy[p]]==1)cnt++; } if(arr[i][j]==0) { if(cnt==a)temp[i][j]=1; } else { if(cnt>=b&&cnt<c) { temp[i][j]=1; } else { temp[i][j]=0; } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)arr[i][j]=temp[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)printf("%d ", arr[i][j]); printf("\n"); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n, m, x, y; scanf("%d %d %d %d", &n, &m, &x, &y); int arr[101][101]={}; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%d", &arr[i][j]); } } int ans=0; int cnt=0; for(int i=1;i+x-1<=n;i++) { for(int j=1;j+y-1<=m;j++) { cnt=0; for(int a=0;a<x;a++) { for(int b=0;b<y;b++) { cnt+=arr[j+b][i+a]; } } ans=max(ans, cnt); } } printf("%d", ans); } */ /* #include <bits/stdc++.h> using namespace std; int main() { int dp[21][4]={}; int n, arr[21][2]; scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &arr[i][0]); for(int i=1;i<=n;i++)scanf("%d", &arr[i][1]); dp[1][2]=arr[1][0]; dp[1][1]=arr[1][1]; for(int i=2;i<=n;i++) { dp[i][2]=dp[i-1][2]+arr[i][0]; dp[i][1]=dp[i-1][1]+arr[i][1]; dp[i][3]=max(dp[i-1][2]+arr[i][1], dp[i-1][1]+arr[i][0]); dp[i][3]=max(dp[i-1][3]+arr[i][1], dp[i][3]); dp[i][3]=max(dp[i-1][3]+arr[i][0], dp[i][3]); } printf("%d", dp[n][3]); }*/ #include <bits/stdc++.h> using namespace std; int n, m, arr[11][11], cnt, visited[11][11]; int dist[7][7]; vector<pair<int, pair<int, int> > > link; int parent[7]; int findf(int x) { if(x==parent[x])return x; return parent[x]=findf(parent[x]); } void unionf(int x, int y) { int px=findf(x), py=findf(y); parent[py]=px; } void dfs(int x, int y) { if(visited[x][y])return ; visited[x][y]=1; if(arr[x][y]==0)return ; arr[x][y]=cnt; dfs(x+1, y); dfs(x-1, y); dfs(x, y+1); dfs(x, y-1); } int main() { scanf("%d %d", &n, &m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)scanf("%d", &arr[i][j]); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(visited[i][j])continue; if(arr[i][j]==1) { cnt++; dfs(i, j); } } } for(int i=1;i<=6;i++) { for(int j=1;j<=6;j++)dist[i][j]=2147483647; } for(int i=1;i<=n;i++) { int start=0, name=-1; for(int j=1;j<=m;j++) { if(arr[i][j]==0)continue; if(start==0) { start=j, name=arr[i][j]; } else { if(arr[i][j]==name) { start=j; } else { if(j-start-1!=1){ dist[name][arr[i][j]]=min(dist[name][arr[i][j]], j-start-1); dist[arr[i][j]][name]=min(dist[arr[i][j]][name], j-start-1); } start=j; name=arr[i][j]; } } } } for(int i=1;i<=m;i++) { int start=0, name=-1; for(int j=1;j<=n;j++) { if(arr[j][i]==0)continue; if(start==0) { start=j, name=arr[j][i]; } else { if(arr[j][i]==name) { start=j; } else { if(j-start-1!=1){ dist[name][arr[j][i]]=min(dist[name][arr[j][i]], j-start-1); dist[arr[j][i]][name]=min(dist[arr[j][i]][name], j-start-1); } start=j; name=arr[j][i]; } } } } for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++)printf("%d ", dist[i][j]); printf("\n"); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)printf("%d ", arr[i][j]); printf("\n"); } printf("\n"); for(int i=1;i<=cnt;i++) { for(int j=i+1;j<=cnt;j++) { if(dist[i][j]!=2147483647) { link.push_back({dist[i][j], {i, j}}); } } } printf("%d\n", link.size()); for(int i=1;i<=cnt;i++)parent[i]=i; sort(link.begin(), link.end()); int ac=0; int ans=0, link1, link2; /*for(int i=0;i<link.size();i++) { if(ac==cnt-1)break; link1=link[i].second.first, link2=link[i].second.second; if(findf(link1)!=findf(link2)) { ac++; ans+=link[i].first; unionf(link1, link2); } } if(ac!=cnt-1) { printf("-1"); return 0; } printf("%d", ans);*/ }

/*#include <bits/stdc++.h> using namespace std; bool cmp(int x, int y) { if(x>=y)return true; return false; } int main() { int bindo[1001]={}; int n, a; scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%d", &a); bindo[a]++; } int bb=0, bs=20000000, sb=0, ss=2000001; int maxbin=0, minbin=0; int cnt=0; for(int i=1;i<=1000;i++) { maxbin=max(maxbin, bindo[i]); } for(int i=1;i<=1000;i++) { if(bindo[i]!=maxbin) { minbin=max(minbin, bindo[i]); } } if(minbin==0)minbin=maxbin; for(int i=1;i<=1000;i++) { if(bindo[i]==maxbin) { cnt++; bb=max(bb, i); bs=min(bs, i); } if(bindo[i]==minbin) { ss=min(ss, i); sb=max(sb, i); } } if(cnt>=2) { printf("%d", bb-bs); return 0; } printf("%d", max(abs(bb-ss), abs(bs-sb))); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { printf("out"); }*/ /*#include <bits/stdc++.h> using namespace std; int n, m; vector<pair<int, int> > arr[100001]; int parent[100001][21]; long long int dist[100001][21]; int visited[100001]; int dep[100001]; void dfs(int par, int cur, int dis, int depth) { if(visited[cur]) return ; visited[cur]=1; parent[cur][0]=par; dist[cur][0]=dis; dep[cur]=depth; for(int i=0; i<arr[cur].size(); i++) { dfs(cur, arr[cur][i].first, arr[cur][i].second, depth+1); } } void ans1(int x, int y) { long long int ans=0; int temp; if(dep[x]<dep[y]) { temp=x; x=y; y=temp; } int dif=dep[x]-dep[y]; int cnt=0; while(dif) { if(dif%2) { ans+=dist[x][cnt]; x=parent[x][cnt]; } dif/=2; cnt++; } if(x==y) { printf("%lld\n", ans); return ; } for(int i=20; i>=0; i--) { if(parent[x][i]!=parent[y][i]&&parent[x][i]!=0&&parent[y][i]!=0) { ans+=dist[x][i]+dist[y][i]; x=parent[x][i]; y=parent[y][i]; } } ans+=dist[x][0]+dist[y][0]; x=parent[x][0]; printf("%lld\n", ans); } void ans2(int u, int v, int k) { int x=u, y=v; int temp; if(dep[x]<dep[y]) { temp=x; x=y; y=temp; } int dif=dep[x]-dep[y]; int cnt=0; while(dif) { if(dif%2) { x=parent[x][cnt]; } dif/=2; cnt++; } if(x!=y) { for(int i=20; i>=0; i--) { if(parent[x][i]!=parent[y][i]&&parent[x][i]!=0&&parent[y][i]!=0) { x=parent[x][i]; y=parent[y][i]; } } x=parent[x][0]; } //printf("%d ", x); int len=dep[u]-dep[x]; k--; if(len>=k) { cnt=0; while(k) { if(k%2) { u=parent[u][cnt]; } cnt++; k/=2; } printf("%d\n", u); } else { len=dep[v]-dep[x]-(k-len); cnt=0; while(len) { if(len%2) { v=parent[v][cnt]; } cnt++; len/=2; } printf("%d\n", v); } } int main() { scanf("%d", &n); int a, b, c; for(int i=1; i<n; i++) { scanf("%d %d %d", &a, &b, &c); arr[a].push_back({b, c}); arr[b].push_back({a, c}); } dfs(0, 1, 0, 0); for(int i=1; i<=20; i++) { for(int j=1; j<=n; j++) { parent[j][i]=parent[parent[j][i-1]][i-1]; dist[j][i]=dist[j][i-1]+dist[parent[j][i-1]][i-1]; } } scanf("%d", &m); int cmd, u, v, k; for(int i=1; i<=m; i++) { scanf("%d", &cmd); if(cmd==1) { scanf("%d %d", &u, &v); ans1(u, v); } if(cmd==2) { scanf("%d %d %d", &u, &v, &k); ans2(u, v, k); } } }*/ /* #include <bits/stdc++.h> using namespace std; int n, depa, depb, parent[10001], tempa, tempb; int main() { int t; scanf("%d", &t); int a, b; while(t--) { depa=0, depb=0; memset(parent, 0, sizeof(parent)); scanf("%d", &n); for(int i=1;i<n;i++) { scanf("%d %d", &a, &b); parent[b]=a; } scanf("%d %d", &a, &b); tempa=a, tempb=b; while(tempa) { tempa=parent[tempa]; depa++; } while(tempb) { tempb=parent[tempb]; depb++; } if(depa>depb) { while(depa!=depb) { a=parent[a]; depa--; } } else if(depb>depa) { while(depa!=depb) { b=parent[b]; depb--; } } while(a!=b) { a=parent[a]; b=parent[b]; } printf("%d\n", a); } }*/ #include <bits/stdc++.h> using namespace std; int main() { }

/*#include <bits/stdc++.h> using namespace std; //(1, 5) (2, 6) (3, 7) (4, 8) map<pair<pair<int, int>, int>, int> mp; map<pair<int, int>, int> visited; int dx[9]= {0, -1, -2, -2, -1, 1, 2, 2, 1}; int dy[9]= {0, 2, 1, -1, -2, -2, -1, 1, 2}; int n, m, x, y, k; long long int haha=0, hahaha; void sch(int cx, int cy, int cnt, int start) { printf("%d\n", cnt); if(cx<1||cy<1||cx>n||cy>m) { //if(cnt==2)printf("%d %d\n", cx, cy); return ; } if(mp.find({{cx, cy}, cnt})!=mp.end()) { if(cnt==2)printf("haha\n"); return ; } mp.insert({{{cx, cy}, cnt}, 1}); if(cnt==k) { if(visited.find({cx, cy})==visited.end()); { haha++; visited.insert({{cx, cy}, 1}); } return ; } int nx, ny; for(int i=start; i<=8; i++) { nx=cx+dx[i]; ny=cy+dy[i]; sch(nx, ny, cnt+1, i); } } int main() { scanf("%d %d %d %d %d", &n, &m, &x, &y, &k); sch(x, y, 0, 1); hahaha=n*m; printf("%lld", hahaha-haha); }*/ /* #include <bits/stdc++.h> using namespace std; //(1, 5) (2, 6) (3, 7) (4, 8) map<pair<pair<int, int>, int>, int> mp; map<pair<int, int>, int> visited; int dx[9]= {0, -1, -2, -2, -1, 1, 2, 2, 1}; int dy[9]= {0, 2, 1, -1, -2, -2, -1, 1, 2}; int n, m, x, y, k; long long int haha=0, hahaha; void sch(int cx, int cy, int cnt, int start) { int giu=cnt%2; //printf("%d\n", cnt); if(cx<1||cy<1||cx>n||cy>m) { //if(cnt==2)printf("%d %d\n", cx, cy); return ; } if(mp.find({{cx, cy}, giu})!=mp.end()) { if(mp[ {{cx, cy}, giu}]<cnt) { return ; } printf("%d\n", mp[ {{cx, cy}, giu}]); mp.erase({{cx, cy}, giu}); } mp.insert({{{cx, cy}, giu}, cnt}); if(cnt==k) { if(visited.find({cx, cy})==visited.end()); { haha++; visited.insert({{cx, cy}, 1}); } return ; } int nx, ny; for(int i=1; i<=8; i++) { nx=cx+dx[i]; ny=cy+dy[i]; sch(nx, ny, cnt+1, i); } } int main() { scanf("%d %d %d %d %d", &n, &m, &x, &y, &k); sch(x, y, 0, 1); hahaha=n*m; printf("%lld", hahaha-haha); }*/ /*#include <bits/stdc++.h> using namespace std; //(1, 5) (2, 6) (3, 7) (4, 8) map<pair<pair<int, int>, int>, int> mp; map<pair<int, int>, int> visited; int dx[9]= {0, -1, -2, -2, -1, 1, 2, 2, 1}; int dy[9]= {0, 2, 1, -1, -2, -2, -1, 1, 2}; int x, y, k; long long int n, m; long long int haha=0, hahaha; void sch(int cx, int cy, int cnt, int start) { //printf("%d\n", cnt); if(cx<1||cy<1||cx>n||cy>m) { //if(cnt==2)printf("%d %d\n", cx, cy); return ; } if(mp.find({{cx, cy}, cnt})!=mp.end()) { // if(cnt==2)printf("haha\n"); return ; } mp.insert({{{cx, cy}, cnt}, 1}); if(cnt==k) { if(visited.find({cx, cy})==visited.end()); { haha++; visited.insert({{cx, cy}, 1}); } return ; } int nx, ny; for(int i=1; i<=8; i++) { nx=cx+dx[i]; ny=cy+dy[i]; sch(nx, ny, cnt+1, i); } } int main() { scanf("%lld %lld %d %d %d", &n, &m, &x, &y, &k); sch(x, y, 0, 1); hahaha=n*m; printf("%lld %lld %lld", hahaha-haha, hahaha, haha); }*/ /* #include <bits/stdc++.h> using namespace std; //(1, 5) (2, 6) (3, 7) (4, 8) map<pair<pair<int, int>, int>, int> mp; map<pair<int, int>, int> visited; int dx[9]= {0, -1, -2, -2, -1, 1, 2, 2, 1}; int dy[9]= {0, 2, 1, -1, -2, -2, -1, 1, 2}; int x, y, k; long long int n, m; long long int haha=0, hahaha; void sch(int cx, int cy, int cnt, int start) { int giu=cnt%2; //printf("%d\n", cnt); if(cx<1||cy<1||cx>n||cy>m) { //if(cnt==2)printf("%d %d\n", cx, cy); return ; } if(cnt==k) { if(visited.find({cx, cy})==visited.end()); { haha++; visited.insert({{cx, cy}, 1}); } return ; } if(mp.find({{cx, cy}, giu})!=mp.end()) { if(mp[ {{cx, cy}, giu}]>cnt) { return ; } printf("%d\n", mp[ {{cx, cy}, giu}]); mp.erase({{cx, cy}, giu}); } mp.insert({{{cx, cy}, giu}, cnt}); int nx, ny; for(int i=1; i<=8; i++) { nx=cx+dx[i]; ny=cy+dy[i]; sch(nx, ny, cnt+1, i); } } int main() { scanf("%lld %lld %d %d %d", &n, &m, &x, &y, &k); sch(x, y, 0, 1); hahaha=n*m; printf("%lld %lld %lld", hahaha-haha, hahaha, haha); }*/ #include <bits/stdc++.h> using namespace std; //(1, 5) (2, 6) (3, 7) (4, 8) map<pair<pair<int, int>, int>, int> mp; map<pair<int, int>, int> visited; int dx[9]= {0, -1, -2, -2, -1, 1, 2, 2, 1}; int dy[9]= {0, 2, 1, -1, -2, -2, -1, 1, 2}; int x, y, k; long long int n, m; long long int haha=0, hahaha; void sch(int cx, int cy, int cnt, int start) { //printf("%d\n", cnt); if(cx<1||cy<1||cx>n||cy>m) { //if(cnt==2)printf("%d %d\n", cx, cy); return ; } if(mp.find({{cx, cy}, cnt})!=mp.end()) { // if(cnt==2)printf("haha\n"); return ; } mp.insert({{{cx, cy}, cnt}, 1}); if(cnt==k) { if(visited.find({cx, cy})==visited.end()); { haha++; visited.insert({{cx, cy}, 1}); } return ; } int nx, ny; for(int i=1; i<=8; i++) { nx=cx+dx[i]; ny=cy+dy[i]; sch(nx, ny, cnt+1, i); } } int main() { scanf("%lld %lld %d %d %d", &n, &m, &x, &y, &k); int ek=k-k%2; for(int i=0;i<=k;i+=2)sch(x, y, i, 1); hahaha=n*m; printf("%lld", hahaha-haha); }

/*#include <bits/stdc++.h> using namespace std; #define MAX 2147483647 vector<pair<int, int> > arr[10001]; int n, m, dist[10001]; void dijkstra() { priority_queue<pair<int, int> >pq; pq.push({0, 1}); while(!pq.empty()) { int next=pq.top().second, nextdist=-pq.top().first; pq.pop(); for(int i=0;i<arr[next].size();i++) { int ha=arr[next][i].first, haha=arr[next][i].second; if(dist[ha]>nextdist+haha) { dist[ha]=nextdist+haha; pq.push({-dist[ha], ha}); } } } } int main() { scanf("%d %d", &n, &m); int a, b, c; for(int i=1;i<=n;i++)dist[i]=MAX; for(int i=1;i<=m;i++) { scanf("%d %d %d", &a, &b, &c); arr[a].push_back({b, c}); arr[b].push_back({a, c}); } dijkstra(); if(dist[n]==MAX) { printf("Impossible"); return 0; } printf("%d", dist[n]); }*/ /*#include <bits/stdc++.h> using namespace std; int n, arr[11][11], ans=987654321, visited[11], cnt; void backtracking(int current) { if(current==n+1) { ans=min(ans, cnt); return ; } for(int i=1;i<=n;i++) { if(!visited[i]) { visited[i]=1; cnt+=arr[current][i]; backtracking(current+1); visited[i]=0; cnt-=arr[current][i]; } } } int main() { scanf("%d", &n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)scanf("%d", &arr[i][j]); } backtracking(1); printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int n, k, visited[501], link[501]; vector<int> arr[501]; bool dfs(int node) { if(visited[node])return false; visited[node]=1; for(int i=0;i<arr[node].size();i++) { int next=arr[node][i]; if(link[next]==0) { link[next]=node; return true; } if(dfs(link[next])) { link[next]=node; return true; } } return false; } int main() { scanf("%d %d", &n, &k); int a, b; for(int i=1;i<=k;i++) { scanf("%d %d", &a, &b); arr[a].push_back(b); } int ans=0; for(int i=1;i<=n;i++) { memset(visited, 0, sizeof(visited)); if(dfs(i))ans++; } printf("%d", ans); } */ #include <bits/stdc++.h> using namespace std; int n, m; string s[81]; int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i=1;i<=n;i++)cin >> s[i]; } }

/*#include <bits/stdc++.h> using namespace std; #define HA 10000 int main() { int dp[11][20001]={}, arr[101]; int n, t; scanf("%d %d", &n, &t); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); dp[2][arr[1]-arr[2]+HA]=1; for(int i=2;i<=n-1;i++) { for(int j=0;j<=20000;j++) { if(dp[i][j]!=0) { dp[i+1][j-arr[i+1]]=1; dp[i+1][j+arr[i+1]]=2; } } } int dab[101]={}, top=0, start=t+HA, cnt=0; //printf("%d", dp[n][start]); for(int i=n;i>=2;i--) { if(dp[i-1][start+arr[i]]!=0||i==2) { if(dp[i][start]==2) { cnt++; } else { top++; dab[top]=dp[i][start]; for(int j=1;j<=cnt;j++) { top++; dab[top]=2; } cnt=0; } start+=arr[i]; } else if(dp[i-1][start-arr[i]]!=0||i==2) { if(dp[i][start]==2) { cnt++; } else { top++; dab[top]=dp[i][start]; for(int j=1;j<=cnt;j++) { top++; dab[top]=2; } cnt=0; } start-=arr[i]; } } for(int i=top;i>=1;i--) { printf("%d\n", dab[i]); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[9][9], n; scanf("%d", &n); for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++)scanf("%d", &arr[i][j]); } for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++)arr[i][j]-=n; } for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++) printf("%d ", arr[i][j]); printf("\n"); } } */ /* #include <bits/stdc++.h> using namespace std; int tim[10001], n, v, c; vector<pair<int, int> > arr[10001]; void dijkstra() { priority_queue<pair<int, int> > pq; tim[c]=0; pq.push({0, c}); while(!pq.empty()) { int next=pq.top().second, nextim=-pq.top().first; pq.pop(); for(int i=0;i<arr[next].size();i++) { int connect=arr[next][i].first, connecttim=arr[next][i].second; if(tim[connect]==-1||tim[connect]>nextim+connecttim) { tim[connect]=nextim+connecttim; pq.push({-tim[connect], connect}); } } } } pair<int, int> haha() { int fir=0, sec=0; for(int i=1;i<=n;i++) { if(tim[i]==-1)continue; fir++; sec=max(sec, tim[i]); } return make_pair(fir, sec); } int main() { int t, a, b, s; pair<int, int> ans; scanf("%d", &t); while(t--) { memset(tim, -1, sizeof(tim)); for(int i=0;i<=10000;i++)arr[i].clear(); scanf("%d %d %d", &n, &v, &c); for(int i=1;i<=v;i++) { scanf("%d %d %d", &a, &b, &s); arr[b].push_back({a, s}); } dijkstra(); ans=haha(); printf("%d %d\n", ans.first, ans.second); } }*/ /* #include <bits/stdc++.h> using namespace std; int n, m; int visited[1001], link[1001]; vector<int>arr[1001]; bool dfs(int x) { if(visited[x])return false; visited[x]=1; for(int i=0;i<arr[x].size();i++) { if(link[arr[x][i]]==0||dfs(link[arr[x][i]])) { link[arr[x][i]]=x; return true; } } return false; } int main() { scanf("%d %d", &n, &m); int k, a; for(int i=1;i<=n;i++) { scanf("%d", &k); for(int j=1;j<=k;j++) { scanf("%d", &a); arr[i].push_back(a); } } int ans=0; for(int i=1;i<=n;i++) { for(int i=0;i<=1000;i++)visited[i]=0; if(dfs(i))ans++; } printf("%d\n", ans); //for(int i=1;i<=m;i++)printf("%d ", link[i]); }*/ /* #include <bits/stdc++.h> using namespace std; int visited[1001], link[1001], n, m; vector<int> arr[1001]; int dfs(int x, int y) { if(visited[x]>2)return 0; visited[x]++; int connect, ret=0; for(int i=0;i<arr[x].size();i++) { connect=arr[x][i]; if(link[connect]==0||dfs(link[connect], 1)>=1) { link[connect]=x; ret++; } if(ret==2)break; if(ret==1&&y==1)break; } return ret; } int main() { scanf("%d %d", &n, &m); int k, a; for(int i=1;i<=n;i++) { scanf("%d", &k); for(int j=1;j<=k;j++) { scanf("%d", &a); arr[i].push_back(a); } } int ans=0; for(int i=1;i<=n;i++) { memset(visited, 0, sizeof(visited)); ans+=dfs(i, 0); } printf("%d\n", ans); for(int i=1;i<=m;i++)printf("%d ", link[i]); } */ //#include <bits/stdc++.h> //using namespace std; // //int n, m; //int visited[1001], link[1001]; //vector<int>arr[1001]; // //bool dfs(int x) //{ // if(visited[x])return false; // visited[x]=1; // for(int i=0;i<arr[x].size();i++) // { // if(link[arr[x][i]]==0||dfs(link[arr[x][i]])) // { // link[arr[x][i]]=x; // return true; // } // } // return false; //} // //int main() //{ // scanf("%d %d", &n, &m); // int k, a; // for(int i=1;i<=n;i++) // { // scanf("%d", &k); // for(int j=1;j<=k;j++) // { // scanf("%d", &a); // arr[i].push_back(a); // } // } // int ans=0; // for(int i=1;i<=n;i++) // { // for(int j=1;j<=2;j++){ // for(int i=0;i<=1000;i++)visited[i]=0; // if(dfs(i))ans++; // } // } // printf("%d\n", ans); // //for(int i=1;i<=m;i++)printf("%d ", link[i]); //} // #include <bits/stdc++.h> using namespace std; int ans[100], prime[2000], lef[100], rig[100], n, arr[51], rightop,, leftop; void haha(int node) { for(int i=1;i<=leftop;i++) { if(!visited[i]) { visited[i]=true; } } } int main() { scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", &arr[i]); for(int i=1;i<=n;i++) { if(arr[i]%2==0) { rightop++; rig[rightop]=arr[i]; } else { leftop++; lef[leftop]=arr[i]; } } if(rightop!=leftop) { printf("-1"); return 0; } haha(); }

/*#include <bits/stdc++.h> using namespace std; #define HA 10000 int main() { int dp[11][20001]={}, arr[101]; int n, t; scanf("%d %d", &n, &t); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); dp[2][arr[1]-arr[2]+HA]=1; for(int i=2;i<=n-1;i++) { for(int j=0;j<=20000;j++) { if(dp[i][j]!=0) { dp[i+1][j-arr[i+1]]=1; dp[i+1][j+arr[i+1]]=2; } } } int dab[101]={}, top=0, start=t+HA, cnt=0; //printf("%d", dp[n][start]); for(int i=n;i>=2;i--) { if(dp[i-1][start+arr[i]]!=0||i==2) { if(dp[i][start]==2) { cnt++; } else { top++; dab[top]=dp[i][start]; for(int j=1;j<=cnt;j++) { top++; dab[top]=2; } cnt=0; } start+=arr[i]; } else if(dp[i-1][start-arr[i]]!=0||i==2) { if(dp[i][start]==2) { cnt++; } else { top++; dab[top]=dp[i][start]; for(int j=1;j<=cnt;j++) { top++; dab[top]=2; } cnt=0; } start-=arr[i]; } } for(int i=top;i>=1;i--) { printf("%d\n", dab[i]); } }*/ #include <bits/stdc++.h> using namespace std; int main() { int arr[9][9], n; scanf("%d", &n); for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++)scanf("%d", &arr[i][j]); } for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++)arr[i][j]-=n; } for(int i=1;i<=8;i++) { for(int j=1;j<=8;j++) printf("%d ", arr[i][j]); printf("\n"); } }

/*#include <bits/stdc++.h> using namespace std; int segmenta[2000001], segmentb[2000001], n, k, arr[500001], brr[500001]; long long int suma[500001]={}, sumb[500001]={}; void make(int node, int start, int End) { if(start==End) { segmenta[node]=arr[start]; segmentb[node]=brr[start]; return ; } int mid=(start+End)/2; make(node*2, start, mid); make(node*2+1, mid+1, End); segmenta[node]=segmenta[node*2]+segmenta[node*2+1]; segmentb[node]=segmentb[node*2]+segmentb[node*2+1]; } long long int asum(int node, int start, int End, int l, int r) { if(start>=l&&End<=r)return segmenta[node]; if(start>r||End<l)return 0; int mid=(start+End)/2; return asum(node*2, start, mid, l, r)+asum(node*2+1, mid+1, End, l, r); } long long int bsum(int node, int start, int End, int l, int r) { if(start>=l&&End<=r)return segmentb[node]; if(start>r||End<l)return 0; int mid=(start+End)/2; return bsum(node*2, start, mid, l, r)+bsum(node*2+1, mid+1, End, l, r); } int binary(long long int ha) { int start=1, End=n-k+1, mid, ret=1; while(start<End) { mid=(start+End)/2; if(sumb[mid]<ha) { start=mid; ret=start; } if(sumb[mid]>ha) { End=mid-1; } else { return mid; } } return ret; } long long int Abs(long long int x) { if(x<0)return -x; return x; } int main() { long long int ans=2100000000000000; scanf("%d %d", &n, &k); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); for(int i=1;i<=n;i++)scanf("%d", &brr[i]); make(1, 1, n); for(int i=1;i<=n-k+1;i++) { suma[i]=asum(1, 1, n, i, i+k-1)-2*arr[i]; sumb[i]=(bsum(1, 1, n, i, i+k-1)-2*brr[i])*(-1); } int index; for(int i=1;i<=n-k+1;i++) { index=binary(-suma[i]); if(index+1<=n-k+1) ans=min(ans, Abs((suma[i]+sumb[index+1]))); ans=min(ans, Abs((suma[i]+sumb[index]))); } printf("%lld", ans); //|s1-s2+b-a| }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int m, f, n; scanf("%d %d %d", &m, &f, &n); }*/ #include <bits/stdc++.h> using namespace std; int main() { int ans[10]= {0, 1, 2, 5, 6, 8, 9}; int ha61[10]= {0, 99999, 199998, 499995, 599991, 799992, 899994}; int ha62[10]= {0, 9990, 19980, 49950, 59910, 79920, 89940}; int ha63[10]= {0, 900, 1800, 4500, 5100,7200, 8400}; int ha64[10]= {0, -900, -1800, -4500, -5100, -7200, -8400}; int ha65[10]= {0, -9990, -19980, -49950, -59910, -79920, -89940}; int ha66[10]= {0, -99999, -199998, -499995, -599991, -799992, -899994}; int ha51[10]= {0, 9999, 19998, 49995, 59991, 79992, 89994}; int ha52[10]= {0, 990, 1980, 4950, 5910, 7920, 8940}; int ha53[10]= {0, 0, 0, 0, -300, 0, 300}; int ha54[10]= {0, -990, -1980, -4950, -5910, -7920, -8940}; int ha55[10]= {0, -9999, -19998, -49995, -59991, -79992, -89994}; int ha41[10]= {0, 999, 1998, 4995, 5991, 7992, 8994}; int ha42[10]= {0, 90, 180, 450, 510, 720, 840}; int ha43[10]= {0, -90, -180, -450, -510, -720, -840}; int ha44[10]= {0, -999, -1998, -4995, -5991, -7992, -8994}; int ha31[10]= {0, 99, 198, 495, 591, 792, 894}; int ha32[10]= {0, 0, 0, 0, -30, 0, -30}; int ha33[10]= {0, -99, -198, -495, -591, -792, -894}; int ha21[10]= {0, 9, 18, 45, 51, 72, 84}; int ha22[10]= {0, -9, -18, -45, -51, -72, -84}; int ha11[10]= {0, 0, 0, 0, -3, 0, 3}; int t; scanf("%d", &t); while(t--) { int x; scanf("%d", &x); for(int i=1; i<=6; i++) { if(ha11[i]==x) { printf("%d\n", ans[i]); continue; } } for(int i1=1; i1<=6; i1++) { for(int i2=0; i2<=6; i2++) { if(ha21[i1]+ha22[i2]==x) { printf("%d\n", ans[i1]*10+ans[i2]); continue; } } } for(int i1=1; i1<=6; i1++) { for(int i2=0; i2<=6; i2++) { for(int i3=0; i3<=6; i3++) { if(ha31[i1]+ha32[i2]+ha33[i3]==x) { printf("%d", ans[i1]*100+ans[i2]*10+ans[i3]); continue; } } } } for(int i1=1; i1<=6; i1++) { for(int i2=0; i2<=6; i2++) { for(int i3=0; i3<=6; i3++) { for(int i4=0; i4<=6; i4++) { if(ha41[i1]+ha42[i2]+ha43[i3]+ha44[i4]==x) { printf("%d\n", ans[i1]*1000+ans[i2]*100+ans[i3]*10+ans[i4]); continue; } } } } } for(int i1=1; i1<=6; i1++) { for(int i2=0; i2<=6; i2++) { for(int i3=0; i3<=6; i3++) { for(int i4=0; i4<=6; i4++) { for(int i5=0;i5<=6;i5++) { if(ha51[i1]+ha52[i2]+ha53[i3]+ha54[i4]+ha55[i5]==x) { printf("%d\n", ans[i1]*10000+ans[i2]*1000+ans[i3]*100+ans[i4]*10+ans[i5]); continue; } } } } } } } }

/*#include <bits/stdc++.h> using namespace std; int segment[200001], A[50001], B[50001], pos[100001], n, con[50001]; int sum(int node, int start, int End, int l, int r) { if(l<=start&&r>=End)return segment[node]; if(start>r||End<l)return 0; int mid=(start+End)/2; return sum(node*2, start, mid, l, r)+sum(node*2+1, mid+1, End, l, r); } void update(int node, int start, int End, int target) { if(start==End) { if(start==target)segment[node]++; return ; } if(start<=target&&End>=target) { segment[node]++; } else { return ; } int mid=(start+End)/2; update(node*2, start, mid, target); update(node*2+1, mid+1, End, target); } int main() { scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &A[i]); for(int i=1;i<=n;i++) { scanf("%d", &B[i]); pos[B[i]]=i; } int ans=0, m, k, p; for(int i=1;i<=n;i++) { p=pos[A[i]]; ans+=sum(1, 1, n, p, n); con[p]=1; update(1, 1, n, p); } printf("%d", ans); } */ /* #include <bits/stdc++.h> using namespace std; int main() { int t, n, arr[100001], m, check[100001], canuse[100001], top; scanf("%d", &t); bool ans; while(t--) { m=2147483647; top=0; memset(check, 0, sizeof(check)); scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d", &arr[i]); m=min(m, arr[i]); } for(int i=1; i<=n; i++) { if(arr[i]%m==0) { top++; canuse[top]=arr[i]; } else { check[i]=1; } } sort(canuse+1, canuse+1+top); top=0; for(int i=1; i<=n; i++) { if(check[i]==1) continue; top++; arr[i]=canuse[top]; } ans=true; for(int i=2; i<=n; i++) { if(arr[i]>=arr[i-1]) { continue; } else { ans=false; break; } } if(ans) { printf("YES\n"); } else { printf("NO\n"); } } }*/ /* #include <bits/stdc++.h> using namespace std; int Gcd(int x, int y) { if(x==0)return y; return Gcd(y%x, x); } int main() { string s; int ha=1, haha=0, hahaha; cin >> s; for(int i=0;i<s.size();i++) { if(s[i]=='.') { hahaha=i+1; break; } } for(int i=1;i<=s.size()-hahaha;i++) { ha*=10; } for(int i=hahaha;i<s.size();i++) { haha*=10; haha+=s[i]-'0'; } int gcd=Gcd(haha, ha); printf("%d %d", haha/gcd, ha/gcd); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int dp[100001][2]={}; dp[1][1]=1; dp[1][0]=1; for(int i=2;i<=100000;i++) { dp[i][1]=dp[i-1][1]+dp[i-1][0]; dp[i][0]=dp[i-1][1]; dp[i][1]%=1000000007; dp[i][0]%=1000000007; } int n; scanf("%d", &n); printf("%d", (dp[n][1]+dp[n][0])%1000000007); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int k, n; cin >> k >> n; printf("%d", k*n); }*/ /* #include <bits/stdc++.h> using namespace std; int gcd(int x, int y) { if(y==0)return x; return gcd(y, x%y); } int main() { int a, b, temp; scanf("%d %d", &a, &b); if(a<b) { temp=a; a=b; b=temp; } int ha=gcd(a, b); if(ha==1) { printf("coprime"); return 0; } printf("no"); } */ /* #include <bits/stdc++.h> using namespace std; int main() { int n, arr[100001]; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &arr[i]); sort(arr+1, arr+1+n); int mid=(n+1)/2, top=0, haha[100001]; long long int need[100001]= {}; for(int i=mid; i<=n; i++) { top++; haha[top]=arr[i]; } //printf("\ntop:%d\n", top); for(int i=2; i<=top; i++) { need[i]=need[i-1]+(haha[i]-haha[i-1])*(i-1); } //printf("\nneed:%d\n", need[2]); int t, x, start, End; scanf("%d", &t); while(t--) { scanf("%d", &x); if(x>=need[top]) { printf("%d\n", haha[top]+(x-need[top])/top); } else { start=1, End=top; while(start<End) { mid=(start+End)/2; if(need[mid]>x) { End=mid-1; } else if(need[mid]<x) { start=mid; if(start+1==End) { if(need[start+1]<=x) start++; break; } } else { start=mid; break; } } //printf("arr:%d\n", haha[start]); printf("%d\n", haha[start]+(x-need[start])/(start)); } } }*/

/*#include <bits/stdc++.h> using namespace std; int n, top, cnt=0; char ans[8]; void haha(int x, int y) { if(x==n) { cnt++; if(cnt%2==0) return ; for(int i=1;i<=top;i++) printf("%c", ans[i]); printf("\n"); return ; } if(y==0) { top++; ans[top]='O'; haha(x+1, 0); haha(x+1, 1); top--; } else { top++; ans[top]='X'; haha(x+1, 0); haha(x+1, 1); top--; } } int main() { scanf("%d", &n); haha(0, 0); haha(0, 1); }*/ /* #include <bits/stdc++.h> using namespace std; int gavi[10][10]={}, sevi[10][10]={}, arr[10][10], ha=0, boxvi[10][10]; int boxn(int x, int y) { int box=1; if(x==1||x==2||x==3) { box=1; } else if(x==4||x==5||x==6) { box=4; } else { box=7; } if(y==4||y==5||y==6) { box++; } else if(y==7||y==8||y==9) { box+=2; } return box; } void ans(int x, int y) { if(x==10&&ha==0) { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) printf("%d ", arr[i][j]); printf("\n"); } ha=1; return ; } if(y==10) { ans(x+1, 1); return ; } if(arr[x][y]!=0) { ans(x, y+1); return ; } int possible[10]={}, top=0; for(int i=1;i<=9;i++) { if(gavi[x][i]==0&&sevi[y][i]==0&&boxvi[boxn(x, y)][i]==0) { top++; possible[top]=i; } } for(int i=1;i<=top;i++) { int con=possible[i]; gavi[x][con]=1; sevi[y][con]=1; boxvi[boxn(x, y)][con]=1; arr[x][y]=con; ans(x, y+1); gavi[x][con]=0; sevi[y][con]=0; boxvi[boxn(x, y)][con]=0; arr[x][y]=0; } } int main() { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) scanf("%d", &arr[i][j]); } int temp; for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { if(arr[i][j]!=0) { boxvi[boxn(i, j)][arr[i][j]]=1; gavi[i][arr[i][j]]=1; sevi[j][arr[i][j]]=1; } } } ans(1, 1); if(ha==0) { printf("Not Possible"); } }*/ /* #include <bits/stdc++.h> using namespace std; int n, ans[81], top, hahaha; void haha(int x, int y) { // printf("haha\n"); if(top==n&&hahaha==0) { for(int i=1;i<=top;i++) printf("%d", ans[i]); hahaha=1; return ; } if(x==n+1) return ; top++; ans[top]=y; int a=2, b, c; while(a<=x) { c=1; b=a/2; for(int i=x-a+1;i<=x-b;i++) { if(ans[i]!=ans[i+b]) { c=0; break; } } if(c==1){ top--; return ; } a+=2; } for(int i=1;i<=3;i++) { if(i!=y&&hahaha==0) { haha(x+1, i); } } top--; } int main() { scanf("%d", &n); haha(1, 1); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); if(n==1) { printf("2"); return 0; } int ans=4, cur=2; for(int i=3;i<=n;i++) { ans+=cur+1; cur++; ans%=137; } printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int k, temp, mo, top=0; scanf("%d", &k); string s; cin >> s; char ans[21]={}; for(int i=0;i<s.size();i++) { mo=3*(i+1)+k; temp=26+s[i]-'A'+1-mo; if(temp!=26) temp%=26; top++; ans[top]=temp+'A'-1; } for(int i=1;i<=top;i++) printf("%c", ans[i]); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n, cur, old; float sum=0; scanf("%d", &n); string s; for(int i=1;i<=n;i++) { cin >> s; for(int i=1;i<s.size();i++) { if(s[i]=='M'||s[i]=='F') { cur=i+2; old=s[cur]-'0'; cur++; while(s[cur]!=',') { old*=10; old+=s[cur]-'0'; cur++; } break; } } sum+=old; } printf("%.2f", sum/(float)n); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int prime[4000001]={}, a, b; scanf("%d %d", &a, &b); for(int i=3;i<=2000;i++) { for(int j=i*2;j<=4000000;j+=i) { prime[j]=1; } } for(int i=a;i<=b;i++) { if(i%2==0)continue; if(prime[i]==0&&prime[i+2]==0&&i+2<=b) { printf("%d %d\n", i, i+2); } } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n, i; scanf("%d", &n); long long int sum=0; for(i=1;i*i<n;i++) { if(n%i==0) sum+=i+n/i; } if(i*i==n)sum+=i; printf("%lld", sum); }*/ /* #include <bits/stdc++.h> using namespace std; string s; int hab(int x, int y) { int sum=0; for(int i=x;i<=y;i++) { sum*=10; sum+=s[i]-'0'; } return sum; } int main() { long long int dp[1001]={}, k; scanf("%d", &k); cin >> s; dp[0]=s[0]-'0'; for(int i=1;i<s.size();i++) { if(i+1<=k) dp[i]=hab(0, i); for(int j=1;i-j>=0;j++) { if(j>k)break; dp[i]=max(dp[i], dp[i-j]+hab(i-j+1, i)); } } printf("%lld", dp[s.size()-1]); }*/

/*#include <bits/stdc++.h> using namespace std; int n, lef[200001], rig[200001], all[200001], ans[200001], arr[50001]; void make(int node, int start, int End) { if(start==End) { lef[node]=rig[node]=all[node]=ans[node]=arr[End]; return ; } int mid=(start+End)/2; make(node*2, start, mid); make(node*2+1, mid+1, End); lef[node]=max(lef[node*2], all[node*2]+lef[node*2+1]); rig[node]=max(rig[node*2+1], all[node*2+1]+rig[node*2]); all[node]=all[node*2]+all[node*2+1]; ans[node]=max(max(ans[node*2], ans[node*2+1]), rig[node*2]+lef[node*2+1]); } int le(int node, int start, int End, int l, int r) { if(End<start)return -2147483647; if(start>=l&&End<=r)return lef[node]; if(start>r||End<l)return -2147483647; int mid=(start+End)/2; int ret=le(node*2, start, min(mid, r), l, r); if(mid>=l&&mid+1<=r) ret=max(ret, ans[node*2]+le(node*2+1, max(mid+1, l), End, l, r)); return ret; } int ri(int node, int start, int End, int l, int r) { if(End<start)return -2147483647; if(start>=l&&End<=r)return rig[node]; if(start>r||End<l)return -2147483647; int mid=(start+End)/2; int ret=ri(node*2+1, max(l, mid+1), End, l, r); if(mid>=l&&mid+1<=r)ret=max(ret, ans[node*2+1]+ri(node*2, start, min(mid, r), l, r)); return ret; } int Ans(int node, int start, int End, int l, int r) { if(start>=l&&End<=r)return ans[node]; if(start>r||End<l)return -2147483647; int mid=(start+End)/2; int ret=max(Ans(node*2, start, mid, l, r), Ans(node*2+1, mid+1, End, l, r)); if(mid>=l&&mid+1<=r) { ret=max(ret, le(1, 1, n, mid+1, min(r, End))+ri(1, 1, n, max(l, start), mid)); } return ret; } int main() { scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); int m, a, b; make(1, 1, n); scanf("%d", &m); while(m--) { scanf("%d %d", &a, &b); printf("%d\n", Ans(1, 1, n, a, b)); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[2000]={}; int n, a; scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%d", &a); arr[a]++; } vector<int> ans[20001]; for(int i=1;i<=n;i++) { //if(arr[i]==0)continue; ans[arr[i]].push_back(i); } sort(arr, arr+1001); //printf("%d\n", arr[1000]); int b, c, d, temp=arr[1000]; for(int i=1000;i>=1;i--) { if(arr[i]!=temp) { temp=arr[i]; break; } } //printf("%d\n", ans[arr[1000]][0]); //sort(ans[arr[1000]].begin(), ans[arr[1000]].end()); // sort(ans[temp].begin(), ans[temp].end()); int ba1=ans[arr[1000]][0], sa1=ans[arr[1000]][0], ba2=ans[temp][0], sa2=ans[temp][0]; for(int i=0;i<ans[arr[1000]].size();i++) { ba1=max(ba1, ans[arr[1000]][i]); sa1=min(sa1, ans[arr[1000]][i]); } for(int i=0;i<ans[temp].size();i++) { ba2=max(ba2, ans[temp][i]); sa2=min(sa2, ans[temp][i]); } int real=max(abs(ba1-sa2), abs(sa1-ba2)); printf("%d", real); }*/ /* #include <bits/stdc++.h> using namespace std; void haha(int x, int y) { if(y==0)return ; if(x==0){ printf("\n"); haha(y-1, y-1); return ; } printf("*"); haha(x-1, y); } int main() { int n; scanf("%d", &n); haha(n, n); }*/ #include <bits/stdc++.h> using namespace std; void haha(int x, int y) { if(x==y) { printf("%d", x); return ; } if(x>y) { haha(x/2, y); } else { haha(x, y/2); } } int main() { int a, b; scanf("%d %d", &a, &b); haha(a, b); }

/*#include <bits/stdc++.h> using namespace std; int segment[200001], arr[50001], n, ret, m; int make(int node, int start, int End) { if(start==End)return segment[node]=arr[start]; int mid=(start+End)/2; int l=arr[mid], r=arr[mid+1], le=l, ri=r; for(int i=mid-1;i>=start;i--) { l+=arr[i]; le=max(l, le); } for(int i=mid+2;i<=End;i++) { r+=arr[i]; ri=max(r, ri); } return segment[node]=max(ri+le, max(make(node*2, start, mid), make(node*2+1, mid+1, End))); } int res(int node, int start, int End, int lef, int rig) { if(lef<=start&&End<=rig)return segment[node]; if(End<lef||start>rig)return -2147483647; int mid=(start+End)/2; int l=arr[mid], r=arr[mid+1], le=l, ri=r; for(int i=mid-1;i>=max(start, lef);i--) { l+=arr[i]; le=max(l, le); } for(int i=mid+2;i<=min(rig, End);i++) { r+=arr[i]; ri=max(r, ri); } if(mid>=lef&&mid+1<=rig) { } else { le=-987654321, ri=-987654321; } return max(ri+le, max(res(node*2, start, mid, lef, rig), res(node*2+1, mid+1, End, lef, rig))); } int main() { scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); make(1, 1, n); //printf("%d", segment[2]); scanf("%d", &m); int a, b; for(int i=1;i<=m;i++) { scanf("%d %d", &a, &b); printf("%d\n", res(1, 1, n, a, b)); } }*/ #include <bits/stdc++.h> using namespace std; int main() { }

/*#include <bits/stdc++.h> using namespace std; int segment[200001], n, arr[50001], ret; int make(int node, int start, int End) { if(start==End){ return segment[node]=arr[start]; } int mid=(start+End)/2; int ri=make(node*2, start, mid); int le=make(node*2+1, mid+1, End); segment[node]=max(ri, le); return segment[node]; } int result(int node, int start, int End, int l, int r) { if(End<l||start>r)return 0; if(l<=start&&End<=r)return segment[node]; int mid=(start+End)/2; int ri=result(node*2, start, mid, l, r); int le=result(node*2+1, mid+1, End, l, r); ret=max(ri, le); return ret; } int main() { scanf("%d", &n); for(int i=0;i<n;i++) scanf("%d", &arr[i]); make(1, 0, n-1); int m; scanf("%d", &m); int a, b; for(int i=1;i<=m;i++) { scanf("%d %d", &a, &b); printf("%d ", result(1, 0, n-1, a-1, b-1)); } }*/ /* #include <bits/stdc++.h> using namespace std; int maxsegment[200001], arr[50001], n, minsegment[200001]; void make(int node, int start, int End) { if(start==End) { maxsegment[node]=minsegment[node]=arr[start]; return ; } int mid=(start+End)/2; make(node*2, start, mid); make(node*2+1, mid+1, End); maxsegment[node]=max(maxsegment[node*2], maxsegment[node*2+1]); minsegment[node]=min(minsegment[node*2], minsegment[node*2+1]); } int maxres(int node, int start, int End, int l, int r) { if(start>=l&&End<=r)return maxsegment[node]; if(End<l||start>r)return 0; int mid=(start+End)/2; int res1=maxres(node*2, start, mid, l, r); int res2=maxres(node*2+1, mid+1, End, l, r); return max(res1, res2); } int minres(int node, int start, int End, int l, int r) { if(start>=l&&End<=r)return minsegment[node]; if(End<l||start>r)return 2147483647; int mid=(start+End)/2; return min(minres(node*2, start, mid, l, r), minres(node*2+1, mid+1, End, l, r)); } int main() { int m; scanf("%d %d", &n, &m); for(int i=1;i<=n;i++) scanf("%d", &arr[i]); make(1, 1, n); int a, b; //printf("%d %d", maxsegment[1], minsegment[1]); for(int i=1;i<=m;i++) { scanf("%d %d", &a, &b); printf("%d\n", maxres(1, 1, n, a, b)-minres(1, 1, n, a, b)); } }*/ #include <bits/stdc++.h> using namespace std; int segment[200001], n, m, arr[50001]; int make(int node, int start, int End) { if(start==End)return segment[node]=arr[start]; int mid=(start+End)/2; int l=mid, r=mid+1, le=l, ri=r; for(int i=mid-1;i>=start;i--) { l+=arr[i]; le=max(l, le); } for(int i=mid+2;i<=End;i++) { r+=arr[i]; ri=max(ri, r); } return segment[node]=max(le+ri, max(make(node*2, start, mid), make(node*2+1, mid+1, End))); } int res(int node, int start, int End, int lef, int rig) { if(start>=lef&&End<=rig)return segment[node]; if(End<lef||start>rig)return -987654321; int mid=(start+End)/2; int l=mid, r=mid+1, le=l, ri=r; for(int i=mid-1;i>=max(start, lef);i--) { l+=arr[i]; le=max(l, le); } for(int i=mid+2;i<=min(End, rig);i++) { r+=arr[i]; ri=max(ri, r); } return max(max(le+ri, res(node*2, start, mid, lef, rig)), res(node*2+1, mid+1, End, lef, rig)); } int main() { scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &arr[i]); make(1, 1, n); printf("%d", segment[1]); scanf("%d", &m); int a, b; for(int i=1;i<=m;i++) { scanf("%d %d", &a, &b); printf("%d\n", res(1, 1, n, a, b)); } }

/*#include <bits/stdc++.h> using namespace std; int c, n, temp[11], ans[11], max1=-2, max2=-1, arr[11], top, cur; void haha(int x) { if(x==n+1) { if(cur>max1||(cur==max1&&top>=max2)) { max1=cur; max2=top; for(int i=1;i<=10;i++) ans[i]=temp[i]; } return ; } if(cur+arr[x]<=c) { top++; cur+=arr[x]; temp[top]=arr[x]; haha(x+1); top--; cur-=arr[x]; } haha(x+1); } int main() { scanf("%d %d", &c, &n); for(int i=1;i<=n;i++) scanf("%d", &arr[i]); haha(1); if(max2==0) { printf("-1"); return 0; } for(int i=1;i<=max2;i++) printf("%d ", ans[i]); }*/ /* #include <bits/stdc++.h> using namespace std; int n, m, k; vector<pair<int, int> > arr[100001]; int main() { scanf("%d %d %d", &n, &m, &k); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b, ans=0, cur, temp, boo; cin >> a >> b; for(int i=a;i<=b;i++) { boo=1; for(int j=1;j<i;j++) { cur=j; temp=j; while(temp>0) { cur+=temp%10; temp/=10; } if(cur==i) boo=0; } if(boo) ans+=i; } printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; string s="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; void haha(int x, int y) { if(x==0) return ; haha(x/y, y); printf("%c",s[x%y]); } int main() { int n, k; scanf("%d %d", &n, &k); if(n==0) { printf("0"); return 0; } haha(n, k); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b; scanf("%d %d" , &a, &b); vector<int> arr; for(int i=1;i*i<=a;i++) { if(a%i==0) { arr.push_back(i); arr.push_back(a/i); } } for(int i=1;i*i<=b;i++) { if(b%i==0) { arr.push_back(i); arr.push_back(b/i); } } sort(arr.begin(), arr.end()); int temp=arr[1]; printf("%d ", arr[1]); for(int i=1;i<arr.size();i++) { if(temp==arr[i])continue; printf("%d ", arr[i]); temp=arr[i]; } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b, ans=0, arr[10]={}, cur, top=0, boo; cin >> a >> b; for(int i=a;i<=b;i++) { for(int j=a;j<=b;j++) { boo=1; cur=i*j; top=0; while(cur>0) { top++; arr[top]=cur%10; cur/=10; } for(int k=1;k<top-k+1;k++) { if(arr[k]!=arr[top-k+1]) boo=0; } if(boo) ans=max(ans, i*j); } } printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; bool isprime(long long int x) { for(long long int i=2;i*i<=x;i++) { if(x%i==0) return false; } return true; } int main() { long long int n, ans=0; cin >> n; for(long long int i=2;i*i<=n;i++) { if(n%i==0) { if(isprime(i)) ans=max(ans, i); if(isprime(n/i)) ans=max(ans, n/i); } } if(isprime(n)) ans=n; printf("%lld", ans); }*/ #include <bits/stdc++.h> using namespace std; int main() { }

/*#include <bits/stdc++.h> using namespace std; int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); int com[31][31]={}; memset(com, 1, sizeof(com)); com[0][0]=1; for(int i=1;i<=30;i++) { com[i][0]=1; com[i][i]=1; for(int j=1;j<i;j++) com[i][j]=com[i-1][j-1]+com[i-1][j]; } if(k==0) { printf("%d", com[n+m-2][n-1]); return 0; } int mod=k%m; int mok=k/m; if(mod==0)mok--; if(mod==0)mod=m; int ans=com[((mok)+1)+mod-1-1][mod-1]*com[n-(mok)+m-(mod)+1-1-1][m-(mod)+1-1]; printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int ans=0, a, b, n; scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%d %d", &a, &b); ans+=b%a; } printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[7][2]={}, n, k, a, b, ans=0; scanf("%d %d", &n, &k); for(int i=1;i<=n;i++) { scanf("%d %d", &a, &b); arr[b][a]++; } ans+=(arr[1][1]+arr[1][0]+arr[2][1]+arr[2][0])/k+1; if((arr[1][1]+arr[1][0]+arr[2][1]+arr[2][0])%k==0)ans--; ans+=(arr[3][0]+arr[4][0])/k+1; if((arr[3][0]+arr[4][0])%k==0)ans--; ans+=(arr[3][1]+arr[4][1])/k+1; if((arr[3][1]+arr[4][1])%k==0)ans--; ans+=(arr[5][0]+arr[6][0])/k+1; if((arr[5][0]+arr[6][0])%k==0)ans--; ans+=(arr[5][1]+arr[6][1])/k+1; if((arr[5][1]+arr[6][1])%k==0)ans--; printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n; string s; cin >> n; while(n--) { cin >> s; for(int i=s.size()-1;i>=0;i--) printf("%c", s[i]); printf("\n"); } }*/ /* #include <bits/stdc++.h> using namespace std; int dp[100001]; int dab(int x) { if(dp[x]!=0) return dp[x]; if(x==1) return 1; if(x%2==0) { return dp[x]=dab(x/2)+1; } else { return dp[x]=dab(3*x+1)+1; } } int main() { int a, b; scanf("%d %d", &a, &b); int da=-1, ma; for(int i=a;i<=b;i++) { if(dab(i)>da) { da=dab(i), ma=i; } } printf("%d %d", ma, da); } */ /* #include <bits/stdc++.h> using namespace std; void dab(int x, int y) { if(x==0) return ; if(y==1&&x%10==0) { dab(x/10, 1); return ; } printf("%d", x%10); dab(x/10, 0); } int main() { int n; scanf("%d", &n); if(n==0){ printf("0"); return 0; } dab(n, 1); }*/ /* #include <bits/stdc++.h> using namespace std; string s="0123456789ABCDEF"; void dab(int x, int y) { if(x==0)return; dab(x/y, y); printf("%c", s[x%y]); } int main() { int n, k; scanf("%d %d", &n, &k); dab(n, k); }*/ #include <bits/stdc++.h> using namespace std; int main() { int a, b; scanf("%d %d", &a, &b); }

/*#include <bits/stdc++.h> using namespace std; int main() { double a, b, d; char c; scanf("%lfx%c%lf", &a, &c, &b); d=-b; printf("%.2lf", d/a); }*/ /* #include <bits/stdc++.h> using namespace std; bool boo=false; unsigned long long n, a, b, c; struct cmp{ bool operator()(unsigned long long x, unsigned long long y) { return x>y; } }; priority_queue <unsigned long long, vector<unsigned long long>, cmp> pq; void haha(unsigned long long t, int cnt) { if(t<0||cnt>=20) return ; if(t%n==0) { pq.push(t); } haha(t*10, cnt+1); haha(t*10+1, cnt+1); } int main() { cin >> n; haha(1, 0); if(pq.empty()) { printf("0"); return 0; } printf("%llu", pq.top()); }*/ /* #include <bits/stdc++.h> using namespace std; int arr[1002][1002], dist[1002][1002], n, m, start=0, top=0, qu[1002][2]; int anc, nex, ney; int ha[4][2]={ {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; void bfs(int x, int y) { anc=dist[x][y]; for(int i=0;i<=3;i++) { nex=x+ha[i][0], ney=y+ha[i][1]; if(nex<1||ney<1||nex>n||ney>m||abs(arr[x][y]-arr[nex][ney])>1||dist[nex][ney]==987654321) continue; top++; qu[top][0]=nex, qu[top][1]=ney; dist[nex][ney]=dist[x][y]+1; } } int main() { for(int i=0;i<=1001;i++) for(int j=0;j<=1001;j++) dist[i][j]=987654321; scanf("%d %d", &n, &m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d", &arr[i][j]); } top++; qu[top][0]=1, qu[top][1]=1; dist[1][1]=1; while(top!=start) { start++; bfs(qu[start][0], qu[start][1]); } if(dist[n][m]==987654321) { printf("0"); return 0; } printf("%d", dist[n][m]); } */ /* #include <bits/stdc++.h> using namespace std; #define INF 4500000000 struct line{ long long int m, n; }; double cross(struct line x, struct line y) { return (y.n-x.n)/(x.m-y.m); } int main() { struct line temp, stk[100001]; long long int right=0, siz=0, r[100001], l[100001], a, b, t, top=0, pos, f, mid, start, End, left; int n; long long int dp[10001]={}; scanf("%lld", &t); while(t--) { left=INF; top=0, siz=0, right=0; scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%lld %lld", &a, &b); if(left==INF) left=min(left, a-b); if(a+b<=right) continue; while(a-b<=l[siz]&&siz>0) { siz--; } siz++; left=a-b; r[siz]=a+b, l[siz]=a-b, right=a+b; } dp[1]=(r[1]-l[1])*(r[1]-l[1]); top++; stk[top].m=-l[1]*2, stk[top].n=l[1]*l[1]; for(int i=2;i<=siz;i++) { temp.m=(-1)*(l[i])*2, temp.n=dp[i-1]+l[i]*l[i]; while(top>1) { if(cross(stk[top], stk[top-1])<cross(temp, stk[top])) break; top--; } top++; stk[top]=temp; f=r[i]; pos=top; if(f<cross(stk[top], stk[top-1])) { start=1, End=top; while(start+1<End) { mid=(start+End)/2; if(cross(stk[mid], stk[mid-1])>f) { End=mid-1; } else { start=mid; } } pos=start; } dp[i]=(stk[pos].m*f)+stk[pos].n+(r[i]*r[i]); dp[i]=min(dp[i], (r[i]-l[1])*(r[i]-l[1])); } cout << dp[siz]/4; if(dp[siz]%4==1)printf(".25\n"); if(dp[siz]%4==2)printf(".50\n"); if(dp[siz]%4==3)printf(".75\n"); if(dp[siz]%4==0)printf(".00\n"); //for(int i=1;i<=siz;i++) //printf("%d\n", dp[i]); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n, k, arr[20001]={}, ans=0; scanf("%d %d\n", &n, &k); string s; cin >> s; for(int i=0;i<n;i++) { if(s[i]=='H') arr[i]=1; } for(int i=0;i<n;i++) { //printf("%d ", arr[i]); if(s[i]!='H') continue; for(int j=max(0, i-k);j<=min(n-1, i+k);j++) { if(arr[j]==0) { arr[j]=1; ans++; break; } } } printf("%d", ans); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b, c, d, n, k; cin >> n >> k; if(k*(k+1)/2>n) { printf("-1"); return 0; } n-=k*(k+1)/2; n%=k; printf("%d", k+n-1); }*/ /* #include <bits/stdc++.h> using namespace std; int ans, arr[11][11], visited[11], n; void backt(int x, int y) { if(x==n) { ans=max(ans, y); return ; } for(int i=1;i<=n;i++) { if(!visited[i]) { visited[i]=1; backt(x+1, y+arr[x+1][i]); visited[i]=0; } } } int main() { scanf("%d", &n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%d", &arr[i][j]); } backt(0, 0); printf("%d", ans); } */ #include <bits/stdc++.h> using namespace std; int main() { int n, ans=0; cin >> n; string s; for(int i=1;i<=n;i++) { cin >> s; for(int j=0;j<s.size();j++) { if(s[j]==',') { if(s[j+1]=='M') ans++; break; } } } printf("%d\n%d", ans, n-ans); }

/*#include <stdio.h> #include <stdlib.h> int min(int x, int y) { if(x>y) return y; return x; } int main() { int arr[4][4]={}, i, j; scanf("%d %d %d %d %d %d %d %d", &arr[1][1], &arr[2][1], &arr[1][2], &arr[3][1], &arr[2][2], &arr[1][3], &arr[3][2], &arr[2][3]); printf(" %d\n %d %d\n%d %d %d\n %d %d\n *\n", arr[1][1], arr[2][1], arr[1][2], arr[3][1], arr[2][2], arr[1][3], arr[3][2], arr[2][3]); char c[2]; int curx=3, cury=3, tempx, tempy; int t=20; while(t--) { tempx=curx, tempy=cury; scanf("%s", c); if(c[0]=='b'&&c[1]=='l') { curx--; if(curx<1) { curx++; printf("error\n"); continue; } arr[tempx][tempy]=arr[curx][cury]; arr[curx][cury]=10; } if(c[0]=='b'&&c[1]=='r') { cury--; if(cury<1) { cury++; printf("error\n"); continue; } arr[tempx][tempy]=arr[curx][cury]; arr[curx][cury]=10; } if(c[0]=='t'&&c[1]=='l') { cury++; if(cury>3) { cury--; printf("error\n"); continue; } arr[tempx][tempy]=arr[curx][cury]; arr[curx][cury]=10; } if(c[0]=='t'&&c[1]=='r') { curx++; if(curx>3) { curx--; printf("error\n"); continue; } arr[tempx][tempy]=arr[curx][cury]; arr[curx][cury]=10; } printf(" "); if(arr[1][1]!=10){ printf("%d\n", arr[1][1]); } else { printf("*\n"); } printf(" "); if(arr[2][1]!=10){ printf("%d ", arr[2][1]); } else { printf("* "); } if(arr[1][2]!=10){ printf("%d\n", arr[1][2]); } else { printf("*\n"); } if(arr[3][1]!=10){ printf("%d ", arr[3][1]); } else { printf("* "); } if(arr[2][2]!=10){ printf("%d ", arr[2][2]); } else { printf("* "); } if(arr[1][3]!=10){ printf("%d\n", arr[1][3]); } else { printf("*\n"); } printf(" "); if(arr[3][2]!=10){ printf("%d ", arr[3][2]); } else { printf("* "); } if(arr[2][3]!=10){ printf("%d\n", arr[2][3]); } else { printf("*\n"); } printf(" "); if(arr[3][3]!=10){ printf("%d", arr[3][3]); } else { printf("*"); } printf("\n"); } } */ #include <stdio.h> int arr[6][6]= {}; #define INF 987654321 int visited[6][6]; void dfs(int x, int y) { if(x<1||y<1||x>4||y>4) return ; if(visited[x][y]) return ; visited[x][y]=1; if(arr[x+1][y]==arr[x][y]) dfs(x+1, y); if(arr[x-1][y]==arr[x][y]) dfs(x-1, y); if(arr[x][y+1]==arr[x][y]) dfs(x, y+1); if(arr[x][y-1]==arr[x][y]) dfs(x, y-1); arr[x][y]=INF; } int main() { memset(arr, -1, sizeof(arr)); for(int i=1; i<=4; i++) for(int j=1; j<=4; j++) scanf("%d", &arr[i][j]); for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) printf("%d ", arr[i][j]); printf("\n"); } int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); int temp=arr[a][b]; arr[a][b]=arr[c][d]; arr[c][d]=temp; int t[6][6]; while(1) { memset(visited, 0, sizeof(visited)); for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) t[i][j]=arr[i][j]; } for(int i=1; i<=4; i++) { for(int j=1; j<=4; j++) { if(!visited[i][j]&&arr[i][j]==arr[i+1][j]||arr[i][j]==arr[i][j+1]) { dfs(i, j); } } } for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { if(arr[i][j]!=INF&&arr[i+1][j]==INF) { arr[i+1][j]=arr[i][j]; arr[i][j]=INF; } } } int boo=1; for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { if(arr[i][j]!=t[i][j]) boo=0; } } if(boo) { for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { if(arr[i][j]==INF) { printf("* "); } else { printf("%d ", arr[i][j]); } } printf("\n"); } return 0; } } }

/*#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int cnt=0; if(s.size()>=1) { if(s[0]=='3'||s[0]=='6'||s[0]=='9') cnt++; } if(s.size()>=2) { if(s[1]=='3'||s[1]=='6'||s[1]=='9') cnt++; } if(s.size()>=3) { if(s[2]=='3'||s[2]=='6'||s[2]=='9') cnt++; } if(cnt==1) { printf("K"); return 0; } if(cnt==2) { printf("KK"); return 0; } if(cnt==3) { printf("KKK"); return 0; } cout<<s; } */ /* #include <bits/stdc++.h> using namespace std; int main() { int n, s; scanf("%d %d", &n, &s); int arr[100001]={}; for(int i=1;i<=n;i++) scanf("%d", &arr[i]); int mid, start=1, End=n; while(start<=End) { mid=(start+End)/2; if(arr[mid]<s) { start=mid+1; } else if(arr[mid]>s) { End=mid-1; } else { printf("%d", mid); return 0; } } printf("-1"); }*/ /* #include <bits/stdc++.h> using namespace std; int a, n, arr[22]={}, ans=0; void haha(int x, int y) { if(y==n+1&&x<a) { ans=max(ans, x); return ; } if(x>a) { return ; } haha(x+arr[y], y+1); haha(x, y+1); } int main() { scanf("%d", &a); scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", &arr[i]); haha(0, 1); printf("%d", ans); } */ /* #include <bits/stdc++.h> using namespace std; int arr[7][3], puha[7][3], ans; void haha(int x, int y, int z) { for(int i=1;i<=6;i++) { for(int j=0;j<=2;j++) { if(arr[i][j]<puha[i][j]||arr[i][j]>=6) return ; } } if(z==16) { ans=1; } if(y>6) { x++; y=x+1; } puha[x][0]++; puha[y][2]++; haha(x, y+1, z+1); puha[x][0]--; puha[y][2]--; puha[x][1]++; puha[y][1]++; haha(x, y+1, z+1); puha[x][1]--; puha[y][1]--; puha[x][2]++; puha[y][0]++; haha(x, y+1, z+1); puha[x][2]--; puha[y][0]--; } int main() { for(int ppp=0;ppp<=3;ppp++) { memset(puha, 0, sizeof(puha)); ans=0; for(int i=1;i<=6;i++){ for(int j=0;j<=2;j++){ scanf("%d", &arr[i][j]);} } haha(1, 2, 1); printf("%d ", ans); } }*/ /* #include <bits/stdc++.h> using namespace std; int n; int cnt, visited[14], arr[14], visit[14][14]; void chess(int x) { if(x==n+1) { if(cnt<3){ for(int i=1;i<=n;i++) printf("%d ", arr[i]); printf("\n");} cnt++; return ; } for(int i=1;i<=n;i++) { int boo=1; for(int j=x;j>=1;j--) { if(visit[j][i]||(i-(x-j)>0&&visit[j][i-(x-j)])||(i+(x-j)<=n&&visit[j][i+(x-j)])) { boo=0; break; } } if(boo) { visit[x][i]=1; arr[x]=i; chess(x+1); visit[x][i]=0; } } } int main() { scanf("%d", &n); chess(1); printf("%d", cnt); }*/

/*#include <bits/stdc++.h> using namespace std; #define MOD 1999 int main() { int n, r; scanf("%d %d", &n, &r); int dp[2001][2001]={}; int N[2000]={}, R[2000]={}, top=0; while(n>0) { top++; N[top]=n%MOD; n/=MOD; //printf("%d", n); if(r>0){ R[top]=r%MOD; r/=MOD;} } dp[0][0]=1; dp[1][0]=1; dp[1][1]=1; for(int i=2;i<=2000;i++) { dp[i][0]=1; dp[i][i]=1; for(int j=1;j<i;j++) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%MOD; } int ans=1; for(int i=top;i>=1;i--) { if(N[i]<R[i]) { printf("0"); return 0; } ans*=dp[N[i]][R[i]]; ans%=MOD; } printf("%d", ans); } */ /* #include <bits/stdc++.h> using namespace std; #define MOD 100000007 int main() { int a, b; scanf("%d %d", &a, &b); int dp[102][102]={}; dp[0][0]=1; dp[1][0]=1; dp[1][1]=1; for(int i=2;i<=100;i++) { dp[i][0]=1; dp[i][i]=1; for(int j=1;j<i;j++){ printf("%d %d", i-1, j-1); dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%MOD;} } printf("%d", dp[a][b]); } */ /* #include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); int a; int cnt=0; int i; while(n--) { cnt=0; scanf("%d", &a); for(i=1;i*i<=a;i++) { if(i*i==a) break; if(a%i==0) cnt++; } cnt*=2; if(i*i==a) cnt++; cnt+=m/a; cnt-=1; printf("%d\n", cnt); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { printf("10 6"); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); int a, b; scanf("%d %d", &a, &b); int visit[101]={}; for(int i=1;i<=a;i++) { int k; scanf("%d", &k); visit[k]++; } for(int i=1;i<=b;i++) { int k; scanf("%d", &k); visit[k]++; } int ans1=0, ans2=0; for(int i=1;i<=n;i++) { if(visit[i]==0) ans1++; if(visit[i]==2) ans2++; } printf("%d %d", ans1, ans2); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int dp[1000001]; int n; scanf("%d", &n); for(int i=1;i<=1000000;i++) dp[i]=2100000000; for(int i=0;i<=n;i++) { dp[i+1]=min(dp[i+1], dp[i]+1); dp[i+3]=min(dp[i+3], dp[i]+1); dp[i+5]=min(dp[i+5], dp[i]+1); dp[i+10]=min(dp[i+10], dp[i]+1); } printf("%d", dp[n]); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { printf("%d", 8+997/36); } */ /* #include <bits/stdc++.h> using namespace std; int main() { int m; int dab1[1000001], dab2[1000001], dab3[1000001], top1=0, top2=0, top3=0, arr[1000001], n; scanf("%d", &m); for(int i=1; i<=m; i++) scanf("%d", &arr[i]); scanf("%d", &n); for(int i=1; i<=m; i++) { if(arr[i]<n) { top1++; dab1[top1]=arr[i]; } else if(arr[i]==n) { top2++; dab2[top2]=arr[i]; } else { top3++; dab3[top3]=arr[i]; } } for(int i=1; i<=top1; i++) printf("%d ", dab1[i]); for(int i=1; i<=top2; i++) printf("%d ", dab2[i]); for(int i=1; i<=top3; i++) printf("%d ", dab3[i]); } */ /* #include <bits/stdc++.h> using namespace std; int main() { ||a+m|-|b||=k m>a a+m-|b|>0 a+m=k+|b| m=k+|b|-a; a+m-|b|<0 -a-m=k-|b| m=|b|-k-a m }*/ #include <bits/stdc++.h> using namespace std; int gcd(int x, int y) { if(x==0) return y; return gcd(y%x, x); } int main() { float a; cin >> a; a*=100; int ans1, ans2, Max=0; for(int i=(int)a-5;i<=(int)a+4;i++) { int gc=gcd(i, 10000); //printf("%d %d\n", i, gc); if(gc>Max) { ans1=i/gc; ans2=10000/gc; Max=gc; } } printf("%d/%d", ans1, ans2); }

/*#include <bits/stdc++.h> using namespace std; int cnt, n; void dab(int x, int y) { if(x==n) { cnt++; return ; } if(x>n) return ; if(y==0) { dab(x+3, 2); dab(x+1, 0); dab(x+2, 0); } else { dab(x+1, y-1); dab(x+2, y-1); return ; } } int main() { scanf("%d", &n); int dp[16][4]= {}; dab(0, 0); printf("%d", cnt); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); int dp[21][2]={}; dp[1][0]=1, dp[1][1]=1; for(int i=2;i<=n;i++) { dp[i][1]=dp[i-1][0]+dp[i-1][1]; dp[i][0]=dp[i-1][1]; } printf("%d", dp[n][1]+dp[n][0]); }*/ /* #include <bits/stdc++.h> using namespace std; int dab(int x, int y, int z) { if(x<0) return 0; if(y==0) return 1; if(z==0) { return dab(x-2, y-1, 1)+dab(x-1, y, 1); } else { return dab(x-1, y-1, 0)+dab(x-1, y, 1); } } int main() { int n, k; scanf("%d %d", &n, &k); printf("%d", dab(n, k, 0)); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[11]; int ans[7]; int sum=0, top=-1; for(int i=1; i<=9; i++) { cin >> arr[i]; sum+=arr[i]; } for(int i=1; i<=9; i++) { for(int j=1; j<=9; j++) { if(i==j) continue; if(sum-arr[i]-arr[j]==100) { for(int k=1; k<=9; k++) { if(k!=i&&k!=j) { top++; ans[top]=arr[k]; } } sort(ans, ans+7); for(int p=0; p<7; p++) printf("%d\n", ans[p]); return 0; } } } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); int arr[16][3]; int dp[16][3]; for(int i=1;i<=n;i++) scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]); dp[1][0]=arr[1][0]; dp[1][1]=arr[1][1]; dp[1][2]=arr[1][2]; for(int i=2;i<=n;i++) { dp[i][0]=min(dp[i-1][2], dp[i-1][1])+arr[i][0]; dp[i][1]=min(dp[i-1][0], dp[i-1][2])+arr[i][1]; dp[i][2]=min(dp[i-1][0], dp[i-1][1])+arr[i][2]; } printf("%d", min(min(dp[n][0], dp[n][1]), dp[n][2])); }*/ /* #include <bits/stdc++.h> using namespace std; int dab(int x) { if(x==1) return 1; if(x==2) return 2; return dab(x-1)+dab(x-2); } int main() { int n; scanf("%d", &n); printf("%d", dab(n)); }*/ /* #include <bits/stdc++.h> using namespace std; int a, b, c, d, cnt=2100000000; map<pair<int, int>, int> visited; void dab(int x, int y, int z) { if(visited.find({x, y})!=visited.end()&&visited[ {x, y}]<z) return ; if(visited.find({x, y})!=visited.end()&&visited[ {x, y}]>z) { visited[ {x, y}]=z; } else { visited.insert({{x, y}, z}); } if(x==c&&y==d) { cnt=min(cnt, z); //printf("%d", z); } if(x<a) { dab(a, y, z+1); } if(x>0) { dab(0, y, z+1); } if(b-y>=x) { dab(0, y+x, z+1); } else { dab(x-(b-y), b, z+1); } if(y<b) { dab(x, b, z+1); } if(y>0) { dab(x, 0, z+1); } if(a-x>=y) { dab(x+y, 0, z+1); } else { dab(a, y-(a-x), z+1); } } int main() { scanf("%d %d %d %d", &a, &b, &c, &d); dab(0, 0, 0); if(visited.find({c, d})!=visited.end()) { printf("%d", cnt); } else { printf("-1"); } }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); int t=0, k=0; int x=0, y=0; if(a==c&&b==d) { printf("2"); return 0; } while(1) { if(y==b) { y=0; } else if(x==0) { x=a; } else if(x+y<b) { y+=x; x=0; } else { x-=(b-y); y=b; } t++; if(x==c&&y==d) k=t; if(x==0&&y==0) break; } if(k==0) { printf("-1"); return 0; } else { printf("%d", min(k, t-k)); } }*/ /* #include <bits/stdc++.h> using namespace std; int n; bool zero(int x) { return !x; } int main() { scanf("%d", &n); if(zero(n)) printf("zero"); else printf("non zero"); return 0; }*/ /* #include <bits/stdc++.h> using namespace std; int n; bool zero(int x) { return !x; } bool plus(int x) { return x>0; } int main() { scanf("%d", &n); if(zero(n)) printf("zero"); else printf("%s", Plus(n)?"plus":"minus"); return 0; }*/ /* #include <bits/stdc++.h> using namespace std; long long int f(double x) { long long int t=(long long int)x; if(t<x) return x+1; else return x; } int main() { }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int arr[5]; for(int i=0;i<5;i++) scanf("%d", &arr[i]); for(int i=4;i>=0;i--) printf("%d ", arr[i]); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); printf("%d %d %d", c, b, a); }*/ /* #include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); for(int i=0;i<s.size();i++) { if(s[i]==',') { printf(" "); continue; } if(s[i]==' ') continue; if(s[i]==';') { printf("\n"); continue; } printf("%c", s[i]); } }*/