akhauriyash/Code-Regression huggingface dataset:
n,m = map(int,input().split())
mod = 10**9 + 7

if abs(n-m) >= 2:
    print(0)
    exit()

if n == m:
    tmp = 1
    for i in range(1,n+1):
        tmp = (tmp*i)%mod
    ans = (2*tmp*tmp)%mod
else:
    tmp = 1
    for i in range(1,min(n,m)+1):
        tmp = (tmp*i)%mod
    ans = (tmp*tmp*max(n,m))%mod

print(ans)




Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main() {
    int A, B, K;
    cin >> A;
    cin >> B;
    cin >> K;

    int count = 0;
    int i = 1;

    for(int i = 100; i > 0; i--) {
        if(A%i == 0 && B%i==0) count++;
        
        if(count == K) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;

}

Measured memory_bytes: 256
(N, _), *edges = [list(map(int, s.split())) for s in open(0)]
graph = {i: [] for i in range(N)}
for a, b in edges:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
print("\n".join(str(len(graph[i])) for i in range(N)))


Measured memory_bytes: 3060
#include <algorithm>
#include <map>
#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <iterator>
#include <array>
typedef long long int ll;
using namespace std;
#define maxN 200005
#define mod 1000000007

string s;
void solve()
{
    cin >> s;
    if (s == "ABC")
    {
        cout << "ARC\n";
    }
    else
    {
        cout << "ABC\n";
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

Measured memory_bytes: 3640
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    int sum_a = 0;
    rep(i,n){
        cin >> a[i];
        sum_a += a[i];
    }
    int sum_x = sum_a/2;
    int s[100010] = {0};
    int ans[100010] = {0};

    int aa = 0;
    for(int i = 1;i < n;i += 2){
        aa += a[i];
    }
    ans[0] = sum_x - aa;
    s[1] = sum_x - aa;
    for(int i = 0;i < n-1;i += 2){
        s[i+2] = s[i]+a[i];
    }
    for(int i = 1;i < n-1;i += 2){
        s[i+2] = s[i]+a[i];
    }
    for(int i = 0;i<n;i++){
        cout << (s[i+1]-s[i] )*2<< " " ;
    }cout << endl;




    
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc133.contest.atcoder.jp/tasks/abc133_b

Measured memory_bytes: 2816
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;


int main() {
	double x1, x2, x3, x4, y1, y2, y3, y4, dist1, dist2, dist3, dist4, dist5, dist6;

	while (scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4) != EOF) {
		dist1 = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
		dist2 = sqrt((x2 - x4) * (x2 - x4) + (y2 - y4) * (y2 - y4));
		dist3 = fabs((y2 - y4) * x1 + (x4 - x2) * y1 + y2 * (x2 - x4) - x2 * (y2 - y4)) / (sqrt((y2 - y4) * (y2 - y4) + (x4 - x2) * (x4 - x2)));
		dist4 = fabs((y1 - y3) * x2 + (x3 - x1) * y2 + y1 * (x1 - x3) - x1 * (y1 - y3)) / (sqrt((y1 - y3) * (y1 - y3) + (x3 - x1) * (x3 - x1)));
		dist5 = fabs((y2 - y4) * x3 + (x4 - x2) * y3 + y2 * (x2 - x4) - x2 * (y2 - y4)) / (sqrt((y2 - y4) * (y2 - y4) + (x4 - x2) * (x4 - x2)));
		dist6 = fabs((y1 - y3) * x4 + (x3 - x1) * y4 + y1 * (x1 - x3) - x1 * (y1 - y3)) / (sqrt((y1 - y3) * (y1 - y3) + (x3 - x1) * (x3 - x1)));

		if (dist1 < dist3 || dist2 < dist4 || dist1 < dist5 || dist2 < dist6) {
			printf("NO\n");
		}
		else {
			printf("YES\n");
		}
	}

	return 0;
}


Measured memory_bytes: 2556
a, b = map(int, input().split())

A = []
B = []

for i in range(1, int(a**0.5) + 1):
    if a % i == 0:
        A.append(i)
        A.append(a//i)
for j in range(1, int(b**0.5) + 1):
    if b % j == 0:
        B.append(j)
        B.append(b//j)

C = set(A) & set(B)


D = []


def uni(x):
    for i in range(1, int(x**0.5)+1):
        if x % i == 0 and i != 1:
            return False
    return True


for i in C:
    if uni(i):
        D.append(i)
print(len(D))

Measured memory_bytes: 41948
using DataStructures
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  N,M,K  = readint()
  A = readint()
  B = readint()

  TA = Vector{int}(undef,N+1)
  TB = Vector{int}(undef,M+1)
  TA[1] = 0
  TB[1] = 0
  for i in 1:N
    TA[i+1] = TA[i] + A[i]
  end
  for i in 1:M
    TB[i+1] = TB[i] + B[i]
  end

  maxK = 0
  b = M
  for i in 0:N
 
    for j in b:-1:0
      if TA[i+1] + TB[j+1] <= K
        b = j
        if i + j > maxK 
          maxK = i+j
        end
        break 
      end
      if j == 0
        println(maxK)
        return
      end
    end
  end
  println(maxK)


end

main()

Measured memory_bytes: 230440
N = int(input())

def dfs(n, is3, is5, is7):
    if(n > N): 
        return 0
    ans = 0
    if(is3 and is5 and is7): ans += 1
    ans += dfs(n * 10 + 3, True, is5, is7)
    ans += dfs(n * 10 + 5, is3, True, is7)
    ans += dfs(n * 10 + 7, is3, is5, True)
    return ans

if __name__ == "__main__":
    print(dfs(0, False, False, False))



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n, x;
  cin >> n >> x;
  vector<long long> v(n);
  for(int i=0; i < n; i++) cin >> v[i];
  sort(v.begin(), v.end());
  int count = 0;
  for(int i=0; i < n; i++) {
    x -= v[i];
    if(x < 0) break;
    count++;
  }
  cout << count - (0 < x ? 1 : 0) << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define NUM 100

int main(){
   char s[NUM];
   int i;
   scanf("%s",s);
   for(i=0;i<strlen(s);i++){
      s[i]='x';
   }
   for(i=0;i<strlen(s);i++){
      printf("%c",s[i]);
   }
   return 0;
}

Measured memory_bytes: 1628
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

Int n, k, ans;
vector<Int> p;
vector<Int> q;
using P = pair<Int, Int>;
P operator*(P x, P y){
	return P(min(x.first, y.first), max(x.second, y.second));
}
template <class M> class segment_tree{
public:
	size_t N;
	vector<M> V;
	M e;
	segment_tree(vector<M> v, const M &_e){
		e = _e;
		size_t sz = v.size();
		N = 1;
		while(N < sz) N <<= 1;
		V.resize(2*N, e);
		for(size_t i=0; i<sz; ++i) V[N+i] = v[i];
		for(size_t i=N-1; i>0; --i) V[i] = V[2*i] * V[2*i+1];
	}

	void update(size_t x, M val){
		x += N;
		V[x] = val;
		x >>= 1;
		while(x > 0){
			V[x] = V[2*x] * V[2*x+1];
			x >>= 1;
		}
	}

	M get(size_t l, size_t r){ // [l, r)
		M lres = e;
		M rres = e;
		l += N;
		r += N;
		while(l < r){
			if(l & 1){
				lres = lres * V[l];
				++l;
			}
			if(r & 1){
				--r;
				rres = V[r] * rres;
			}
			l >>= 1;
			r >>= 1;
		}
		return lres * rres;
	}
};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> k;
	p.resize(n);
	for(auto &i:p) cin >> i;
	q.resize(n);
	q[0] = 1;
	for(Int i=1; i<n; ++i){
		if(p[i] > p[i-1]){
			q[i] = q[i-1] + 1;
		}else{
			q[i] = 1;
		}
	}
	vector<P> v(n);
	for(Int i=0; i<n; ++i) v[i] = P(p[i], p[i]);
	segment_tree<P> s(v, P(1e9, -1));
	ans = 1;
    bool f = (q[k-1] < k);
	for(Int i=k; i<n; ++i){
//      cout << i << " " << ans << "\n";
		if(q[i] >= k){
			if(f) ++ans;
			f = false;
			continue;
		}
		if(p[i-k] > s.get(i-k, i).first || p[i] < s.get(i-k+1, i+1).second) ++ans;
//		cout << i << " " << s.get(i-k, i).first << " " << s.get(i-k+1, i+1).second << "\n";
//      cout << i << " " << ans << "\n";
	}
	cout << ans << "\n";
}

Measured memory_bytes: 17792
#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <functional>
    #include <numeric>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include <utility>
    #include <sstream>
    #include <complex>
    #include <fstream>
    #include <bitset>
    #include <time.h>
    #include <tuple>
     
    using namespace std;
     
    typedef long long ll;
    typedef pair<ll, ll> P;
    typedef vector<ll> V;
    typedef complex<double> Point;
     
    #define PI acos(-1.0)
    #define EPS 1e-10
    const ll INF = 1e12;
    const ll MOD = 1e9 + 7;
     
    #define FOR(i,a,b) for(int i=(a);i<(b);i++)
    #define rep(i,N) for(int i=0;i<(N);i++)
    #define ALL(s) (s).begin(),(s).end()
    #define EQ(a,b) (abs((a)-(b))<EPS)
    #define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
    #define fi first
    #define se second
    #define N_SIZE (1LL << 20)
    #define NIL -1
    #define MAX_N 100100
     
    string s;
     
    int main() {
    	cin >> s;
    	if ((s[1] == s[2] && s[2] == s[3])||(s[0] == s[1] && s[1] == s[2]))cout << "Yes" << endl;
    	else cout << "No" << endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxx = 2000000;
const int INF = 1 << 30;

int A[maxx + 1];
int n;
void maxHeapify(int i) {
	
	int left = 2 * i, right = 2 * i + 1;
	int largest;

	// ?????????????????????????????????????????????????????§??????????????¶?????§???????????????
	if (left <= n && A[left] > A[i])
		largest = left;
	else
		largest = i;

	if (right <= n && A[right] > A[largest])
		largest = right;
	
	if (largest != i) {
		swap(A[i], A[largest]);
		maxHeapify(largest);
	}

}

int extract() 
{
	int maxv;
	if (n < 1)
		return -INF;
	maxv = A[1];
	A[1] = A[n--];
	maxHeapify(1);
	return maxv;
}

int insert(int key) {
	n++;
	int i = n;
	A[n] = -INF;
	if (key < A[i])
		return -INF;
	A[i] = key;
	while (i > 1 && A[i / 2] < A[i]) {
		swap(A[i], A[i / 2]);
		i /= 2;
	}

}
int main()
{
	char op[20];
	int k;
	while (scanf("%s", op) != EOF&&op[2] != 'd') {
		if (op[0] == 'i') {
			scanf("%d", &k);
			insert(k);
		}
		else {
			printf("%d\n", extract());
		}
	}
	return 0;
}

Measured memory_bytes: 7040
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<set>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

#define ketasitei setprecision(15) //15桁表示



int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll c = 0;
	for (int i = 2; i < n; i++)
	{
		if (s[i - 2] == 'A' && s[i - 1] == 'B' && s[i] == 'C')
			c++;
	}
	cout << c << endl;;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++) a[i]=sc.nextInt();
        Arrays.sort(a);
        System.out.print(Integer.toString(a[n-1])+" ");
        int ans = a[n-2];
        if(a[n-1]%2==0){
            int target = a[n-1]/2;
            for(int i=n-3;i>=0;i--){
                if(Math.abs(target-a[i])<Math.abs(target-ans)) ans = a[i];
            }
        }
        else{
            int t1 = a[n-1]/2;
            int t2 = a[n-1]/2+1;
            for(int i=n-3;i>=0;i--){
                int old = Math.min(Math.abs(ans-t1),Math.abs(ans-t2));
                int cur = Math.min(Math.abs(a[i]-t1),Math.abs(a[i]-t2));
                if(cur<old) ans = a[i];
            }
        }
        System.out.print(ans);
    }
}


Measured memory_bytes: 50756
#include <iostream>
#include <string.h>

using namespace std;

int main() {
	long long n;
	long long tosi[5];
	cin >> n;
	cin >> tosi[0];
	cin >> tosi[1];
	cin >> tosi[2];
	cin >> tosi[3];
	cin >> tosi[4];
	long int min = tosi[0];
	for (int i = 0; i < 5; i++) {
		if (tosi[i] < min) {
			min = tosi[i];
		}
	}
	cout << (n - 1) / min + 5 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();
    int n;
    cin >> n;
    set<int> st;
    rep(i, n){
         int x;
        cin >> x;
        st.insert(x);
    }
    cout << (st.size() == n ? "YES":"NO") << endl;
}

Measured memory_bytes: 9600
import math
from itertools import permutations
def dist(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        D[i][j] = dist(A[i],A[j])
cnt = 0
for z in permutations(range(N),N):
    for i in range(N):
        cnt += D[z[i]][z[j]]
print(cnt/math.factorial(N))

Measured memory_bytes: 40812
fun main(args: Array<String>) {
    val (h, w) = readLine()!!.split(' ').map(String::toInt)
    val sMap = Array(h) { CharArray(w) }
    (0 until h).forEach { sMap[it] = readLine()!!.toCharArray() }

    val lMap = Array(h) { IntArray(w) { 0} }
    for (th in 0 until h) {
        for (tw in 0 until w) {
            if (sMap[th][tw] == '#') continue
            if (tw == 0) {
                lMap[th][tw] = 1
            } else {
                lMap[th][tw] = lMap[th][tw - 1] + 1
            }
        }
    }

    val rMap = Array(h) { IntArray(w) { 0 } }
    for (th in 0 until h) {
        for (tw in (w - 1) downTo 0) {
            if (sMap[th][tw] == '#') continue
            if (tw == w - 1) {
                rMap[th][tw] = 1
            } else {
                rMap[th][tw] = rMap[th][tw + 1] + 1
            }
        }
    }

    val uMap = Array(h) { IntArray(w) { 0} }
    for (tw in 0 until w) {
        for (th in (h - 1) downTo 0) {
            if (sMap[th][tw] == '#') continue
            if (th == h - 1) {
                uMap[th][tw] = 1
            } else {
                uMap[th][tw] = uMap[th + 1][tw] + 1
            }
        }
    }

    val dMap = Array(h) { IntArray(w) { 0 } }
    for (tw in 0 until w) {
        for (th in 0 until h) {
            if (sMap[th][tw] == '#') continue
            if (th == 0) {
                dMap[th][tw] = 1
            } else {
                dMap[th][tw] = dMap[th - 1][tw] + 1
            }
        }
    }

    var max = 0
    for (tw in 0 until w) {
        for (th in 0 until h) {
            if (sMap[th][tw] == '#') continue
            max = Math.max(max, rMap[th][tw] + lMap[th][tw] + uMap[th][tw] + dMap[th][tw] - 3)
        }
    }
    println(max)
}

Measured memory_bytes: 139556
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<stdio.h>


using namespace std;
typedef long long ll;
int input(){
  int x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}
int gcd(int x, int y){
	if(x<y){
    return gcd(y,x);
  }
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}
int moji(char in)
{
    int ans = (int)in-(int)'a'+1;
    if((in < 1) || (in > 26)){
        ans = 100;
    }
    return ans;
}
int cost[10][10];
int d[10];
bool used[10];
int V;
void dijkstra(int s){
  fill(d,d+V,100000);
  fill(used,used+V,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<V;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<V;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}









int main() {
  int H,W;
  cin>>H>>W;
  V=10;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      cin>>cost[i][j];
    }
  }
  int A[H][W];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>A[i][j];


    }
  }
  int sum=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(A[i][j]!=-1){
        dijkstra(A[i][j]);
        sum+=d[1];

      }


    }
  }
  cout<<sum<<endl;
  


  

    


  

  
  
  
  
}


  
  


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)
 
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
 
#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()
 
typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};
 
ll comb(ll n, ll k) {
    if (k > n) return 0;
    if (k * 2 > n) k = n-k;
    if (k == 0) return 1;
 
    ll result = n;
    for( ll i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
 
    int N, P;
    cin >> N >> P;
 
    int even = 0, odd = 0;
    rep(i, N) {
        int A;
        cin >> A;
        if (A%2) odd++;
        else     even++;
    }
 
    // DUMP2(even, odd);
 
    ll ans = pow(2, even);
 
    ll tmp = 0;
    for (int i=P; i<=odd; i+=2) {
        tmp += comb(odd, i);
        // DUMP2(i, tmp);
        // cerr << comb(odd, i) << endl;
    }
    ans *= tmp;
 
    //if (P == 1 && odd == 0) {
    //     cout << 0 << endl;
    // } else {
        cout << ans << endl;
    //}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N;
VL b;

int main() {
    cin >> N;
    REP(i, N) b.emplace_back(IN() - i - 1);
    sort(All(b));
    ll ans = 0, mid=0;
    if(N%2) mid=b[N/2];
    else mid=(b[N/2]+b[N/2-1])/2;
    REP(i, N) ans += abs(b[i] - mid);
    cout << ans;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>

using namespace std;

int main(void){
	int D,N;
	cin >> D >> N;
	int ans;
	if(D==0){
		ans = N;
		if(N==100)ans+=1;
	}
	else if(D==1){
		ans = N*100;
		if(N==100)ans+=100;
	}else{
		ans = N*10000;
		if(N==100)ans+=10000;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
def main():
    word = input()
    count = {"a": 0, "b": 0, "c": 0}
    for w in word:
        count[w] += 1
    answer = list(count.values())
    answer.sort()
    print("YES" if (answer[0] == answer[1] and abs(answer[1] - answer[2]) <= 1) or
                   (answer[1] == answer[2] and abs(answer[0] - answer[1]) <= 1) else "NO")


if __name__ == '__main__':
    main()



Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main()
{
    int A,B,C;
    cin >>A>>B>>C;
    if (((A==5)||(A==7))&&((B==5)||(B==7))&&((C==5)||(C==7))&&(A+B+C==17))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>

#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}

ll gcd(ll a, ll b) {
  if (a == 0 || b == 0) return a + b;
  if (b > a) return gcd(b, a);
  return gcd(b, a % b);
}




int main(void) {

  ll t1, t2, a1, a2, b1, b2;
  cin >> t1 >> t2;
  cin >> a1 >> a2;
  cin >> b1 >> b2;

  ll g = (b1-a1)*t1, h = (b2-a2)*t2;

  if ((g > 0 && g + h > 0) || (g < 0 && g + h < 0)) {
    cout << 0 << endl;
    return 0;
  }

  if (g + h == 0) {
    cout << "infinity\n";
    return 0;
  }

  //cout << g << " " << h << endl;

  ll d = g - (2LL*g + h); //cout << d << endl;
  if (g % d == 0) cout << 2LL*(g/d+1LL)-2LL << endl;
  else cout << 2LL*(g/d+1LL)-1LL << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main() {
	int N;
	string S;
	cin >> N >> S;
	int A = 0;
	for (int i = 0; i+2 < N; i++) {
		if (S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C')
			A++;
	}
	cout << A << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        List<String> inputDataList = new ArrayList<String>();
        String input = null;

        try {
            while ((input = in.readLine()) != null) {
                inputDataList.add(input);
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        fishing(inputDataList);
    }

    private static void fishing(List<String> inputDataList) {
        String[] inputDataArray = inputDataList.get(0).split(" ");
        int[] catchFish = new int[Integer.parseInt(inputDataArray[0])];
        int events = Integer.parseInt(inputDataArray[1]);
        int max = 1;

        for (int i = 1; i <= events; i++) {
            max = fishCount(inputDataList.get(i), catchFish, max);
            System.out.println(max + " " + catchFish[max - 1]);
        }
    }

    private static int fishCount(String event, int[] catchFish, int max) {
        String[] eventData = event.split(" ");
        int participant = Integer.parseInt(eventData[0]);
        int getFishNum = Integer.parseInt(eventData[1]);

        catchFish[participant - 1] = catchFish[participant - 1] + getFishNum;

        if (participant == max) {
            if (getFishNum < 0) {
                return topParticipant(catchFish);
            } else {
                return participant;
            }
        }

        if (catchFish[participant - 1] > catchFish[max - 1]
                || (catchFish[participant - 1] == catchFish[max - 1] && participant < max)) {
            return participant;
        } else {
            return max;
        }
    }

    private static int topParticipant(int[] catchFish) {
        int max = 0;

        for (int i = 1; i < catchFish.length; i++) {
            if (catchFish[i] > catchFish[max]) {
                max = i;
            }
        }

        return max + 1;
    }

}

Measured memory_bytes: 89052
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};



void solve(){
    ll n;
    ll a[110];
    cin>>n;
    rep(i,n) cin>>a[i];
    sort(a,a+n);
    reverse(a,a+n);
    ll c=0,d=0;
    rep(i,n){
        if(i%2==0) c+=a[i];
        else d+=a[i];
    }
    cout<<c-d<<endl;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    solve();

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < static_cast<int>(b); i++)
#define FORR(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) FOR (i, 0, n)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
template <typename T>
void print(const vector<vector<T>> matrix);
template <typename T>
void print(const vector<T> vec);
template <typename Arg>
void print(const Arg arg);
template <typename Head, typename... Args>
void print(const Head head, const Args... args);
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
using ll = long long;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> vec(n);
    rep(i,n)
        cin >> vec[i];
    vector<ll> origin = vec;
    sort(all(vec));

    repall(i, origin) {
        if (i <= vec[n/2-1])
            print(vec[n/2]);
        else print(vec[n/2-1]);
    }

    return 0;
}

//---------------------------------------------
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    repall (i, vec)
        cout << i << ' ';
    cout << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}


Measured memory_bytes: 5376
/*
 * あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
 * 
 * 同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
 */

import java.util.*;
	public class Main{
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //入力
            int a = Integer.parseInt(sc.next());
            int b = Integer.parseInt(sc.next());
            int c = Integer.parseInt(sc.next());
            int x = Integer.parseInt(sc.next());
            
            int aa = x/500;
            int counter = 0;
            
            for(int i=0; i<=Math.min(aa,a); i++){
            	for(int j=0; j<=Math.min((x-i*500)/100, b); j++){
            		if((x - i*500 - j*100)%50 == 0 && (x - i*500 - j*100)/50 <=c){
            			counter++;
            		}
            	}
            }
            
            //出力
            System.out.println(counter);
            sc.close();
        }
    }
	

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define P 1000000007
#define ll long long
#define ld long double
#define N (1<<17)
#define pii pair<int, int>
#define F first
#define S second

using namespace std;

int n;
ld d[3030][3030], p[3030];

int main(){

	cin >> n;

	for(int i=0; i<n; i++) cin >> p[i];

	d[0][0] = 1.0;

	for(int i=0; i<n; i++){
		for(int j=0; j<=i; j++){
			d[i+1][j+1] += d[i][j]*p[i];
			d[i+1][j] += d[i][j]*(1-p[i]);
		}
	}

	ld ans = 0.0;
	for(int i=0; i<=n/2; i++) ans += d[n][n-i];

	cout << setprecision(12) << ans << endl;

	return 0;

}


Measured memory_bytes: 141824
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define FOR(i,k,n) for((i)=(k);(i)<(n);(i)++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define pb push_back
#define all(a) (a).begin(),(a).end()  //greater<int>()
using namespace std;

int main(){
	int A,B,C,D;
	cin>>A>>B>>C>>D;

	if(A*B>=C*D) cout<<A*B;
	else if(A*B<C*D) cout<<C*D;

	return 0;
}


Measured memory_bytes: 256
program main;
var a,b,c,temp : integer;
begin
    temp:=0;
    readln(a,b,c);
    temp:=a;
    a:=b;
    b:=temp;
    temp:=a;
    a:=c;
    c:=temp;
    writeln(a,' ',b,' ',c);
end.

Measured memory_bytes: 1388
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


class UnionFind{
    public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> parent;

    //-1で初期化。最初はすべてバラバラ
    UnionFind(int N){
        parent = vector<int>(N,-1);
    }

    //Aがどのグループに属しているか(Aの根)を調べる
    int root(int A){
        if(parent[A] < 0) return A;
        return parent[A]=root(parent[A]);
    }

    //自分のいるグループの頂点数を調べる
    int size(int A){
        return -parent[root(A)];
    }

    //AとBをくっつける
    bool unite(int A, int B) {
    //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        //既にくっついているからくっつけない
        if(A == B) return false; 

        //大きいほう(A)に小さいほう(B)をくっつける
        //大小が逆ならひっくり返す
        if(size(A) < size(B)) swap(A,B);

        //Aのサイズを更新する
        parent[A] += parent[B];
        //Bの親をAに変更する
        parent[B] = A;

        return true;
    }

    //AとBが同じグループならtrueを返す
    bool same(int A, int B){
        return root(A)==root(B);
    } 
};

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    cin>>n;
    vector<pair<int,int>> x(n),y(n);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        x[i] = make_pair(a,i);
        y[i] = make_pair(b,i);
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());

    UnionFind uni(n);

    vector<pair<int,pair<int,int>>> v;
    for(int i=1;i<n;i++){
        v.push_back(make_pair(x[i].first - x[i-1].first , make_pair(x[i].second,x[i-1].second)));
        v.push_back(make_pair(y[i].first - y[i-1].first, make_pair(y[i].second,y[i-1].second)));
    }
    sort(v.begin(),v.end());

    ll ans = 0;
    for(auto i:v){
        if(!uni.same(i.second.first,i.second.second)){
            uni.unite(i.second.first,i.second.second);
            ans += i.first;
        }
    }
    cout<<ans<<endl;


    

}

Measured memory_bytes: 6900
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
typedef pair<int,int> pr;
ll ans;
int n,L;
pr p[201000];
ll calc(vector<pair<pr,pr> > v){
	ll now=0;
//	for(auto&x:v) now+=x.second.first*x.second.second;
	ll s=0;
	for(int i=0,j=L-1;j<v.size();i++,j++)
		s+=v[i].second.first,now+=v[j].second.second*s;
	return now;
}
vector<pair<pr,pr> > merge(vector<pair<pr,pr> > v){
	vector<pair<pr,pr> > res;
	if(v.size()<L) return res;
	int cnt=v.size()/L;
	for(int i=0;i<cnt;i++)
		res.emplace_back(pr{v[i*L].first.first,i==cnt-1?v.back().first.second:v[i*L+L-1].first.second},pr{0,0});
	for(int i=0;i<v.size();i++){
		if(i+1>=L) res[(i+1)/L-1].second.second+=v[i].second.second;
		if(v.size()-i>=L) res[cnt-(v.size()-i)/L].second.first+=v[i].second.first;
	}
	ans-=calc(res);
	return res;
}
int main(){
	read(n);read(L);
	for(int i=1;i<=n;i++){
		int x;read(x);
		p[i]=pr{x,i};
	}
	sort(p+1,p+n+1);
	int now=1,k;ans=n;
	vector<pair<pr,pr> > v;
	while(!v.empty()||now<=n){
		if(v.empty()) k=p[now].first;
		else k++;
		while(now<=n&&k==p[now].first) v.emplace_back(pr{p[now].second,p[now].second},pr{1,1}),now++;
		sort(v.begin(),v.end());
		vector<pair<pr,pr> > nxt;
		for(int i=0,j=0;i<v.size();i=++j){
			vector<pair<pr,pr> > res;
			res.push_back(v[i]);
			while(j+1<v.size()&&v[j+1].first.first==v[j].first.second+1) res.push_back(v[++j]);
			ans+=calc(res);
			for(auto&x:merge(res)) nxt.push_back(x);
		}
		v=nxt;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 12244
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#include <queue>
#include <regex>
#include <cassert>
#include <map>
// #include "bits/stdc++.h"

using namespace std;
//debug

#define rep(i, N, M) for (ll i = N; i < M; ++i)
#define rrep(i, N, M) for (ll i = N; i > M; --i)
#define pb push_back


typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll, vector<pll>> pqpll;
typedef priority_queue<ll, vll, greater<ll>> pqll_greater;
typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll_greater;


#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define _CRT_SECURE_NO_WARNINGS

template<class T, class S>
T atbit(T n, S i) {
	return (n >> i) % i;
}

template<class T>
T getbit(T i) {
	return 1LL << i;
}
template<class T>
T POW(T n, T m) {
	T res = 1;
	rep(i, 0, m) {
		res *= n;
	}
	return res;
}

ll power(ll x, ll y,ll mod) {
	if (y == 0)return 1;
	if (y == 1)return x % mod;
	if (y % 2 == 0)return POW(power(x, y / 2, mod), 2LL) % mod;
	return ((POW(power(x, y / 2, mod), 2LL) % mod)*(x%mod))%mod;
}
ll div(ll a,ll  b, ll mod) {
	return (a* power(b, mod - 2,mod))%mod;
}

//#define TRANSFORM(v,w,func) decltype(v) w ; transform((v).begin(),(v).end(),back_inserter(w),func);

using namespace std;

ll MOD_NUM = POW(10LL, 9LL) + 7;


int main() {
	string S, T;
	cin >> S >> T;
	map<char, char> memo;
	ll N = S.size();
	string res="Yes";
	string alphabet = "abcdefghijklmnopqrstuvwxyz";
	
	auto calc = [&](string S,string T) {
		rep(i, 0, alphabet.size()) {
			char tmp = '-';
			rep(j, 0, N) {
				if (T[j] == alphabet[i] && tmp == '-') {
					tmp = S[j];
				}
				else if (T[j] == alphabet[i] && S[j]!=tmp) {
					return false;
				}

			}

		}
		return true;
	};
	auto a = calc(S, T);
	auto b = calc(T, S);
	if (calc(S, T) && calc(T, S))cout << "Yes";
	else cout << "No";

		

}


Measured memory_bytes: 1400
/*---------------Go Code GO---------------*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using Order_Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//(order) Set.order_of_key(); (pointer) Set.find_by_order();

#define PI acos(-1.0)
#define O_O                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define precision(a) fixed << setprecision(a)
#define endl '\n'
#define Flush cout << flush
#define LLMX 0x3fffffffffffffff

long long N;

int main()
{
    O_O;
    long long N, K;
    long long gcd, k, mx = 0;
    cin >> N >> K;
    cin >> gcd;
    mx = gcd;

    for (int i = 1; i < N; i++)
    {
        cin >> k;
        mx = max(mx, k);
        gcd = __gcd(gcd, k);
    }
    if (K > mx)
    {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    if (K%gcd==0)
        cout << "POSSIBLE" << endl;
    else
        cout << "IMPOSSIBLE" << endl;

    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9+7;

int main()
{
    int N;cin >> N;
    vector<int> vec;
    for(int i = 0;i < N;i++){
        int b;cin >> b;
        vec.push_back(b);
    }
    ll ans = 0;
    for(int i = 0;i < N - 1;i++){
        for(int j = i + 1;j < N;j++){
            ans += vec.at(i) * vec.at(j);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

	int a,b,c;

	scanf("%d %d %d",&a,&b,&c);

	if(a<=b&&b<=c){
		printf("%d %d %d\n",a,b,c);
	}else if(b<=a&&a<=c){
		printf("%d %d %d\n",b,a,c);
	}else if(c<=a&&a<=b){
		printf("%d %d %d\n",c,a,b);
	}else if(a<=c&&c<=b){
		printf("%d %d %d\n",a,c,b);
	}else if(b<=c&&c<=a){
		printf("%d %d %d\n",b,c,a);
	}else if(c<=b&&b<=a){
		printf("%d %d %d\n",c,b,a);
	}

	return 0;

}

Measured memory_bytes: 2724
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,K;
  string S;
  cin >> N >> S >> K;
 
  char F = S.at(K-1);
  
  for(int i=0; i<N; i++) {
    if(S.at(i) != F) S.at(i) ='*';
  }
  cout << S << endl;
}
  

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using namespace std;

int main(){
	int N, M;
	cin >> N >> M;
	int road[N+1];
	rep(i,N+1) road[i] = 0;
	rep(i,M) {
		int a, b;
		cin >> a >> b;
		road[a]++; road[b]++;
	}
	for (int i = 1; i <= N; i++) {
		cout << road[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 3548
#include<stdio.h>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<math.h>
#define pans (((long long)pow(10,9))+(long long)7)
#define rep(i,n) for(int i = 0;i < (n);++i)
using namespace std;

int main(){
    long long n,k;
    long long ans = 1;
    cin >> n >> k;
    int s = 0,e = n-1;
    long long t;
    bool f = false;
    vector<long long> A(n);
    rep(i,n){
        cin >> t;
        A[i] = t%pans;
    }
    sort(A.rbegin(),A.rend());
    if(k%2 != 0){
        if(A[s] < 0) f = true;
        ans *= A[s];
        s++;
    }
    rep(i,int(k/2)){
        if(k == 1)break;
        if(A[s]*A[s+1] > A[e]*A[e-1] || f == true){
            ans *= (A[s]*A[s+1])%pans;
            s += 2;
        }else{
            ans *= (A[e]*A[e-1])%pans;
            e -= 2;
        }
        ans %= pans;
    }
    if(ans < 0)ans += pans;
    printf("%lld",ans);
}

Measured memory_bytes: 4832
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
void work(int n,int x)
{
    int ans=0;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<i; ++j)
            for (int k=1; k<j; ++k)
                if (i!=k && k!=j && i+j+k==x)
                    ans+=1;
    cout<<ans<<endl;

}

int main()
{
    int n,x;
    while (1)
    {
        cin>>n>>x;
        if (x ==0 && n == 0) break;
        work(n,x);
    }

    return 0;
}




Measured memory_bytes: 3084
import sys
from operator import itemgetter
input = sys.stdin.readline

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=itemgetter(0))

count = 0
index = 0
for i in range(N):
    count += AB[i][1]
    if(count >= M):
        count -= AB[i][1]
        index = i
        break

money = 0
for i in range(index):
    money += AB[i][0]*AB[i][1]
money += (M-count)*AB[index][0]
print(money)

Measured memory_bytes: 29064
#include <cstdio>

char s[10];
int cnta,cntb,cntc;

int main()
{
  scanf("%s",s);
  for(register int i=0; i<3; ++i)
    {
      if(s[i]=='a')
        {
          ++cnta;
        }
      if(s[i]=='b')
        {
          ++cntb;
        }
      if(s[i]=='c')
        {
          ++cntc;
        }
    }
  if((cnta==1)&&(cntb==1)&&(cntc==1))
    {
      puts("Yes");
    }
  else
    {
      puts("No");
    }
  return 0;
}


Measured memory_bytes: 128
#include <string>
#include <iostream>
using namespace std;

int main() {
	string s;
	while (getline(cin,s)) {
		for (int i = 0;i < 26;++i) {
			for (char &c : s) {
				if (c != ' ' && c != '.') {
					++c;
					if (c > 'z') {
						c -= (char)26;
					} else if (c < 'a') {
						c += (char)26;
					}
				}
			}
			if (s.find("the") != string::npos || s.find("this") != string::npos || s.find("that") != string::npos) {
				cout << s << endl;
				break;
			}
		}
	}
}

Measured memory_bytes: 3008
def depth_search(u, t):
    t += 1
    s.append(u)
    d[u] = t
    for v in range(N):
        if adjacency_list[u][v] == 0:
            continue 
        if d[v] == 0 and v not in s:
            t = depth_search(v, t)
    t += 1
    s.pop()
    f[u] = t
    return t

N = int(input())
adjacency_list = [[0 for j in range(N)] for i in range(N)]
for _ in range(N):
    u, k, *v = input().split()
    for i in v:
        adjacency_list[int(u)-1][int(i)-1] = 1

s = []
d = [0 for _ in range(N)]
f = [0 for _ in range(N)]

t = 0
for u in range(N):
    if d[u] == 0:
        t = depth_search(u, t)

for i in range(N):
    print("{} {} {}".format(i+1, d[i], f[i]))


Measured memory_bytes: 5748
#include <iostream>
using namespace std;

int main() {
  int q;
  cin >> q;
  long long count = 0;
  for (auto i=0; i<q; i++) {
    int p, n;
    char c;
    cin >> p >> c >> n;
    if (c == '(') {
      count += n;
    } else {
      count -= n; 
    }
    if (count == 0) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1152
s = input()
n = len(s)
ans = 0
def check(s):
    for i in s:
        if i not in 'AGCT':
            return False
    return True

for i in range(n):
    for j in range(i+1,n+1):
        p = s[i:j]
        if check(p):
            ans = max(ans, j-i)
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define itn int

typedef long long ll;
typedef pair<ll,ll> p;


int main()
{
  vector<int> v(3, 0);
  cin >> v[0] >> v[1] >> v[2];

  sort(all(v));
  cout << v[2] * 10 + v[1] + v[0] << endl;

}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
ans = 0
for i in range(1, N + 1):
    # iが出た時
    point = i
    tmp = 1 / N
    cnt = 0
    while point < K:
        tmp *= 1 / 2
        point *= 2
        cnt += 1
    # print(cnt)
    ans += tmp
print(ans)




Measured memory_bytes: 3896
#include<cstdio>

using namespace std;

int main(){
	int a, b; scanf("%d %d", &a, &b);
	int s[14]; s[1] = 13;
	for(int i = 2; i <= 13; i++) s[i] = i - 1;
	if(s[a] > s[b]) puts("Alice");
	if(s[a] < s[b]) puts("Bob");
	if(s[a] == s[b]) puts("Draw");
	return 0;
}

Measured memory_bytes: 128
def divisor(n):
    res = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            res.append((i, n // i))
            if n != i * i:
                res.append((n//i, i))
    return res


if __name__ == "__main__":
    n = int(input())
    d = divisor(n)

    ans = 0
    for x, y in d:
        if y == 1:
            continue
        div, mod = divmod(n, y - 1)
        if div == mod:
            ans += y - 1

    print(ans)


Measured memory_bytes: 3700
#a
"""
import math
a, b = map(str, input().split())
j = int(a + b)
if math.sqrt(j).is_integer():
    print("Yes")
else:
    print("No")
"""

#b
"""
ans = ["Positive","Negative"]
a, b = map(int, input().split())
if 0 < a:
    print("Positive")
elif b >= 0:
    print("Zero")
else:
    print(ans[(b-a)%2-1])
"""

#C
"""
import itertools
n = int(input())
MARCH = ["M", "A", "R", "C", "H"]
march = [0 for _ in range(5)]
for i in range(n):
    s = input()
    if s[0] in MARCH:
        march[MARCH.index(s[0])] += 1
num = list(range(5))
a = list(itertools.combinations(num, 3))
ans = 0
for i in a:
    bf = 1
    for k in i:
        bf *= march[k]
    ans += bf
print(ans)
"""

#D
"""
n = int(input())
D = [list(map(int, input().split())) for _ in range(n)]
q = int(input())
p = [int(input()) for _ in range(q)]
for i in range(n):
    D[i].insert(0, 0)
    D[i].insert(n+1, 0)
D.insert(0,[0 for _ in range(n + 2)])
D.insert(n + 2, [0 for _ in range(n + 2)])
print(D)
"""

#E
"""
s = input()
bf = s[0]
ans = 0
for i in range(1,len(s)):
    if bf != s[i]:
        ans += 1
        bf = s[i]
print(ans)
"""

#F
n = int(input())
ta = [list(map(int, input().split())) for _ in range(n)]
bf = ta[0]
ans = ta[0]
for i in ta:
    if ans == i:
        continue
    elif ans[0] <= i[0] and ans[1] <= i[1]:
        ans = i
    else:
        a = ((ans[0] - 1) // i[0]) + 1
        b = ((ans[1] - 1) // i[1]) + 1
        ab = max(a,b)
        ans = [i[0] * ab, i[1] * ab]

print(ans[0]+ans[1])

Measured memory_bytes: 39408