akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int [] a=new int[5];
		for(int i=0; i<a.length; i++){
			a[i]=sc.nextInt();
		}
		Arrays.sort(a);
		for(int i=a.length-1; i>0; i--){
			System.out.printf("%d ",a[i]);
		}
		System.out.println(a[0]);


		}

}

Measured memory_bytes: 26176
N = input()
if N == "SUN":
  print(7)
if N == "MON":
  print(6)
if N == "TUE":
  print(5)
if N == "WED":
  print(4)
if N == "THU":
  print(3)
if N == "FRI":
  print(2)
if N == "SAT":
  print(1)

Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[10001];

	int i, j;
	int jcnt, icnt;


	while (scanf("%s", str) != EOF){

	
	jcnt = 0;

	for (i = 0; i < strlen(str) - 2; i++){

		if (str[i] == 'J' && str[i + 1] == 'O' && str[i + 2] == 'I'){
			jcnt++;
		}
	}

	icnt = 0;
	for (i = 0; i < strlen(str) - 2; i++){
		if (str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I'){
			icnt++;
		}
	}

	

		printf("%d\n", jcnt);
		printf("%d\n", icnt);

	}
	return (0);
}
		

		

Measured memory_bytes: 552
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}


int main(){
  
  string s;
  cin>>s;
  int ans = 0;
  REP(i,6){
    if(s[i] == '1'){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0; 
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r; cin>>r;
    if (r<1200){
        cout<<"ABC\n";
    }else if(r<2800){
        cout<<"ARC\n";
    }else{
        cout<<"AGC\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a=0;
  int W,H,x,y,
  r=0;
  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
  if(x-r>=0&&x+r<=W){
    if(y-r>=0&&y+r<=H){
      a=1;
    }
  }
  else{
    a=0;
  }
  if(a==1){
    printf("Yes\n");
  }
  else if(a==0){
    printf("No\n");
  }
  return 0;
}

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

public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int a = Integer.parseInt(s[0]);
		int b = Integer.parseInt(s[1]);
		int menseki = a*b;
		int syu = (a+b)*2;
		System.out.println(menseki+" "+syu);
	}

}

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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;
    vector<ll> yaku1, yaku2;
    ll ulim = sqrt(N);
    for(ll i = 1; i <= ulim; i++){
        if(N%i == 0){
            yaku1.push_back(i);
            yaku1.push_back(N/i);
        }
    }
    N--;
    for(ll i = 1; i <= ulim; i++){
        if(N%i == 0){
            yaku2.push_back(i);
            yaku2.push_back(N/i);
        }
    }
    N++;
    sort(yaku1.begin(), yaku1.end());
    sort(yaku2.begin(), yaku2.end());
    set<ll> ans;
    for(int i = 1; i < yaku1.size(); i++){
        ll k = yaku1[i];
        ll val = N;
        while(val % k == 0) val/=k;
        if(val % k == 1) ans.insert(yaku1[i]);
    }
    for(int i = 1; i < yaku2.size(); i++){
        if(yaku2[i] > 1) ans.insert(yaku2[i]);
    }
    cout << ans.size() << endl; 
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(void)
{
 int h,m;
 unsigned long s;

 scanf("%d",&s);

 h = s / 3600;
 s = s - h*3600;
 m = s / 60;
 s = s - m*60;

 printf("%d:%d:%d\n",h,m,s);

 return 0;
}


Measured memory_bytes: 2112
/*
    ____        __
   / __ \____  / /_  ____ _____ ___
  / /_/ / __ \/ __ \/ __ `/ __ `__ \
 / _, _/ /_/ / / / / /_/ / / / / / /
/_/ |_|\____/_/ /_/\__,_/_/ /_/ /_/
*/
#include<bits/stdc++.h>

typedef long long ll ;

#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define vpii vector<pair<int , int>>
#define i_n   int i = 0 ; i< n ; i++
#define cn  int n ; cin>>n
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cina int a[n] ; for(int i = 0 ; i < n ; i++) cin>>a[i]
#define pb push_back
#define SZ(x) ll(x.size())

using namespace std;
const int maxn = 1000*100+5 ;

int main()
{
	migmig ;
	int n , ans = 0 , m ; 
	cin>>n ; 
	m = n ; 
	while(n > 0)
	{
		ans += n%10 ; 
		n /= 10 ; 
	}
//	cout<<ans<<endl ; 
	if(m % ans == 0) cout<<"Yes" ; 
	else cout<<"No" ; 
}
//////
////////
///////////



Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N, A, B = map(int, input().split())

    ans = 0
    n = N // (A + B)
    ans += n * A

    N -= n * (A + B)
    ans += min(A, N)

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

struct UnionFind
{
	vector<int> par;
	UnionFind(int n) :par(n, -1) {}
	int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
	void unite(int x, int y)
	{
		x = find(x); y = find(y);
		if (x == y) return;
		if (par[y] < par[x]) swap(x, y);
		if (par[x] == par[y]) par[x]--;
		par[y] = x;
		if (find(x) != find(y)) par[find(y)] = x;
	}
	int count()
	{
		int cnt = 0;
		REP(i, par.size()) if (par[i] < 0) cnt++;
		return cnt;
	}
	bool same(int x, int y)
	{
		return find(x) == find(y);
	}
};


int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, h, w; cin >> n >> h >> w;
	vector<vi> hor(h), ver(w);
	UnionFind uf(n);
	int edge = 0;
	REP(i, n)
	{
		int a, b; cin >> a >> b;
		a--; b--;
		if (a == 0 || b == 0 || a == h - 1 || b == w - 1) edge = 1;
		hor[a].push_back(i);
		ver[b].push_back(i);
	}
	for (auto v : hor)
	{
		REP(i, v.size() - 1)
		{
			uf.unite(v[i], v[i + 1]);
		}
	}
	for (auto v : ver)
	{
		REP(i, v.size() - 1)
		{
			uf.unite(v[i], v[i + 1]);
		}
	}
	int cnt = 0;
	REP(i, n)
	{
		if (uf.par[i] >= 0) cnt++;
	}
	if (uf.count() == 1) cout << cnt << endl;
	else cout << cnt + uf.count() + (uf.count() - 1) - edge << endl;
	return 0;
}

Measured memory_bytes: 9740
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]
ab = sorted(ab, key=lambda x:(x[1], x[0]))

t = 0
for i in range(n):
    t += ab[i][0]
    if t > ab[i][1]:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 119972
N = int(input())
A = list(map(int, input().split()))
ans = 0
_a = A[0]
for a in A[1:]:
    tmp = 0
    #print(a, _a, _a - a)
    if a - _a < 0:
        tmp = _a - a
    ans += tmp
    _a = a + tmp
print(ans)

Measured memory_bytes: 32288
#include <bits/stdc++.h>
using namespace std;
 
# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;
 
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
 
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
 
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}
 
 
const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
 
void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}
 
void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}
 
// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}
 
 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};
 
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}
 
 
int main() {
    ll x,y;
    cin >> x >> y;
 
    if(x==y){
        pl(0)
    } else if(abs(x)==abs(y)){
        pl(1)
    } else if(x*y>=0 && y > x){
        pl(y - x)
    } else if(x*y>0  && x > y){
        pl(x - y + 2)
    } else if(x*y==0 && x > y){
        pl(x - y + 1)        
    } else {
        pl(abs(abs(x)-abs(y))+1)
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n, m;
const int N = 100000+10;
int x[N], y[N];

int main(){
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 1; i <= n; i++)scanf("%d", &x[i]);
        for(int i = 1; i <= m; i++)scanf("%d", &y[i]);
        sort(x+1, x+n+1);
        sort(y+1, y+m+1);
        
        int tmpx = 0, tmpy = 0;
        ll ans = 0;
        int cnt = n+m, px = 1, py = 1;
        while(cnt--){
            if(px > n)
            {
                ans += (ll)(n+1-tmpx) * (ll)y[py];
                py++;
                tmpy++;
            }
            else if(py > m)
            {
                ans += (ll)(m+1-tmpy) * (ll)x[px];
                px++;
                tmpx++;
            }
            else if(x[px] <= y[py])
            {
                ans += (ll)(m+1-tmpy) * (ll)x[px];
                px++;
                tmpx++;
            }
            else 
            {
                ans += (ll)(n+1-tmpx) * (ll)y[py];
                py++;
                tmpy++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <string.h>
int main(void)
{
    int N,R;
    scanf("%d %d",&N,&R);
  int count=0;
    while( N>0){
       N/=R;
       count++;


    }
    printf("%d",count);

    return EXIT_SUCCESS;
}



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

int main(){
  string a,b;
  cin >> a >> b;
  vector<set<int>>alf(26),alf2(26);
  for(int i=0,l=a.size();i<l;i++){
    alf.at(b.at(i)-'a').insert(a.at(i)-'a');
    alf2.at(a.at(i)-'a').insert(b.at(i)-'a');
  }
  bool ans=true;
  for(int i=0;i<26;i++)if(alf.at(i).size()>1||alf2.at(i).size()>1)ans=false;
  cout << (ans?"Yes":"No") << endl;
  return 0;
}

Measured memory_bytes: 3900
#include<stdio.h>
#include <sstream>
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
#define BUF_SIZE 1024
#define ARRAY_SIZE 100
 
int main(){
 
    char buf[BUF_SIZE] = {0};
    int n = atoi(fgets(buf,BUF_SIZE,stdin));
 
    int array[ARRAY_SIZE] = {0};
 
    for(int i = 0; i < n; i++){
        cin >> array[i];
    }
 
    for(int k = 0;k < n; k++){
        if(k != n-1){
            printf("%d ",array[k]);
        }else{
            printf("%d\n",array[k]);
        }
    }
 
    int v = 0;
    int j = 0;
    for(int i = 1; i < n; i++){
        v = array[i];
        j = i-1;
        while(j >= 0 && array[j] > v){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = v;
        for(int k = 0;k < n; k++){
            if(k != n-1){
                printf("%d ",array[k]);
            }else{
                printf("%d\n",array[k]);
            }
        }
    }
 
}


Measured memory_bytes: 3172
n = gets.to_i
a = gets.split.map(&:to_i)

l = Array.new(n + 2)
r = Array.new(n + 2)

l[0] = 0
1.upto(n - 1) do |i|
  l[i] = l[i - 1].gcd(a[i - 1])
end

r[n + 1] = 0
n.downto(2) do |i|
  r[i] = r[i + 1].gcd(a[i - 1])
end

ans = 0
n.times do |i|
  gcd = l[i].gcd(r[i + 2])
  ans = gcd if ans < gcd
end
puts ans

Measured memory_bytes: 10124
#include<iostream>
#include<vector>

int main()
{
  int N, K;
  std::cin >> N >> K;
  std::vector<int> h(N);
  for(size_t i= 0; i< N; i++)
  {
    std::cin>>h[i];    
  }
  int count = 0;
  for(size_t i= 0; i< N; i++)
  {
    if(h[i]>=K)
    {
      count++;
    }
  }
  std::cout << count << std::endl;
  return 0;
}

Measured memory_bytes: 640
import java.util.*;



class Main
    {
        public static void main(String args[]) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int a[] = new int[n];
            int b[] = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                b[a[i] - 1] = i + 1;
            }

            for(int i = 0; i < n; i++) System.out.print(b[i] + " ");
            System.out.println();


        }
    }

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n

typedef long long ll;

typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<string> vs;

typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

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

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	string s;
	ll ans=INF;
	cin >> s;
	for(char c='a';c<='z';c++){
		vll v;
		ll cnt=0;
		rep(i,SIZE(s)){
			if(s[i]==c){
				if(cnt!=0) v.pb(cnt);
				cnt=0;
			}
			else{
				cnt++;
				if(i==SIZE(s)-1) v.pb(cnt);
			}
		}
		if(SIZE(v)==0) ans=0;
		else{
			ll tmp=maxvec(v);
			chmin(ans,tmp);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

typedef struct {
	int par;
	int heit = 1;
}node_t;
vector<node_t> node;

int ans;
int root(int a) {
	if (node[a].par == 0) return a;
	return root(node[a].par);
}

void unite(int a, int b) {
	int a_rt = root(a), b_rt = root(b);
	if (a_rt == b_rt) return;
	
	int up, low;
	if (node[a_rt].heit >= node[b_rt].heit) up = a_rt, low = b_rt;
	else up = b_rt, low = a_rt;

	node[low].par = up;
	node[up].heit = max(node[up].heit, node[low].heit + 1);
	ans--;
}

int main(void) {
	int N, M;
	cin >> N >> M;

	node = vector<node_t>(N + 1);
	ans = N;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		unite(a, b);
	}

	cout << ans << endl;

}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
long long a[100009];
main(){
   int n;
   cin >> n;
   for(int k = 2; k <= 1000; k++){
        if(n == k* (k - 1) / 2){
            cout << "Yes\n" << k << endl;
            int cnt = 0;
            vector<vector<int> > v(k);
            for(int i = 0; i < k; i++){
                for(int j = i + 1; j < k; j++){
                    v[i].push_back(++cnt);
                    v[j].push_back(cnt);
                }
            }
            for(int i = 0; i < k; i++){
                cout<<v[i].size()<<" ";
                for(int j : v[i])
                    cout<<j<<" ";
                cout<<endl;
            }
            return 0;
        }
   }
   cout << "No"<<endl;
   return 0;
}


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

int main(void) {
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n - 2; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') ans++;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

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

    int N;
    cin >> N;
    vi a(N), b(N), A(N), B(N);
    rep(i, N)cin >> a[i];
    rep(i, N)cin >> b[i];

    int ans = 0;

    for (int i = 0; i < 29; ++i) {
        rep(j, N) {
            A[j] = a[j] % (1 << (i + 1));
            B[j] = b[j] % (1 << (i + 1));
        }
        sort(all(A));
        sort(all(B));
        int l = 0, r = 0, L = 0, R = 0;
        
        int bit = 0;
        for (int j = N - 1; j >= 0; --j) {
            while (l < N && A[j] + B[l] < (1 << i))l++;
            while (r < N && A[j] + B[r] < 2*(1 << i))r++;
            while (L < N && A[j] + B[L] < 3*(1 << i))L++;
            bit ^= (r - l + N - L) & 1;
        }
        if (bit)ans |= 1 << i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3584
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
l =[a,b,c,d,e]
count = 0
for i in range(5) :
    for j in range(i + 1) :
        if abs(l[i] - l[j]) > k :
            count = 1

if count == 0 :
    print("Yay!")
else :
    print(":(")


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

const int N = 200005;

int n;
int a[N], b[N];

int solve() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &a[i], &b[i]);
  }

  sort(a, a + n);
  sort(b, b + n);

  if (n & 1) {
    printf("%d\n", b[n/2] - a[n/2] + 1);
  } else {
    printf("%d\n", (b[n/2-1] + b[n/2]) - (a[n/2-1] + a[n/2]) + 1);
  }
  return 0;
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  for (int tc = 0; tc < t; ++tc) {
    // printf("Case #%d: ", tc+1);
    solve();
  }
  return 0;
}


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

int main() {
  int a, b, c; cin >> a >> b >> c;
  if (a == b && b == c) {
    cout << "No";
  }
  else if(a == b) {
    if (a != c) cout << "Yes";
    else cout << "No";
  }
  else if(b == c) {
    if (b != a) cout << "Yes";
    else cout << "No";
  }
  else if(c == a) {
    if (c != b) cout << "Yes";
    else cout << "No";
  }
  else cout << "No";
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if l[i] + l[j] > l[k] and l[i] != l[j] and l[j] != l[k] and l[k] != l[i]:
                ans += 1
print(ans)

Measured memory_bytes: 9136
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 

vector <string> v;
void cal(int r,int c,int k,int &test,vector <int> &v2,int cur);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r=nxt(),c=nxt(),k=nxt();
    v.resize(r);
    for(int i=0;i<r;i++)
        cin>>v[i];

    int test=r+c-2;
    vector <int> v2;
    cal(r,c,k,test,v2,0);
    cout<<test<<endl;

    return 0;   
}

void cal(int r,int c3,int k,int &test,vector <int> &v2,int cur)
{
    if(cur<r)
    {
        int count=v2.size();
        int n=v2.size();
        vector <int> c;
        c.resize(n+1,0);
        bool f=0;
        for(int i=0;i<c3;i++)
        {
           bool flag=0;
            int x=0;
            vector <int> c2;
            c2.resize(n+1,0);
            for(int j=0;j<=n-1;j++)
            {
                while(x<=v2[j])
                {
                    if(v[x][i]=='1'){
                        c[j]++;
                        c2[j]++;
                        if(c[j]>k)
                            flag=1;
                        if(c2[j]>k)
                            f=1;
                    }
                    x++;
                }
            }
            while(x<r)
            {
                if(v[x][i]=='1'){
                    c[n]++;
                    c2[n]++;
                    if(c[n]>k)
                        flag=1;
                    if(c2[n]>k)
                        f=1;
                }
                x++;
            }
            if(flag)
            {
                count++;
                c=c2;
            }

        }

        if(!f&&count<test)
            test=count;

        for(int i=cur;i<=r-2;i++)
        {
            v2.push_back(i);
            cal(r,c3,k,test,v2,i+1);
            v2.pop_back();
        }
    }
}


 
 


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

int main() {
	char C, X[4] = { 'A', 'C', 'G', 'T' };
	cin >> C;
	for (int i = 0; i < 4; i++) {
		if (C == X[i]) cout << X[3 - i];
	}
}

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

int main() {
	unsigned long long N;
	cin >> N;
	vector<unsigned long long> A(N);
	for (unsigned long long i = 0; i < N; i++)cin >> A[i];
	sort(A.rbegin(), A.rend());
	unsigned long long ans = 0, ans2 = 0;
	for (unsigned long long i = 0; i < N; i++) {
		if (N % 2 == 0) {
			if (i < N / 2 - 1)ans += 2 * A[i];
			else if (i == N / 2 - 1)ans += A[i];
			else if (i == N / 2)ans -= A[i];
			else ans -= 2 * A[i];
		}
		if (N % 2 == 1) {
			if (i < N / 2 - 1)ans += 2 * A[i];
			else if (i == N / 2 - 1 || i == N / 2)ans += A[i];
			else ans -= 2 * A[i];
		}
	}
	for (unsigned long long i = 0; i < N; i++) {
		if (N % 2 == 1) {
			if (i < N / 2)ans2 += 2 * A[i];
			else if (i == N / 2 || i == N / 2 + 1)ans2 -= A[i];
			else ans2 -= 2 * A[i];
		}
	}
	ans = max(ans, ans2);
	cout << ans << endl;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define rv(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define P pair<int,int>
using namespace std;
const int M = 1100000;
const ll inf = 9e18;
int n,m,k;
int a[M]={0};
const int mod = 1e9+7;
bool vs[M]={0};
int flag=2;
void div(int x) {
    for(int i=2;i*i<=x;i++) {
        if(x%i) continue;
        if(vs[i]) {flag=1;return;}
        vs[i] = 1;
        while(x%i==0) {x/=i;}
    }
    if(x>1) {
        if(vs[x]) flag=1;
        vs[x] = 1;
    }
}
void solve() {
    cin >> n;
    fo(i,1,n) cin>>a[i];
    int co=a[1];
    fo(i,2,n) {
        co = __gcd(co,a[i]);
    }
    fo(i,1,n) {
        div(a[i]);
        if(flag==1) break;
    }
    if(flag==2) printf("pairwise coprime\n");
    else if(co==1) printf("setwise coprime\n");
    else printf("not coprime\n");
}
int main()
{ 
    int t;
    //cin >> t;
    t = 1;
    while (t--) {
        solve();
    }
    return 0;
}


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

#define mem( arr, i ) fill( arr, arr + sizeof (arr), i )
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
const lli I_MAX = 1LL << 60;
const lli mod = 1000000007;


void solve() {
	string s, t;
	cin >> s >> t;
	
	set<char> S, T;
	map<char,int> ss, tt;
	int cntS = 0, cntT = 0;
	vcI SS, TT;
	
	for (auto x : s) {
		if ( !S.count(x) ) {
			S.insert(x);
			ss[x] = cntS++ ;
		}
		SS.push_back( ss[x] );
	}
	
	for (auto y : t) {
		if ( !T.count(y) ) {
			T.insert(y);
			tt[y] = cntT++ ;
		}
		TT.push_back( tt[y] );
	}
	
	if ( SS == TT ) cout << "Yes\n";
	else cout << "No\n";
}

int main() {
	int t = 1;
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
//		printf("Case #%d: ", i );
		solve();
	}
	return 0;
}


Measured memory_bytes: 2944
"use strict";
var __spreadArrays = (this && this.__spreadArrays) || function () {
    for (var s = 0, i = 0, il = arguments.length; i < il; i++) s += arguments[i].length;
    for (var r = Array(s), k = 0, i = 0; i < il; i++)
        for (var a = arguments[i], j = 0, jl = a.length; j < jl; j++, k++)
            r[k] = a[j];
    return r;
};
exports.__esModule = true;
var fs_1 = require("fs");
var main = function () { return fs_1.readFileSync('/dev/stdin', 'utf8').slice(0, -1); };
var args = main().split('\n');
var t = args[1].split(' ').map(function (x) { return +x; });
var ans = args
    .slice(3)
    .map(function (v) {
    var _a = v.split(' '), p = _a[0], x = _a[1];
    return __spreadArrays(t.filter(function (_, i) { return i !== +p - 1; }), [+x]).reduce(function (ac, cu) { return ac + cu; });
})
    .join('\n');
console.log(ans);


Measured memory_bytes: 11468
import java.util.*;

public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      String[] s = sc.next().split("");
      StringBuilder sb = new StringBuilder();
      for(String t:s){
        if(t.equals("0")){
          sb.append("0");
        }
        if(t.equals("1")){
          sb.append("1");
        }
        if(t.equals("B")){
          if(sb.length() > 0){
            sb.deleteCharAt(sb.length()-1);
          }
        }
      }
      
      System.out.println(sb.toString());
    }
}

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

int main(){
  string s; cin >> s;
  int n = s.size();

  int acnt = 0;
  ll ans = 0;
  rep(i, n - 1){
    //cout << s[i] << " ";
    if(s[i] == 'A'){
      acnt++;
    }
    else{
      if(s[i] == 'B' && s[i + 1] == 'C'){
        ans += acnt;
        i++;
      }
      else{
        acnt = 0;
      }
    }
    //cout << acnt << endl;
  }
  //cout << s.size() << endl;
  //cout << n << endl;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3700
#include <stdio.h>
#include <stdlib.h>

int main()

{
	int a[200005], i, n;
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	     scanf("%d", &a[i]);
	     
	for(i = n - 1; i > 0; i -= 2) 
	      printf("%d ", a[i]);
	      
	printf("%d ", a[0]);
	
	for(i = abs(i) + 1; i < n; i += 2)
	       printf("%d ", a[i]);
	       
	 return 0;
}

Measured memory_bytes: 2816
N,Y = list(map(int,input().split()))
Y_1 = Y // 1000
x = 0

while True:
    a = Y_1 - N - 9*x

    if a < 0:
        break
    elif (a%4 == 0):
        y = a // 4
        if (N - x - y >= 0):
            print(x,y,N-x-y)
            exit()
        else:
            x += 1

    else:
        x += 1

print('-1 -1 -1')

Measured memory_bytes: 3064
#include<iostream>
#include <string>
#include <vector>
#include <cmath>
#define ll long long
#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int C;
    string ans =  "Yes";
    vector<int> a(3), b(3);
    vector<vector<int> > c(3, vector<int>(3));

    rep(i,3) rep(j,3) cin >> c[i][j];
    C = c[0][0];
    rep(i,3) rep(j,3) c[i][j] -= C;

    a[0] = 0; b[0] = 0;
    a[1] = c[1][0]; a[2] = c[2][0];
    b[1] = c[0][1]; b[2] = c[0][2];

    rep(i,2) rep(j,2) {
      if(c[i+1][j+1] != a[i+1] + b[j+1]) ans = "No";
    }


    cout << ans << endl;
}


Measured memory_bytes: 256
e=Hash.new [];$_.split.map{|v|e[v]+=[$.-2]}while gets;a=[0]*($.-1);(1..$.).map{|w|u={};e[v=w.to_s].map{|j|u[a[j]]=1};t=1;e[v].map{|j|1>a[j]&&(t+=1until$\==u[t];a[j]=t;t+=1)}};p a.max;$><<a*$/

Measured memory_bytes: 188496
#include <iostream>
#include <stdio.h>
using namespace std;

int main(int argc, char *argv[])
{
    int a, b, c, res = 0;
    scanf("%d %d %d", &a, &b, &c);
    for (int i = a; i <= b; i++)
    {
        if (0 == c % i)
        {
            res++;
        }
    }
    printf("%d\n",res);
    return 0;
}



Measured memory_bytes: 3212
a, b, k = map(int, raw_input().strip().split())

m = min(a, b)

cnt = 0
ans = m
for d in xrange(m, 0, -1):
    if a % d == 0 and b % d == 0:
        cnt += 1
    if cnt == k:
        ans = d
        break

print ans


Measured memory_bytes: 27884
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if(n%1000==0) cout << 0 << endl;
    else cout << (n/1000+1)*1000 - n << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
 
using namespace std;
 
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
 
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int main(void) {
  int i;
  int a=0,b=0;
  int n;
  rep(i,4){
    cin>>n;
    a+=n;
  }
  rep(i,4){
    cin>>n;
    b+=n;
  }
  cout<<max(a,b)<<endl;
}

Measured memory_bytes: 3072
#include<iostream>
using namespace std;
int main(){
    int m,d,d1,d2,count=0;
    cin>>m>>d;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=d;j++){
            d1=j%10;
            d2=j/10;
            if(d1>=2 && d2>=2 && d1*d2==i)
                count++;
        }
    }
    cout<<count<<"\n";
    return 0;
}


Measured memory_bytes: 256
a = list(map(int,input().split()))
ans = [-1,100000000000000]
for i in range(a[0]):
	ct = list(map(int,input().split()))
	if ct[1] <= a[1]:
		if ct[0] < ans[1]:
			ans = [i,ct[0]]
		
	
if ans[0]<0:
	print('TLE')
else:
	print(ans[1])

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

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

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

vector<int> v;
int n;
int dp[100001];

int main(){
  cin >> n;
  v.push_back(1);
  FOR(i,1,10){
    if(n>=pow(6,i)){
      v.push_back(pow(6,i));
    }else{
      break;
    }
    if(n>=pow(9,i)){
      v.push_back(pow(9,i));
    }
  }
  REP(i,n+1) dp[i] = INF;
  dp[0] = 0;
  FOR(i,1,n+1){
    REP(j,v.size()){
      if(i-v[j]<0) continue;
      dp[i] = min(dp[i],dp[i-v[j]]+1);
    }
  }
  cout << dp[n] << endl;
}

/*
int n;
int cnt;
vector<int> v;



int main(){
  cin >> n;
  if(n<6){
    cout << n <<endl;
    return 0;
  }
  cnt = n%6;
  n -= cnt;
  for(int i = 20;i>0;i--){
    if(n==0) break;
    ll p;
    if(i%2==1){
      p = pow(9,i);
      if(n>=p){
        cnt += n/p;
        n -= n/p*p;
      }
    }
  }
  for(int i = 20;i>0;i--){
    if(n==0) break;
    ll p;
    p = pow(6,i);
    cout << p << endl;
    if(n>=p){
      cout << p << " " << n/p <<endl;
      cnt += n/p;
      n -= n/p*p;
    }
  }
  cout << cnt<<endl;
}


int main(){
  cin >> n;
  FOR(i,1,20){
    int t = pow(6,i);
    if(t>n) break;
    v.push_back(t);
  }
  FOR(i,1,20){
    int t = pow(9,i);
    if(t>n) break;
    v.push_back(t);
  }
  v.push_back(1);
  sort(v.begin(),v.end(),greater<int>());
  cnt = 0;
  REP(i,v.size()){
    int a = n/v[i];
    n %= v[i];
    cnt += a;
    cout << v[i] <<" " << a <<endl;
  }
  cout << cnt <<endl;
}
*/


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

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int>> fr(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		fr[a].push_back(b);
		fr[b].push_back(a);
	}

	vector<bool> check(n+1, false);

	int ret = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (check[i]) {
			continue;
		}
		int temp = 1;
		queue<int> q;
		q.push(i);
		check[i] = true;

		while (!q.empty())
		{
			int qf = q.front();
			for (auto& j : fr[qf]) {
				if (check[j]) {
					continue;
				}
				q.push(j);
				check[j] = true;
				++temp;
			}
			q.pop();
		}

		ret = max(ret, temp);
	}

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 14860
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
long long n,m,k;

bool calc(int i)
{
	long long x=(i>=n?i+1:i);
	if(i<1 || i>k)return true;
	long long y=(k-i+1>=m?k-i+2:k-i+1);
	return x*y<(long long)n*m;
}

void FujiwaraNoMokou()
{
	scanf("%lld%lld",&n,&m);
	long long l=0,r=inf;
	for(;l<r-1;)
	{
		k=(l+r)>>1;
		//printf("l=%d r=%d k=%d\n",l,r,k);
		bool flag=true;
		for(int i=k/2-10;i<k/2+10;i++)
		{
			flag&=calc(i);
		}
		for(int i=n-10;i<n+10;i++)
		{
			flag&=calc(i);
		}
		for(int i=k-m-10;i<k-m+10;i++)
		{
			flag&=calc(i);
		}
		if(flag)l=k;else r=k;
	}
	printf("%lld\n",l);
}

int main()
{
	int t;
	scanf("%d",&t);
	for(;t--;)
	{
		FujiwaraNoMokou();
	}
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut seq = vec![0; n];
    let mut sum = 0;
    for i in 0..n {
        seq[i] = read::<i64>();
        sum += seq[i];
    }
    seq.sort();
    sum -= seq[n - 1] * 2;
    println!("{}", if sum > 0 { "Yes" } else { "No" })
}


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

using namespace std;

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

    int points[N][D];

    for (int point = 0; point < N; point++)
    {
        for (int dimension = 0; dimension < D; dimension++)
        {
            cin >> points[point][dimension];
        }
    }
    
    int valid_combos = 0;
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            int before_sqrt = 0;
            for(int d = 0; d < D; d++)
            {
                before_sqrt += pow(abs(points[i][d] - points[j][d]), 2);
            }

            long double sr = sqrt(before_sqrt);
            if (sr - floor(sr) == 0)
            {
                valid_combos++;
            }
        }
    }

    cout << valid_combos;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    char X,Y;

    cin>>X>>Y;

    if(int(X)>int(Y))
    {
        cout<<">";
    }
    else
    {
        if(int(X)<int(Y))
        {
            cout<<"<";
        }
        else{cout<<"=";}
    }

	return 0;
}

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

int K;

void solve()
{
	if(K%2 == 0 || K%10 == 5) cout << -1 << '\n';
	else{
		int cur = 1, x = 7;
		set<int> seen;
		while(true){
			if(x % K == 0){
				cout << cur << '\n';
				return;
			}
			if(seen.count(x)){
				cout << -1 << '\n';
				return;
			}
			(x = 10*x+7)%=K;
			cur++;
		}
	}
}


int main()
{
	cin >> K;
	solve();
	return 0;
}

Measured memory_bytes: 3616
/*
source: ABC 141 F Xor Sum 3
*/
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MXN = 100005;

int main(){
    int n;
    LL a[MXN], b[MXN], sum = 0;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
        sum ^= a[i];
    }
    for(int i = 0; i < n; ++i)
    {
        a[i] &= (~sum);
        for(int j = 60; j >= 0; --j)
        {
            if((a[i] >> j) & 1)
            {
                if(b[j] == 0)
                {
                    b[j] = a[i];
                    break;
                }
                else
                {
                    a[i] ^= b[j];
                }
            }
        }
    }
    LL x = 0;
    for(int i = 60; i >= 0; --i)
    {
        x = max(x, x ^ b[i]);
    }
    cout << (x + (x ^ sum)) << '\n';
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<ll> v;

void enum_div(ll n)//nの約数を列挙
{
	for(ll i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			v.push_back(i);
			if(i!=1 && i*i!=n)
			{
				v.push_back(n/i);
			}
		}
	}
}

int main() {
  int N,M;
  scanf("%d%d", &N,&M);

  int maxdiv = 1000000001;

  enum_div(M);

  FOR(i,0,SZ(v)-1){
    if(v[i]>=N && v[i]<maxdiv) maxdiv = v[i];
    // cout << v[i] << endl;
  }

  // cout << maxdiv << endl;

  if(maxdiv == 1000000001){
    cout << 1 << endl;
    return 0;
  }
  else{
    cout << M/maxdiv << endl;
  }
  

}



Measured memory_bytes: 256
import bisect
import sys
input = sys.stdin.readline
a,b,q=map(int,input().split())
S,T=[],[]
for i in range(a):
  S.append(int(input()))
for i in range(b):
  T.append(int(input()))
def f(list,n):
  if n<list[0]:
    return [-float("inf"),list[0]]
  elif list[-1]<n:
    return [list[-1],float("inf")]
  else:
    i=bisect.bisect_left(list,n)
    return [list[i-1],list[i]]
def g(SS,TT,x):
  a,b,c,d=x-SS[0],SS[1]-x,x-TT[0],TT[1]-x
  dis1=max(a,c)
  dis2=min(2*a+d,2*d+a)
  dis3=max(b,d)
  dis4=min(2*b+c,2*c+b)
  return min([dis1,dis2,dis3,dis4])
for i in range(q):
  x=int(input())
  print(g(f(S,x),f(T,x),x))

Measured memory_bytes: 12188
/*ITP1_7_B:How many ways?*/
#include <iostream>
using namespace std;

int main() 
{
  int n,x;

  while(true)
  {
    int count = 0;

    cin >> n >> x;
    if(n==0 && x==0) break;

    for(int i=1;i<=n-2;i++)
    {   
      for(int j=i+1;j<=n-1;j++)
      {   
        for(int k=j+1;k<=n;k++)
        {   
          int sum = i + j + k;
          if(sum==x)
            count++;
        }   
      }   
    }   

    cout << count << endl;
  }

  return 0;
}



Measured memory_bytes: 3100
#include <stdio.h>

int main(){
	
	long long int N, sum = 0;
	scanf("%lld", &N);
	
	for(int i=1; i<=N; i++){
		if(i%3 == 0){
		}
		else if(i%5 == 0){
		}
		else if(i%3 == 0 && i%5 == 0){
		}
		else{
			sum+= i;
		}
	}
	printf("%lld\n", sum);
	return 0;
}

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

typedef pair<int, int> P;
constexpr int IINF = INT_MAX;

struct edge{
    int to, cap, cost, rev;
};

int V, E, F;
vector<vector<edge> > G;
vector<int> h, dist, prevv, preve;

void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge){to, cap, cost, int(G[to].size())});
    G[to].push_back((edge){from, 0, -cost, int(G[from].size())-1});
}

// 最小費用流
int min_cost_flow(int s, int t, int f){
    h.resize(G.size());
    dist.resize(G.size());
    prevv.resize(G.size());
    preve.resize(G.size());
    int res = 0;
    fill(h.begin(), h.end(), 0);
    while(f > 0){
        priority_queue<P, vector<P>, greater<P> > que;
        fill(dist.begin(), dist.end(), IINF);
        dist[s] = 0;
        que.push({0,s});
        while(!que.empty()){
            P p = que.top();
            que.pop();
            int v = p.second;
            if(dist[v] < p.first) continue;
            for(int i=0;i<int(G[v].size());i++){
                auto &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push({dist[e.to], e.to});
                }
            }
        }
        if(dist[t] == IINF){
            return -1;
        }
        for(int v=0; v<G.size(); v++) h[v] += dist[v];
        int d = f;
        for(int v=t; v!=s; v=prevv[v]){
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d*h[t];
        for(int v=t; v!=s; v=prevv[v]){
            auto &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main() {
    cin >> V >> E >> F;
    G.resize(V);
    for(int i=0;i<E;i++){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        add_edge(u, v, c, d);
    }
    cout << min_cost_flow(0, V-1, F) << endl;
    return 0;
}



Measured memory_bytes: 3212
#include<stdio.h>
#include<stdlib.h>
typedef struct{int id; int p; char s[11];} restaurant;
restaurant r[100];
int n, i;

int compare_r(const void *A, const void *B){
	const restaurant *a = A;
	const restaurant *b = B;
	for(int i=0; i<10; i++){
		if(a->s[i] > b->s[i]){return 1;}else if(a->s[i] < b->s[i]){return -1;}
	}
	if(a->p < b->p){
		return 1;
	}else if(a->p > b->p){
		return -1;
	}else{
		return 0;
	}
}
int main(void){
	scanf("%d", &n);
	for(i=0; i<n; i++){
		r[i].id = i+1;
		scanf("%s%d", r[i].s, &(r[i].p));
	}
    qsort(r, n, sizeof(restaurant), compare_r);
	for(i=0; i<n; i++){
		printf("%d\n", r[i].id);
	}
}


Measured memory_bytes: 128