akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0
for i in range(N - K + 1):
    ans -= A[i] * cmb(N - 1 - i, K - 1, p)
A = A[::-1]
for i in range(N - K + 1):
    ans += A[i] * cmb(N - 1 - i, K - 1, p)
print(ans % p)

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e16+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll n;
    cin>>n;
    ll sum=0;
    Vec a(n);
    rep(i,n)cin>>a[i];
    Vec s(n);
    rep(i,n){
        if(i==0){
            s[0]=a[0];
            continue;
        }
        s[i]=s[i-1]+a[i];
    }
    ll ans=INF;

    ll m = s[n-1];

    rep(i,n){
        ll tmp = INF;
        if(s[i]*2<=m){
            tmp = m-s[i]*2;
        }else{
            tmp= s[i]*2-m;
        }
        ans = min(ans,tmp);
    }
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 3456
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [A, B] = [int(input_raw[0]), int(input_raw[1])]
    if A * B % 2 == 0:
        print "No"
    else:
        print "Yes"

if __name__ == '__main__':
    main()


Measured memory_bytes: 2932
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
namespace mydef {
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
bool dbg = false;
}  // namespace mydef
using namespace mydef;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
#define pi pair<int, int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define asn ans


void solve() {
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;
    int cnt = 0;
    for (auto& c : S) {
        cnt += (c - '0');
    }
    Yes(cnt % 9 == 0);

    solve();
    return 0;
}


Measured memory_bytes: 3720
#include<iostream>
#include<string.h>
using namespace std;
 
int main()
{
  int n;
  cin>>n;
  
  string a,b,c,d;
  int e=0,f=0,g=0,h=0;
  
  a="AC";
  b="WA";
  c="TLE";
  d="RE";
  
  for(int i=0;i<n;i++)
  { string s;
    cin>>s;
    
    if(s[0]==a[0])
      e++;
    else if(s[0]==b[0])
      f++;
    else if(s[0]==c[0])
      g++;
    else
      h++;
  }
  
  cout<<a<<" x "<<e<<endl;
  cout<<b<<" x "<<f<<endl;
  cout<<c<<" x "<<g<<endl;
  cout<<d<<" x "<<h<<endl;
  
  
  
  return 0;}

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

char s[2][2001];
int dp[2002][2002][2], n[2];
int main() {
	scanf("%d%d%s%s", &n[0], &n[1], s[0], s[1]);
	int Max = 0;
	for (int i = n[0]; i >= 0; i--)for (int j = n[1]; j >= 0; j--)rep(t, 2)rep(k, 2) {
		int a = (k ? dp[i][j + 1][!t] : dp[i + 1][j][!t]), b = (k ? j : i);
		if (b == n[k] || (a&1) == t)continue;
		if (t != (s[k][b] == 'I' ? 0 : 1))dp[i][j][t] = max(dp[i][j][t], a + 1);
		if (dp[i][j][t]&1)Max = max(Max, dp[i][j][t]);
	}
	printf("%d\n", Max);
}

Measured memory_bytes: 34504
#include <iostream>

#define N_MAX 100

void print_array(int *A, int N)
{
    if (N <= 0) return;
    std::cout << A[0];
    for (int i = 1; i < N; i++) {
        std::cout << " " << A[i];
    }
    std::cout << std::endl;
    return;
}

int main(void)
{
    int N;
    int A[N_MAX];

    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }

    print_array(A, N);
    for (int i = 1; i < N; i++) {
        int val_insert = A[i];
        int j;
        for (j = i - 1; A[j] > val_insert && j >= 0; --j) {
            A[j + 1] = A[j];
        }
        A[j + 1] = val_insert;
        print_array(A, N);
    }
    return 0;
}






Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    int n;
    cin>>n;
    vi p(n);
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    int ans=0;
    for(int i=1;i<n-1;i++){
        if(p[i]!=max(max(p[i-1],p[i]),p[i+1]) && p[i]!=min(min(p[i-1],p[i]),p[i+1])){
            ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
// In the Name of God

#include <bits/stdc++.h>

using namespace std;

#define	ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(v) v.begin(), v.end()
#define bpc(v) __builtin_popcountll(v)
#define itr iterator
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; --i)
#define ub upper_bound
#define lb lower_bound

const int N = 1e2 + 5;
const ll inf = 1e18 + 1;
const int mod = 1e9 + 7;
const double eps = 1e-15;
const int pw = 257;

int n, m, a[N * 10], b[N * 10], c[N * 10], ans;
ll p[N][N];

int main() {
	#ifdef Madi
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	#endif

	ios_base :: sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;

	rep(i, 1, n)
		rep(j, 1, n)
			if (i != j)
				p[i][j] = inf;

	rep(i, 1, m) {
		cin >> a[i] >> b[i] >> c[i];
		p[a[i]][b[i]] = min(p[a[i]][b[i]], c[i] * 1ll);
		p[b[i]][a[i]] = min(p[b[i]][a[i]], c[i] * 1ll);
	}

	rep(k, 1, n)
		rep(i, 1, n)
			rep(j, 1, n) 
				p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
	
	rep(k, 1, m) {
		bool ok = 1;
		rep(i, 1, n) {
			rep(j, 1, n) {
				if (p[i][a[k]] + c[k] + p[b[k]][j] == p[i][j])
					ok = 0;
				if (p[i][b[k]] + c[k] + p[a[k]][j] == p[i][j])
					ok = 0;			 
			}
		}                            
		ans += ok;
	}

	cout << ans;
	return 0;
}

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

using namespace std;
 
#define debug(s) cerr << #s << " = " << s << '\n'
#define all(v) (v).begin(), (v).end()
#define mem(a,val) memset(a, val, sizeof a)
 
#define ff first
#define ss second
typedef long long ll;

int cnt[10];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> v;
  v.push_back("AC");
  v.push_back("WA");
  v.push_back("TLE");
  v.push_back("RE");
  for (int i = 1; i <= n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < 4; ++j) {
      string p = v[j];
      if (s == p) cnt[j]++;
    }
  }
  for (int i = 0; i < 4; ++i) {
    cout << v[i] << " x " << cnt[i] << endl;
  }
}

Measured memory_bytes: 3660
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    String s = r.readLine();
    int n = Integer.parseInt(s);
    String a = r.readLine();
    String b = r.readLine();
    String c = r.readLine();
    int z = 0;
    for(int i = 0; i < n; i++)
    {
      if(a.charAt(i) == b.charAt(i) && a.charAt(i) == c.charAt(i))
      {
        z += 0;
      }
      else if(a.charAt(i) == b.charAt(i) || a.charAt(i) == c.charAt(i) || c.charAt(i) == b.charAt(i))
      {
        z += 1;
      }
      else
      {
        z += 2;
      }
    }

    System.out.println(z);
  }

}


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

int main() {
    int x[4];
    int y[4];

    for(int i = 0; i < 2; i++) {
        cin >> x[i] >> y[i];
    }

    x[2] = x[1] + y[0] - y[1];
    y[2] = -x[0] + x[1] + y[1];
    x[3] = x[0] + y[0] - y[1];
    y[3] = -x[0] + x[1] + y[0];

    cout << x[2] << " " << y[2] << " ";
    cout << x[3] << " " << y[3]; 

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)
const ll INF = 1LL << 60;

int main()
{

  int N, M;
  cin >> N >> M;
  vector<pair<ll, ll>> v;
  rep(i, N)
  {
    ll a, b;
    cin >> a >> b;
    v.push_back(make_pair(a, b));
  }
  sort(v.begin(), v.end());
  ll ans = 0;
  ll cnt = 0;
  rep(i, N)
  {
    if (M > cnt)
    {
      ans += min(v[i].second, M - cnt) * v[i].first;
      cnt += min(v[i].second, M - cnt);
    }
  }
  cout << ans;
}

Measured memory_bytes: 2420
#include <stdio.h>
#define MAX 100
#define INF 200000

int n, U[MAX][MAX];
void dijkstra();

int main(){
  int i, j, u, k, v, m;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      U[i][j] = INF;
    }
  }

  for(i = 0; i < n; i++){
    scanf("%d%d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d%d",&v,&m);
      U[u][v] = m;
    }
  }
  dijkstra();

  return 0;
}

void dijkstra(){
  int i, u, v, d[MAX], color[MAX], min;
  for(i = 0; i < n; i++){
    d[i] = INF;
    color[i] = 0;
  }
  d[0] = 0;
  color[0] = 1;
  while(1){
    u = -1;
    min = INF;
    for(i = 0; i < n; i++){
      if(color[i] != 2 && min > d[i]){
        u = i;
        min = d[i];
      }
    }
    if(u == -1) break;
    color[u] = 2;

    for(v = 0; v < n; v++){
      if(color[v] != 2 && U[u][v] != -1){
        if(d[v] > d[u] + U[u][v]){
          color[v] = 1;
          d[v] = d[u] + U[u][v];
        }
      }
    }
  }

  for(i = 0; i < n; i++) printf("%d %d\n",i, d[i]);
}

Measured memory_bytes: 636
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''


def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    C = [0] * N
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        A[i] = a
        B[i] = b
        C[i] = c

    happy = [[0] * 3 for i in range(N)]
    happy[0] = [A[0], B[0], C[0]]
    for i in range(1, N):
        happy[i][0] = A[i] + max(happy[i-1][1], happy[i-1][2])
        happy[i][1] = B[i] + max(happy[i-1][2], happy[i-1][0])
        happy[i][2] = C[i] + max(happy[i-1][0], happy[i-1][1])
        # print(i, happy[i-1], happy[i])
    print(max(happy[N-1]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 34676
import java.util.Scanner;

public class Main {
	static final long MOD = 1000000007;
	static long modpow(long n, long y){
		if(y == 0){
			return 1;
		}else if(y == 1){
			return n % MOD;
		}else{
			if(y % 2 == 0){
				long r = modpow(n , y / 2);
				return (r * r) % MOD;
			}else{
				long r = modpow(n , y / 2);
				long r2 = (r * r) % MOD;
				return (r2 * n) % MOD;				
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long ret = 0;
		long A = 0;
		long memo[] = new long[K + 1];
		for(int i = K ; i >= 1 ; --i){
			long comb = modpow(K / i, N);
			for(int j = 2 ; j * i <= K ; ++j){
				comb = (comb - memo[i * j] + MOD) % MOD;
			}
			memo[i] = comb;
			A += comb;
			ret = (ret + comb * (long)i) % MOD;
		}
		System.out.println(ret);
	}
}


Measured memory_bytes: 28312
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

int main(){
    fast_io

    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    vector<ll> sum(n+1);
    sum[0] = 0;
    for(int i=1;i<=n;i++){
      sum[i] = a[i-1] + sum[i-1];
      // sum[i] %= mod;
    }

    ll ans = 0;
    for(int i=0;i<n;i++){
        ll res = (sum[n]-sum[i+1])%mod;
        ans += res * a[i];
        ans %= mod;
    }
    cout << ans%mod<<endl;
    return 0;
}


Measured memory_bytes: 6356
n=int(input())
ans=""
for l in range(1,15):
  if n<=26**l:
    n-=1
    for j in range(l):
      ans+=chr(ord('a')+n%26)
      n//=26
    break
  else:
    n-=26**l
    
print(ans[::-1])
    

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

int main() 
{
  int n, k;
  cin >> n >> k;
  int ans = 0;

  while (n > 0) {
    n /= k;
    ans++;
  }
  cout << ans << endl;
  return 0;
  
}



Measured memory_bytes: 256
#include<stdio.h>
#define M 500000
int a[M],b[M],count=0;
void mergeSort(int *a,int l,int r){
  int i,j,k,m;
  if(r>l){
    m=(r+l)/2;
    mergeSort(a,l,m);
    mergeSort(a,m+1,r);
    for(i=m+1;i>l;i--)
      b[i-1]=a[i-1];
    for(j=m;j<r;j++)
      b[r+m-j]=a[j+1];
    for(k=l;k<=r;k++){
      a[k]=(b[i]<b[j])?b[i++]:b[j--];
      count++;
    }
  }
}

main(){
  int i,n;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  mergeSort(a,0,n-1);
  for(i=0;i<n-1;i++)
    printf("%d ",a[i]);
  printf("%d\n%d\n",a[n-1],count);
  return 0;
}


Measured memory_bytes: 5628
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <time.h>
using namespace std; 

int main(){
	int A, B;
	cin >> A >> B;
	if (B % A == 0)
		cout << A + B << endl;
	else
		cout << B - A << endl;

	return 0;
}

Measured memory_bytes: 256
import math
a, b, h, m = map(int, input().split())
A = (m * 6)
B = (h * 30) + (m * 0.5)

C = min(abs(A - B), 360 - abs(A - B))
D = math.cos(math.radians(C))

print(math.sqrt(a**2 + b ** 2 - 2*D*a * b))

Measured memory_bytes: 9508
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

#define TRACE(x) std::cout << #x << " = " << x << "\n"
#define _ << " _ " <<

using namespace std;

int factPow2(int N) {
  int r = 0;
  while (N > 0) {
    N /= 2;
    r += N;
  }
  return r;
}

int binomMod2(int N, int K) {
  return factPow2(N) == factPow2(K) + factPow2(N - K) ? 1 : 0;
}

int main() {
  std::ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    A[i] = (S[i] - '0') - 1;
  }

  vector<int> c(N);
  for (int i = 0; i < N; ++i) {
    c[i] = binomMod2(N - 1, i);
  }

  int cnt1s = 0, sum1s = 0, sum2s = 0;
  for (int i = 0; i < N; ++i) {
    if (A[i] == 1) {
      cnt1s++;
      sum1s ^= c[i];
    }
    if (A[i] == 2) {
      sum2s ^= c[i];
    }
  }
  if (cnt1s > 0) {
    cout << (sum1s ? "1" : "0") << "\n";
    return 0;
  }

  cout << (sum2s ? "2" : "0") << "\n";
  return 0;
}


Measured memory_bytes: 9116
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=105;
int n,a[MAXN];
void PI(){printf("Impossible\n");}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	if(a[1]==a[2]&&a[2]==a[3]){PI();return 0;}
	if(a[n]!=a[n-1]){PI();return 0;}
	if(a[1]!=a[2]&&a[1]*2!=a[n]){PI();return 0;}
	if(a[1]==a[2]&&a[1]*2-1!=a[n]){PI();return 0;}
	for(int i=n-1;i>=1;i--)
		if(a[i]!=a[i+1]&&a[i]+1!=a[i+1]){
			PI();return 0;
		}
	printf("Possible\n");
	return 0;
}

Measured memory_bytes: 256
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        前処理 = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0                    # 範囲外という事はすなわち、そのような場合の数は無いはずなので、0を出力すればよい。（これが無いとREになる）
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

MOD = 10**9 + 7
N = int(input())
C = Combination(N+1)
v = {}
for i, a in enumerate(map(int, input().split()),start=1):
    if v.get(a,0)==0:
        v[a] = i
    else:
        L = i-v[a]
        break
for l in range(1,N+2):
    print((C(N+1,l)-C(N-L,l-1))%MOD)

Measured memory_bytes: 97496
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
//main
signed main(){
  int L,R;cin>>L>>R;int ans=LINF;
  if(R-L>2020)cout<<0<<endl;
  else{

    for(int i=L;i<R;i++){
      for(int j=i+1;j<=R;j++){
        ans=min(ans,((i%2019)*(j%2019))%2019);
      }
    }
    cout<<ans<<endl;
  }

}


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

/* #pragma */
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

/*alias*/
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int

/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

/* func */
int GCD(int a,int b){return b?GCD(b,a%b):a;}
long long GCD(long long a, long long b){return b ? GCD(b, a%b) : a;}
int LCM(int a, int b){return a * b / GCD(a, b);}
long long LCM(long long a, long long b){return a * b / GCD(a, b);}

/*struct*/
struct aaa {
	aaa() {
		cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);
	};
}aaaaaaa;

/* const */
const int INF = 1001001001;
const long long LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const double EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//Counterclockwise from the 6o'clock direction
//Take the x-axis downward and the y-axis right

//#define int long long

//g++ -std=c++14 -Wall --pedantic-errors -o template template.cpp
//g++ -std=c++14 -Wall --pedantic-errors template.cpp
//chcp 65001

/*global*/



signed main()
{
	int n;cin >> n;
	int l; cin >> l;

	int fsum{};
	for(int i = 1; i <= n; ++i){
		fsum += l+i-1;
	}

	int want{};
	int sum{};
	int msa = 10000;
	int sa{};
	int ans{};
	for(int i = 1; i <= n; ++i){//sa最小にするiを出力
	sum = 0;
		for(int j = 1; j <= n; ++j){
			if(i != j)
			sum += l+j-1;
		}

		sa = (int)abs(fsum-sum);
		if(sa < msa){
			want =i;
			msa = sa;
			ans = sum;
		}
	}
	cout << ans << endl;
    return 0;
}


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

#define REP(i,n) for(int i=0,_n=(int)(n); i < _n; i++)
typedef long long ll;

double solve(int N, double d1, double x) {
  double sum = 2*N*d1 + x*(double)N*(2*N-1);
  double res = sum / (2 * N);
  return res;
}

int main2() {
  int N;
  double d1;
  double x;
  cin >> N >> d1 >> x;

  double ans = 0;
  while (N > 0) {
    ans += solve(N, d1, x);
    d1 = d1 + (2 * d1 + 5 * x) / (2 * N);
    x = (2 * N + 4) * x / (2  * N);
    N--;
  }
  printf("%.10f\n", ans);
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <cmath>
#include <iostream>

using namespace std;

typedef long long int ll;

const long long INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9; 
 
int main(void){
    int n,k;
    // int n;
    scanf("%d", &n);
    scanf("%d", &k);

    ll h[n];
    ll costs[n];

    for( int i = 0; i < n; ++i ){
        ll height;
        scanf("%lld", &height);
        h[i] = height;
    }
    for( int i = n - 1; i >= 0; --i ){
        // printf("%s\n", "========");
        ll c;
        if (i == n - 1) {
            c = 0;
        } else if (i == n - 2) {
            c = abs(h[i + 1] - h[i]);
        } else {
            c = INF; 
            for (int a = 1; a <= k; ++a) {
                // printf("%s\n", "---");
                // printf("jump_range: %d\n", a);
                // printf("current: %d\n", i);
                if (a + i >= n) {
                    break;
                }
                int jump_to;
                jump_to = i + a;
                ll jump_cost;
                jump_cost = abs(h[jump_to] - h[i]) + costs[jump_to];
                // printf("jump_to: %d\n", jump_to);
                // printf("jump_cost: %lld\n", jump_cost);
                if (c > jump_cost)
                {
                    c = jump_cost;
                }
            }
        }
        // printf("%d\n", i);
        // printf("%lld\n", c);
        costs[i] = c;
    }
    // printf("result: %lld", costs[0]);
    printf("%lld", costs[0]);
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>


int main() {
	int n; std::cin >> n;
	std::string str; std::cin >> str;
	int count = 1;
	for (auto i = 1; i < str.size(); ++i) {
		if (str[i] != str[i - 1]) ++count;
	}
	std::cout << count << std::endl;
}

Measured memory_bytes: 1144
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm> // sort

#define DEBUG 0

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll mod = 1000000007;
static const ll INF = 1000000000000000000LL;
                    //999999997000000003
                    //1000000000000000000

using namespace std;

int main(){
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;
    int res = 1;

    for(int i = 1; i <=N; i*=2)
    {
        if(i <= N)
        {
            res = i;
        }
        else
        {
            break;
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
# AGC 20 A
n, a, b = [int(el) for el in input().split(' ')]

while 1 <= a <= n and 1 <= b <= n:
    if b != a + 1 and 1 <= a +1 <= n:
        a = a + 1
    elif b != a - 1 and 1 <= a - 1 <= n:
        a = a - 1
    else:
        print('Borys')
        break
    if a != b - 1 and 1 <= b - 1 <= n:
        b = b - 1
    elif a != b + 1 and 1 <= b + 1 <= n:
        b = b + 1
    else:
        print('Alice')
        break



Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#define DEBUG(x) std::cout << '>' << #x << ':' << x << '\n';
#define PRINTVEC(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i] << ' '; std::cout << '\n';
#define PRINTPAIR(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i].first << ' ' << x[i].second << '\n'; std::cout << '\n';
#define PRINTSET(x) for (auto it = x.begin(); it != x.end(); it++) { std::cout << *it << ' '; } std::cout << '\n';
#define io std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);   
const int INF = 1<<29;
typedef long long ll;
using namespace std;

vector<vector<int>> adj;
vector<bool> vis;

void dfs(int i) {
    vis[i] = true;
    for (auto it = adj[i].begin(); it != adj[i].end(); it ++) {
        if (!vis[*it]) {
            dfs(*it);
        }
    }
}
 
int solve() {
    int n,m;
    cin >> n >> m;
    adj.resize(n);
    vis.resize(n,false);
    for (int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        x--,y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int cmp = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(i);
            cmp++;
        }
    }
    return cmp - 1;
}

int main()
{
	io;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout);  
    #endif

    cout << solve() << endl;

    #ifndef ONLINE_JUDGE   
    std::cout << '\n' << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
    #endif
    return 0;
}


Measured memory_bytes: 9456
#include <bits/stdc++.h>
using namespace std;
static const long long MOD=1000000007;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
  long long N;
  cin>>N;
  Bint A[200010];
  Bint sum=0;
  for(long long i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  Bint ans=0;
  sum-=A[0];
  for(long long i=0;i<N-1;i++){
    //cout<<ans<<" "<<sum<<endl;
    ans+=A[i]*sum;
    ans%=MOD;
    sum-=A[i+1];
  }
  
  cout<<ans<<endl;
  return 0;
}

 

 

Measured memory_bytes: 9944
if __name__ == "__main__":
    N,L = input().split()
    tastesum = 0
    tastemin = 1000000000
    N = int(N)
    L = int(L)
    for i in range(N):
        tmptaste = i + L
        if abs(tastemin) > abs(tmptaste):
            tastemin = tmptaste
        tastesum = tastesum + tmptaste
    tastesum = tastesum - tastemin
    print(tastesum)    


Measured memory_bytes: 2940
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
    #define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
    #define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
const int MAXN = 123;
LL nums[MAXN];




int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout.precision(10); cout << fixed;
#ifdef LOCAL
    freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
    LL n, x; cin >> n >> x;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums+n);
    int i = 0;
    for (; i < n; i++) {
        if (x >= nums[i]) x -= nums[i];
        else break;
    }
    if (i == n && x != 0) i--;
    cout << i << endl;






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, ans;
char c[N];
int main() {
    scanf("%d%s", &n, c + 1);
    for(int i = 1, ptr = n; i <= n; ++i) {
        if(c[i] == 'W') {
            while(ptr > i && c[ptr] == 'W')--ptr;
            if(ptr == i)break;
            ans++;
            swap(c[i], c[ptr]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3896
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int cnt[4];
double dp[330][330][330];

int main(){
    int n, a;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a;
        cnt[a]++;
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                int nonzero = i + j + k;
                if(nonzero == 0) continue;
                dp[i][j][k] = (double) n / nonzero;
                if(i - 1 >= 0) dp[i][j][k] += dp[i-1][j+1][k] * i / nonzero;
                if(j - 1 >= 0) dp[i][j][k] += dp[i][j-1][k+1] * j / nonzero;
                if(k - 1 >= 0) dp[i][j][k] += dp[i][j][k-1] * k / nonzero;
            }
        }
    }
    printf("%.18lf\n", dp[cnt[3]][cnt[2]][cnt[1]]);
}

Measured memory_bytes: 258304
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <iomanip>
using namespace std;

int main() {
  int n, x;
  int l[110];
  cin >> n >> x;
  for (int i = 0; i < n; i++) {
    cin >> l[i];
  }


  int d[110];
  d[0] = 0;
  for (int i = 1; i < n+1; i++) {
    d[i] = d[i-1] + l[i-1];
  }

  int ans = 0;
  for (int i = 0; i < n+1; i++) {
    if (d[i] <= x) {
      ans++;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string s;
    cin >> s;
 
    int k;
    cin >> k;
 
    long long size = s.size();
 
    s = s + ' ';
    vector<int> cnt(size, 0);
 
    bool start=false;
    bool end=false;
 
    int tmp = -1;
 
    long long sum = 0;
 
    bool flag=true;
    int cnt_start=1;
    int cnt_end=0;
 
     if(size == 1){
        sum = k / 2;
        cout << sum << endl;
        return 0;
    }
 
    for(int i=0; i < size-1; i++){
        if(s.at(i) != s.at(i+1)){
            break;
        }
        if(i == size-2){
            sum = ((size) * k) / 2;
            cout << sum << endl;
            return 0;
        }
    }
 
    for(int i=1; i < size; i++){
        if(s.at(0) == s.at(i)){
            cnt_start++;
        }
        else{
            break;
        }
    }
 
    for(int i=size-1; i > 0; i--){
        if(s.at(0) == s.at(i)){
            cnt_end++;
        }
        else{
            break;
        }
    }
 
    for(int j=0; j < size-1; j++){
        if(s.at(j) != s.at(j+1)){
            start = false;
        }
        else if(s.at(j) == s.at(j+1) && tmp <= j){
            start = true;
        }
 
 
        for(int i=j; i < s.size(); i++){
            if(s.at(j) == s.at(i) && start == true){
                cnt.at(j)++;
                end = true;
  //            cout << cnt.at(j) << endl;
            }
            else if(s.at(j) != s.at(i)  && end == true){
                start = false;
                end = false;
                tmp = i;
                cnt.at(j) = cnt.at(j) / 2;
            }
        }
    }
 
    for(int c: cnt){
//        cout << c << endl;
        sum += c;
    }

    sum = k * sum;
    if((cnt_start + cnt_end) % 2 == 0 && cnt_start % 2 != 0 && cnt_end % 2 != 0){
        sum += (k-1);
    }

    cout << sum << endl;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> p(n),c(n);
    rep(i,n) cin >> p[i],--p[i];
    rep(i,n) cin >> c[i];
    ll ans = -LINF;
    rep(i,n){
        int x = i;
        ll s = 0;
        vector<ll> score;
        while(1){
            x = p[x];
            score.push_back(s);
            s+=c[x];
            if(x==i){
                break;
            }
        }
        ll res = -LINF;
        for(int i=1;i<min(k+1,(int)(score.size()));++i) res = max(res,score[i]);
        ans = max(ans,res);
        ll cyc_score = s;
        int cyc = score.size();

        //cout << cyc << " " << cyc_score << " " << endl;
        if(cyc_score < 0 || k+1 < (int)(score.size())) continue;
        rep(i,score.size()) res = max(res,score[i]+cyc_score*((k-i)/cyc));
        ans = max(ans,res);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3732
distance' i j
	| i `mod` j == 0 = i `div` j + j - 2
	| otherwise      = distance' i (j - 1)

distance n = distance' n (isqrt n)
	where
		isqrt = floor . sqrt . fromIntegral

main :: IO ()
main = do
	n <- readLn
	print $ distance n


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N, K; cin >> N >> K;
  ll A[N]; rep(i,N) cin >> A[i];
  ll l = -2*pow(10,1), r = 2*pow(10,1);

  vector<ll> pl, mi;
  ll pc = 0, mc = 0, zc = 0;
  rep(i,N) {
    if (A[i]==0) zc++;
    else if (A[i]<0) { mi.push_back(-1*A[i]); mc++; }
    else { pl.push_back(A[i]); pc++; }
  }
  sort(all(pl)); sort(all(mi));

  ll result = 0;
  if (pc*mc>=K) {
    ll l = 0, r = powl(10,18);
    while (l!=r) {
      ll mid = (l+r+1)/2;
      ll count = 0;
      for (auto x: mi) count += pc - (lower_bound(all(pl),(mid+(x-1))/x) - pl.begin());
      if (count>=K) l = mid;
      else r = mid-1;
      // cout << mid << "->" << count << endl;
    }
    result = -1*l;
  }
  else if (K>pc*mc+zc*(pc+mc)+zc*(zc-1)/2) {
    K -= pc*mc+zc*(pc+mc)+zc*(zc-1)/2;
    K--;
    ll l = 0, r = powl(10,18);
    while (l!=r) {
      ll mid = (l+r+1)/2;
      ll count = 0;
      rep(i,mc) {
        count += upper_bound(all(mi), mid/mi[i]) - mi.begin();
        if (mi[i]*mi[i]<=mid) count--;
      }
      rep(i,pc) {
        count += upper_bound(all(pl), mid/pl[i]) - pl.begin();
        if (pl[i]*pl[i]<=mid) count--;
      }
      count /= 2;
      if (count>K) r = mid-1;
      else l = mid;
      // cout << mid << "->" << count << endl;
    }
    result = l+1;
  }
  // cout << K << endl;
  cout << result << endl;
  return 0;
}

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

using namespace std;

int A[3][3], h[3], v[3];
int r=0;
int l=0;

bool check(int num) {
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if (num == A[i][j]) {
                h[i]++;
                v[j]++;
                if (i == j) {
                    r++;
                }
                if (i == 2-j) {
                    l++;
                } 
                if ((h[i] == 3) || (v[j] == 3) || r == 3 || l == 3) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int N, tmp;
    for(int i=0; i<3; i++) {
        cin >> A[i][0] >> A[i][1] >> A[i][2];
        h[i] = 0;
        v[i] = 0;
    }
    cin  >> N;
    for(int i=0; i<N; i++) {
        cin >> tmp;
        if (check(tmp)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define For(i,x,y) for(int i=(x);i<=(y);++i)
#define pll pair<ll,ll>
#define fr first
#define sd second
using namespace std;

pll a[N];
ll ansx=0,ansy=1,sum[N],S=0;
bool cmp(const pll &a,const pll &b){ return a.fr>b.fr; }
ll calc(int x,int y){ return y<=x?sum[x]-a[y].fr:sum[x]; }
ll gcd(ll x,ll y){ return x%y?gcd(y,x%y):y; }

int main(){
    int n; scanf("%d",&n);
    For(i,1,n){
        scanf("%lld%lld",&a[i].fr,&a[i].sd);
        S+=a[i].fr;
        a[i].fr=max(a[i].fr,a[i].sd);
    }
    sort(a+1,a+n+1,cmp);
    For(i,1,n) sum[i]=sum[i-1]+a[i].fr;
    For(i,1,n){
        int l=0,r=n,num=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(calc(mid,i)>=S-a[i].sd) num=mid,r=mid-1;
            else l=mid+1;
        }
        if(num<0) continue;
        if(calc(num,i)>=S) continue;
        ll nowx=1ll*(1ll*n-(num-(i<=num)))*a[i].sd-S+calc(num,i),nowy=1ll*n*a[i].sd;
        ll p=gcd(nowx,nowy);nowx/=p,nowy/=p;
        if(1.0*nowx*ansy>1.0*nowy*ansx) ansx=nowx,ansy=nowy;        
    }
    printf("%lld %lld\n",ansx,ansy);
}


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

int main() {
  int n;
  cin >>n;
  int kotae=0;
  int num=1;
  for(int i=2;i<=n;i++){
    int count=0;
    int x=i;
    while(x%2==0){
      count++;
      x/=2;
    }
    if(kotae<count){
      kotae=count;
      num=i;
    }
  }
  cout<<num<<endl;
  return 0;
}
      

      

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,ma,mi;
  cin>>n>>a;
  ma=a;
  mi=a;
  for(int i=1;i<n;i++){
    cin>>a;
    ma=max(ma,a);
    mi=min(mi,a);
  }
  cout<<ma-mi;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    ll X;
    cin >> X;
    ll k = 1;
    while(k*(k+1)/2 < X) k++;
    cout << k << endl;
}

Measured memory_bytes: 256
n,A,B,C=map(int,input().split(' '))
l=[int(input()) for i in range(n)]
INF=10**9
def bfs(cur,a,b,c):
    if cur==n:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c)>0 else INF
    else:
        ret0=bfs(cur+1,a,b,c)
        ret1=bfs(cur+1,a+l[cur],b,c)+10
        ret2=bfs(cur+1,a,b+l[cur],c)+10
        ret3=bfs(cur+1,a,b,c+l[cur])+10
        return min(ret0,ret1,ret2,ret3)
print(bfs(0,0,0,0))
    


Measured memory_bytes: 3064
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0] * 3 for _ in range(n+1)]
for i in range(1,n+1):
  dp[i][0]=max(dp[i-1][1],dp[i-1][2])+l[i-1][0]
  dp[i][1]=max(dp[i-1][0],dp[i-1][2])+l[i-1][1]
  dp[i][2]=max(dp[i-1][0],dp[i-1][1])+l[i-1][2]

print(max(dp[n][0],dp[n][1],dp[n][2]))


Measured memory_bytes: 50140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF (1 << 29)

int main(){
  int n, m;
  int cost[21][21];
  int a, b, c, d;
  
  for(int i = 0 ; i < 21 ; i++){
    for(int j = 0 ; j < 21 ; j++){
      cost[i][j] = INF;
      if(i == j) cost[i][j] = 0;
    }
  }
      
  cin >> n >> m;
  while(m--){
    scanf("%d,%d,%d,%d", &a, &b, &c, &d);
    cost[a][b] = c;
    cost[b][a] = d;
  }
  
  for(int k = 1 ; k <= n ; k++){
    for(int i = 1 ; i <= n ; i++){
      for(int j = 1 ; j <= n ; j++){
	cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
      }
    }
  }
  
  int x1, x2, y1, y2;
  scanf("%d,%d,%d,%d", &x1, &x2, &y1, &y2);
  
  cout << y1 - y2 - cost[x1][x2] - cost[x2][x1] << endl;
}

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a,b;
	cin>>a>>b;
	if(a<0&&b>=0){
		cout<<"Zero"<<endl;
	}else if(a==0&&b==0){
		cout<<"Zero"<<endl;
	}else if(a<0&&b<0){
		if((b-a)%2==0){
			cout<<"Negative"<<endl;
		}else{
			cout<<"Positive"<<endl;
		}
	}else if(a>0&&b>0){
		cout<<"Positive"<<endl;
	}
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

long long gcd(long long x,long long y){
  long long tmp;
  if(x<y){
    tmp=x;
    x=y;
    y=tmp;
  }
  if(y==0) return x;
  return gcd(x%y,y);
}

int main(){
  long long a,b,i,n,cnt=0;
  scanf("%lld%lld",&a,&b);
  n=gcd(a,b);
  for(i=2;i<=sqrt(n);i++) {
    if(n==1) break;
    if(n%i==0){
      cnt++;
      while(n%i==0){
				n/=i;
			}
    }
  }
  if(n==1){
    printf("%lld",cnt+1);
  }
  else{
    printf("%lld",cnt+2);
  }
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>

#define MOD (1000000000LL+7LL)

int main(void)
{
	int N,M;
	scanf("%d %d\n",&N, &M);
	if (M>N){
		int tmp;
		tmp=M;M=N;N=tmp;
	}
	//printf("%d %d\n",M,N);
	assert(M<=N);
	if ((N-M)>=2){
		printf("0\n");
		return 0;
	}
	// nPn*mPm = N!*M!
	long long ret=1;
	long long m,n;
	if (M==N)ret*=2;
	for (m=1;m<=M;m++){
		ret *= m;
		ret %= MOD;
	}
	for (n=1;n<=N;n++){
		ret *= n;
		ret %= MOD;
	}
	printf("%lld\n",ret);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

void yn(bool b){
  if(b) cout << "Yes" << endl;
  else cout << "No" << endl;
  return;
}

int main() {
  lint n, t = 0;
  bool b = 1;
  cin >> n;
  vector<pii> v(n);
  rep(i, n) cin >> v[i].se >>  v[i].fi;
  sort(v.begin(),  v.end());
  rep(i, n){
    t += v[i].se;
    if(t > v[i].fi){
      b = 0;
      break;
    }
  }
  yn(b);
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>

using namespace std;

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

int N;
int a[100010];

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }

    sort(a, a+N);
    ll s1 = 0, s2 = 0;
    int l = 0, r = N-1;
    bool l_t = true;
    int m = 1e9;
    while(l < r){
        s1 += a[r] - a[l];
        m = min(a[r] - a[l], m);
        if(l_t){
            l_t = false;
            l++;
        }
        else{
            l_t = true;
            r--;
        }
    }
    s1 += a[l] - a[0];
    s1 -= m;

    l = 0; r = N-1;
    l_t = false;
    m = 1e9;
    while(l < r){
        s2 += a[r] - a[l];
        m = min(a[r] - a[l], m);
        if(l_t){
            l_t = false;
            l++;
        }
        else{
            l_t = true;
            r--;
        }
    }
    s2 += a[N-1] - a[l];
    s2 -= m;

    cout << max(s1, s2) << endl;


    return 0;

}



Measured memory_bytes: 640
function Main(input: string) {
  const lines = input.split('\n');
  const params1 = lines[0].split(' ');

  const x = parseInt(params1[1]);
  const xs = lines[1].split(' ').map(x => parseInt(x));

  const d = xs.map(a => Math.abs(a - x)).reduce(euclid);

  console.log(d);
}

function euclid(m: number, n: number): number {
  if (m < n) return euclid(n, m);
  if (n === 0) return m;
  return euclid(n, m % n);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 28072
K = int(input())
mod = 0
# mod Kは、0,1,...,K-1　の高々K種類
# i=K+1 まで行くと鳩の巣原理よりmodが既出になり、以降ループ
# すなわちi=Kまで見れば十分
for i in range(1, K + 1):
    mod = (10 * mod + 7) % K
    if mod % K == 0:
        print(i)
        exit()
print(-1)


Measured memory_bytes: 9164