akhauriyash/Code-Regression huggingface dataset:
n = gets.chomp
n = n.slice!(-1)

if n == "2"
	puts "hon" 
end
if n == "4"
	puts "hon" 
end
if n == "5"
	puts "hon" 
end
if n == "7"
	puts "hon" 
end
if n == "9"
	puts "hon" 
end
if n == "0"
	puts "pon" 
end
if n == "1"
	puts "pon" 
end
if n == "6"
	puts "pon" 
end
if n == "8"
	puts "pon" 
end
if n == "3"
	puts "bon" 
end

Measured memory_bytes: 14280
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static ArrayList<Edge> E;

	public static void main(String[] args) {
		while (true) {
			N = sc.nextInt();
			if (N == 0) break;
			M = sc.nextInt();
			E = new ArrayList<Edge>();
			for (int i = 0; i < M; ++i) {
				int a = sc.nextInt() - 1;
				int b = sc.nextInt() - 1;
				int w = sc.nextInt();
				E.add(new Edge(a, b, w));
			}
			Collections.sort(E);
			System.out.println(solve());
		}
	}

	static int solve() {
		int ans = 99999;
		for (int i = 0; i < M; ++i) {
			if (i != 0 && E.get(i).w == E.get(i - 1).w) continue;
			UnionFind uf = new UnionFind(N);
			for (int j = i; j < M; ++j) {
				Edge e = E.get(j);
				int diff = e.w - E.get(i).w;
				if (diff >= ans) break;
				uf.union(e.f, e.t);
				if (uf.size(0) == N) {
					ans = diff;
					break;
				}
			}
		}
		return ans == 99999 ? -1 : ans;
	}

	static class Edge implements Comparable<Edge> {
		int f, t, w;

		public Edge(int f, int t, int w) {
			this.f = f;
			this.t = t;
			this.w = w;
		}

		public int compareTo(Edge o) {
			return this.w - o.w;
		}

	}

	static class UnionFind {
		int[] set;

		UnionFind(int n) {
			set = new int[n];
			Arrays.fill(set, -1);
		}

		void union(int a, int b) {
			int rtA = root(a);
			int rtb = root(b);
			if (rtA == rtb) {
				return;
			}
			set[rtA] += set[rtb];
			set[rtb] = rtA;
		}

		boolean find(int a, int b) {
			return root(a) == root(b);
		}

		int root(int a) {
			if (set[a] < 0) {
				return a;
			} else {
				set[a] = root(set[a]);
				return set[a];
			}
		}

		int size(int a) {
			return -set[root(a)];
		}
	}

}

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;

int main(){
  int N,M; cin >> N >> M;
  vector<ll> h(N);
  map<int,bool> m;
  for(int i = 0; i < N; i++){
    cin >> h[i];
    m[i] = true;
  }

  for(int i = 0; i < M; i++){
    int tmp1, tmp2;
    cin >> tmp1 >> tmp2;
    tmp1--; tmp2--;

    if(h[tmp1] <= h[tmp2]){
      m[tmp1] = false;
    }
    if(h[tmp2] <= h[tmp1]){
      m[tmp2] = false;
    }
  }

  int ans = 0;
  for(int i = 0; i < N; i++){
    if(m[i]) ans++;
  }
  cout << ans << endl;
}



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


  
int main(){
  

  int n,m,c;
  cin>>n>>m>>c;
  
  vector<int> base(m);
  
  for (int i=0;i<m;i++){
    cin>>base.at(i);
  }
  
  int answer=0;
  
  for (int i=0;i<n;i++){
    int check=0;
    for (int j=0;j<m;j++){
      int aj;
      cin>>aj;
      check+=aj*base.at(j);
    }
    
    if (check+c>0){
      answer+=1;
    }
  }
  
  cout<<answer<<endl;
  
  
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	
	Scanner a = new Scanner(System.in);
		
	int S = a.nextInt();
	int h = S/3600;
	int m = (S % 3600)/60;
	int s = S- (h*3600+m*60);
	System.out.println(h + ":" + m + ":" + s);
    }
}

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

if __name__ == '__main__':
    flag = False
    A,B,X = map(int,input().split())

    if (X-A)<0:
        flag = False
    elif (X-A)<B:
        flag = True

    if flag == True:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 2940
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

class DSU(object):
    
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1] * n
        self.cycle = False

    def find(self, key):
        if self.parent[key] != key:
            self.parent[key] = self.find(self.parent[key])
        return self.parent[key]

    def union(self, a, b):
        s1, s2 = self.find(a), self.find(b)
        if s1 != s2:
            if self.rank[s1] < self.rank[s2]:
                self.parent[s1] = s2
                self.rank[s2] += self.rank[s1]
            else:
                self.parent[s2] = s1
                self.rank[s1] += self.rank[s2]
        else:
            self.cycle = True
        
    def has_cycle(self):
        return self.cycle
    
    def show_parent(self):
        return self.parent

    def show_rank(self):
        return self.rank

def solve():
    n, m = map(int, input().split())
    d = DSU(n + 1)
    if m > 0:
        for _ in range(m):
            a, b = map(int, input().split())
            d.union(a, b)
        # print(d.show_parent())
        print(max(d.show_rank()))
    else:
        print(1)

solve()

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

int main()
{
	double get ;
	double high ;

	while( cin >> get )
	{
		high = 4.9 *(get/9.8)*(get/9.8) ;

		int i = ceil( high/5 ) ;
		cout << i+1 << endl ;
	}

	return 0 ;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
#define P printf
#define S scanf
#define PII pair<int,int>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define heap priority_queue
#define Q queue
#define V vector
#define T top
#define F front
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define PLL pair<ll,ll>
using namespace std;
const int N=200005;
struct LINE{
    ll a,b;
    ll value(ll x){
        return a*x+b;
    }
    PLL insect(LINE A){
        ll a1=A.a,b1=A.b;
        ll sed,suan;
        sed=b1-b;
        suan=a-a1;
        if(suan<0) suan=-suan,sed=-sed;
        return {sed,suan};
    }
};
ll dp[N],h[N];
vector<LINE> lines;
int main(){
    int n;
    ll C;
    S(" %d %lld",&n,&C);
    FOR(i,1,n){
        S(" %lld",&h[i]);
    }
    int idx=0;
    lines.pb({-2*h[1],h[1]*h[1]+dp[1]});
    FOR(i,2,n){
        // query
        while(idx+1<lines.size() && lines[idx].value(h[i])>lines[idx+1].value(h[i])) idx++;
        ll V=lines[idx].value(h[i]);
        dp[i]=h[i]*h[i]+V+C;
        // insert
        LINE tmp={-2*h[i],h[i]*h[i]+dp[i]};
        while(idx<=lines.size()-2){ // while still have at least 1
            PLL A=tmp.insect(lines.end()[-1]);
            PLL B=lines.end()[-1].insect(lines.end()[-2]);
            if((__int128)A.x*B.y<=(__int128)B.x*A.y) lines.pop_back();
            else{
                break;
            }
        }
        lines.pb(tmp);
    }
    P("%lld",dp[n]);
    return 0;
}


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

public class Main {

	public static void main(String[] args) {

		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		 try{

			 int S = Integer.parseInt(br.readLine());

			 System.out.printf("%d:%d:%d\n",S/3600,(S%3600)/60,S%60);

		 }catch(IOException e){
			 e.printStackTrace();
		 }
	}
}





Measured memory_bytes: 24672
"use strict";
function main(input) {
    const arr = input.split("\n");
    const N = parseInt(arr[0]);
    const S = ["AC", "WA", "TLE", "RE"];
    const mul = " x ";
    let C = Array(S.length);
    C.fill(0);
    for (let i = 1; i < N + 1; i++) C[S.indexOf(arr[i])]++;
    for (let i = 0; i < S.length; i++)  console.log(S[i] + mul + C[i]);
    return;
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 37428
#include "bits/stdc++.h"
#define REP(i,n,N) for(ll i=(n); i<(N); i++)
#define RREP(i,n,N) for(ll i=(N-1); i>=n; i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define p(s) cout<<(s)<<endl
#define p2(a,b) cout<<(a)<<" "<<(b)<<endl
#define v2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll inf=1e18;
const ll NODE_SIZE = 60;

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

ll H;  //フィールドの高さ
ll W;  //フィールドの幅
ll start_y, start_x;    //開始座標

string field[NODE_SIZE];      //格子状のフィールド (string)

ll d[NODE_SIZE][NODE_SIZE];
//幅優先探索 (フィールド: 配列/string)
void bfs_field() {
    queue<pair<ll,ll>> q; //<コスト, 座標(y,x)>
    bool visited[H][W];
    REP(i,0,H)REP(j,0,W) visited[i][j]=false;    //初期位置を設定
    REP(i,0,H)REP(j,0,W) d[i][j]=0;
    d[start_y][start_x] = 1;
    q.push({start_y, start_x});  //開始ノードを追加

    while(!q.empty()){
        ll cur_y = q.front().first;
        ll cur_x = q.front().second;
        q.pop();
        if(visited[cur_y][cur_x]) continue;
        visited[cur_y][cur_x] = true;

        REP(k,0,4){
            ll next_y = cur_y + dy[k];
            ll next_x = cur_x + dx[k];

            if(!CK(next_y,0,H) || !CK(next_x,0,W)) continue;  //範囲外
            if(field[next_y][next_x]=='#') continue; //壁
            /* ここに問題ごとの条件 */
            if(!visited[next_y][next_x]){     //未到達の座標だけpush.
                q.push({next_y, next_x});
                d[next_y][next_x] = d[cur_y][cur_x] + 1;
            }
        }
    }
}
int main(){
    cin>>H>>W;
    REP(i,0,H){
        cin>>field[i];
    }
    ll cnt=0;
    REP(i,0,H){
        REP(j,0,W){
            if(field[i][j]=='.') cnt++;
        }
    }
    assert(cnt>=2);
    start_y=0;
    start_x=0;
    bfs_field();
    if(d[H-1][W-1]==0) p(-1);
    else p(cnt - d[H-1][W-1]);
    return 0;
}

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

int main()
{

    int x1, y1, x2, y2, a,b;
    cin >> x1>>y1>>x2>>y2;
    a = x2 - x1;
    b = y2 - y1;
    cout <<x2-b <<" "<<y2+a<<" "<<x1-b<<" "<<y1+a<< endl;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL-1
double EPS=1e-9;
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef complex<double> P;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
long long int MOD = 1000000007;
/*
cin >> n;
vi a(n);
rep(i,n)cin>>a[i];
*/
vi primes;
int num[1005]={0};
int main(){
	int N,a,b;
	cin >>N>>a>>b;
	vi x(N);
	rep(i,N)cin>>x[i];
	ll sum=0;
	
	ll A=a,B=b;
	for(int i=0;i<N-1;i++){
		
		ll dif=(ll)x[i+1]-(ll)x[i];
		if(dif*A>B)sum+=B;
		else sum+=dif*A;
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include <set>
#include <utility>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
typedef pair<string, int> P;
typedef long long ll;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
const int MAXN = 100000;
const int MAXE = 100000;
const int MAXV = 10000;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
struct UnionFind{
    vector<int> par,rank;
    UnionFind(int n):par(n),rank(n){
        for(int i=0;i<n;++i) par[i]=i;
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry) return ;
        if(rank[ry]>rank[rx]) par[rx]=ry;
        else par[ry]=rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
};
int main(){
    int n,t;cin>>n>>t;
    vector<pii> dish(n);
    for(int i=0;i<n;++i) cin>>dish[i].first>>dish[i].second;
    sort(dish.begin(),dish.end());
    vector<vector<int> > dp(n+1,vector<int>(t,0));
    for(int i=0;i<n;++i){
        for(int j=0;j<t;++j){
            dp[i+1][j]=dp[i][j];
            int time=dish[i].first;
            int tasty=dish[i].second;
            if(j>=time){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-time]+tasty);
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;++i){
        ans=max(ans,dp[i][t-1]+dish[i].second);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 38636
#include<iostream>
using namespace std;
#define MAX 10000

bool prime[MAX];

void Prime_table(int n){
	prime[0] = false;
	prime[1] = false;
	for(int i = 2; i < MAX; i++) prime[i] = true;


	for(int i = 2; i*i <= n; i++){
		if(prime[i]){
			for(int j = i*i; j <= n; j += i){
				prime[j] = false;
			}
		}
	}
}

int main(){
	int n;
	while(cin >> n){
		Prime_table(n);
		int cnt = 0;
		for(int i = 1,j = n; i <= n; i++,j--){
			if(prime[i] == true && prime[j] == true){
				cnt++;
			}
		}
	cout << cnt << endl;
	}
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

signed main()
{
    int X, Y;
    cin >> X >> Y;
    printf("%lld\n", X + Y / 2);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 2005;

vector<int> G[MAX_N];

void dfs(int u,int p,int d,vi& dist)
{
    dist[u] = d;
    each(v,G[u]){
        if(v != p){
            dfs(v,u,d+1,dist);
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,K;
    cin >> n >> K;
    vp edge(n-1);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].pb(b-1),G[b-1].pb(a-1);
        edge[i] = P(a-1,b-1);
    }
    int ans = INF;
    if(K % 2){
        rep(i,n-1){
            vector<int> d(n,0);
            dfs(edge[i].fi,edge[i].se,0,d);
            dfs(edge[i].se,edge[i].fi,0,d);
            int res = 0;
            rep(j,n){
                if(d[j] > (K-1)/2){
                    res++;
                }
            }
            cmn(ans,res);
        }
    }else{
        rep(i,n){
            vector<int> d(n,0);
            dfs(i,-1,0,d);
            int res = 0;
            rep(j,n){
                if(d[j] > K/2){
                    res++;
                }
            }
            cmn(ans,res);
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (i * j == n) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}



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

int main(){
	int a,b;
	cin >> a >> b;

	if(a==b){
		cout <<"Draw"<<endl;
		return 0;
	}else if(a==1){
		cout <<"Alice" <<endl;
		return 0;
	}else if(b==1){
		cout << "Bob"<<endl;
		return 0;
	}else if(a>b){
		cout << "Alice"<<endl;
		return 0;
	}else {
		cout << "Bob" <<endl;
		return 0;
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b,c;
  cin>>a>>b>>c;
  if(b-a==c-b) cout<<"YES"<<'\n';
  else cout<<"NO"<<'\n';
  return 0;
}


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

int fun(int N, int A[]){
    
    for (int i = 0; i < 12; i++){
        if (N % 2 == 0){
            A[i] = 0;
        } else {
            A[i] = 1;
        }
        
        N /= 2;
    }
    
    return 0;
}

int main(){
    
    int i, j, k, H, W, K, count, sum, ans;
    cin >> H >> W >> K;
    count = 0;
    sum = 0;
    ans = 0;
    
    int C[H][W], D[H][W];
    
    int A[12] = {};
    
    char ddd;
    
    for (i = 0; i < H; i++){
        for (j = 0; j < W; j++){
            
            cin >> ddd;
            if (ddd == '.'){
                C[i][j] = 0; //白
            } else if (ddd == '#'){
                C[i][j] = 1; //黒
            } else {
                
            }
        }
    }
        
    for (i = 0; i < int(pow(2, H + W)); i++){
        
        for (int x = 0; x < H; x++){
            for (int y = 0; y < W; y++){
                D[x][y] = C[x][y];
            }
        }
        
        fun(i, A);
        
        for (j = 0; j < H; j++){
            
            if (A[j] == 1){
                for (k = 0; k < W; k++){
                    D[j][k] = 0;
                }
            }
        }
        
        for (j = H; j < H + W; j++){
            
            if (A[j] == 1){
                for (k = 0; k < H; k++){
                    D[k][j - H] = 0;
                }
            }
        }
        
        count = 0;
        
        for (int x = 0; x < H; x++){
            for (int y = 0; y < W; y++){
                
                if (D[x][y] == 1) count++;
            }
        }
        
        if (count == K) ans++;
        
    }
    
    cout << ans << "\n";
    
    return 0;
}




Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<string,int> P;

struct rollinghash{
	static const int MD=3;
	const ll base[MD]={1007LL,1009LL,1009LL};
	const ll mods[MD]={999999937LL, 1000000007LL,912941443LL};
	vector<ll> hash[MD];
	vector<ll> pw[MD];
	void construct(const string &str){
		int n=str.size();
		for(int i=0;i<MD;i++){
			pw[i].resize(n+1);
			pw[i][0]=1;
			for(int j=0;j<n;j++){
				pw[i][j+1]=pw[i][j]*base[i]%mods[i];
			}
		}
		for(int i=0;i<MD;i++){
			hash[i].resize(n+1);
			hash[i][0]=0;
			for(int j=0;j<n;j++){
				hash[i][j+1]=(hash[i][j]*base[i]%mods[i]+str[j])%mods[i];
			}
		}
	}

	// calc hash value [l,r)
	ll hash_value(int l,int r,int i){
		return ((hash[i][r]-hash[i][l]*pw[i][r-l])%mods[i]+mods[i])%mods[i];
	}
};

rollinghash rol[100005];

int n;
const int B=300;
P p[100005];
int rid[100005];
int cnt[100005];
int Bcnt[500];

bool isok(int s,int t){
	//printf("isok%d %d\n",s,t);
	int len=p[s].first.size();
	for(int i=0;i<3;i++){
		if(rol[s].hash_value(0,len,i)!=rol[t].hash_value(0,len,i))return false;
	}
	return true;
}

int query(int s){
	int v=s;
	while(v%B!=0 && v<n){
		if(cnt[v]==1){
			if(p[s].first.size()>p[v].first.size())return -1;
			if(isok(s,v)){
				return (p[v].second+1);
			}else{
				return -1;
			}
		}
		v++;
	}
	while(v<n){
		if(Bcnt[v/B]>0)break;
		v+=B;
	}
	while(v<n){
		if(cnt[v]==1){
			if(p[s].first.size()>p[v].first.size())return -1;
			if(isok(s,v)){
				return (p[v].second+1);
			}else{
				return -1;
			}
		}
		v++;
	}
	return -1;
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin >> p[i].first;
		p[i].second=i;
	}
	sort(p,p+n);
	for(int i=0;i<n;i++){
		rol[i].construct(p[i].first);
		rid[p[i].second]=i;
	}
	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		b--;
		if(a==1){
			cnt[rid[b]]++;
			Bcnt[rid[b]/B]++;
		}
		if(a==2){
			cnt[rid[b]]--;
			Bcnt[rid[b]/B]--;
		}
		if(a==3){
			printf("%d\n",query(rid[b]));
		}
	}
	return 0;
}



Measured memory_bytes: 86908
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int y=0;
  for (int i=0;i<N;i++){
    string x;
    cin >> x;
    if (x=="Y"){
      y = 1;
      break;
    }
  }
  if (y==1){
    cout << "Four" << endl;
  }
  else{
    cout << "Three" << endl;
  }
}

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

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<int>> v(H,vector<int>(W));//
  vector<bool> tate(W,false);
  vector<bool> yoko(H,false);
  vector<string> ans(H,"");
  for(int i = 0; i < H;i++){
    string str= {""};
    cin >> str;
    ans[i].append(str);
    for(int j = 0; j< W;j++){
      if(ans[i][j] == '#'){
        tate[j] = true;
        yoko[i] = true;
      }
    }
 }
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(tate[j]&&yoko[i])cout << ans[i][j];
    }
    if(yoko[i])cout << endl;
  }
  cout << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace abc139_b
{
    static class Program
    {
        static void Main(string[] args)
        {
            var items = Console.ReadLine().ToIntArray();
            var a = (double)items[0];
            var b = (double)items[1];

            // b = (a - 1) * n + 1
            // n = (b - 1) / (a - 1)
            var n = (int)Math.Ceiling((b - 1) / (a - 1));

            Console.WriteLine($"{n}");
        }

        static int ToInteger(this string s)
        {
            return int.Parse(s);
        }

        static int[] ToIntArray(this string s, char separator = ' ')
        {
            return s.Split(separator).Select(m => m.ToInteger()).ToArray();
        }
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<cmath>

using namespace std;

#define ll long long

signed main(void) {
    ll n;
    cin >> n;
    ll div5 = 0LL;
    if(n%2LL==1LL){
        cout << 0LL << endl;
        return 0;
    }
    for(ll i=1LL;;i++){
        ll temp = pow(5LL,i);
        if(temp>n) break;
        div5 += n/temp/2LL;
    }
    cout << div5 << endl;
    return 0;
}

Measured memory_bytes: 256
def ext_euclid(a, b):
    # return (x, y, gcd(a, b)) such that a * x + b * y = gcd(a, b)
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euclid(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euclid(a, mod)
    return x % mod


def comb_list_1(H, W, A, B, mod, modinv_list):
    # (h+B-1)_C_(B-1)  (h in {0, ..., H-A-1})
    ret = [0 for _ in range(H - A)]
    c = 1
    for h in range(H - A):
        ret[h] = c
        c *= h + B
        c *= modinv_list[h + 1]
        c %= mod
    return ret


def comb_list_2(H, W, A, B, mod, modinv_list):
    # (-h+H+W-B-2)_C_(W-B-1)  (h in {0, ..., H-A-1})
    ret = [0 for _ in range(H - A)]
    # initial value -> (A+W-B-1)_C_(W-B-1)  (h = H-A-1)
    c = 1
    for a in range(1, A + 1):
        c *= (a + W - B - 1)
        c *= modinv_list[a]
        c %= mod
    # fill elements of result list from the back
    for h in range(H - A - 1, -1, -1):
        ret[h] = c
        c *= H - h + W - B - 1
        c *= modinv_list[H - h]
        c %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    H, W, A, B = list(map(int, input().split(' ')))
    modinv_list = [None] + [mod_inv(h, MOD) for h in range(1, H + 1)]  # modinv doesn't exist on h = 0
    combs_1 = comb_list_1(H, W, A, B, MOD, modinv_list)
    combs_2 = comb_list_2(H, W, A, B, MOD, modinv_list)
    ans = 0
    for c1, c2 in zip(combs_1, combs_2):
        ans += c1 * c2
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

ll rec(ll n) {
    if (n == 1) return 1;
    return rec(n / 2) * 2 + 1;
}

int main() {
    ll n;
    cin >> n;
    cout << rec(n) << endl;
}


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

int main(){
  int A[3],X=0,Y=0;
  cin>>A[0]>>A[1]>>A[2];
  for(int i=0;i<3;i++){
    if(A[i]==5){
      X++;
    }
    else if(A[i]==7){
      Y++;
    }
  }
  if(X==2&&Y==1){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
  return 0;
}
    

Measured memory_bytes: 256
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # input
    n = int(input().strip())
    a = list(map(int, input().strip().split()))

    # check if "for all i in [0,n-1], C[a[i]] == 0"
    C = Counter()
    for i in range(n):
        if C[a[i]] != 0:  # fail
            print("NO")
            return
        else:             # pass
            C[a[i]] += 1
    print("YES")
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 110572
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll N,K;
cin>>N>>K;
vector<ll> vec(N);
for(ll i=0;i<N;i++) {
  cin>>vec[i];
}
sort(all(vec));
reverse(all(vec));
ll ans=0;
for(ll i=0;i<K;i++) {
  ans+=vec[i];
}

cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define pb push_back
using namespace std;static const long long INFL = 0x3F3F3F3F3F3F3F3FLL;
typedef int64_t ll;
typedef pair<ll, ll> pll;
// ダイクストラ法（プライオリティキュー）
struct DijkstraPQ {
    struct edge { int64_t to, cost; };
    int V;
    vector<vector<edge>> G;
    vector<int64_t> d;
    
    DijkstraPQ(int _n) {
        init(_n);
    }
    void init(int _n) {
        V = _n;
        G.clear();
        d.clear();
        G.resize(V, vector<edge>());
        d.resize(V, INFL);
    }
    void dijkstra(int64_t s) {
        // greaterを指定することでfirstが小さい順に取り出せるようにする
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        fill(d.begin(), d.end(), INFL);
        d[s] = 0;
        pq.push(pll(0, s));
        while (!pq.empty()) {
            pll p = pq.top();
            pq.pop();
            ll v = p.second; // secondは頂点の番号
            if (d[v] < p.first) continue; // firstは最短距離
            for (int i = 0; i < G[v].size(); i++) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    pq.push(pll(d[e.to], e.to));
                }
            }
        }
    }
};
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll N;
        in >> N;
        DijkstraPQ dk(N);
        ll a, b, c;
        rep(i, N - 1) {
            in >> a >> b >> c;
            a--; b--;
            dk.G[a].pb({b, c});
            dk.G[b].pb({a, c});
        }
        ll Q, K;
        in >> Q >> K;
        K--;
        dk.dijkstra(K);
        ll x, y;
        rep(i, Q) {
            in >> x >> y;
            x--; y--;
            ll ans = dk.d[x] + dk.d[y];
            out << ans << endl;
        }
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 11120
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

int debug = 0;
int x, y;
bool field[8][8];

void startfrom(int x, int y){
	if(debug) cout << "start from " << x << " " << y << endl;
	
	field[x][y] = false;
	for(int i=-3;i<=3;i++){
		if((0 <= x+i && x+i < 8) &&
		field[x+i][y] == true){
			startfrom(x+i,y);
		}
		if((0 <= y+i && y+i < 8) &&
		field[x][y+i] == true){
			startfrom(x,y+i);
		}
	}
	
}

int main(void){
	//bool field[8][8];
	
	memset(field,false,sizeof(field));
	
	int n;
	cin >> n;
	//cin.ignore(); // CR+LF
	
	for(int i=0;i<n;i++){
		string str;
				
		//if(i!=0) cout << endl; // for between each dataset
		for(int j=0;j<8;j++){
			cin >> str;
			if(debug) cout << "input str = " << str << endl;
			for(int k=0;k<8;k++){
				field[j][k] = str[k] - '0';
				if(debug) cout << field[j][k];
			}
			if(debug) cout << endl;
		}
		
		cin >> y; //NOTE: these are 1 origin
		cin >> x;
		
		//recursive
		startfrom(x-1,y-1);
		cout << "Data " << i+1 << ":" <<endl; 
		for(int j=0;j<8;j++){
			for(int k=0;k<8;k++){
				cout << field[j][k];
			}
			cout << endl;
		}
//		cout << endl;
	}

}

Measured memory_bytes: 0
n = gets.to_i
s = gets.chomp.bytes
dot = '.'.ord
a = Array.new(n){Array.new(2, 0)}
if s[0] == dot
  a[0][0] = 1
else
  a[0][1] = 1
end
1.upto(n - 1) do |i|
  if s[i] == dot
    a[i][0] = a[i - 1][0] + 1
    a[i][1] = a[i - 1][1]
  else
    a[i][0] = a[i - 1][0]
    a[i][1] = a[i - 1][1] + 1
  end
end
min = [a[n - 1][0], a[n - 1][1]].min
n.times do |i|
  min = a[n - 1][0] - a[i][0] + a[i][1] if min > a[n - 1][0] - a[i][0] + a[i][1]
end
puts min

Measured memory_bytes: 14136
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main{
	static Scanner s=new Scanner(System.in);
	static IntStream REPS(int v){return IntStream.range(0,v);}
	static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
	static IntStream INS(int n) {return REPS(n).map(i->getInt());}
	static int getInt(){return Integer.parseInt(s.next());}
	static class Pair<T,U>{
		T l;U r;
		Pair(T L,U R){l=L;r=R;}
		T getL(){return l;}
		U getR(){return r;}
	}


	static final int h=getInt(),w=getInt(),n=getInt(),a[]=INS(n).toArray();
	public static void main(String[]$){

		if(w==1) {
			for(int i=0;i<n;++i) {
				for(int j=0;j<a[i];++j) {
					System.out.println(i+1);
				}
			}
			return;
		}

		int[][]f=new int[h][w];
		Arrays.stream(f).forEach(o->Arrays.fill(o,-1));
		int x=0,y=0,dx=1,dy=0;
		int color=0;
		try {
			while(true){
				--a[color];
				f[y][x]=color+1;
				if(a[color]==0)++color;

				x+=dx;y+=dy;

				if(x==w-1) {
					if(y%2==0) {
						dx=0;
						dy=1;
					}else {
						dx=-1;
						dy=0;
					}
				}
				if(x==0) {
					if(y%2==1){
						dx=0;
						dy=1;
					}else {
						dx=1;
						dy=0;
					}
				}
			}
		}catch (Exception e) {
		}
		Arrays.stream(f).map(
				o->Arrays.stream(o)
				.mapToObj(String::valueOf)
				.collect(Collectors.joining(" "))
				).forEach(System.out::println);
	}
}

Measured memory_bytes: 30876
x, y = map(int, input().split())
minusx = x * -1
minusy = y * -1
a = [0]*4
a[0] = y - x
a[1] = y - minusx + 1
a[2] = minusy - x + 1
a[3] = minusy - minusx + 2
ans = 1001001001
for i in a:
    if i < 0:
        pass
    else:
        ans = min(ans,i)

print(ans)


Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const string EMP = " ";
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

int main(){
  ull n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  ll mn = min({a,b,c,d,e});
  ll ans = (n + mn -1) / mn + 4;
  cout << ans << endl;
  return 0;
}


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

int main(){
    char b;
    cin >> b;
    if(b == 'A') cout << "T" << "\n";
    else if(b == 'C') cout << "G" << "\n";
    else if(b == 'T') cout << "A" << "\n";
    else if(b == 'G') cout << "C" << "\n";
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
K=input()

L=[]

def dfs(n,depth):
    L.append(n)
    if depth==9: return
    ichi_no_kurai=n%10
    for i in range(max(0,ichi_no_kurai-1),min(ichi_no_kurai+2,10)):
        next=n*10+i
        dfs(next,depth+1)

for n in range(1,10):
    dfs(n,0)

L.sort()
print L[K-1]

Measured memory_bytes: 45084
K = int(input())
L = 0
if K % 7 == 0:
  L = 9*K//7
else:
  L = 9*K
  
ans = -1
s = 10
for i in range(1,L,1):
  if s % L == 1:
    ans = i
    break
  s = s % L * 10
print(ans)

Measured memory_bytes: 63200
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll s, a = 1e9;
    cin >> s;
    cout << 0 << " " << 0 << " " << a << " " << 1 << " " << (s % a ? a-s%a : 0) << " " << (s+a-1)/a << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }


vector<string> split(string str)
{
    vector<string> result;
    int cutAt;
    while( (cutAt = min(str.find_first_of(" "), min(str.find_first_of(","), str.find_first_of(".")))) != str.npos )
    {
        if(cutAt > 0)
        {
            result.push_back(str.substr(0, cutAt));
        }
        str = str.substr(cutAt + 1);
    }
    if(str.length() > 0)
    {
        result.push_back(str);
    }
	return result;
}


int main()
{
	string str;
	getline(cin, str);

	vector<string> sp = split(str), res;
	
	int flag = 0;
	rep(i, sp.size())
		if(2 < sp[i].size() && sp[i].size() < 7)
			cout << (flag++ ? " " : "") << sp[i];

	cout << endl;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
  
	string s, temp, str;
    cin >> s;
  	int k = 1;
    int n = s.length();
    temp = s[0];
  	for (int i = 1; i < n; ++i){
 		str = s[i];
    	if(str != temp)
        {k++; temp = str;}
      else
      {i++; 
        if(i<n) {temp = str + s[i]; k++;} 
      }
    }
  cout << k;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
    //long long int t,n,a,b,i,j,k,l,sum;
    string s;
    cin>>s;
    if(s[0]=='7'||s[1]=='7'||s[2]=='7')
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
int main()
{
	int a = 0, b = 0, c = 0, d = 0, e = 0, min = 0, ma = 0, ans = 0, ansb = 0, counta = 0,countb, crowdy[101] = {},  bu = 0;
	int reset = 0,w=0;
	char hairetu[200] = {};
	int number[10000], price[10000], sort[100000] = {}, kisu[10000] = { 100000 }, gusu[10000] = { 100000 };
	using namespace std;
	int x = 0, y = 0, z = 0, play[200] = {}, acount = 0, bcount = 0;
	std::string toki, tokit, fun,funt;
	cin >> a >> b;
	if (a % b == 0) {
		cout << 0 << endl;
	}
	else {
		cout << 1 << endl;
	}

	
}

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

int solve(vector<int> &v, int n, int k){
  ll dp[n+2][k+2];
  memset(dp, 0, sizeof dp);

  for(int j=0;j<=k;j++){
      dp[1][j]=(j>v[1])?0:1;
  }
    for(int i=2;i<=n;++i){
        for(int j=0;j<=k;++j){
            if(j==0){
                     dp[i][0]=dp[i-1][0];
            }
            else{
                dp[i][j]=  (1000000007+dp[i][j-1] + dp[i-1][j] - ((j-v[i]-1>=0)?dp[i-1][j-v[i]-1]:0))%1000000007;
            }
        }
    }
   return dp[n][k];


}
int main() {
    int n,k;
    cin>>n>>k;
    vector<int> v(n+1);
    for(int i=1;i<=n;++i){
        cin>>v[i];
    }
    cout<<solve(v,n,k);
    return 0;}

Measured memory_bytes: 83100
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int d = scan.nextInt();

		int l = a+b;
		int r = c+d;

		if(l>r) {
			System.out.println("Left");
		}else if(l<r) {
			System.out.println("Right");

	}else {
		System.out.println("Balanced");
	}
}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define RNG(i,from,to) for(ll i=(from); i<(ll)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vecll;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> void println(T e){ cout << to_string(e) << endl; }
template<typename T> void println(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void println(const vector<vector<T>>& vv){ for(const auto& v : vv){ println(v); } }
template<typename Iter> void println(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
template<typename T> T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; }
template<typename T> T mod_inv(T x, const T &p) { return mod_pow(x, p-2, p); }
const ll DVSR = 1e9+7;

int main(int argc, char const *argv[])
{

  ll N; cin >> N;

  ll pat = 0;
  RNG(i, 1, N+1) {
    ll cnt = 0;
    ll current = i;
    RNG(x, 1, (ll)floor(sqrt(i))+1) {
      ll tmp1 = current - x*x;
      if (tmp1 > 0) {
        RNG(y, 1, (ll)floor(sqrt(tmp1))+1) {
          ll tmp2 = tmp1 - y*y - x*y;
          if (tmp2 > 0) {
            RNG(z, 1, 100) {
              ll mul = (y+x)*z + z*z;
              if (tmp2 == (y+x)*z + z*z) cnt += 1;
              if (mul > tmp2) break;
            }
          }
        }
      }
    }
    cout << cnt << endl;
  }
  return 0;
}


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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Ostream,typename Container>
Ostream& operator<<(Ostream& os,const Container& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

bool solve(vs ss)
{
	ss.erase(unique(all(ss)),end(ss));
	vvi d(26,vi(26));
	rep(i,26) d[i][i]=0;
	rep(i,ss.size()-1){
		const string &s1=ss[i],&s2=ss[i+1];
		for(int j=0;;j++){
			if(j==s2.size()) return false;
			if(j==s1.size()) break;
			if(s1[j]!=s2[j]){
				int u=s1[j]-'a',v=s2[j]-'a';
				d[u][v]=1;
				break;
			}
		}
	}
	rep(k,26) rep(i,26) rep(j,26) d[i][j]|=d[i][k]&d[k][j];
	rep(i,26) if(d[i][i]) return false;
	return true;
}

int main()
{
	for(int n;cin>>n && n;){
		vs ss(n);
		rep(i,n) cin>>ss[i];
		cout<<(solve(ss)?"yes":"no")<<endl;
	}
}

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

int main() {
	int n;

	cin >> n;
	
	if ((n / 10) % 111 == 0) {
		cout << "Yes" << endl;
	}

	else if (((n % 1000) % 111) == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3140
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramE
    {
        static void Main()
        {
            int n = NextInt;
            var array = IntList;
            var inc = Enumerable.Repeat(0L, n).ToArray();
            var dec = Enumerable.Repeat(0L, n).ToArray();

            for (int i = 0; i < n; i++)
            {
                if (i + array[i] < n) inc[array[i] + i]++;
                if (i - array[i] >= 0) dec[i - array[i]]++;
            }

            System.Console.WriteLine(Enumerable.Range(0, n).Sum(i => inc[i] * dec[i]));
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 46896
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = (ll) 1e18;
int main()
{
  ll a,b;
  cin >> a >> b;
  cout << max({a+b,a-b,a*b}) << endl;
  return 0;
}

Measured memory_bytes: 3544
from collections import defaultdict

N = int(input())
S = defaultdict(dict)
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        xi, yi = map(int, input().split())
        S[i][xi - 1] = yi

ans = 0
for i in range(1 << N):
    possible = True
    c = 0
    for j in range(N):
        if i >> j & 1:
            c += 1
            for xi, yi in S[j].items():
                if i >> xi & 1 != yi:
                    possible = False
                    break
    if possible:
        ans = max(ans, c)
print(ans)


Measured memory_bytes: 3316
n = int(input())
l = list(map(int, input().split()))

from heapq import *

heapify(l)

for i in range(n-1):
    tmp1 = heappop(l)
    tmp2 = heappop(l)
    heappush(l, (tmp1+tmp2)/2)
print(l[0])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 15;
bool vis[MAXN];
int main() {
#ifdef CitricAcid
    freopen ("input.txt", "rt", stdin);
#endif

    int n;
    scanf("%d", &n);
    ll res = 7, tmp = 7;
    bool legal = false;
    for(int i = 1; true; i++) {
        int t = res % n;
        if(vis[t]) break;
        if(t == 0) {
            legal = true;
            printf("%d\n", i);
            break;
        }
        vis[t] = true;
        tmp = tmp * 10 % n;
        res = (res + tmp) % n;
    }
    if(!legal) printf("-1\n");

#ifdef CitricAcid
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
/*
# author : CitricAcid
# date : 2020/08/03
*/

Measured memory_bytes: 4676
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
	int n;
	cin>>n;
	int a[n+1],b[n+1],sum;
	cin>>a[1];
	sum=a[1];
	for(int i=2;i<=n;i++){
		cin>>a[i];
		sum=sum^a[i];
	}
	for(int i=1;i<=n;i++){
		b[i]=sum^a[i];
		cout<<b[i]<<" ";
	}
	return 0;
}


Measured memory_bytes: 6672
#include<bits/stdc++.h>
using namespace std;
char s[1005],t[1005];
int main(){
	scanf("%s%s",s,t);
	int ans=1e5,l1=strlen(s),l2=strlen(t);
	for(int i=0;i<=l1-l2;i++){
		int w=0;
		for(int j=0;t[j];j++)w+=(s[i+j]!=t[j]);
		ans=min(ans,w);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 3824