akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 2e5 + 10;

int n;
double a[N], b[N], cum[N], cumk[N], ans[N];

double compute(int from, int to, int idx) {
    if (idx == from) return a[from];
    if (idx == to) return a[to];
    double ans = ((to-idx) * a[from] + (idx-from) * a[to]) / (to-from);

    double cost = 0;
    double c = 2.0*(to-idx)/(to-from);
    cost += c * (cumk[idx+1] - cumk[from+1]);
    cost -= c * from * (cum[idx+1] - cum[from+1]);

    double d = 2.0*(idx-from)/(to-from);
    cost += d * to * (cum[to] - cum[idx+1]);
    cost -= d * (cumk[to] - cumk[idx+1]);

    return ans - cost;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    pair<double,int> mx;
    forn(i,n) {
        cin >> a[i];
        mx = max(mx, {a[i],i});
    }
    forn(i,n) cin >> b[i];
    {
        int idx = mx.second;
        vector<double> na(n), nb(n);
        forn(i,n) {
            na[i] = a[(i+idx)%n];
            nb[i] = b[(i+idx)%n];
        }
        forn(i,n) {
            a[i] = na[i];
            b[i] = nb[i];
        }
    }

    a[n] = a[0];
    forn(i,n+1) {
        cum[i+1] = cum[i] + b[i];
        cumk[i+1] = cumk[i] + b[i]*i;
    }


    vi convex(1,0);
    int sz = 1;
    forsn(i,1,n) {
        double cand = compute(convex.back(), n, i);
        if (cand <= a[i]) {
            while (sz >= 2 && compute(convex[sz-2], i, convex[sz-1]) > a[convex[sz-1]]) {
                convex.pop_back();
                sz--;
            }
            convex.push_back(i);
            sz++;
        }
    }
    convex.pb(n);


    vector<double> best(n);
    forn(i,si(convex)-1){
        forsn(j,convex[i], convex[i+1]) 
            best[j] = compute(convex[i], convex[i+1], j);
    }

    double ans = 0;
    for (auto x : best) ans += x;
    cout << fixed << setprecision(12) << ans / n;
    return 0;
}


Measured memory_bytes: 12464
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(30) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 5100000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli A,B,C,D,E,F,N,M,K,L,R,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  Vec(dp,lli,200000,0);
  dp[100]=1;
  dp[101]=1;
  dp[102]=1;
  dp[103]=1;
  dp[104]=1;
  dp[105]=1;
  rep(i,0,120000){
    if(dp[i]==1){
      dp[i+100]=1;
      dp[i+101]=1;
      dp[i+102]=1;
      dp[i+103]=1;
      dp[i+104]=1;
      dp[i+105]=1;
    }
  }
  Out(dp[N]);
}

Measured memory_bytes: 1792
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <map>
#include <numeric>
#include <cassert>

using namespace std;
#define int long long
#define uint unsigned long long
constexpr int MOD = 1000000007;
constexpr int INF = 1145141919810;

#define LOADVEC(type,name,N) std::vector<type>name(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOADVEC2(type,name0,name1,N) std::vector<type>name0(N),name1(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn]; \
}

#define LOADVEC3(type,name0,name1,name2,N) std::vector<type>name0(N),name1(N),name2(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn];cin >> name2[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;


void proc();

signed main() {
	ios::sync_with_stdio(false);
	proc();
	return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/


void proc() {
	LOAD(int, A);
	LOAD(int, B);
	LOAD(int, T);
	cout << B * (T / A) << endl;
}


#endif


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String a=sc.next();
		String b=sc.next();
		int c=Integer.parseInt(a+b);
		for(int i=0;i*i<=c;i++) {
			if(i*i==c) {
				System.out.println("Yes");
				System.exit(0);
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 22612
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=nl()

ans=0

nums = dict()

for i in range(n):
  num_i = i+a[i]
  if num_i not in nums:
    nums[num_i]=0
  nums[num_i]+=1

for j in range(n):
  num_j = j-a[j]
  if num_j in nums:
    ans+=nums[num_j]

print(ans)

Measured memory_bytes: 111844
import java.util.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int items[] = new int[N];
        for (int i = 0; i < N; i ++) {
            items[i] = sc.nextInt();
        }
        double total = Arrays.stream(items).sum();
        double min = 1.0 * total / (4 * M);
        int cnt = Arrays.stream(items).filter(i -> i >= min).map(i -> 1).sum();
        if (cnt >= M) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 28496
#include <stdio.h>

int main(int argc, char const *argv[])
{
  int W, a, b;
  scanf("%d%d%d", &W, &a, &b);
  if(a+W<b) {
    printf("%d\n", b-W-a);
  } else if (b+W<a) {
    printf("%d\n", a-b-W);
  } else {
    printf("0\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	if (n==1 || n==2 || n==3 || n==5 || n==7 || n==11 || n==13 || n==15 || n==17 || n==19 || n==23 || n==29 || n==31)
	{
		cout<<1<<endl;
	}
	else if (n==4 || n==6 || n==9 || n==10 || n==14 || n==21 || n==22 || n==25 || n==26)
	{
		cout<<2<<endl;
	}
	else if (n==28 || n==30)
	{
		cout<<4<<endl;
	}
	else if (n==8 || n==12 || n==18 || n==20 || n==27)
	{
		cout<<5<<endl;
	}
	else if (n==16)
	{
		cout<<14<<endl;
	}
	else if (n==24)
	{
		cout<<15<<endl;
	}
	else
	{
		cout<<51<<endl;
	}
	return 0;
 } 

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

int main() {
	ll n, m;
	cin >> n >> m;
	if (abs(n - m) >= 2) {
		cout << 0 << endl;
		return 0;
	}
	if (n > m)swap(n, m);
	ll ans = 1;
	if (n == m) {
		ans = 2;
		for (int i = 1; i <= n; i++) {
			ans *= i;
			ans %= 1000000007;
			ans *= i;
			ans %= 1000000007;
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			ans *= i;
			ans %= 1000000007;
			ans *= i;
			ans %= 1000000007;
		}
		ans *= m;
		ans %= 1000000007;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N, M, K;
  cin >> N >> M >> K;
  if(K == 0){
    cout << 0 << endl;
    return 0;
  }
  vvll G(N+M, vll(0));
  while(K--){
    ll x, y;
    cin >> x >> y;
    y += N;
    G.at(x).push_back(y);
    G.at(y).push_back(x);
  }
  vll match(N+M, -1);
  vll flag(N+M, 0);
  function<bool(ll)> dfs = [&](ll v){
    flag[v] = 1;
    for(int i = 0; i < sz(G.at(v)); i++){
      ll next = G.at(v).at(i);
      ll u = match.at(next);
      if(u == -1 || (!flag[u] && dfs(u))){
        match.at(v) = next;
        match.at(next) = v;
        return true;
      }
    }
    return false;
  };
  ll ans = 0;
  for(int i = 0; i < N; i++){
    if(match.at(i) == -1){
      fill(ALL(flag), 0);
      if(dfs(i)) ans++;
    }
  }
  cout << ans << endl;
}


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

int main(void) {
  string N;
  cin >> N;
  cout << ((N[0] == N[1] && N[1] == N[2]) || (N[1] == N[2] && N[2] == N[3])
               ? "Yes"
               : "No")
       << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(void){
	unsigned short *A,*B;
	
	int C[VMAX+1];
	int n,i,j;
	scanf("%d",&n);
	
	A=malloc(sizeof(short)*n+1);
	B=malloc(sizeof(short)*n+1);
	
	for(i=0;i<=VMAX;i++) C[i]=0;
	
	for(i=0;i<n;i++){
		scanf("%hu",&A[i+1]);
		C[A[i+1]]++;
	}
	
	for(i=1;i<=VMAX;i++) C[i]=C[i]+C[i-1];
	
	for(j=1;j<=n;j++){
		B[C[A[j]]]=A[j];
		C[A[j]]--;
	}
	
	for(i=1;i<=n;i++){
		if(i>1)printf(" ");
		printf("%d",B[i]);
	}
	printf("\n");
	
	return 0;
}

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

void North(int Dice[]) {
	int p = Dice[0];
	Dice[0] = Dice[1];
	Dice[1] = Dice[5];
	Dice[5] = Dice[4];
	Dice[4] = p;
}

void South(int Dice[]) {
	int p = Dice[0];
	Dice[0] = Dice[4];
	Dice[4] = Dice[5];
	Dice[5] = Dice[1];
	Dice[1] = p;
}

void East(int Dice[]) {
	int p = Dice[0];
	Dice[0] = Dice[3];
	Dice[3] = Dice[5];
	Dice[5] = Dice[2];
	Dice[2] = p;
}

void West(int Dice[]) {
	int p = Dice[0];
	Dice[0] = Dice[2];
	Dice[2] = Dice[5];
	Dice[5] = Dice[3];
	Dice[3] = p;
}

void Left(int Dice[]) {
	int p = Dice[1];
	Dice[1] = Dice[2];
	Dice[2] = Dice[4];
	Dice[4] = Dice[3];
	Dice[3] = p;
}

void Right(int Dice[]) {
	int p = Dice[1];
	Dice[1] = Dice[3];
	Dice[3] = Dice[4];
	Dice[4] = Dice[2];
	Dice[2] = p;
}

bool same(int Dice1[], int Dice2[]) {
	for (int i = 0; i < 6; i++) {
		if (Dice1[i] != Dice2[i]) return false;
	}
	return true;
}

int main() {
	int Dice1[6], Dice2[6];
	bool check = false;
	for (int i = 0; i < 6; i++) {
		cin >> Dice1[i];
	}
	for (int i = 0; i < 6; i++) {
		cin >> Dice2[i];
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 4; j++) {
			if (same(Dice1, Dice2)) check = true;
			Left(Dice2);
		}
		North(Dice2);
		for (int j = 0; j < 4; j++) {
			if (same(Dice1, Dice2)) check = true;
			Left(Dice2);
		}
		East(Dice2);
	}
	if (check) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<string,int>;
using node = tuple<int, int, int>;

ll a[100010];

int main(void){
  int k;
  cin >> k;
  for(int i = 0;i < k;++i){
    cin >> a[i];
  }
  ll l = 2,u = 2;
  for(int i = k-1;i >= 0;--i){
    ll x = (l / a[i] + !(l % a[i] == 0)) * a[i];
    ll y = (u / a[i]) * a[i];
    if(!(l <= x && x <= u &&
         l <= y && y <= u)){
      puts("-1");
      return 0;
    }
    l = x;
    u = y + a[i] - 1;
  }
  cout << l << " " << u << endl;
  return 0;
}


Measured memory_bytes: 1024
Scanf.scanf "%d %d" (fun n m ->
    let link = Array.make m [] in
    for i = 0 to n - 1 do
        Scanf.scanf " %d" (fun k ->
            for j = 1 to k do
                Scanf.scanf " %d" (fun l ->
                    let l = l - 1 in
                    link.(l) <- i :: link.(l)
                )
            done
        )
    done;
    let par = Array.init n (fun i -> i) in
    let rec root x =
        if x = par.(x) then x else
            let r = root par.(x) in
            let () = par.(x) <- r in
            r
    in
    let merge a b =
        if root a <> root b then (
            par.(par.(b)) <- par.(a)
        )
    in
    Array.iter (fun l ->
        match l with
        | [] -> ()
        | hd :: tl -> List.iter (fun v -> merge hd v) tl
    ) link;
    let rec loop i =
        if i = n then "YES" else
            if root 0 = root i then loop (i + 1) else "NO"
    in
    print_endline @@ loop 0
)

Measured memory_bytes: 7168
#include<stdio.h>
char x[2097152],y[2097152];
int wz[2097152],v[2097152];
int num=0;
void add(int ps,int val,int k)
{
	if(val==0)
	{
		return;
	}
	if(num)
	{
		if(wz[num-1]==ps)
		{
			int val2=v[num-1];
			num--;
			add(ps+1,val&val2,k);
			add(ps,val^val2,k);
			return;
		}
	}
	if(k==0||val!=3)
	{
		wz[num]=ps;
		v[num]=val;
		num++;
		return;
	}
	if(num==0)
	{
		add(ps+k,3,0);
		return;
	}
	if(wz[num-1]>ps+k)
	{
		add(ps+k,3,0);
		return;
	}
	add(wz[num-1],3,k-wz[num-1]+ps);
}
int val[2097152];
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s%s",x,y);
	for(int i=0;i<n;i++)
	{
		if(x[i]=='1')
		{
			val[n-i-1]+=2;
		}
	}
	for(int i=0;i<m;i++)
	{
		if(y[i]=='1')
		{
			val[m-i-1]++;
		}
	}
	for(int i=2000005;i>=0;i--)
	{
		add(i,val[i],k);
		val[i]=0;
	}
	for(int i=0;i<num;i++)
	{
		val[wz[i]]=v[i];
	}
	bool ok=false;
	for(int i=2000005;i>=0;i--)
	{
		if(val[i]&2)
		{
			ok=true;
		}
		if(ok)
		{
			if(val[i]&2)
			{
				putchar('1');
			}
			else
			{
				putchar('0');
			}
		}
	}
	putchar('\n');
	ok=false;
	for(int i=2000005;i>=0;i--)
	{
		if(val[i]&1)
		{
			ok=true;
		}
		if(ok)
		{
			if(val[i]&1)
			{
				putchar('1');
			}
			else
			{
				putchar('0');
			}
		}
	}
	putchar('\n');
	return 0;
}

Measured memory_bytes: 24576
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
#define ll long long
#define ull unsigned ll
/*Fast I/O goes here*/
const double EPS = 1e-8;
const ll PR = 19260817;
const ll inv2 = 500000004;
const ll inv3 = 333333336;
const int N = 105;
int n, m;
char a[N][N];
int cnt[N];
int main() {
	cin>>n>>m;
	memset(cnt, 0, sizeof(cnt));
	for(int i=0; i<n; i++) cin>>a[i];
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cnt[a[i][j]-'a']++;
		}
	}
	for(int i=0; i<((n>>1)*(m>>1)); i++) {
		int j;
		for(j=0; j<26; j++) {
			if(cnt[j]>=4) {cnt[j]-=4;break;}
		}
		if(j>=26) {
			puts("No");return 0;
		}
	}
	for(int i=0; i<(((n&1)*(m>>1))+((m&1)*(n>>1))); i++) {
		int j;
		for(j=0; j<26; j++) {
			if(cnt[j]>=2) {cnt[j]-=2;break;}
		}
		if(j>=26) {
			puts("No");return 0;
		}
	}
	puts("Yes");
	return 0;
}

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

#define ll long long
#define ull unsigned long long
#define vii vector<int>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define pldld pair<long long double, long long double>
#define ff first
#define ss second
#define pb push_back
#define read freopen("alu.txt","r",stdin);
#define write freopen("vorta.txt","w",stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(NULL);
#define PI 2*acos(0.0)
#define DEBUG(x) cerr << #x << " = " << x << endl

const int MAX = 3e5 + 5, MOD = 1e9 + 7, MAXLG = log2(MAX)+1;
const ll inf = 1e18 + 5;

int arr[MAX];
int mx = 0;
void compress(int n){
    vii v;
    for(int i=0;i<n;i++) v.pb(arr[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=0;i<n;i++){
        int zipped=lower_bound(v.begin(),v.end(),arr[i])-v.begin()+1;
        arr[i]=zipped;
        mx=max(mx,zipped);
    }
}

int bit[MAX];
void update(int pos, int val){
    while(pos <= mx){
        bit[pos] = max(bit[pos], val);
        pos += (pos & (-pos));
    }
}

int get(int pos){
    int ret = 0;
    while(pos > 0){
        ret = max(ret, bit[pos]);
        pos -= (pos & (-pos));
    }
    return ret;
}

int col[MAX];
int main(){

    fastio;
    int n;
    cin>>n;
    for(int i=0; i<n; i++) cin>>arr[i];
    compress(n);

    for(int i=n-1; i>=0; i--){
        int g = get(arr[i]);
        col[i] = g + 1;
        update(arr[i], g + 1);
//        cout<<g<<" "<<col[i]<<" "<<get(arr[i])<<"\n";
    }

    int ans = 0;
    for(int i=0; i<n; i++){
//        cout<<col[i]<<" ";
        ans = max(ans, col[i]);
    }
//    cout<<"\n";
    cout<<ans<<"\n";

}


Measured memory_bytes: 1544
#include<bits/stdc++.h>
using namespace std;
int n,k;char c[5010],ans[5010],s[10010],g;
void chk(char *s){
	for(int i=0;i<n;i++)if(s[i]!=ans[i]){
		if(s[i]>ans[i])return;
		for(int j=0;j<n;j++)ans[j]=s[j];
		return;
	}
}
void solve(char *s,int t){
	char e[10010];
	for(int i=0;i<n;i++)e[i]=s[i];
	for(int i=n;i<n*2;i++)e[i]=s[n+n-i-1];
	if(t==1){
		for(int i=n;i>=0;i--)if(e[i-1]!=g||i==0){
			return chk(e+i);
		}
	}
	else{
		for(int i=0;i<=n;i++)if(e[i+n]!=g&&e[i+n-1]==g){
			solve(e+i,t-1);
			return;
		}
	}
}
int main(){
	cin>>n>>k;scanf("%s",c);
	g=*min_element(c,c+n);
	if(k>15){
		for(int i=1;i<=n;i++)putchar(g);
		return 0;
	}
	for(int i=0;i<n;i++)ans[i]=c[i];
	for(int i=0;i<n;i++)s[i]=c[i];
	for(int i=n;i<n*2;i++)s[i]=c[n+n-i-1];
	for(int i=0;i<=n;i++)chk(s+i);
	if(k>1)for(int i=0;i<=n;i++)solve(s+i,k-1);
	for(int i=0;i<n;i++)putchar(ans[i]);
	return 0;
}


Measured memory_bytes: 384
fun main(args: Array<String>) {
    val n = readLine()?.toInt() ?: return
    val coordinates = mutableListOf<List<Int>>()
    coordinates.add(listOf(0, 0, 0))
    for (i in 0 until n) {
        val input = readLine()?.split(" ")?.map { it.toInt() } ?: return
        coordinates.add(input)
    }

    val flag = canTravel(coordinates)

    if (flag) {
        println("Yes")
    } else {
        println("No")
    }
}

private fun canTravel(coordinates: MutableList<List<Int>>): Boolean {
    for (i in 1 until coordinates.size) {
        val times = coordinates[i][0] - coordinates[i - 1][0]
        val coordinateFrom = Pair(coordinates[i - 1][1], coordinates[i - 1][2])
        val coordinateTo = Pair(coordinates[i][1], coordinates[i][2])
        val flag = canMoveFromAtoBInTimes(times, coordinateFrom, coordinateTo)
        if (!flag) return flag
    }
    return true
}

private fun canMoveFromAtoBInTimes(times: Int, coordinateFrom: Pair<Int, Int>, coordinateTo: Pair<Int, Int>): Boolean {
    val disX = coordinateTo.first - coordinateFrom.first
    val disY = coordinateTo.second - coordinateFrom.second

    val distance = abs(disX) + abs(disY)

    if (distance > times) return false

    return ((times - distance) % 2 == 0)
}

private fun abs(a: Int): Int {
    return if (a < 0) -a else a
}

Measured memory_bytes: 64572
N = int(input())
import sys
graph = [dict() for _ in range(N)]

for i in range(N-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w

color = [-1] * N

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(i, col):
    color[i] = col
    for k, v in graph[i].items():
        if color[k] == -1:
            if v % 2 == 0:
                dfs(k, col)
            else:
                dfs(k, 1-col)

dfs(0, 1)

# 1 -> 0
# 2 -> 1

for c in color:
    print(c)


Measured memory_bytes: 89332
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	int k, a, b;
	cin >> k >> a >> b;
	for(int i=a;i<=b;i++){
		if(i%k == 0){
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stdio.h>
#include <math.h>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef pair<int, int> pii;

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define repm(i, a, b) for(int i = (a); i >= (b); i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える




int main(){
    int k;
    cin >> k;

    ll ans = 0;
    repp(a, 1, k) repp(b, 1, k) repp(c, 1, k){
        int gcd = __gcd(a, b);
        gcd = __gcd(gcd, c);

        ans += gcd;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,x,a;
    cin >> n >> x;
    int m = 10000,c = 0;
    rep(i,n){
        cin >> a;
        c += a;
        chmin(m,a);
    }
    PRINT((x-c)/m+n);
}


Measured memory_bytes: 256
import java.util.Scanner;

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

        int n = sc.nextInt();
        int h = sc.nextInt();
        int w = sc.nextInt();

        int hCnt = 0;
        int wCnt = 0;
        for (int i = 0; i < n; i++) {
            if (i + h <= n)
                hCnt++;
            else
                break;
        }
        for (int i = 0; i < n; i++) {
            if (i + w <= n)
                wCnt++;
            else
                break;
        }

        System.out.println(hCnt * wCnt);
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int X;
	cin >> X;

	int a = X / 100;
	int b = X % 100;
	//cout << a << " " << b << endl;
	if (a * 5 >= b) {
		cout << 1 << endl;
	}
	else {
		cout << 0 << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K,N;
  cin>>K>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  priority_queue<int> B;
  for(int i=0;i<N-1;i++){
    B.push(A.at(i+1)-A.at(i));
  }
  B.push(A.at(0)+K-A.at(N-1));
  int X;
  X=K-B.top();
  cout<<X<<endl;
}

Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;

string remove_front_zero(string n){
  for(int i = 0; i < n.size(); i++){
    if(n[i] != '0'){
      string ret;
      for(int j = i; j < n.size(); j++){
        ret.push_back(n[j]);
      }
      return ret;
    }
  }
  return "0";
}

bool dp_less(string n1, string n2){
  if(n1.size() < n2.size()){
    return true;
  }
  if(n1.size() > n2.size()){
    return false;
  }
  for(int i = 0; i < n1.size(); i++){
    if(n1[i] < n2[i]){
      return true;
    }
    if(n1[i] > n2[i]){
      return false;
    }
  }
  return false;
}

bool real_less(string x, string y){
  string n1 = remove_front_zero(x);
  string n2 = remove_front_zero(y);
  if(n1.size() < n2.size()){
    return true;
  }
  if(n1.size() > n2.size()){
    return false;
  }
  for(int i = 0; i < n1.size(); i++){
    if(n1[i] < n2[i]){
      return true;
    }
    if(n1[i] > n2[i]){
      return false;
    }
  }
  return false;
}

string grid[70];
string dp[70][70];
int main(){
  while(true){
    int W;
    int H;
    cin >> W >> H;
    if(W == 0 && H == 0){
      break;
    }
    for(int i = 0; i < H; i++){
      cin >> grid[i];
    }
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        dp[i][j] = "";
      }
    }
  

    for(int i = H - 1; i >= 0; i--){
      for(int j = W - 1; j >= 0; j--){
        if('A' <= grid[i][j] && grid[i][j] <= 'Z'){
          continue;
        }
        string max_next = "";
        if(i < H - 1 && '0' <= grid[i + 1][j] && grid[i + 1][j] <= '9'){
          max_next = dp[i + 1][j];
        }
        if(j < W - 1 && '0' <= grid[i][j + 1] && grid[i][j + 1] <= '9'){
          if(dp_less(max_next, dp[i][j + 1])){
            max_next = dp[i][j + 1];
          }
        }
        reverse(max_next.begin(), max_next.end());
        max_next.push_back(grid[i][j]);
        reverse(max_next.begin(), max_next.end());
        dp[i][j] = max_next;
      }
    }

    string ans = "0";
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(real_less(ans, dp[i][j])){
          ans = dp[i][j];
        }
      }
    }
    cout << remove_front_zero(ans) << endl;
  }
  return 0;
}


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

int main() {
    char s[4];
    for (int i = 0; i < 4; i++) cin >> s[i];
    sort(s, s + 4);
    if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n; cin>>n;
    printf("%.6f\n",n*n*n/27.0);
    return 0;
}

Measured memory_bytes: 3748
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a,b) (a > b) ? a : b
#define MIN(a,b) (a < b) ? a : b
const int inf = 1000000000; // 10^9

int main(){
   char c;scanf("%c",&c);
   if(c == 'a'||c == 'i'||c == 'u'||c == 'e'||c == 'o'){
      printf("vowel\n");
   }else{
      printf("consonant\n");
   }
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <set>
#include <map>
#define INF 1000000000
#define rep(i,n) for(int i =0;i<n;i++)
using namespace std;
typedef long long int ll;

string A = ".,!?_",B="abc",C="def",D="ghi",E="jkl",F="mno",G="pqrs",H="tuv",I="wxyz";


int main(){
    int n;
    cin >> n;
    rep(w,n){
        string S;
        cin >> S;
        string ans="";
        int i=0;
        while (i<S.length()) {
            char ch = S[i];
            if(ch=='0'){
                i++;
                continue;
            }
            int t=0;
            while (S[i]!='0' and i<S.length()){
                i++;
                t++;
            }
            if(ch=='1'){
                        int flag = (t-1)%5;
                        if(flag == 4){
                            ans += " ";
                        }else{
                            ans += A[flag];
                        }
                    }
            if(ch=='2'){
                int flag = (t-1)%3;
                ans += B[flag];
            }
            if(ch=='3'){
                int flag = (t-1)%3;
                ans += C[flag];
            }
            if(ch=='4'){
                int flag = (t-1)%3;
                ans += D[flag];
            }
            if(ch=='5'){
                int flag = (t-1)%3;
                ans += E[flag];
            }
            if(ch=='6'){
                int flag = (t-1)%3;
                ans += F[flag];
            }
            if(ch=='7'){
                int flag = (t-1)%4;
                ans += G[flag];
            }
            if(ch=='8'){
                int flag = (t-1)%3;
                ans += H[flag];
            }
            if(ch=='9'){
                int flag = (t-1)%4;
                ans += I[flag];
            }
            i++;
        }
        cout << ans << endl;
    }
}

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

namespace ABC147A
{
    class Program
    {
        static void Main(string[] args)
        {
            int A, B, C, D;
             var word = Console.ReadLine().Split(' ');

            A = int.Parse(word[0]);
            B = int.Parse(word[1]);
            C = int.Parse(word[2]);
            D = 0;
            D = A + B + C;
            if (D >= 22)
            {
                Console.Write("bust");
            }
            else if (D <= 21)
            {
                Console.Write("win");
            }

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {//
        n:usize,
        mut a:[i128;n],
    }
    let mut cumsum = vec![0i128; n + 1];
    for i in 0..n {
        cumsum[i + 1] = cumsum[i] + a[i];
        cumsum[i + 1] %= MOD;
    }
    let mut ans = 0i128;
    for i in 0..n - 1 {
        ans += a[i] * (cumsum[n] - cumsum[i + 1] + MOD) % MOD;
        ans %= MOD;
    }
    println!("{}", ans);
}
const MOD: i128 = 1000000007;


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

	int Abs (int a){
		if(a<0){
			a=-a;
		}
		return a;
	}

int main (){
	int A,B,C;cin>>A>>B>>C;
	int a=Abs(A-B);
	int b=Abs(B-C);
	int c=Abs(C-A);
	int max=a;
	if(max<b)max=b;
	if(max<c)max=c;
	cout<<a+b+c-max<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

bool check(string &s) {
    int n = s.size();
    string r = s;
    reverse(s.begin(), s.end());
    for (int i=0; i<n; i++) {
        if (r[i] != s[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    int n = s.size();
    string t = s.substr(0, (n-1)/2);
    string u = s.substr((n+3) / 2 - 1);
    cout << (check(s) && check(t) && check(u) ? "Yes" : "No") << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

constexpr lint inf = 1e18;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m, l; cin >> n >> m >> l;
  VV<lint> g(n, V<lint>(n, inf));
  for (int v = 0; v < n; ++v) {
    g[v][v] = 0;
  }
  while (m--) {
    int u, v, w; cin >> u >> v >> w, --u, --v;
    if (w > l) continue;
    g[u][v] = g[v][u] = w;
  }
  VV<> res(n, V<>(n));
  for (int s = 0; s < n; ++s) {
    V<lint> d(n + 1, inf);
    d[s] = 0;
    V<bool> vis(n);
    while (true) {
      int v = n;
      for (int u = 0; u < n; ++u) if (not vis[u] and d[u] < d[v]) {
        v = u;
      }
      if (v == n) break;
      if (d[v] > l) {
        for (int u = 0; u < n; ++u) if (d[u] > l) {
          ++res[s][u];
          d[u] = inf;
        }
        V<bool> b(n);
        for (int u = 0; u < n; ++u) if (d[u] and d[u] <= l) {
          d[u] = 0;
          b[u] = true;
        }
        for (int u = 0; u < n; ++u) if (b[u]) {
          for (int w = 0; w < n; ++w) {
            d[w] = min(d[w], g[u][w]);
          }
        }
      } else {
        vis[v] = true;
        for (int u = 0; u < n; ++u) {
          d[u] = min(d[u], d[v] + g[v][u]);
        }
      }
    }
  }
  for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  }
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (g[i][j] == inf) {
    res[i][j] = -1;
  }
  int q; cin >> q;
  while (q--) {
    int s, t; cin >> s >> t, --s, --t;
    cout << res[s][t] << '\n';
  }
}


Measured memory_bytes: 1664
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define pof pop_front()
#define pob pop_back()
#define Rep(i,n) for(li i=0,nn=(li)(n);i!=nn;++i)
#define Rep1(i,n) for(li i=1,nn=(li)(n)+1;i!=nn;++i)
#define Size(v) (li)(v.size())
#define SortA(v) sort(v.begin(),v.end())
#define SortD(v) sort(v.rbegin(),v.rend())
#define All(a) (a).begin(),(a).end()
#define Input(a) for(li ii=0,nn=(li)(a.size());ii!=nn;++ii){cin>>(a).at(ii);}
#define Input2(a,b) for(li ii=0,nn=(li)(a.size());ii!=nn;++ii){cin>>(a).at(ii)>>(b).at(ii);}
#define mp make_pair
using li = int64_t;
using intl = int64_t;
using vi = vec<li>;
using vb = vec<bool>;
using vvi = vec<vi>;
using qi = deque<li>;
using pi = pair<li, li>;
using vpi = vec<pi>;
using si = set<li>;
using vsi = vec<si>;
using mii = map<li, li>;
using vmii = vec<mii>;
vec<li> dx = {0, 1, 0, -1, 1, 1, -1, -1};
vec<li> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr li INF = LLONG_MAX;

void Yes(li b) {
	if (b)cout << "Yes";


	else cout << "No";
}
void yes(li b) {
	if (b)cout << "yes";
	else cout << "no";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cout.precision(16);

	string S,T;
	cin >>S>>T;

	li minans = INF;
	Rep(i,Size(S)-Size(T)+1){
		li cnt=0;
		Rep(j,Size(T)){
			if(S[i+j]!=T[j])cnt++;
		}

	minans = min(minans,cnt);
	}

	cout <<minans;

}

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

int main(){
	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n);
	int c[10010] = {0};
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		c[a[i]]++;
	}
	for(int i = 1; i < 10010; i++)
		c[i] += c[i-1];
	for(int i = n-1; i >= 0; i--) {
		b[c[a[i]]-1] = a[i];
		c[a[i]]--;
	}
	for(int i = 0; i < n - 1; i++)
		printf("%d ", b[i]);
	printf("%d\n", b[n-1]);
}



Measured memory_bytes: 18340
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

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



signed main() {
	string A;
	cin >> A;

	int len = A.length();

	int ans = 0;
	for (int i = 1;i < len;i++) {
		ans += i;
	}


	int alpha[26];
	REP(i, 26) alpha[i] = 0;
	REP(i,len){
		for (char c = 'a';c <= 'z';c++) {
			if (A[i] == c) alpha[c - 'a']++;
		}
	}

	REP(i, 26) {
		int a = alpha[i];
		ans = ans - a * (a - 1) / 2;
	}

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

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int vis[30];
char word[256];
int main()
{
	cin>>word;
	int len = strlen(word);
	string ans = "";
	for(int i=0;i<len;i++)
	{
		ans += word[i];
		vis[word[i]-'a'] = 1;
	 } 
	
	for(int i=0;i<26;i++)
	{
		if(!vis[i])
		{
			ans += (char)(i+'a');
			break;
		}
	}
	if(ans!=word)
	cout<<ans<<endl;
	else
	{
		string tmp = "";
		for(int i=0;i<len;i++)
		{
			tmp += word[i];
		}
		if(next_permutation(word,word+len))
		{
			string ans = "";
			for(int i=0;i<len;i++)
			{
				if(word[i]>tmp[i])
				{
					ans += word[i];
					break; 
				}
				ans += word[i]; 
			}
			cout<<ans<<endl;
		}
		else
		{
			cout<<-1<<endl;
		}
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;

int main(){
  int N;
  cin>>N;
  vector<int> A(N),B(N),C(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  for(int i=0;i<N;i++){
    cin>>B.at(i);
  }
  for(int i=0;i<N;i++){
    cin>>C.at(i);
  }

  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  sort(C.begin(),C.end());

  ll ans=0;
  for(int i=0;i<N;i++){
    int x=B.at(i);
    ll n=lower_bound(A.begin(),A.end(),x)-A.begin();
    ll m=upper_bound(C.begin(),C.end(),x)-C.begin();
    ans+=n*(N-m);
  }
  cout<<ans<<endl;
}


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

int factrial(int n){
    int x = 1;
    for(int i = 1; i <= n; i++){
        x *= i;
    }
    return x;
}

int count_min(vector<int> set, int num, int N){
    int x = 0;
    for(int i = 0; i < N; i++){
        if(set.at(i) != 0 && set.at(i) < num){
            x++;
        }
    }
    return x;
}

int dic_num(int N, vector<int> P){
    int num = 0;
    vector<int> set(N);
    for(int i = 0; i < N; i++){
        set.at(i) = i+1;
    }
    for(int i = 0; i < N; i++){
        num += count_min(set, P.at(i), N)*factrial(N-i-1);
        set.at(P.at(i)-1) = 0;
    }
    return num+1;
}

int main() {
    int N;
    //配列の初期化
    cin >> N;
    vector<int> P(N);
    vector<int> Q(N);

    for(int i = 0; i < N; i++){
        cin >> P.at(i);
    }
    for(int i = 0; i < N; i++){
        cin >> Q.at(i);
    }

    int P_num = dic_num(N, P);
    int Q_num = dic_num(N, Q);

    if(P_num > Q_num){
        cout << P_num - Q_num << endl;
    }
    else{
        cout << Q_num - P_num << endl;
    }


    return 0;
}

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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i=0;i<(n);i++)
#define rep2(i, m, n) for(int i=m;i<(n);i++)
#define rrep(i, n, m) for(int i=n;i>=(m);i--)
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll MOD = 1000000007;
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N, M;
    cin >> N >> M;
    vector<tuple<int, int, int>> items;
    for (int i = 0; i < M; ++i) {
        int p, y;
        cin >> p >> y;
        items.push_back(make_tuple(p, y, i));
    }
    sort(items.begin(), items.end());
    unordered_map<int, string> ans;
    int ken = -1;
    int cnt = 1;
    for (auto item : items) {
        int p = get<0>(item);
        int i = get<2>(item);
        if (p != ken) {
            cnt = 1;
            ken = p;
        } else {
            cnt++;
        }
        ostringstream s1, s2;
        s1 << setw(6) << setfill('0') << p;
        s2 << setw(6) << setfill(('0')) << cnt;
        ans[i] = s1.str() + s2.str();
    }
    for (int i = 0; i < M; ++i) {
        cout << ans[i] << endl;
    }

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}


Measured memory_bytes: 11508
import math
from collections import defaultdict

n, m = map(int, input().split())

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

pr = prime_factors(m)
di = {}
di = defaultdict(int)
for i in pr:
    while m % i == 0:
        m = m // i
        di[i] += 1

"""def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))"""
mod = 10 ** 9 + 7
MAX_N = 10 ** 5 + 100
factorial = [1] * MAX_N
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 階乗を用意
calc_factorial()

ans = 1

for i in di:
    ans = ans * comb(di[i] + n - 1, di[i]) % mod
print(ans)

Measured memory_bytes: 7284
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int k;cin>>k;
  int a,b;cin>>a>>b;
  int m=(a-1)/k+1;
  m*=k;
  if(m<=b)
    cout<<"OK"<<endl;
   else
     cout<<"NG"<<endl;
  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
#include<string.h>
#define N 1001
 char X[N], Y[N];
void LCS(void){
  int c[N][N], m, n, i, j;
  m = strlen(X+1);
  n = strlen(Y+1);
  for(i = 1; i <= m; i++) c[i][0] = 0;
  for(j = 0; j <= n; j++) c[0][j] = 0;
  for(i = 1; i <= m; i++){
    for(j = 1; j <= n; j++) {
      if(X[i] == Y[j]) c[i][j] = c[i-1][j-1] + 1;
      else if(c[i-1][j] >= c[i][j-1]) c[i][j] = c[i-1][j];
      else c[i][j] = c[i][j-1];
    }
  }
  printf("%d\n", c[m][n]);
}

int main(){
  int n, i;
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%s %s", X+1, Y+1);
    LCS();
  }
  return 0;
}

Measured memory_bytes: 4520
import java.util.Scanner;

public class Main
{
	static int selectionSort(int A[], int n)
	{
		int ret = 0;
		for (int i = 0; i < n; i++)
		{
			int minj = i;
			for (int j = i; j < n; j++)
			{
				if(A[j] < A[minj])
				{
					minj = j;
				}
			}
			if(minj != i)
			{
				int temp = A[i];
				A[i] = A[minj];
				A[minj] = temp;
				++ret;
			}
		}
		return ret;
	}
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int A[] = new int[n];
		for (int i = 0; i < n; i++)
		{
			A[i] = sc.nextInt();
		}
		int ans = selectionSort(A, n);
		for (int i = 0; i < n; i++)
		{
			System.out.print(A[i]);
			if(i < n - 1)
			{
				System.out.print(" ");
			}
		}
		System.out.println("\n" + ans);
		sc.close();
	}
}


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

int main(){
    double a;
    while(cin>>a){
        double S=a;
        for(int i=0;i<9;i++){
            a=((i&1)?a/3:a*2);
            S+=a;
        }
        cout<<setprecision(8)<<S<<endl;
    }

    return 0;
}

Measured memory_bytes: 1276
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Char
import Data.Int
import Data.Foldable
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B

solve :: Int -> Int
solve !n = 180 * n - 360

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  print $ solve n


Measured memory_bytes: 380
#include<iostream>
#include<algorithm>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int n;
int a[21];

int f(int i,int sum1,int sum2){
	if(i==n)return abs(sum1-sum2);
	return min(f(i+1,sum1+a[i],sum2),f(i+1,sum1,sum2+a[i]));
}

int main(){
	while(cin>>n,n){
		rep(i,n)cin>>a[i];
		cout<<f(0,0,0)<<endl;
	}
	return 0;
}

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

using namespace std;

const double pi=3.14159265358979323946;
int main()
{
//    freopen("int.txt","r",stdin);

    double a;
    while(cin>>a)
    {
        double s=a*a*pi;
        double c=(double)2*a*pi;
        printf("%.6lf ",s);
        printf("%.6lf\n",c);
    }
}



Measured memory_bytes: 3200
n = int(input())
dat = list(map(int,input().split()))

minAbs = 10**10 

s = 0
cntminus = 0
for d in dat:
    if abs(d)<minAbs:
        minAbs = abs(d)
    if d<0:
        cntminus+=1
    s+=abs(d)
if cntminus%2:
    s-=minAbs*2

print(s)


Measured memory_bytes: 14332
from sys import stdin
input = stdin.readline

N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]

ans = -1

for i in range(2 ** N):
    A = [0] * M
    buy = 0
    for j in range(N):
        if (i >> j) & 1:
            buy += ca[j][0]
            for k in range(1, M + 1):
                A[k - 1] += ca[j][k]

    for i in range(M):
        if A[i] < X:
            break

        if i == M - 1:
            if ans == -1:
                ans = buy
            else:
                ans = min(ans, buy)

print(ans)


Measured memory_bytes: 68744
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static boolean judge(int[][] mat , int A , int B){
		int H = mat.length;
		int W = mat[0].length;
		for(int i = 0 ; i < mat.length ; ++i){
			int S1 = 0;
			for(int j = 0 ; j < mat[0].length ; ++j){
				S1 += mat[i][j];
			}
			if(S1 == A || S1 == W - A){				
			}else{
				return false;
			}
		}
		for(int i = 0; i < mat[0].length ; ++i){
			int S2 = 0;
			for(int j = 0 ; j < mat.length ; ++j){
				S2 += mat[j][i];
			}
			if(S2 == B || S2 == H - B){
				
			}else{
				return false;
			}
		}
		return true;
	}
	static boolean next(int[][] mat){
		for(int h = 0 ; h < mat.length ; ++h){
			for(int w = 0 ; w < mat[0].length ; ++w){
				if(mat[h][w] == 0){
					mat[h][w] = 1;
					return true;
				}else{
					mat[h][w] = 0;
				}
			}
		}
		return false;
	}
	static void print(int[][] mat){
		for(int i = 0 ; i < mat.length ; ++i){
			StringBuilder sb = new StringBuilder();

			for(int j = 0 ; j < mat[i].length ; ++j){
				sb.append(mat[i][j]);
			}
			System.out.println(sb);
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int A = sc.nextInt(); 
		int B = sc.nextInt();
		int mat[][] = new int[H][W];
		for(int b = 0 ; b < B ; ++b){
			for(int a = 0 ; a < A ; ++a){
				mat[b][a] = 0;
			}
			for(int a = A ; a < W ; ++a){
				mat[b][a] = 1;
			}
		}
		for(int b = B ; b < H ; ++b){
			for(int a = 0 ; a < A ; ++a){
				mat[b][a] = 1;
			}
			for(int a = A ; a < W ; ++a){
				mat[b][a] = 0;
			}			
		}
		if(judge(mat, A, B)){
			print(mat);
		}else{
			System.out.println("No");
		}
		/*
		do{
			if(judge(mat, A, B)){
				System.out.println(Arrays.deepToString(mat));
				break;
			}
//			System.out.println(Arrays.deepToString(mat));
		}while(next(mat));
		*/
		sc.close();
	}
}


Measured memory_bytes: 33988
#include <stdio.h>
#include <stdlib.h>
int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        printf("node %d: key = %d, ", i, a[i]);
        if(i/2 >= 1){
            printf("parent key = %d, ", a[i/2]);
        }
        if(i*2 <= n){
            printf("left key = %d, ", a[2*i]);
            if(i*2+1 <= n){
                printf("right key = %d, ", a[2*i+1]);
            }
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 2732