akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define ll long long
#define vi vector < int >
#define si set <int>
#define mii map <int, int>
#define vll vector < ll >
#define pii pair < int , int >
#define ff first
#define tc \
    int ttt; cin >> ttt;\
    while(ttt --)
#define ss second
#define f(i,a,b) for(int i=a;i<b;i++)
#define rev(i,a,b) for(int i=a;i>=b;i--)
#define nl '\n'
#define all(x) x.begin() , x.end()
#define mne min_element
#define mxe max_element
ll gcd(ll x, ll y) {return y == 0 ? x : gcd(y, x % y);}
int logg(ll x , ll y) {if (x == 0) return -1; return logg(x / y, y) + 1;}
ll poww(ll a, ll b, ll m) {
	if (b == 0) return 1;
	ll ans = 1;
	ans = poww(a, b >> 1, m);
	ans = (ans * ans) % m;
	if (b & 1) ans = (ans * a) % m;
	return ans;
}
// Start of code
int r, c;
int dp[1001][1001];

int solve() {

	f(i, 1, c + 1) {
		if (dp[1][i] == -1) break;
		else dp[1][i] = 1;
	}
	f(i, 1, r + 1) {
		if (dp[i][1] == -1) break;
		else dp[i][1] = 1;
	}

	f(i, 2, r + 1) {
		f(j, 2, c + 1) {
			if (dp[i][j] == -1) continue;
			else dp[i][j] = ((dp[i - 1][j] == -1 ? 0 : dp[i - 1][j])  + (dp[i][j - 1] == -1 ? 0 : dp[i][j - 1])) % mod;
		}
	}

	return dp[r][c];
}

int32_t main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast;
	cin >> r >> c;
	char ch;
	f(i, 1, r + 1) {
		f(j, 1, c + 1) {
			cin >> ch;
			if (ch == '.') dp[i][j] = 0;
			else dp[i][j] = -1;
		}
	}
	cout << solve();
}

Measured memory_bytes: 11476
#include <iostream>
using namespace std;
 
int comb2(int m, int s) {
    if ( s>=3 && s<=2*m-1 ) {
        return min( max( m-s/2,0 ), (s-1)/2 );
    } else {
        return 0;
    }
}


int main() {
    while (true) {
        int n, x;
        cin >> n >> x;

        if (n == 0 && x==0) {
            break;
        }

        int res = 0;
        int tmp = 0;
        for (int i=min(n,x-3);i>0;i--) {
            tmp = comb2(i-1, x-i);
            if (tmp == 0) {
                break;
            }
            res += tmp;
        }
        cout << res << endl;
    }
    return 0;
}



Measured memory_bytes: 2984
def main():
    n, m = list(map(int, raw_input().split()))
    xyz = []
    for _ in range(n):
        x, y, z = map(int, raw_input().split())
        xyz.append([x, y, z])
    ans = 0
    for xs in [1, -1]:
        for ys in [1, -1]:
            for zs in [1, -1]:
                xyz.sort(key=lambda l: l[0]*xs + l[1]*ys + l[2]*zs, reverse=True)
                x = sum(l[0] for l in xyz[:m])
                y = sum(l[1] for l in xyz[:m])
                z = sum(l[2] for l in xyz[:m])
                ans = max(ans, abs(x) + abs(y) + abs(z))
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 32876
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

signed main(){
	int n;
	cin>>n;
	cout<<n*n*3<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int N, A;
	cin >> N >> A;
	cout << pow(N, 2) - A;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
    int f[100001]={0},a[100001],n,i;
    int main()
    {
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=2;i<=n;i++)
    {
    if(i==2)
    {
    f[i]=abs(a[i]-a[i-1])+f[i-1];
    continue;
    }
    f[i]=min(abs(a[i]-a[i-1])+f[i-1],abs(a[i]-a[i-2])+f[i-2]);
    }
    printf("%d",f[n]);
    return 0;
    }

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

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

  sort(a,a+N);
  sort(b,b+N);
  sort(c,c+N);

  ll ans = 0LL;
  for(int i=0;i<N;i++){
    int x = b[i];
    ll cnta = lower_bound(a,a+N,x) - a;
    ll cntc = N - (upper_bound(c,c+N,x) - c);
    ans += cnta * cntc;
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, k;
	cin >> N >> k;

	vector<Int> a(N);

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

	Int ans = 0;
	N -= k;
	k--;
	ans += 1 + (N + k - 1) / k;
	cout << ans << endl;

}

Measured memory_bytes: 1024
program prob
  implicit none
  integer :: a,b,c
  
  read(*,*) a, b, c

  if ( a < c .and. c < b ) then
     write(*,'(a)') 'Yes'
  else if ( b < c .and. c < a ) then
     write(*,'(a)') 'Yes'
  else
     write(*,'(a)') 'No'
  end if
  
  stop
end program prob


Measured memory_bytes: 2892
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define LFOR(i, a, b) for (long long int i = (a); i <= (b); i++)
#define LRFOR(i, a, b) for (long long int i = (a); i >= (b); i--)
#define MOD 1000000007
#define INF 1000000000           // 2000000000
#define LINF 1000000000000000000 // 9000000000000000000
#define DINF 1000000000000000.0
#define PI 3.14159265358979

//.size()はunsigned int　0-1をするとオーバーフローする

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

int dy[5] = {-1, 0, 1, 0, 0};
int dx[5] = {0, -1, 0, 1, 0};

int main(void) {
    int n,w,h;
    int now=0;
    
    cin>>h>>w>>n;

    if(h>w){
        FOR(i,1,w){
            now+=h;
            if(now>=n){
                cout<<i<<endl;
                break;
            }
        }
    }else{
        FOR(i,1,h){
            now+=w;
            if(now>=n){
                cout<<i<<endl;
                break;
            }
        }
    }
}


Measured memory_bytes: 256
R = lambda: map(int, input().split())
 
n = int(input())
if n % 3:
    ans = 'YNeos'[any(R())::2]
else:
    a = sorted(R())
    m = n // 3
    if a[0] ^ a[m] ^ a[2 * m]:
        ans = 'No'
    elif any(len(set(a[i:i + m])) > 1 for i in range(0, n, m)):
        ans = 'No'
    else:
        ans = 'Yes'
print(ans)


Measured memory_bytes: 14116
#include"bits/stdc++.h"
using namespace std;


int main() {
	int a, b;
	cin >> a >> b;
	int x = b - a;
	int sum = 0;
	int ans;

	for (int i = 1; i < x; i++) {
		sum += i;
	}
	ans = sum - a;

	cout << ans << endl;
}

Measured memory_bytes: 256
loop do
    m, f, r = gets.chomp.split.map(&:to_i)
    score = ""
    if [m, f, r].all?{ |x| x == -1 }
        break
    elsif [m, f].any?{ |x| x == -1 }
        score = "F"
    elsif 80 <= m + f
        score = "A"
    elsif 65 <= m + f
        score = "B"
    elsif 50 <= m + f || 50 <= r
        score = "C"
    elsif 30 <= m + f
        score = "D"
    else
        score = "F"
    end
    puts score
end


Measured memory_bytes: 6872
#include <iostream>
#include <queue>
#include <utility>
#include <ctype.h>
#include <cstdlib>
using namespace std;

typedef pair<int,int> P;
int H,W,N;
int inf = 10e8;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
char G[1010][1010];
int hp = 1,sum = 0;
int sx,sy;
int times[1010][1010];

bool valid(int x,int y){
	return 0<=x && x<H && 0<=y && y<W && G[x][y]!='X';
}

int bfs(){
	queue<P> q;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			times[i][j] = inf;
		}
	}
	while(hp<=N){
		q.push(P(sx,sy));
		times[sx][sy] = 0;
		while(q.size()){
			P p = q.front();q.pop();
			if(isdigit(G[p.first][p.second]) && hp == atoi(&G[p.first][p.second])){
				hp++;
				sum += times[p.first][p.second];
				sx = p.first;sy = p.second;
				for(int i=0;i<H;i++){
					for(int j=0;j<W;j++){
						times[i][j] = inf;
					}
				}
				while(q.size()){
					q.pop();
				}
				break;
			}
			for(int i=0;i<4;i++){
				int x = p.first + dx[i] , y  = p.second + dy[i];
				if(valid(x,y) && times[x][y]==inf){
					q.push(P(x,y));
					times[x][y] = times[p.first][p.second] + 1;
				}
			}
		}
	}
	return sum;
}

int main(){
	cin >> H >> W >> N;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin >> G[i][j];
			if(G[i][j] == 'S'){
				sx = i;
				sy = j;
			}
		}
	}
	cout << bfs() << endl;
}


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

int a[101],dp[101];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==a[i-1])	dp[i]=dp[i-1]+1;
		else	dp[i]=1;
		if(!(dp[i]&1))	ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void){
	int w;
	int b[10];
	int i;
	while(scanf("%d",&w) != EOF){
		for(i = 0;i <= 9;i++){
			b[i] = w%2;
			w = w/2;
		}
		int p_flag = 0;
		for(i = 0;i <= 9;i++){
			if(p_flag == 0){
				if(b[i] == 1){
					printf("%d",(int)pow(2,i));
					p_flag = 1;
				}
			}else{
				if(b[i] == 1)printf(" %d",(int)pow(2,i));
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 640
#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

while 1:
    s=input().rstrip()
    if s=="END OF INPUT":
        break
    ans=""
    now=0
    for i in range(len(s)):
        if s[i]==" ":
            ans+=str(now)
            now=0
        else:
            now+=1
    print(ans+str(now))


Measured memory_bytes: 5560
l, r = map(int, input().split())


all_mod = []

cnt1 = 0
for i in range(l, r, 1):
    cnt = 0
    for j in range(l + 1, r + 1, 1):
        mod = (i * j) % 2019

        all_mod.append(mod)

        if mod == 0:
            break

        cnt += 1

        if cnt > 2019:
            break

    if mod == 0:
        break

    cnt1 += 1
    if cnt1 > 2019:
        break

print(min(all_mod))

Measured memory_bytes: 10500
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long ans = 1;
		for(int i = n;i>0;i--){
			ans *= i;
		}
		
		System.out.println(ans);
	}
}

Measured memory_bytes: 24108
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadInt();

            var list = new List<int>();
            for (int i = 0; i < n; i++)
            {
                var a = ReadInt();
                list.Add(a);
            }

            int[] array = new int[n];

            for (int ii = 0; ii < n; ii++)
            {
                array[ii] = list[ii];
            }
            Array.Sort(array);

            var listmax = array[n - 1];
            var listseccond = array[n - 2];

            for (int j = 0; j < n; j++)
            {
                if (list[j] == listmax)
                {
                    WriteLine(listseccond);
                }
                else
                {
                    WriteLine(listmax);
                }
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        //最大公約数

        public static int Gcd(int a, int b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            while (b != 0)
            {
                var reminder = a % b;
                a = b;
                b = reminder;
            }
            return a;
        }

        //最小公倍数
        public static int Lcm(int a, int b)
        {
            return a * b / Gcd(a, b);
        }

        //文字数を数える
        public static int CountChar(string s, char c)
        {
            return s.Length - s.Replace(c.ToString(), "").Length;
        }
    }
}


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

int main(){
	
	int n;
	int a[100002];

	int c=0,ans=0;

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i!=0){
			if(a[i-1] >= a[i]){
				c++;
			}
			else{
				if(ans < c){
					ans = c;
				}
				c=0;
			}
		}
	}

	if(ans<c){
		ans=c;
	}

	cout<<ans<<endl;
	return(0);

}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mode        998244353
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323

const int N = 1e5+5;
ll n, a[N], k;
set<ll>orig;

void solve()
{
       cin>>n>>k;
       ll mx=0,x, g=0;
       rep(i,0,n)
       {
              cin>>x;
              orig.insert(x);
              mx=max(mx, x);
              g=__gcd(g,x);
       }
       if(orig.find(k)!=orig.end())
       {
              cout<<"POSSIBLE";
              exit(0);
       }
       ll u = (mx/g)*g;
       if(k%g==0 && k<=u)
       {
              cout<<"POSSIBLE";
              exit(0);
       }
       cout<<"IMPOSSIBLE";
}


int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


Measured memory_bytes: 4992
dp = [ [0]*1001 for x in range(11)]
dp[0][0] = 1
for i in range(101):
    for j in range(9,-1,-1):
        for k in range(1001-i):
            dp[j+1][k+i] += dp[j][k]

while 1:
    n, s = map(int, raw_input().split())
    if (n, s) == (0, 0): break
    print dp[n][s]

Measured memory_bytes: 4424
#define _CRT_SECURE_NO_WARNINGS // #pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <sstream>
#include <cmath>
#include <set>
#include <map>
#include <stack>
using namespace std; 

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define len(x) ((int)(x).size())
#define tmax(a,b,c) max((a),max((b),(c)))
#define tmin(a,b,c) min((a),min((b),(c)))
#define debug(x) cerr << #x << " is " << x << endl;

typedef pair<int, int> Pii;
typedef vector<int> Vi;
typedef vector<vector<int> > VVi;
typedef long long ll;
const int inf = 2e9;
const ll ll_inf = 1e17;
const int mod = 1e9 + 7;
const long double eps = 1e-10;

char c[4] = {'m', 'c', 'x', 'i'};
int d[4] = {1000, 100, 10, 1};

int main()
{
	int n;
	cin >> n;
	rep(i,0,n) {
		string a[2];
		cin >> a[0] >> a[1];
		int b[2] = {};
		rep(i,0,2) {
			rep(j,0,4) {
				rep(k,0,min(2, (int)a[i].size())) {
					if (a[i][k] == c[j]) {
						if (k == 0) {
							b[i] += d[j];
							a[i] = a[i].substr(1);
						}
						else {
							int e = a[i][k-1] - '0';
							b[i] += e * d[j];
							a[i] = a[i].substr(2);
						}
					}
				}
			}
		}
		int sum = b[0] + b[1];
		string ans;
		rep(i,0,4) {
			int x = sum / d[i];
			sum %= d[i];
			if (x >= 2) ans += '0'+x;
			if (x) ans += c[i];
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1204
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

string divide[4] = {"dream", "dreamer", "erase", "eraser"};

int main() {
    string s; cin >> s;

    reverse(s.begin(), s.end());
    for (int j = 0; j < 4; j++) {
        string &d = divide[j];
        reverse(d.begin(), d.end());
    }

    bool can = true;
    int i = 0;
    while (i < s.size()) {
        can = false;
        for (int j = 0; j < 4; j++) {
            string &d = divide[j];
            if (s.substr(i, d.size()) == d) {
                can = true;
                i += d.size();
                break;
            }
        }
        if (!can) break;
    }

    puts(can ? "YES" : "NO");

    return 0;
}

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

ll n;
ll a[(1<<18)];
P s[(1<<18)][2];

int main() {
    cin >> n;
    rep(i,(1<<n)) {
        cin >> a[i];
        s[i][0] = P(a[i],i);
        s[i][1] = P(-1,-1);
    }
    ll ans = -1;
    for (int i = 1; i < (1<<n); i++) {
        rep(j,n) {
            if (!(i&(1<<j))) continue;
            int k = i-(1<<j);
            rep(l,2) {
                if (s[k][l].second == s[i][0].second || s[k][l].second == s[i][1].second) continue;
                if (s[k][l].first > s[i][0].first) {
                    s[i][1] = s[i][0];
                    s[i][0] = s[k][l];
                } else if (s[k][l].first > s[i][1].first) {
                    s[i][1] = s[k][l];
                }
            }
        }
        ans = max(ans, s[i][0].first+s[i][1].first);
        cout << ans << endl;
    }
}
































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

int D, N;

int devide(int n) {
    if (n % 100 != 0) return 0;
    return devide(n / 100) + 1;
}

int main() {
    cin >> D >> N;

    int count = 0;
    for (int i = 1; ; i++) {
        if (devide(i) == D) count++;

        if (count == N) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll  long long 
#define ull unsigned long long int
#define boost ios_base::sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL)
#define vi vector<int>
#define P push_back
#define F first
#define S second
#define debug(x) cout<<x<<" "
#define pi vector<pair<int,int> >
#define all(a) a.begin(),a.end()
//#define int ll
#define vvi vector<vector<int>>
using namespace std;
using namespace __gnu_pbds;
typedef tree <pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll const mod=1e9+7;
int powi(int i,int b){
    int res=1;
    while(b){
        if(b&1)res*=i,res%=mod;
        b>>=1;
        i*=i;
        i%=mod;
    }
    return res;
}
// map<int,int> m;
// ll fact(int n){
// 	//if(n==0)return 0;
// 	if(n<=1)return 1;
// 	if(m[n]!=0)return m[n];
// 	return (n*fact(n-1))%mod;
// }
// int ncr(int n,int r){
//     int h=fact(n);
//     int v=fact(r);
//     int j=fact(n-r);
//     v*=j;
//     v%=mod;
//     v=powi(v,mod-2);
//     return (h*v)%mod;
// }
// vi ar(2000000);
// vi sz(2000000);
// int root(int a){
//     if(ar[a]==a)return a;
//     return ar[a]=root(ar[a]);
// }
// int merge(int a,int b){
//     int h=root(a),j=root(b);
//     int ans=sz[h]*sz[j];
//     sz[j]+=sz[h];
//     if(h!=j){
//         ar[h]=j;
//     }
//     return ans;
// }
void solve(){
    int s,w;
    cin>>s>>w;
    if(w>=s){
        cout<<"unsafe";
    }else{
        cout<<"safe";
    }
}
signed main(){
    boost;
    int t=1;
    //cin>>t;
    for(int _=1;_<=t;_++){
        //cout<<"Case #"<<_<<": ";
        solve();
        cout<<"\n";
    }
    
    return 0;
}

Measured memory_bytes: 3652
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int[] T = new int[N];
    int[] A = new int[N];

    for (int i = 0; i < N; i++) {
      T[i] = sc.nextInt();
      A[i] = sc.nextInt();
    }

    sc.close();
    
    long[] Takahashi = new long[N];
    long[] Aoki = new long[N];
    
    Takahashi[0] = T[0];
    Aoki[0] = A[0];

    for (int i = 1; i < N; i++) {

      long t = Takahashi[i - 1] / T[i];
      long a = Aoki[i - 1] / A[i];

      if (Takahashi[i - 1] % T[i] != 0) {
        t = t + 1;
      }

      if (Aoki[i - 1] % A[i] != 0) {
        a = a + 1;
      }
      
      long n = Math.max(t, a);

      Takahashi[i] = n * T[i];
      Aoki[i] = n * A[i];

    }

    System.out.println(Takahashi[N - 1] + Aoki[N - 1]);

  }

}

Measured memory_bytes: 25684
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B;
	cin >> N >> A >> B;
	if (abs(A - B) % 2 == 0) {
		cout << "Alice" << endl;
	}
	else {
		cout << "Borys" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

ll N;
string S;
bool dp1[10], dp2[100], dp3[1000];

signed main(){
    cin >> N >> S;
    REP(i, N){
        ll n = S[i] - '0';
        REP(j, 100) dp3[j * 10 + n] |= dp2[j];
        REP(j, 10) dp2[j * 10 + n] |= dp1[j];
        dp1[n] = true;
    }
    ll ans = 0;
    REP(i, 1000) ans += (dp3[i] == true);
    //REP(i, 10) if(dp1[i]) cerr << i << " "; cerr << endl;
    //REP(i, 100) if(dp2[i]) cerr << i << " "; cerr << endl;
    //REP(i, 1000) if(dp3[i]) cerr << i << " "; cerr << endl;
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 3672
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)


typedef map<string, int> map_type;
typedef pair<string, int> value_type;

struct second_order {
  bool operator()(const value_type& x, const value_type& y) const {
    if( x.second != y.second) return x.second < y.second;
    return x.first > y.first;
  }
};

typedef priority_queue<value_type, vector<value_type>, second_order> pqueue_type;


pqueue_type map_to_pqueue(map_type m) {
    pqueue_type que;
    for(auto it=m.begin(); it!=m.end(); ++it) {
        que.push(*it);
    }
    return que;
}


int main(void){
    int n;
    cin >> n;
    cout << 3.1415926535897*n*2 << endl;
    return 0;
}


Measured memory_bytes: 3724
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if (a >= b && a >= c) {
			System.out.println(a * 10 + b + c);
		} else if (b >= a && b >= c) {
			System.out.println(b * 10 + a + c);
		} else {
			System.out.println(c * 10 + a + b);
		}

		sc.close();
	}
}


Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    static class BGreedyTakahashi
    {
        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList();
            var a = inputs[0];
            var b = inputs[1];
            var k = inputs[2];

            long taka = a - k;
            if (taka >= 0)
            {
                Console.WriteLine($"{taka} {b}");
                Console.ReadLine();
                return;
            }
            long aoki = b + taka;
            if (aoki >= 0)
            {
                Console.WriteLine($"{0} {aoki}");
                Console.ReadLine();
                return;
            }

            Console.WriteLine($"{0} {0}");
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 13396
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

# 素因数分解で全部素数冪にして集計
C = Counter()
for a in range(2, N+1):
    C.update(factorize(a))

# 素数冪から約数の個数を求める
ans = 1
for v in C.values():
    ans *= v + 1
    ans %= MOD
print(ans)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
 	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,M;
bool vis[MAXN];
vector<int> to[MAXN];
void Solve() {
    read(N);read(M);
    int a,b;
    vis[N] = 1;
    for(int i = 1 ; i <= M ; ++i) {
	read(a);read(b);
	if(a > b) swap(a,b);
	if(b == N) vis[a] = 1;
	to[a].pb(b);to[b].pb(a);
    }
    if(vis[1]) {puts("POSSIBLE");return;}
    for(auto k : to[1]) {
	if(vis[k]) {puts("POSSIBLE");return;}
    }
    puts("IMPOSSIBLE");
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 12144
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final long MOD = 1000000007;

        long[] f = new long[100002];
        f[0] = f[1] = 1;

        for (int i = 2; i <= 100000; i++) {
            f[i] = (f[i - 1] * i) % MOD;
        }

        while (sc.hasNextInt()) {
            int N = sc.nextInt();
            int M = sc.nextInt();
            long ans = 0;

            if (N == M) {
                ans = (f[N] * f[M] * 2) % MOD;
            } else if (Math.abs(N - M) == 1) {
                ans = (f[N] * f[M]) % MOD;
            }

            System.out.println(ans);
        }
    }
}


Measured memory_bytes: 23252
#include<iostream>
using namespace std;
int t[100007];
int main(){
	int n;
	int a,b,c;
	int i,j,k;
	int s=0;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a;
		t[a]++;
	}
	for(i=0;i<100000;i++){
		b=t[i]+t[i+1]+t[i+2];
		if(b>s)s=b;
	}
	cout<<s<<endl;
	return 0;
}
		
	


Measured memory_bytes: 640
import sys
#input = sys.stdin.buffer.readline

def main():
    s = input().split("T")
    x,y = map(int,input().split())
    l = len(s)
    dx,dy = [len(s[0])],[0]
    nx,ny = [],[]
    for i in range(1,l):
        d = len(s[i])
        if i%2 == 0:
            nx = []
            for num in dx:
                nx.append(num+d)
                nx.append(num-d)
            dx = list(set(nx))
        else:
            ny = []
            for num in dy:
                ny.append(num+d)
                ny.append(num-d)
            dy = list(set(ny))

    if (x in dx and y in dy):
        print("Yes")
    else:
        print("No")
    
if __name__ == "__main__":
    main()


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

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define pp pop_back()
#define ll long long
#define ld long double
#define ok puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

inline ll min(ll a, ll b) {
    return (a > b) ? b : a;
}

inline ll max(ll a, ll b) {
    return (a > b) ? a : b;
}

const int N = 1e6 + 7;
const int inf = 1e9 + 7;
const ll linf = 1e18 + 9;

ll x[51];

map < ll, ll > dp, old;
map < ll, ll > :: iterator it;

main() {
    //freopen("contest.in", "r", stdin); freopen("contest.out", "w", stdout);
    ll n, a; cin >> n >> a;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        x[i] -= a;
    }
    old[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (it = old.begin(); it != old.end(); it++) {
            dp[it -> fr + x[i]] += it -> sc;
            // cout << "dp = " << (it -> fr + x[i]) << ' ' << it -> sc << ' ' << i << endl;
            dp[it -> fr] += it -> sc;
        }
        old.swap(dp);
        dp.clear();
    }
    old[0]--;
    cout << old[0];
}


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

const long long MOD = 1000000007;

long long f[100005], fi[100005];

long long mod_pow(long long x, long long n, long long mod){
	long long res = 1;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

void init(int n){
	f[0] = 1;
	for(int i = 1; i <= n; i++){
		f[i] = f[i-1] * i % MOD;
	}
	fi[n] = mod_pow(f[n], MOD-2, MOD);
	for(int i = n; i > 0; i--){
		fi[i-1] = fi[i] * i % MOD;
	}
}

long long comb(int r, int c){
	if(r < c) return 0;
	return f[r] * fi[c] % MOD * fi[r-c] % MOD;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	vector<long long> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	init(100002);
	sort(a.begin(), a.end());
	long long ans = 0;
	for(int i = k-1; i < n; i++){
		ans = (ans + (a[i]*comb(i, k-1))%MOD) % MOD;
	}
	for(int i = 0; i < n-k+1; i++){
		long long sub = (a[i]*comb(n-i-1, k-1))%MOD;
		if(ans <= sub) ans += MOD;
		ans = (ans - sub) % MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Data.List
import Data.Maybe
import Data.Char

toTuple :: [Int] -> (Int, Int)
toTuple [a,b] = (b,a)

solve :: [(Int,Int)] -> Int -> Int -> Int
solve [] memo bridges = bridges
solve ((to,from):xs) memo bridges = 
  if from <= memo then
    solve xs memo bridges
  else 
    solve xs (to-1) (bridges+1)

main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  xs <- replicateM m $ do 
      s <- BS.getLine
      let (from, s') = fromJust $ BS.readInt $ BS.dropWhile isSpace s
      let (to, _) = fromJust $ BS.readInt $ BS.dropWhile isSpace s'
      return (to, from)
  
  print $ solve (sort xs) 0 0

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

ll N;
void search(ll cur , ll use, ll &counter){
  if(cur > N) return;
  if(use == 0b111) counter++;
  search(cur * 10 + 3, use | 0b001, counter);
  search(cur * 10 + 5, use | 0b010, counter);
  search(cur * 10 + 7, use | 0b100, counter);
}

int main() {
  cin >> N;
  ll ans = 0;
  search(0, 0, ans);
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in);) {
			
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			if (a < b && b < c) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
		
	}

}


Measured memory_bytes: 26116
function Main(input){
  var data = input.split("\n");
  console.log(Math.ceil(data[0]/10)*10
  +Math.ceil(data[1]/10)*10
  +Math.ceil(data[2]/10)*10
  +Math.ceil(data[3]/10)*10
  +Math.ceil(data[4]/10)*10
  +Math.min(
  	(data[0]-1)%10+1,
    (data[1]-1)%10+1,
    (data[2]-1)%10+1,
    (data[3]-1)%10+1,
    (data[4]-1)%10+1
  )
  -10);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 9420
// 6/22 解き直し
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    ll N;
    cin >> N;

    if (N % 2) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;

    while (N > 0) {
        ans += N / 10;
        N /= 5;
    }

    cout << ans << endl;
}

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

bool isprime(int x)
{
	if(x==2)
		return true;
	
	if(x<2||x%2==0)
		return false;

	for(int i=3;i*i<=x;i+=2){
		if(x%i==0)
			return false;
	}

	return true;
}

int main()
{
	int n;
	cin>>n;
	
	int cnt=0;
	
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		
		if(isprime(x)){
			cnt++;
		}
	}

	cout<<cnt<<endl;

	return 0;
}

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

int main(){
	bool cards[4][14];
	int n, rank;
	char suit;

	for ( int s = 0; s < 4; s++ )
		for ( int r = 1; r <= 13; r++)
			cards[s][r] = 0 ;

	cin >> n;
	for ( int i = 0; i < n; i++){
		cin >> suit >> rank;
		if (suit == 'S') cards[0][rank] = 1;
		if (suit == 'H') cards[1][rank] = 1;
		if (suit == 'C') cards[2][rank] = 1;
		if (suit == 'D') cards[3][rank] = 1;
	}
	for ( int s = 0; s < 4; s++){
		for ( int r =  1; r <= 13; r++){
			if ( cards[s][r] ) continue;
			if ( s == 0 ) suit = 'S';
			if ( s == 1 ) suit = 'H';
			if ( s == 2 ) suit = 'C';
			if ( s == 3 ) suit = 'D';
			cout << suit << " " << r << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3092
#include<stdio.h>
void bubbleSort(int *A, int N, int *res)
{
    bool flag = true;
   for(int i=0;flag && i<N;i++)
   {
       flag=false;
       for(int j=N-1;j>i;j--)
       {
           if(A[j]<A[j-1])
           {
               int temp=A[j];
               A[j]=A[j-1];
               A[j-1]=temp;
               flag =true;
               *res=*res+1;
           }
       }
   }

}
int main()
{
    int N;
    int A[110];
    int res =0;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&A[i]);
    }
    bubbleSort(A,N, &res);
    for(int k=0;k<N;k++)
    {
        if(k>0)
        {
            printf(" ");
        }
        printf("%d",A[k]);
    }
    printf("\n%d\n",res);
}


Measured memory_bytes: 2736
import java.util.*;

public class Main {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = scanner.nextInt(), M = scanner.nextInt();
        scanner.nextLine();
        int[][] qs = new int[M][2];
        for (int i = 0; i < M; i++) {
            qs[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        Arrays.sort(qs, Comparator.comparingInt(x -> x[1]));
        int ans = 1;
        int end = qs[0][1];
        for (int i = 1; i < M; i++) {
            int[] q = qs[i];
            if (q[0] < end) {
                continue;
            }
            ans++;
            end = q[1];
        }
        System.out.println(ans);
    }

}

Measured memory_bytes: 144088
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<iomanip>
using namespace std;
int main()
{
	long long int x,y;cin>>x>>y;
	int all=0;
	if(x*y>0)
	{
		all+=abs(x-y);
		if(x>y)all+=2;
		cout<<all<<endl;
		return 0;
	}
	else if(x==0)
	{
		if(y>0)cout<<y<<endl;
		else cout<<-y+1<<endl;
	}
	else if(y==0)
	{
		if(x>0)cout<<x+1<<endl;
		else cout<<-x<<endl;
	}
	else
	{
		all++;
		int sto=x;
		x=-x;
		int all1=abs(x-y);
		if(x>y)all1+=2;
		x=sto;
		y=-y;
		int all2=abs(x-y);
		if(x>y)all2+=2;
		all+=min(all1,all2);
		cout<<all<<endl;
		return 0;
	}
}


Measured memory_bytes: 384
// Author : heyuhhh
// Created Time : 2020/09/13 20:12:41
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5, MOD = 1e9 + 7;
void add(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
void run() {
    int S;
    cin >> S;
    vector<int> dp(S + 1);
    dp[0] = 1;
    for (int i = 0; i < S; i++) {
        for (int j = 3; j <= S; j++) {
            if (i + j <= S) {
                add(dp[i + j], dp[i]);
            }
        }
    }
    cout << dp[S] << '\n';
}
int main() {
#ifdef Local
    freopen("input.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,ans; 
inline int read()
{
	int num=0,flag=1;
	char c=getchar();
	for (;c<'0'||c>'9';c=getchar())
	if (c=='-') flag=-1;
	for (;c>='0'&&c<='9';c=getchar())
	num=(num<<3)+(num<<1)+c-48;
	return num*flag;
}
int main()
{
	a=read();
	b=read();
	c=read();
	d=read();
	ans=min(a,b)+min(c,d);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int n, k, dp[N], ans;

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n % 2)
			res = res * a % mod;
		a = a * a % mod;
		n /= 2;
	}

	return res;
}

int rev (int x) {
	return binpow(n, mod - 2);
}

void add (int &x, int y) {
	x += y;
	if (x >= mod)
		x -= mod;
	if (x < 0)
		x += mod;
}



main () {
	cin >> n >> k;
	for (int i = k; i > 0; --i) {
		dp[i] = binpow(k / i, n);
		for (int j = i + i; j <= k; j += i)
			add(dp[i], -dp[j]);
		add(ans, i * dp[i] % mod);
	}

	cout << ans << endl;
}



Measured memory_bytes: 4416
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}
	void run(){
		Scanner sc=new Scanner(System.in);

		while(true){
			int n=sc.nextInt();
			if(n==0) break;

			int temp[]=new int[n];
			int b[]=new int[500];
			int d=-1,sum=0;

			for(int i=0;i<n;i++){
				temp[i]=sc.nextInt();
				b[i]=temp[i];
				sum+=temp[i];
			}

			boolean flag=false;
			for(int k=1;k<500;k++){
				if((k*(k+1))/2==sum){
					flag=true;
					//System.out.println(sum+" "+k);
					d=k;
				}
			}
			if(!flag){
				System.out.println("-1");
				continue;
			}

			flag=false;
			for(int count=0;count<=10000;count++){
				if(check(b,d)){
					flag=true;
					System.out.println(count);
					break;
				}
				b=tsuminaoshi(b,d);
			}
			if(!flag) System.out.println("-1");
		}
	}
	int[] tsuminaoshi(int b[],int d){
		int count=0,last=0;

		for(int i=0; i<500; i++){
			if(b[i]>0){
				b[i]--;
				count++;
				last=i;
			}
		}

		b[last+1]=count;

		for(int i=0; i<=last+1; i++){
			if(b[i]==0){
				for(int j=i; j<=last+1; j++){
					b[j]=b[j+1];
				}
			}
		}
//		for(int i=0; i<last+1; i++){
//			System.out.print(b[i]+" ");
//		}
//		System.out.println();
		return b;
	}

	boolean check(int b[],int d){
		
		for(int i=0; i<d-1; i++){
			if(b[i]+1 != b[i+1]){
				return false;
			}
		}
		
		return true;
	}
}

Measured memory_bytes: 22376
#include <stdio.h>
int main(void)
{
	int n, x, m, min, i;

	scanf("%d %d", &n, &x);
	min = x;
	for(i=0; i<n; i++){
		scanf("%d", &m);
		x = x - m;
		if(min > m){
			min = m;
		}
	}
	n = n + x / min;
	printf("%d\n", n);
	return 0;
}


Measured memory_bytes: 128
import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

Measured memory_bytes: 34700
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int ans = 0;
for(int i = 0; i < 10; i++)for(int j = 0; j < 10; j++)for(int k = 0; k < 10; k++)for(int l = 0; l < 10; l++)if(i+j+k+l==n) ans++;
cout << ans << endl;
}
return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

constexpr ll mod=1e9+7;
vector<pair<int,int>> v[301];
ll dp[303][303]={1};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    while(m--){
        int l,r,x; cin >> l >> r >> x;
        v[r-1].push_back({l,x});
    }
    // dp[i][j]:最後に使ったindexのうち後ろを持っておく(i>j)
    // 例外1色しか使わない時, i=j=0
    // 1色使う時選び方3通り　それ以外3!=6通り
    for(int i=0;i<n;i++){ // 今i(1-indexed)番目まで埋め終わってる
        // i番目に使った奴と同じものをi+1番目で使った場合遷移なし
        // i+1番目に使わない方のindex jを固定
        // 並び順はk>i>jとなる　そのDP更新を以下で行う
        for(int j=0;j<i;j++){ 
            for(int k=0;k<i;k++){
                (dp[i][j]+=dp[max(j,k)][min(j,k)])%=mod;
            }
        }
        // 条件を満たしてるかの判定
        for(auto p:v[i]){
            for(int j=0;j<=i;j++){
                for(int k=0;k<=j;k++){
                    if(p.second+(j<p.first)+(k<p.first)-3){
                        dp[j][k]=0;
                    }
                }
            }
        }
    }
    ll res=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            (res+=6*dp[i][j])%=mod;
        }
    }
    printf("%lld\n",(res+dp[0][0]*3)%mod);
}

Measured memory_bytes: 4524
int main(void){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a == b){
        printf("a == b\n");
    }else if(a > b){
        printf("a > b\n");
    }else if(a < b){
        printf("a < b\n");
    }
    return 0;
}

Measured memory_bytes: 580
def dist(a,b):
    return ((b[0]-a[0])**2+(b[1]-a[1])**2)**(1/2)
n=int(input())
loca=[list(map(int, input().split())) for _ in range(n)]
import itertools
a=[i for i in range(n)]
sum=0
cnt=0
for i in itertools.permutations(a):
    li=list(i)
    cnt += 1
    for i in range(1,n):
        a=loca[li[i-1]]
        b=loca[li[i]]
        sum+=dist(a,b)
print(sum/cnt)

Measured memory_bytes: 9396
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
inline ll read()
{
	ll x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 1000
#define MM 2000
#define mod 1000000007
struct edge{int x,y,w;}e[MM+5];
bool cmp(const edge&a,const edge&b){return a.w<b.w;}
int f[MN+5];
int gf(int k){return f[k]?f[k]=gf(f[k]):k;}
int ans=1;
inline int pow(int x,int k){
    int sum=1;
    for(;k;k>>=1,x=1LL*x*x%mod) if(k&1) sum=1LL*sum*x%mod;
    return sum;
}
int main(){
	int n,m,i,j,s1=0,s2=1;ll s,x;
	n=read();m=read();x=read();
	for(i=1;i<=m;++i)e[i].x=read(),e[i].y=read(),e[i].w=read();
	sort(e+1,e+m+1,cmp);
	for(i=2;i<=m;++i){
		memset(f,s=0,sizeof(f));
		if(gf(e[i].x)!=gf(e[i].y))f[gf(e[i].x)]=gf(e[i].y),s+=e[i].w;
		for(j=1;j<=m;++j)if(gf(e[j].x)!=gf(e[j].y))f[gf(e[j].x)]=gf(e[j].y),s+=e[j].w;
		if(s==x)++s1;if(s>x) ans=(2*ans)%mod;
	}
	printf("%d",2LL*ans*(pow(2,s1)-1)%mod);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
using namespace std;

int main(){
ll N, total = 0, Ans = 2*powl(10, 14);cin >> N;
vector<ll> V(N);
vector<ll> A(N);

rep(i, 0, N){
    cin >> V[i];
    total += V[i];
    A[i] = total;}

rep(i, 0, N - 1){

    Ans = min(Ans, abs(2*A[i] - total));

}

cout << Ans;

}

Measured memory_bytes: 6408