akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int b[3][3];
    for (int i = 0 ; i < 3 ; i++) {
        for (int j = 0 ; j < 3 ; j++) {
            cin >> b[i][j];
        }
    }
    set<int>st;
    int t;
    cin >> t;
    while(t--) {
        int add;
        cin >> add;
        st.insert(add);
    }
    for (int i = 0 ; i < 3 ; i++) {
        for (int j = 0 ; j < 3 ; j++) {
            if(st.count(b[i][j])) {
                b[i][j] = 1;
            }
            else {
                b[i][j] = 0;
            }
        }
    }
    for (int i = 0 ; i < 3 ; i++) {
        int cnt = 0;
        for (int j = 0 ; j < 3 ; j++){
            if(b[i][j]) {
                cnt++;
            }
        }
        if (cnt == 3) {
            cout << "Yes\n";
            exit(0);
        }
        cnt = 0;
        for (int j = 0 ; j < 3 ; j++){
            if(b[j][i]) {
                cnt++;
            }
        }
        if (cnt == 3) {
            cout << "Yes\n";
            exit(0);
        }
    }
    if(b[0][0] && b[1][1] && b[2][2]) {
        cout << "Yes\n";
        exit(0);
    }
    if(b[0][2] && b[1][1] && b[2][0]) {
        cout << "Yes\n";
        exit(0);
    }
    cout << "No\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vll vec;
  rep(i,n) {
    string t = "";
    t += s[i];
    int m = stoi(t);
    vec.push_back(m);
  }
  ll ans = 0;
  rep(i,1<<n) {
    if(!((i>>(n-1))&1)) continue;
    vll v = vec;
    ll num = 0;
    rep(j,n) {
      num *= 10;
      num += v[j];
      if(i>>j&1) {
        ans += num;
        num = 0;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll int,ll int>
#define pb push_back
#define sbit __builtin_popcount
#define vec vector <int>
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define bg begin()
#define en end()
#define endl "\n"
#define ff first
#define ss second
#define all(x) x.bg,x.en
#define sz(a) (int)a.size()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define sp(x) setprecision(x)
#define fill(a,b) memset(a,b,sizeof(a))
#define fr(i,n) for(int i=0;i<n;i++)
#define rp(i,a,b) for(int i=a;i<b;i++)
#define rr(i,a,b) for(int i=a;i>=b;i--)
#define ft(it,x) for(auto it : x)
#define dbg(x) cerr<<#x<<" "<<x<<endl;
#define dbga(arr,n) cerr<<#arr<<": "; rep(tt,0,n)cerr<<arr[tt]<<" "; cerr<<endl;
#define mapi map<int,int>
#define mapl map<ll int,ll int>
#define val_at(x) find_by_order(x)
#define idx_of(x) order_of_key(x)
#define scni(x) scanf("%d",&x)
#define prt(x) printf("%d\n",x)
#define test(t) int t;cin>>t;while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define val_at(x) find_by_order(x)
#define idx_of(x) order_of_key(x)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> myset;
const int mod=1e9+7;
const int mex=1e6+1;
inline ll power(ll a,ll b)
{
    ll ans=1,temp=a;
    while(b!=0)
    {
        if(b&1)
        ans=ans*temp;
        ans=ans%mod;
        temp=temp*temp;
        temp=temp%mod;
        b/=2;
    }
    return ans;
}
int pr[mex];
vec prime;
inline void seive()
{
    rp(i,2,mex) pr[i]=1;
    for(int i=2;i*i<mex;i++)
    {
        if(pr[i])
        for(int j=i*i;j<mex;j+=i)
        pr[j]=0;
    }
    vec prime;
    rp(i,2,mex)
    {
        if(pr[i]) prime.pb(i);
    }
}
ll int xx,xy,d1;
void exeu(ll int a1,ll int b1)
{
    if(b1==0)
    {
        xx=1;
        xy=0;
        d1=a1;
    }
    else
    {
        exeu(b1,a1%b1);
        ll int temp=xx;
        xx=xy;
        xy=temp-(a1/b1)*xy;
    }
}
ll int modinv(ll int A,ll int M)
{
    exeu(A,M);
    return (xx%M+M)%M;
}
int main()
{
    fast
    int m,n;
    cin>>m>>n;
    fr(i,max(m,n)) cout<<min(m,n);
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n, a, b;
    string s;    
    cin >> n >> a >> b >> s;

    vector<bool> ans(n, false);
    int cnt = 1;
    int x = 1;
    rep(i, n){
        if(s[i] == 'a' && cnt <= a+b){
            ans[i] = true;
            cnt++;
        }
        
        if(s[i] == 'b' && cnt <= a+b && x <= b){
            ans[i] = true;
            x++;
            cnt++;
        }

        //cout << cnt  << " " << x << endl;

    }

    rep(i, n){
        if(ans[i]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }


    return 0;
}

Measured memory_bytes: 848
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <sstream> 
#include <cctype>
#include <stack>
#include <queue>
#include <cstring>
#include <map>
 
using namespace std;

int main(){

	long long q,h,s,d,n;
	cin>>q>>h>>s>>d>>n;

	long long one=q*4;
	one=min(one,h*2);
	one=min(one,s);

	long long res=0;
	if(n%2){
		n--;
		res=min(n*one,n/2*d )+one;
	}else{
		res=min(n*one,n/2*d);
	}

	cout<<res<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int a,b,c,d;
  double f;
  scanf("%d%d",&a,&b);
  c=a/b;
  d= a%b;
  f=(double)a/(double)b;
  printf("%d %d %f\n",c,d,f);
  return 0;
}



Measured memory_bytes: 2696
n,m,l=map(int,input().split())
a=[]
b=[]
for i in range(n):
    a+=[list(map(int,input().split()))]

for i in range(m):
    b+=[list(map(int,input().split()))]
  
c=[]
c=[[sum(a[i][k]*b[k][j] for k in range(m))for j in range(l)] for i in range(n)]
[print(" ".join(list(map(str,c[i])))) for i in range(n)]

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

int n, O[1000000], I[1000000], a, b;
char s[1000001];
bool ok(int t) {
	if (a < t || b < t)return 0;
	int p = n;
	rep(i, t) {
		p = min(p - 1, O[i] - 1);
		while (0 <= p && (s[p] == 'O' || (s[p] == 'I'&&p >= I[t - 1])))p--;
		if (p < 0)return 0;
	}
	return 1;
}
int main() {
	scanf("%d%s", &n, s);
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'I')I[a++] = i;
		if (s[i] == 'O'&&b < a)O[b++] = i;
	}
	int l = 0, r = n / 3;
	while (l != r) {
		int t = (l + r) / 2;
		if (r - l == 1)t = r;
		if (ok(t))l = t;
		else r = t - 1;
	}
	printf("%d\n", l);
}

Measured memory_bytes: 7604
import sys


# input = sys.stdin.readline

def main():
    S = input()
    if S == "SUN":
        print(7)
    elif S == "MON":
        print(6)
    elif S =="TUE":
        print(5)
    elif S =="WED":
        print(4)
    elif S =="THU":
        print(3)
    elif S =="FRI":
        print(2)
    else:
        print(1)


if __name__ == "__main__":
    main()

Measured memory_bytes: 8884
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

//gcd
template<typename T>
T gcd(T a, T b) {
    return b ? gcd(b, a%b) : a;
}

int main() {
    int k; cin >> k;
    ll sum = 0;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int a = 0; a < k; a++) {
                sum += gcd(i + 1, gcd(j + 1, a + 1));
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
	#define dbg(x) cout << #x << " : " << x << endl;
#else 
	#define dbg(x)
#endif

#define int long long
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 200010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x, y;
    cin >> n >> x >> y;
    vi cnt(n - 1, 0);
    fi(1, n + 1) {
    	fj(i + 1, n + 1) {
    		cnt[min(j - i, abs(x - i) + 1 + abs(y - j)) - 1]++;
    	}
    }
    fx(num, cnt)
    	cout << num << '\n';
}

Measured memory_bytes: 256
import java.util.*;class Main{public static void main(String[]z){Scanner s=new Scanner(System.in);for(int a[][]=new int[10][10],m,n,i,j,u,v,r=Integer.MAX_VALUE/2;(m=s.nextInt())>0;System.out.println(u+" "+m)){for(int[]b:a)Arrays.fill(b,r);for(i=u=n=0;m-->0;n=n>i?n:i,n=n>j?n:j)a[i=s.nextInt()][j=s.nextInt()]=a[j][i]=s.nextInt();for(++n;++m<n;)for(i=0;i<n;++i)for(j=0;j<n;++j)a[i][j]=Math.min(a[i][j],a[i][m]+a[m][j]);for(m=r;i-->0;){for(j=v=0;j<n;++j)v+=i!=j?a[i][j]:0;if(m>=v){u=i;m=v;}}}}}

Measured memory_bytes: 12000
require 'scanf'
require 'matrix'

while str = STDIN.gets
    vmin=str.scanf("%f")
    vmin=vmin[0]
    t=vmin/9.8
    y=4.9*t*t
    n=y/5.0+1.0
    n=(n+1.0).to_i #ceil
    print n,"\n"
end

Measured memory_bytes: 6748
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int n, m; cin >> n >> m;
	int maxl = 0, minr = 100005;
	for (int i = 0; i < m; ++i) {
		int l, r; cin >> l >> r;
		maxl = max(maxl, l);
		minr = min(minr, r);
	}
	if (maxl <= minr)cout << minr - maxl + 1 << endl;
	else cout << 0;

	return 0;
}

Measured memory_bytes: 256
/*
        karmany evadhikaras te
        ma phalesu kadacana 
        ma karma-phala-hetur bhur
        ma re sango'stv akarmani (B.G.-2.47)
 
Translation:
        Lord Krsna to Arjuna.
You have a right to perform your prescribed duty, 
but you are not entitled to the fruits of action. 
Never consider yourself the cause of the results of your activities, 
and never be attached to not doing your duty.    
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200005;
const ll mod = 1e9+7;
#define ld long double
#define PI 3.14159265358979323846
const int X = 200005;

void flash()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);
}

//3. Structure or classes
//3. Ends here

//1. Data structures declaration here
ll a[X];
ll b[X];
//1. Ends here

//2. Extra Functions here
//2. Ends here


void solve();
int32_t main()
{
    flash();
    int t;
    t = 1;
    //cin>>t;
    for (int zz = 0; zz < t; zz++)
    {
        solve();
        //cout<<"\n";
    }
    return 0;
}

void solve()
{
    char c;
    cin>>c;
    if(c>='a' && c<='z')cout<<"a";
    else cout<<"A";
    return;
}



Measured memory_bytes: 3636
def gcds(*numbers):
    from math import gcd
    from functools import reduce
    return reduce(gcd, numbers)

def lcms(*numbers):
    from math import gcd
    from functools import reduce
    def lcm_base(x, y):
        return x // gcd(x, y) * y
    return reduce(lcm_base, numbers)

def build_inv(N=10**5, P=10**9+7):
    inv = [0, 1]
    for i in range(2, N + 1):
        inv.append((-inv[P % i] * (P // i)) % P)
    return inv

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    invs = build_inv(10**6, MOD)
    target = lcms(*A)
    print(target*sum(map(lambda x: invs[x], A))%MOD)

    
if __name__ == "__main__":
    resolve()



Measured memory_bytes: 145916
M = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]

    print(solve(m, n, 10 ** 9 + 7))

def solve(m, n, mod):
    r = 1

    for _, c in get_prime_factors(m):
        r = r * mod_comb(c + n - 1, c, mod) % mod
    return r

def mod_comb(n, k, m):
    r = 1
    for i in range(1, k + 1):
        r = r * (n - k + i) * mod_inv(i, m) % m
    return r

def mod_inv(n, m):
    r0, r1 = n, m
    x, y, u, v = 1, 0, 0, 1

    while r1:
        k, r0, r1 = r0 // r1, r1, r0 % r1
        x, y, u, v = u, v, x - k * u, y - k * v

    if r0 != 1:
        raise ValueError

    return x

def get_prime_factors(n):
    from itertools import count, takewhile
    r = n

    for i in takewhile(lambda x: x * x <= r, count(2)):
        c = 0
        while r % i == 0:
            c += 1
            r //= i
        yield i, c

    if r != 1:
        yield r, 1

main()


Measured memory_bytes: 3064
<?php

$size = trim(fgets(STDIN));
$count = 1;
$array[0] = (int)trim(fgets(STDIN));

//入力された値が、$arrayに格納されていなければ格納し、$countを加算する
for($i = 0; $i < $size-1; $i++){
    $newWord = (int)fgets(STDIN);
    if(in_array($newWord, $array) === false){
        $array[] = $newWord;
        $count += 1;
    }
}

echo($count);

?>

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

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> r(n, 0);
	for (int i=0; i<m; i++){
		int a, b;
		cin >> a >> b;
		r[a-1]++;
		r[b-1]++;
	}
	for (int i=0; i<n; i++){
		cout << r[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    if(k==0)return cout<<(n*n)<<endl,0;
    ll ans=0;
    for(ll i=k+1;i<=n;i++){
            ans+=(i-k)*(n/i);
            ll temp=n%i;
            ans+=max(0LL,temp-k+1);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin>>N;
	string ans = "";
	int sign = -1;
	while(N!=0){
		if(N%(-2)==0){
			ans.push_back('0');
		}else{
			ans.push_back('1');
			N=N+sign;
		}
		sign *= -1;
		N=N/2;
	}
	reverse(ans.begin(),ans.end());
	if(ans=="")ans="0";
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

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

        final int n = sc.nextInt();
        final int x = sc.nextInt();

        final int[] m = new int[n];
        int used = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            m[i] = sc.nextInt();
            used += m[i];
            min = Math.min(min, m[i]);
        }

        System.out.println(m.length + (x - used) / min);
    }
}


Measured memory_bytes: 21844
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        String s = sc.next();
        int ans=1;
        
        for(int i=1; i<n; i++){
            if(s.charAt(i-1)!=s.charAt(i)){
                ans++;
            }
        }
        
        System.out.println(ans);
   }
}


Measured memory_bytes: 39404
n = int(input())

l = list(map(int,input().split()))

l.reverse()

x = 0

sum_x = []

for i in range(n-1):
    x += l[i]
    sum_x.append(x)

sum_y = [sum(l)]*(n-1)

for i in range(n-1):
    sum_y[i] -= sum_x[i]
    
abs_xy = []

for i in range(n-1):
    abs_xy.append(abs(sum_x[i]-sum_y[i]))

print(min(abs_xy))

Measured memory_bytes: 90748
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N=I()
    XY=LLIN(N)
    MAX_XY = 10**5+1
    uf=UnionFind((MAX_XY)*2)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    """ 
    http://drken1215.hatenablog.com/entry/2019/06/23/004700
    ・二部グラフにして
    ・連結成分ごとに
    ・完全二部グラフにするように辺を追加する(この二部グラフの辺(x,y)はグリッド上の点(x,y)に対応する)
    """
    

    for x,y in XY:
        unite(x,y+MAX_XY)
    
    cnt_x = defaultdict(int)
    cnt_y = defaultdict(int)
    
    for x in range(MAX_XY):
        cnt_x[ get_root(x) ] += 1
    for y in range(MAX_XY,2*MAX_XY):
        cnt_y[ get_root(y) ] += 1
    
    ans = 0
    #rootが根の連結成分に含まれる(X座標の数)*(Y座標の数)だけ辺がある(もとからあるものは後で引く)
    for root in range(2*MAX_XY):
        ans += cnt_x[root] * cnt_y[root]
    
    ans -= N #もとからN個の辺はある
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 136304
#include <bits/stdc++.h>
#define Maxn 400007
using namespace std;
int a[Maxn],c[Maxn],n;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		c[i]=a[i];
	}
	sort(c+1,c+n+1);
	for (int i=1;i<=n;i++)
		if (a[i]<=c[n/2]) printf("%d\n",c[n/2+1]); else printf("%d\n",c[n/2]);
	return 0;
}


Measured memory_bytes: 3712
import java.util.Scanner;

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

	int n = scan.nextInt();
	if(n % 10 == 9){
	    System.out.println("Yes");
	}else if(n / 10 == 9){
	    System.out.println("Yes");
	}else{
	    System.out.println("No");
	}
    }
}


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

int main(){
    long long N, A, B;
    cin >> N >> A >> B;

    long long i = N / (A + B);
    long long mod = N % (A + B);
    long long ans;
    if(mod <= A){
        ans = i * A + mod;
    }
    else ans = i * A + A;
    cout << ans << endl;
}

Measured memory_bytes: 3576
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
const int MaxN = 1e5;
typedef long long LL;
using namespace std;
queue <int> que;
struct NODE{
	int x , y , w;
	int pos;
}a[MaxN + 5] , b[MaxN + 5];
bool cmp(NODE x , NODE y){
	return x.x < y.x;
}
bool cmp1(NODE x , NODE y){
	return x.y < y.y;
}
bool cmp2(NODE x , NODE y){
	return x.w < y.w;
}
int n  , fa[MaxN + 5];
int Find(int x){
	if(x == fa[x]) return x;
	else return fa[x] = Find(fa[x]);
}
int main()
{
	while(~scanf("%d" , &n)){
		for(int i = 1;i <= n;i++) fa[i] = i;
		for(int i = 1;i <= n;i++){
			scanf("%d%d" , &a[i].x , &a[i].y);
			a[i].pos = i;
		}
		int tot = 0;
		sort(a + 1 , a + n + 1 , cmp);
		for(int i = 2;i <= n;i++){
			int w = a[i].x - a[i - 1].x;
			int u = min(a[i - 1].pos , a[i].pos) , v = max(a[i].pos , a[i - 1].pos);
			b[++tot].x = u;
			b[tot].y = v;
			b[tot].w = w;
		}
		sort(a + 1 , a + n + 1 , cmp1);
		for(int i = 2;i <= n;i++){
			int w = a[i].y - a[i - 1].y;
			int u = min(a[i - 1].pos , a[i].pos), v = max(a[i].pos , a[i - 1].pos);
			b[++tot].x = u;
			b[tot].y = v;
			b[tot].w = w;
		}
		sort(b + 1, b + tot + 1 , cmp2);
		LL ans = 0;
		for(int i = 1;i <= tot;i++){
			int x = Find(b[i].x) , y = Find(b[i].y);
			if(x != y){
				fa[x] = y;
				ans += b[i].w;
			}
		}
		printf("%lld\n" , ans);
	}
}

Measured memory_bytes: 3712
#include <iostream>

using namespace std;

int main() {
	int N;
	long long A[100010];
	long long M = 1;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	
	for (int i = 0; i < N; i++) {
		if (A[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
	}

	for (int i = 0; i < N; i++) {
		if (A[i] > 1000000000000000000 / M) {
			cout << -1 << endl;
			return 0;
		}
		M *= A[i];
	}

	cout << M << endl;

	return 0;
}


Measured memory_bytes: 4424
h=int(input())
w=int(input())
n=int(input())
flg,cnt,pn=0,0,0
mh,mw=h,w
hcnt,wcnt=h,w
while pn<n:
  if mh==mw:
    if hcnt>wcnt:
      flg=0
    else:
      flg=1
  elif mh>mw:
    flg=1
  else:
    flg=0
  if flg==1:
    pn+=mh
    wcnt-=1
    mw-=1
    cnt+=1
  else:
    pn+=mw
    hcnt-=1
    mh-=1
    cnt+=1    
print(cnt)

Measured memory_bytes: 38384
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

bool comp(pair<int,int> a, pair<int,int> b){
  return a.second<b.second;
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n;
  cin>>n;
  vector<pair<int,int>> v(n);
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    v[i]=make_pair(a,b);
  }
  std::sort(v.begin(), v.end());

  lint left;
  bool left_kirisute=false;
  if(n%2==1){
    left=v[n/2].first;
  }else{
    left=(v[n/2-1].first+v[n/2].first)/2;
    if((v[n/2-1].first+v[n/2].first)%2!=0){
      left_kirisute=true;
    }
  }

  lint right;
  bool right_kirisute=false;
  std::sort(v.begin(),v.end(),comp);
  if(n%2==1){
    right=v[n/2].second;
  }else{
    right=(v[n/2-1].second+v[n/2].second)/2;
    if((v[n/2-1].second+v[n/2].second)%2!=0){
      right_kirisute=true;
    }
  }

  if(n%2==1){
    cout<<right-left+1<<endl;
  }else{
    if(left_kirisute==right_kirisute){
      cout<<(right-left)*2+1<<endl;
    }else if(left_kirisute){
      cout<<(right-left)*2<<endl;
    }else{
      cout<<(right-left)*2+2<<endl;
    }

  }

  return 0;
}




Measured memory_bytes: 4792
#include<iostream>

using namespace std;

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

	int a[n],b[n];
	for (int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	long long ans=0;
	long long aa;
	for (int i = n - 1; i >= 0; i--) {
		aa = a[i] + ans;
		if (aa % b[i] == 0) continue;
		
		if (aa > b[i]) {
			ans+=b[i] * (aa / b[i] + 1) - aa;
		}
		else {
			ans += b[i] - aa;
		}
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>
#include <list>
using namespace std;

// int main() {
//   int n,k;
//   cin >> n >> k;
//   int a[k][n];
//   int res=0;
//   int d[k];
//   for(int i = 0; i < k; ++i){
//     cin >> d[i];
//     for(int j=0; j < d[i]; ++j){
//       cin >> a[i][j];
//     }
//   }
//   int s[n];
//   for(int i = 0; i < n; ++i){
//     for(int j = 0; j < n; ++j){
//       s[a[i][j]]++;
//     }
//   }
//   for(int i = 0; i < n; ++i){
//     if(s[i] == 0){
//       res++;
//     }
//   }
//   cout << res << endl;
// }

int N, K;
vector<int> d;
vector<vector<int>> A;

void input() {
  cin >> N >> K;
  d.resize(K);
  A.resize(K, vector<int>());
  for(int i = 0; i < K; i++) {
    cin >> d[i];
    A[i].resize(d[i]);
    for(int j = 0; j < d[i]; j++) {
      cin >> A[i][j];
    }
  }
}

void solve() {
  int ans = 0;
  for(int i = 1; i <= N; i++) {
    bool have = false;
    for(auto v : A) {
      for(auto p : v) {
        if(p == i) have = true;
      }
    }
    if(!have) ans++;
  }
  cout << ans << endl;
}

int main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

int main(){
    int a,b,t,count=0;
    cin>>a>>b>>t;
    while(t>=a){
        t-=a;
        count+=b;
    }

    cout<<count<<endl;
    return 0;

}

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

void s_out(string s){
	for(int i=0;i<s.size();i++){
		cout<<s[i];
		if(i+1==s.size())cout<<"\n";
		else cout<<" ";
	}
}

string l="012345678954321";
int t[10][2]={{0,0},{1,14},{2,13},{3,12},{4,11},{5,10},{6,6},{7,7},{8,8},{9,9}};

int main(){
	
	int n;
	cin>>n;
	for(;n;n--){
		string s1="",s2="";
		int a1=0,a2=0;
		
		char s,g;
		cin>>s>>g;
		int st;
		
		st=t[s-'0'][0];
		while(1){
			s1+=l[st];
			if(l[st]==g)break;
			a1++;
			st++;
			if(st>14)st=0;
		}
		
		st=t[s-'0'][1];
		while(1){
			s2+=l[st];
			if(l[st]==g)break;
			a2++;
			st++;
			if(st>14)st=0;
		}
		
		
		
		
		if(a1<a2)s_out(s1);
		else s_out(s2);
	}
	
	
	return 0;
}


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

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

struct edge {
        int to, cost;
};

vector<edge> g[101010];
long long depth[101010];

void dfs(int v, int prev, long long d) {
        depth[v] = d;
        for (auto u : g[v]) if (u.to != prev) {
                dfs(u.to, v, d + u.cost);
        }
}

int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c;
                cin >> a >> b >> c;
                a --, b --;
                g[a].push_back((edge) { b, c });
                g[b].push_back((edge) { a, c });
        }
        int q, k;
        cin >> q >> k;
        k --;
        dfs(k, -1, 0);
        for (int i = 0; i < q; i ++) {
                int x, y;
                cin >> x >> y;
                x --, y--;
                cout << depth[x] + depth[y] << endl;
        }
        return 0;
}



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

	#define E "\n"
	#define int long long 
	#define f(i,l,n) for(int i=l;i<n;i++)




	int Pow(int b, int n) {
	    int ans=1,x=b; //here ans and x should be long long 
	    while(n)
	    {
	        if(n%2==1) ans=((ans*x));
	        x=((x*x));
	        n=n>>1;
	    }
	    if(x==0) ans=0;
	    return (int)ans;
	}

	int fifth(int n)
	{
		if(n==0 || n==1) return 1;
		n=abs(n);
		int low=1,high=sqrt(sqrt(n));

		while(low<=high)
		{
			int mid=(low+high)/2;
			int p=Pow(mid,5);
			if(p==n) return mid;
			else if(p>n) high=mid-1;
			else low=mid+1;
		}
		return 0;
	}
	
	int x;
	bool chk(int a,int b)
	{
		int d=fifth(b);
		if(d==0 and b!=0) return false;
		if(b<0) d=-d;
		cout<<a<<" "<<d<<E;
		exit(0);
		
	}
	int solve()
	{
		
		cin >> x;

		int i=1;
		if(x==1)return  cout<<"1 0",0;
		for(int i=-1000;i<=1000;i++)
		{
			int b=x-Pow(i,5);
			if(chk(i,-b)) return cout<<i<<" "<<b,0;
		}

		return 0;
	}

	int32_t main()
	{
	  int t=1;
	  //cin >>t;
	  while(t--) solve();

	}

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

using namespace std;

char a[102],b[102];

int main(){
	cin>>a;
	cin>>b;
	int la=strlen(a),lb=strlen(b);
	if(la>lb){
		cout<<"GREATER";
		return 0;
	}
	if(la<lb){
		cout<<"LESS";
		return 0;
	}
	for(int i=0;i<la;i++)
	{
		if(a[i]>b[i]){
		cout<<"GREATER";
		return 0;
	}
		if(a[i]<b[i]){
		cout<<"LESS";
		return 0;
	}

	}
	cout<<"EQUAL";
	return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;

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

        while(true){
            int i,j=0;
            String a =sc.nextLine();
            if(a.equals(".")){
                break;
            }

            int[] rec=new int[a.length()];

            for(i=0;i<a.length();i++){
                String fch=String.valueOf(a.charAt(i));
                if(fch.equals("(")){
                    j++;
                    rec[j]=1;
                }else if(fch.equals(")")){
                    if(rec[j]==1){
                        j--;
                    }else{
                        rec[0]=1;
                        break;
                    }
                }else if(fch.equals("[")){
                    j++;
                    rec[j]=2;
                }else if(fch.equals("]")){
                    if(rec[j]==2){
                        j--;
                    }else{
                        rec[0]=1;
                        break;
                    }
                }
            }
            if(j==0 && rec[0]==0){
                System.out.println("yes");
            }else{
                System.out.println("no");
            }
        }
        sc.close();
    }
}


Measured memory_bytes: 56688
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) (a).size() 
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<=n;i++)
#define ford(i,n) for(int i=n;i>=0;i--) 
#define REP(i,a,n) for(int i=a;i<n;i++)
#define foreach(itr,c) for(__typeof((c).begin(),(c).end())itr=c.begin();itr!=c.end();itr++) 
#define fill(a,b) memset(a,b,sizeof(a))
#define re return
#define INF 1e9
#define LINF 1e18
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi > vpi; 
int main(){
	int a,b;
	cin>>a>>b;
	if(b>=a){
		cout<<"unsafe";
	} 
	else{
		cout<<"safe";
	}
	re 0;
}

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

#define ff first
#define ss second
#define PI acos(-1)
#define pb push_back
#define int long long
#define ld long double
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int MOD = (1e9)+7;
const int N = 55;

int n,m,q,ans = 0;
int a[N],b[N],c[N],d[N];
int arr[N];
int dp[N][N];

int check()
{
    int res = 0;
    for(int i=0;i<q;i++)if(arr[b[i]] - arr[a[i]] == c[i])res+=d[i];
    return res;
}

int rec(int id,int last)
{
    if(id == n)return check();
    int res = 0;
    for(int i=last;i<=m;i++)
    {
        arr[id] = i;
        res = max(res,rec(id+1,i));
    }
    return res;
}

signed main()
{
    FAST
    int tc=1;
    //cin>>tc;
    for(int ti=1;ti<=tc;ti++)
    {
        memset(dp,-1,sizeof(dp));
        cin>>n>>m>>q;
        for(int i=0;i<q;i++)
        {
            cin>>a[i]>>b[i]>>c[i]>>d[i];
            a[i]--;b[i]--;
        }
        cout<<rec(0,1)<<endl;
    }
    return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define n 500000
#define mem(arr) memset(arr, 0, sizeof(arr))
using namespace std;
typedef long long lli;
typedef double llf;
typedef pair<int, int> P;
void solve();
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int times = 1;
//	cin >> times;
	for(int i=0; i<times; i++)
	{
		solve();
		cout << '\n';
	}
	return 0;
}

int a, b, c, d, e, f, g, h;
int arr[n + 50], arr1[n + 50], arr2[n + 50];

//type here

void solve()
{
	lli a, b; cin >> a >> b;
	lli pre[a + 50] = {0};
	for(int i=1; i<=a; i++)
	{
		lli tmp; cin >> tmp;
		pre[i] = pre[i - 1] + tmp;
	}
	lli left = 0, ans = 0;
	map<lli, lli> M;
	M[0] = 1;
	for(int i=1; i<=a; i++)
	{
		if(i >= b)
		{
			M[(pre[left] - left + b) % b] --;
			left ++;
		}
		ans += M[(pre[i] - i + b) % b];
		M[(pre[i] - i + b) % b] ++;
//		cout << ans << '\n';
	}
	cout << ans << '\n';
}

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

int main(){
	int N, M;
	cin >> N >> M;
	bool problem[N] = {0};
	int solved = 0, penalty[N] = {0};
	int totalPenalty = 0;
	while(M-- > 0){
		int p;
		char S[2];
		cin >> p >> S;
		p--;
		
		if(!problem[p]){
			if(S[0] == 'A'){
				solved++;
				totalPenalty += penalty[p];
				problem[p] = true;
			}else{
				penalty[p]++;
			}
		}
	}
	
	cout << solved << " " << totalPenalty;
	return 0;
}

Measured memory_bytes: 768
#include <stdio.h>
 
int main(void) 
{	
	long int N,M;
	scanf("%ld %ld", &N,&M);
	if((N>=2) && (M>=2))
	printf("%ld", (N-2)*(M-2));
	
	if(N==1)
	{
		if(M>=2)
		printf("%ld", M-2);
		else
		printf("1");
	}
	else
	if(M==1)
	printf("%ld", N-2);
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;

int main(void)
{
    int a, b;
    int ans = 0;
    scanf("%d%d", &a, &b);

    printf("%d\n", a * b);
    return 0;
}

Measured memory_bytes: 1728
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <ctime>

using namespace std;
#define RN cout << "\r\n";
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long int ll;
typedef pair<ll, ll> P;

// combination
const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// GCD, LCM
ll gcd(ll a, ll b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    ll n, ans = 0;
    cin >> n;
    map<ll, ll> numbers;
    REP(i, n) {
        ll a;
        cin >> a;
        if (numbers.count(a)) {
            numbers[a] +=1;
        } else {
            numbers[a] =1;
        }
    }
    for (P p : numbers) {
        if (p.second % 2 != 0) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
int N,M;

string name[2003];
vector<int> G[2003];
int Gr[2003];

vector<string> cut_s(const string &s ){
  vector<string> v;
  int k=1;
  for(int i=1;i<(int)s.size();i++){
    if(s[i] == '/' ){
      v.push_back( s.substr(k,i-k) );
      k = i+1;
    }
  }
  v.push_back( s.substr(k) );
  return v;
}

int search(const vector<string> &s){
  int id = 0;
  for(int i=0;i<(int)s.size();i++){
    // cout << s[i] << " "<< id << " "<< name[id] << endl;
    bool f = false;
    if( s[i] == "." ){
      if( G[id].empty() ) return -1;
      continue; 
    }
    if( s[i] == ".." ){
      if( Gr[id] == -1 || G[id].empty() ) return -1;
      id = Gr[id];
      continue;
    }
    if( s[i] == "" ){
      if( G[id].empty() ) return -1;
      for(int j=0;j<(int)G[id].size();j++){
        int to = G[id][j];
        if( name[to] == "index.html" && G[to].empty() ) {
          id = to;
          f = true;
          break;
        }
      }
      if( !f ) return -1;
      continue;
    }
    
    for(int j=0;j<(int)G[id].size();j++){
      int to = G[id][j];
      if( name[to] == s[i] ) {
        id = to;
        f = true;
        break;
      }
    }
    if(!f) return -1;
  }
  //   cout << "last " << id << " " << name[id] << " "<< G[id].size() <<  endl;
  if( G[id].empty() ) return id;
  for(int i=0;i<(int)G[id].size();i++){
    int to = G[id][i];
    if( name[to] == "index.html" && G[to].empty() ) return to;
  }
  return -1;
}

int main(){
  while( cin >> N >> M && (N||M) ){
    int cnt = 0;

    memset(Gr,-1,sizeof(Gr));
    for(int i=0;i<=2000;i++) name[i] = "----";
    for(int i=0;i<=2000;i++) G[i].clear();

    for(int i=0;i<N;i++){
      string s; cin >> s;
      vector<string> c = cut_s( s );
      int id = 0;
      for(int i=0;i<(int)c.size();i++){
        bool f = false;
        for(int j=0;j<(int)G[id].size();j++){
          int to = G[id][j];
          if( name[to] == c[i] ) {
            id = to; f = true; break;
          }
        }
        if( f ) continue;
        
        G[id].push_back( ++cnt );
        Gr[cnt] = id;
        name[cnt] = c[i];
        id = cnt;

      }      
    }

    for(int i=0;i<M;i++){
      string s1, s2; cin >> s1 >> s2;
      vector<string> c1 = cut_s(s1);
      vector<string> c2 = cut_s(s2);
      int id1 = search(c1), id2 = search(c2);
      //  cout <<id1 << " - " << id2 << endl;
      if( id1 == -1 || id2 == -1 ) cout << "not found" << endl;
      else if( id1 != id2 ) cout << "no" << endl;
      else cout << "yes" << endl;
    }

  }
}

Measured memory_bytes: 1404
import math
import collections
import sys

#input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

a,b=MI()
print(a+b//2)

Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
using namespace std;
int main(){
  char b;
  cin >> b;
  if(b == 'A') cout << "T" << endl;
  else if(b == 'T') cout << "A" << endl;
  else if(b == 'G') cout << "C" << endl;
  else cout << "G" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#define SIZE 100005

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

struct UF
{
	int par[SIZE],rank[SIZE];
	ll sz[SIZE];
	int cnt[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=1;
			sz[i]=0;
		}
	}
	void ins(int v,ll x)
	{
		sz[v]=x;
	}
	int find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y])
		{
			par[x]=y;
			cnt[y]+=cnt[x];
			sz[y]+=sz[x];
		}
		else
		{
			par[y]=x;
			cnt[x]+=cnt[y];
			sz[x]+=sz[y];
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	void add(int v)
	{
		cnt[find(v)]++;
	}
	ll getsz(int v)
	{
		return sz[find(v)];
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
}uf;
ll X[SIZE];
PP edge[SIZE];

int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%lld",&X[i]);
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);a--,b--;
		edge[i]=PP(c,P(a,b));
	}
	sort(edge,edge+m);
	int ret=0;
	uf.init(n+2);
	for(int i=0;i<n;i++) uf.ins(i,X[i]);
	for(int i=0;i<m;i++)
	{
		P p=edge[i].second;
		uf.unite(p.first,p.second);
		uf.add(p.first);
		if(uf.getsz(p.first)>=edge[i].first)
		{
			int r=uf.find(p.first);
			ret+=uf.cnt[r];
			uf.cnt[r]=0;
		}
	}
	printf("%d\n",m-ret);
	return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long a,b,c;
}
g[2000];
int n,m;
long long s[2000];
bool cmp(long long a,long long b){
	return a>b;
}
int main(){
	cin>>n>>m;
	memset(s,0,sizeof(s));
	long long ans=-1e9;
	for(int i=1;i<=n;i++)
		cin>>g[i].a>>g[i].b>>g[i].c;
	for(int l=-1;l<=1;l+=2)
		for(int j=-1;j<=1;j+=2)
			for(int k=-1;k<=1;k+=2){
				for(int i=1;i<=n;i++){
					long long sum=0;
					if(l==1)sum+=g[i].a;
					else sum-=g[i].a;
					if(j==1)sum+=g[i].b;
					else sum-=g[i].b;
					if(k==1) sum+=g[i].c;
					else sum-=g[i].c;
					s[i]=sum;
				}
				sort(s+1,s+n+1,cmp);
				long long sum1=0;
				for(int i=1;i<=m;i++)
					sum1+=s[i];
				ans=max(ans,sum1);
			}
			cout<<ans;
			return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    //今から文字入力
   while(1)
   {
       int x;
       int y;
       cin>>x>>y;
       if(x>y)
       {
           swap(x,y);
       }
       if(x==0&&y==0) break;
       cout<<x<<" "<<y<<endl;
   }
    return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
int32_t main(){
	cin >> n;
	bool alleq = true;
	int ans = 0;
	int m = INT_MAX;
	for(int i=0; i<n; ++i){
		int a,b;
		cin >> a >> b;
		if(a != b) alleq = false;
		ans += a;
		if(a > b) m = min(m, b);
	}
	ans -= m;
	if(alleq) cout << 0;
	else cout << ans;
}


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

int main(){
	long long s;
	cin>>s;
	
	const int v=1000000000;
	
	int x=(v-s%v)%v;
	int y=(s+x)/v;
	
	cout<<"0 0 1000000000 1 "<<x<<" "<<y<<endl;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::{max,min};
fn main() {
    input! { 
        n: usize, t: i32,
        a: [i32; n],
    }
    let mut prefix_min = a[0];
    let mut pattern = 0;
    let mut height = 0;
    for i in 0..n {
        if a[i] < prefix_min {
            prefix_min = a[i];
        } else if a[i] - prefix_min == height {
            pattern += 1;
        } else if a[i] - prefix_min > height {
            pattern = 1;
            height = a[i] - prefix_min;
        }
    }
    println!("{}", pattern);
}



Measured memory_bytes: 4352
#include <iostream>

long int N = 0;

bool all(std::string target, std::string research){
    for (char c:research){
        auto it = target.find(c);
        if (it == std::string::npos){
            // 見つからなかったらFalse
            return false;
        }
    }
    return true;
}

long int shichiGoSan(long int x){
    if (x > N){
        return 0;
    }
    int ret = 0;
    if (all(std::to_string(x),"753")){
        ret = 1;
    } else {
        ret = 0;
    }
    int arr[] = {7, 5, 3};
    for (int y:arr){
        ret += shichiGoSan((x * 10) + y);
    }
    return ret;
}

int main(){
    std::cin >> N;
    std::cout << shichiGoSan(0) << std::endl;
    
    return 0;
}

Measured memory_bytes: 384
n, q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for i in range(q)]
ans = [0]
x = 0

for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        x += 1
    ans.append(x)

for i in lr:
    l = i[0]
    r = i[1]
    print(ans[r-1] - ans[l-1])


Measured memory_bytes: 31344