akhauriyash/Code-Regression huggingface dataset:
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1173&lang=jp
#include <iostream>
#include <string>
#include <stdlib.h>
#include <vector>
using namespace std;

string removeExceptParens(string);
bool isBalancedParens(string);

int main() {
	vector<string> lines;
	while (true) {
		string line = "";
		getline(cin, line);
		if (line == ".") {
			break;
		}
		lines.push_back(line);
	}

	for (vector<string>::iterator it = lines.begin(); it != lines.end(); it++) {
		string parenRemovedLine = removeExceptParens(*it);
		if (isBalancedParens(parenRemovedLine)) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}

	return 0;
}

string removeExceptParens(string str){
	string result = "";	
	for (string::iterator it = str.begin(); it != str.end(); it++) {
		if (*it == '(' || *it == ')' || *it == '[' || *it == ']') {
			result += *it;
		}
	}
	return result;
}

bool isBalancedParens(string str) {
//	cout << str << endl;
	if (str == "") {
		return true;
	}
	else {
		string::size_type paren1 = str.rfind("()");
		string::size_type paren2 = str.rfind("[]");
		if (paren1 == string::npos && paren2 == string::npos) {
			return false;
		}
		else {
			if (paren1 != string::npos) {
				str.replace((int)paren1, 2, "");
			}
			else if (paren2 != string::npos) {
				str.replace((int)paren2, 2, "");
			}
			return isBalancedParens(str);
		}
	}
}

Measured memory_bytes: 1696
#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define __TRUE "Yes"
#define __FALSE "No"
#define cout(x) cout << (x) << endl
#define MAX 100001
using namespace std;

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b > c+d) cout("Left");
  else if(a+b < c+d) cout("Right");
  else cout("Balanced");
}

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

namespace ABC155C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var sDict = new Dictionary<string, int>();

            for (var i = 0; i < N; i++)
            {
                var s = Console.ReadLine();
                int value;
                if (!sDict.TryGetValue(s, out value))
                    sDict.Add(s, 1);
                else
                    sDict[s] = value + 1;
            }

            var ansList = new SortedSet<string>(new Comparer());
            foreach (var kvp in sDict.OrderByDescending(x => x.Value))
            {
                if (ansList.Any() && kvp.Value != sDict[ansList.First()])
                    break;

                ansList.Add(kvp.Key);
            }
            //Console.WriteLine();
            Console.WriteLine(string.Join(Environment.NewLine, ansList));
        }

        class Comparer : IComparer<string>
        {
            public int Compare(string x, string y) => string.Compare(x, y, StringComparison.OrdinalIgnoreCase);
        }
    }
}


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

int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(int i=0; i<n-2; i++){
        if(s.at(i) == 'A' && s.at(i+1) == 'B' && s.at(i+2) == 'C'){
            ans++;
        }
    }
    cout << ans;
}

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

int n;
int c[21];
int v[21];

int Solve(int k)
{
	if (k == n)
		return 0;

	int ret = Solve(k + 1);
	ret = max(ret, Solve(k + 1) + v[k] - c[k]);
	return ret;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		scanf("%d", &v[i]);
	for (int i = 0; i < n; ++i)
		scanf("%d", &c[i]);
	cout << Solve(0);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        long count;
        long A = Integer.parseInt(scanner.next());
        long B = Integer.parseInt(scanner.next());
        long C = Integer.parseInt(scanner.next());

        if ( A + B + 1 >= C ){
            count = B + C;
        }else{
            count = B * 2 + A + 1;
        }

        System.out.println(count);
    }
}

Measured memory_bytes: 22608
import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n= sc.nextInt();
    int k=sc.nextInt();
    int count=0;
    for(int i=0;i<n;i++) {
      int temp = sc.nextInt();
      if(temp >=k) {
        count++;
      }
    }
    System.out.println(count);
}
}


Measured memory_bytes: 46568
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	int r;
	cin >> r;
	cout << 3*pow(r,2) << endl;
}

Measured memory_bytes: 256
fn main() {
    let scan = std::io::stdin();

    let mut line = String::new();

    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();

    let n: usize = vec[0].parse().unwrap_or(0);

    for i in 1..n+1 {
        if div3(i) || inculde3(i) {
            print!(" {}", i);                                                                                                                                                                                                                        }
    }
    println!("");                                                                                                                                                                                                                            }

fn inculde3(n: usize) -> bool {
    let mut m = n;
    while m != 0 {
        if m % 10 == 3 {
            return true;
        }
        m /= 10;
    }
    false
}

fn div3(n: usize) -> bool {
    if n % 3 == 0 {
        return true;
    }
    false
}


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

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

    vector<long long int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        a[i] %= m;
    }

    // cumulative sum
    for(int i=1; i<n; i++){
        a[i] += a[i-1];
        a[i] %= m;
    }

    sort(a.begin(),a.end());
    long long int ans = 0;
    long long int count = 1;
    for(int i=0; i<n; i++){
        if(a[i] == 0) ans += 1;

        if(i+1 < n && a[i+1] == a[i]) count += 1;
        else{
            ans += count * (count - 1) / 2;
            count = 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
A = [
    1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15,
    2, 2, 5, 4, 1, 4, 1, 51
]
print(A[int(input()) - 1])


Measured memory_bytes: 2940
import java.util.*;

public class Main
{
    static String ans;
    static int array[]=new int[10];
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();

        for (int i=0;i<n;++i)
        {
            for (int j=0;j<10;++j) { array[j]=sc.nextInt();}
            ans="YES";
            calc();
        }
    }

    public static void calc()
    {
        int a=0;
        int b=0;
        for (int i=0;i<10;++i)
        {
            if (array[i]>a){ a=array[i];}
            else if(array[i]>b) {b=array[i];}
            else { ans="NO";}
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 26216
#include <bits/stdc++.h>
#define x first
#define y second
#define y1 secondy1
#define rank tipa_rank
#define pb push_back
#define mp make_pair
#define pow10 tipa_pow10
#define ll long long
#define INF 1000000000
#define EPS 1e-9
#define EPS2 1e-8
#define PI acos(-1.0)
using namespace std;
int n , m  , q;
vector<vector<int> > g(100000);
int colour[100000];
int maxDist[100000];
vector<int> V;
int dist[100000];
int d[100000] , v[100000] , c[100000];
void bfs(int u , int c , int d)
{
	queue<int> q;
	q.push(u);
	dist[u] = 0;

	if(!colour[u])
		colour[u] = c;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		if(dist[u] == d)
			continue;
		for(int i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i];
			if(dist[v] == -1)
			{
				dist[v] = dist[u] + 1;
				if(maxDist[v] < d - dist[v])
				{
					maxDist[v] = d - dist[v];
					if(!colour[v])
						colour[v] = c;
					q.push(v);
				}
			}

		}
	}
	memset(dist , -1 , sizeof dist);
}
int main() {
	memset(dist , -1 , sizeof dist);
	memset(maxDist , -1 , sizeof maxDist);
	scanf("%d %d" , &n , &m);
	for(int i = 0; i < m; i++)
	{
		int u , v;
		scanf("%d %d" , &u , &v);
		u--;v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	scanf("%d" , &q);
	for(int i = 0; i < q; i++)
	{
		scanf("%d %d %d" , &v[i] , &d[i] , &c[i]);
		v[i]--;
	}
	for(int i = q - 1; i >= 0; i--)
	{
		if(maxDist[v[i]] < d[i])
		{
			bfs(v[i] , c[i] , d[i]);
		}
	}
	for(int i = 0; i < n; i++)
		printf("%d\n" , colour[i]);
}



Measured memory_bytes: 9208
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
if a < 0:
    if b < 0:
        ans = (b-a)*c
    else:
        ans = abs(a)*c+d+b*e
else:
    ans = (b-a)*e
print(ans)


Measured memory_bytes: 5588
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;
//|\_
//g++ -std=c++1z temp.cpp
//./a.out





int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    int n;
    while(1){
        cin>>n;
        if(n==0)break;
        int i,ans=INF;
        vector<int> v(n,0);
        rep(i,n)cin>>v[i];
        sort(v.begin(),v.end());

        rep(i,n-1)ans=min(ans,v[i+1]-v[i]);
        cout<<ans<<endl;
    }
//////////////////////////////////////////////////////
return 0;}



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

n, q = map(int, input().split())
s = input()
tds = [input().split() for _ in range(q)]
tds.reverse()

l = 0
r = n - 1

for t, d in tds:
    if s[l] == t and d == "L":
        l += 1
    if l > 0 and s[l - 1] == t and d == "R":
        l -= 1
    if s[r] == t and d == "R":
        r -= 1
    if r < n - 1 and s[r + 1] == t and d == "L":
        r += 1
    if l > r:
        break

print(r - l + 1)


Measured memory_bytes: 39348
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int m = sc.nextInt();
      	int[] city = new int[n];
      	int a, b;
      	for(int i = 0; i < m; i++){
        	a = sc.nextInt();
          	b = sc.nextInt();
          	city[a-1]++;
          	city[b-1]++;
        }
      	for(int i = 0; i < n; i++){
        	System.out.println(city[i]);
        }
    }
}

Measured memory_bytes: 35864
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500 + j*100 + k*50 == x:
                count += 1

print(count)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;

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

  const int L = LEN(s);

  int x = 0;
  int y = 0;

  for (int i = 0; i < L; ++i) {
    const bool t = s[i] - '0';
    const bool a = (i & 1);

    if (t != a) ++x;
    else ++y;
  }

  cout << min(x, y) << endl;


  return 0;
}



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


class Program
{


    static void Main(string[] args)
    {
        Solve();
    }

    static void Solve()
    {
        Scan sc = new Scan();
        write wr = new write();

        var s = sc.intarr;

        int a = s[0];
        int b = s[1];
        int x = s[2];

        if (a + b >= x && a <= x)
        {
            wr.wri("YES");
        }
        else wr.wri("NO");

    }


}
    class Scan
    {
        public string str => Console.ReadLine();

        public string[] strarr => str.Split(' ');

        public long[] longarr => strarr.Select(long.Parse).ToArray();
        public int[] intarr => strarr.Select(int.Parse).ToArray();
        public char[] chararr => str.ToArray();


}



class write
{
    public void wri<Type>(Type x)
    {
        Console.WriteLine(x);
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;


int main()
{
    ll tmp=0;
    ll N;
    cin >> N;
    for(ll i=1; i<=N; i++){
        tmp+=(N-i+2)*(N-i+1)/2;
    }
    ll ans=tmp;
    for(ll i=0; i<N-1; i++){
        ll u,v;
        cin >> u >> v;
        if(u>v) swap(u,v);
        ans-=u*(N-v+1);
    }
    cout<< ans << endl;


    return 0;
}

Measured memory_bytes: 3644
n, y = map(int, input().split())
y //= 1000
yen = [10, 5, 1]


def bs(n10):
    high = y // 5 + 1
    low = 0
    while high - low > 1:
        mid = (high + low) // 2
        if mid + n10 > n or mid * 5 > y - n10 * 10 - (n - n10 - mid):
            high = mid
        else:
            low = mid
    return low


for i in range(n + 1):
    n5 = bs(i)
    if i * 10 + n5 * 5 + (n - i - n5) == y:
        print("{} {} {}".format(i, n5, n - i - n5))
        break
else:
    print("-1 -1 -1")


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String answer="";
        int length = line.length();
        for(int i=0;i<length;i++){
             char ch = line.charAt(i);
            if(Character.isLowerCase(ch)==true){
                ch=Character.toUpperCase(ch);
            }else{
                ch=Character.toLowerCase(ch);
            }
            answer=String.valueOf(ch);
            System.out.print(answer);
        }
            System.out.println();
sc.close();
        }

    }
    



Measured memory_bytes: 26968
#include<iostream>
using namespace std;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n;
	cin>>n;
	if(n%10==2 || n%10==4 || n%10==5 || n%10==7 || n%10==9){
		cout<<"hon"<<endl;
	}
	else if(n%10==3){
		cout<<"bon"<<endl;
	}
	else{
		cout<<"pon"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int w[1000],v[1000];
long long  m[105][1000000];
int max(int a,int b){
    if(a>b)return a;
    return b;
}
int main(){
    long long n,x;
    cin>>n>>x;
    for(long long i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=x;j++){
            if(w[i]>j)m[i][j]=m[i-1][j];
            else m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
        }
    }
	cout<<m[n][x];
} 

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

using namespace std;

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

    int N, M, Q, l, r, p, q;

    cin >> N >> M >> Q;
    vector<vector<int>> cnt(N + 2, vector<int>(N + 2));

    for (int i = 0; i < M; ++i) {
        cin >> l >> r;
        for (int j = 0; j < l; ++j)
            ++cnt[j][r - 1];
    }

    for (int i = 0; i < N; ++i)
        for (int j = 1; j < N; ++j)
            cnt[i][j] += cnt[i][j - 1];

    for (int i = 0; i < Q; ++i) {
        cin >> p >> q;
        cout << cnt[p - 1][q - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define all(x) x.begin(),x.end()
#define ii int,int 
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define imx INT_MAX
#define imn INT_MIN
#define inf LONG_MAX
#define minf LONG_MIN
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 
#define pre cout<<fixed<<setprecision(10);
#define umap unordered_map
#define uset unordered_set

/*
#define MODM(a,b,md) ((a%md)*(b%md))%md
#define MODA(a,b,md) ((a%md)+(b%md))%md
#define ull unsigned long long int
#define si short int
*/

/*
bool compare(int a,int b) {return a > b;}
bool compare1(ppi a,ppi b) {return a.ff > b.ff;}
bool compare2(ppi a,ppi b) {return a.ss < b.ss;}
ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md) {ll product = 1; while(b){if(b&1){product = MODM(product,a,md);}a = MODM(a,a,md);b = b>>1;} return product%md;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }
*/


int main()
{
    fast

    ll n,k;
    cin>>n>>k;

    vl v(n);

    forn(i,0,n) cin>>v[i];

    vector<ppl> v1(n,{0,0});

    forn(i,0,n)
    {
        forn(j,0,i)
        {
            if(v[j] < v[i]) v1[i].ff++;
        }

        forn(j,i+1,n)
        {
            if(v[j] < v[i]) v1[i].ss++;
        }
    }


    ll total = 0;
    forn(i,0,v1.sze)
    {
        total = (total%mod + ((v1[i].ff)%mod)*(((k*(k-1))/2)%mod))%mod;
        total = (total%mod + ((v1[i].ss)%mod)*(((k*(k+1))/2)%mod))%mod;
    }

    cout<<total;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>

using namespace std;

struct uf_find_tree {
    vector<int> par, sizes;
    uf_find_tree(int n) : par(n), sizes(n, 1) {
        for (int i = 0; i < n; i++) { par[i] = i; }
    }
    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 (sizes[x] < sizes[y]) { swap(x, y); }
        par[y] = x;
        sizes[x] += sizes[y];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sizes[find(x)]; }
};

int main() {
    int n, m, s, t, q;

    scanf("%d %d", &n, &m);

    uf_find_tree uf(n);

    while (m--) {
        scanf("%d %d", &s, &t);
        uf.unite(s, t);
    }

    scanf("%d", &q);

    while (q--) {
        scanf("%d %d", &s, &t);
        printf((uf.same(s, t)) ? "yes\n" : "no\n");
    }

    return 0;
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
int x[100010];
signed main(){
	int n;
	cin>>n;
	f(i,n)cin>>x[i];
	sort(x,x+n);
	cout<<x[n/2]-x[n/2-1]<<endl;
}


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

int main() {
  int N;
  cin >> N;
  N %= 10;
  if (N == 0 || N == 1 || N == 6 || N == 8){
    cout << "pon" << endl;
  }else if (N == 3){
    cout << "bon" << endl;
  }else{
    cout << "hon" << endl;
  }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using ull = unsigned long long;

/* UnionFindTree Lib */
class UnionFindTree {
 public:
  UnionFindTree(int n) : rank_(n, 1), parent_(n) {
    // 0 1 2 3 ...
    iota(parent_.begin(), parent_.end(), 0);
  }

  int find(int x) {
    if (x == parent_[x]) return x;
    else return parent_[x] = find(parent_[x]);
  }
  int find(int x) const {
    if (x == parent_[x]) return x;
    else return find(parent_[x]);
  }

  void unite(int x, int y) {
    x = find(x);  y = find(y);
    if (x == y) return;
    if (rank_[x] > rank_[y]) parent_[y] = x;
    else {
      parent_[x] = y;
      if (rank_[x] == rank_[y]) rank_[y]++;
    }
  }

  bool same(int x, int y) const {
    return find(x) == find(y);
  }

 private:
  vi rank_;
  vi parent_;
};
/* /UnionFindTree Lib */

int main(int argc, char* argv[]) {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  /* */
  int n, k, l;
  cin >> n >> k >> l;

  UnionFindTree road(n), rail(n);
  for (int i = 0; i < k; ++i) {
    int p, q;
    cin >> p >> q;
    --p;  --q;
    road.unite(p, q);
  }

  for (int i = 0; i < l; ++i) {
    int r, s;
    cin >> r >> s;
    --r;  --s;
    rail.unite(r, s);
  }

  vi ans(n, -1);
  map< pair<int, int>, int > countmap;
  for (int i = 0; i < n; ++i) {
    countmap[make_pair(road.find(i), rail.find(i))]++;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d%c", countmap[make_pair(road.find(i), rail.find(i))],
      i == n - 1 ? '\n' : ' ');
  }
  /* */

  return EXIT_SUCCESS;
}


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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved

int main(){
    long long  n,m;
    cin>>n>>m;
    long long ans=n;
    rep(i,m){
    long long a;
    cin>>a;
    ans-=a;
    }
    if(ans<0){
        ans=-1;
    }
    cout<<ans<<endl;
    return 0;

}
/*


*/


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct Node {
    int id;
    Node *parent;
    int child_num;
    vector<Node*> children;
};

int n;
vector<Node*> nodes;

int main(void) {

    scanf("%d", &n);
    nodes.reserve(n);
    for (int i = 0; i < n; ++i) {
        nodes[i] = NULL;
    }

    for (int i = 0, id, n2; i < n; ++i) {
        scanf("%d", &id);
        scanf("%d", &n2);

        Node *pnode = nodes[id];
        if (pnode == NULL) {
            pnode = nodes[id] = new Node;
            pnode->parent = NULL;
        }
        pnode->id = id;
        pnode->child_num = n2;
        pnode->children.reserve(n2);
        for (int j = 0, id2; j < n2; ++j) {
            scanf("%d", &id2);
            Node *cnode = nodes[id2];
            if (cnode == NULL) {
                cnode = nodes[id2] = new Node;
            }
            pnode->children[j] = cnode;
            cnode->id = id2;
            cnode->parent = pnode;
        }
    }

    for (int i = 0; i < n; ++i) {

        int depth = -1;
        Node *node = nodes[i];
        while (node) {
            node = node->parent;
            ++depth;
        }

        const char *type = "internal node";
        if (nodes[i]->parent == NULL) {
            type = "root";
        }
        else if (nodes[i]->child_num == 0) {
            type = "leaf";
        }

        printf("node %d: parent = %d, depth = %d, %s, [",
                nodes[i]->id, (nodes[i]->parent ? nodes[i]->parent->id:-1),
                depth, type);
        for (int j = 0, f = 0; j < nodes[i]->child_num; ++j) {
            if (f) {
                printf(", %d", nodes[i]->children[j]->id);
            }
            else {
                f = 1;
                printf("%d", nodes[i]->children[j]->id);
            }
        }
        printf("]\n");
    }

    for (int i = 0; i < n; ++i) {
        delete nodes[i];
    }

    return 0;
}

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

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


before_max = a[0]
humidai = 0
humidai_sum = 0
for i in range(1,n):
    humidai = 0
    if(before_max >= a[i]):
        humidai = before_max - a[i]
        humidai_sum += humidai

    if(before_max < a[i]):
        before_max = a[i]
        

    #print(humidai,before_max,before_max)
print(humidai_sum)

Measured memory_bytes: 32224
import java.util.Scanner;

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

		int sum = a + b;
		if(sum % 2 == 0) {
			System.out.println(sum/2);
		} else {
			System.out.println(sum/2+1);
		}
		sc.close();
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define int long long
#define double long double
#define yy cout<<"YES\n"
#define nn cout<<"NO\n"
#define rt return
#define ct continue
#define br break
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define mmod 1000000007
#define pmod 998244353
using namespace std;
int gcd(int a,int b){
    while (b) b^=a^=b^=a%=b;
    return a;
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int bigmod(int b,int p,int m){
    int ans=1;
    b%=m;
    if (!b) return 0;
    while (p){
        if (p&1) ans=(ans*b)%m;
        p>>=1;
        b=(b*b)%m;
    }
    return ans;
}
void recur(){
	
	
	
}
void solve(){
	int n,x,m;
	cin>>n>>x>>m;
	int occ[m];
	for (int i=0; i<m; i++) occ[i]=0;
	int p=x%m;
	occ[p]=1;
	for (int i=2; i<=n;i++){
		p*=p;
		p%=m;
		if (occ[p]){
			int ans=0,d=i-occ[p];
			for (int j=0; j<m; j++){
				if (!occ[j]) continue;
				if (occ[j]<occ[p]) ans+=j;
				else ans+=j*((n-occ[j])/d+1);
			}
			cout<<ans;
			return;
		}
		occ[p]=i;
	}
	int ans=0;
	for (int i=0; i<m; i++){
		if (occ[i]) ans+=i;
	}
	cout<<ans;
	
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

Measured memory_bytes: 4368
#define _USE_MATH_DEFINES
#define INF 100000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;

static const double EPS = 1e-8;

const int tx[] = {0,1,0,-1};
const int ty[] = {1,0,-1,0};

bool dp[1000001];
int main(){
	ll z;
	while(~scanf("%lld",&z)){
		if(z==0) break;

		ll maxv = -1;
		for(ll x=1;x*x*x<=z*z*z;x++){
			for(ll y=1;x*x*x+y*y*y<=z*z*z;y++){
				maxv = max(maxv,x*x*x+y*y*y);
			}
		}
		printf("%lld\n",z*z*z-maxv);
	}
}

Measured memory_bytes: 880
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;


void main() {
    int n;
    scan(n);

    int cnt;

    foreach (i ; 0 .. n) {
        string s = readln.chomp;
        if (s == "A") cnt++;
        else {
            if (cnt <= 0) {
                writeln("NO");
                return;
            }
            else {
                cnt--;
            }
        }
    }

    writeln(cnt == 0 ? "YES" : "NO");
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 2472
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;


int main (int argc, char const *argv[])
{
    int N,K;
    cin>>N>>K;
    int syou=N/K;
    int amari=N%K;

    
    if (amari==0) {
        cout<<0<<endl;
    }
    else
    {
        cout<<1<<endl;
    }
    
   
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,0,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

ll GCD(ll a,ll b){
  if(b==0) return a;
  else return GCD(b,a%b);
}

ll LCM(ll a,ll b){
  ll g=GCD(a,b);
  return a/g*b;
}

int main(){
  ll N;
  cin>>N;
  ll T[N];
  REP(i,N) cin>>T[i];
  ll ans=T[0];
  FOR(i,1,N){
    ans=LCM(ans,T[i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
fn main() {
	let n = readLine::<usize>();
	let mut xs = read_vec::<i32>();
	xs.reverse();
	print_vec::<i32>(xs, n);
}

fn print_vec<T: std::fmt::Display>(xs: Vec<T>, n: usize) {
	let len = n - 1;
	for i in 0..len {
		print!("{} ", xs[i]);
	}
	println!("{}", xs[len]);
}

fn readLine<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 5036
#include <stdio.h>
#include <math.h>
#define N 250

int parent(int i){
    return floor(i/2);
}

int left(int i){
    return 2*i;
}

int right(int i){
    return (2*i)+1;
}

int main(){
    int n,A[N],i;
    scanf("%d",&n);
    for(i = 1;i <= n;i++){
        scanf("%d",&A[i]);
    }
    for(i = 1;i <= n;i++){
        printf("node %d: key = ",i);
        printf("%d, ",A[i]);
        if(i != 1){
                printf("parent key = %d, ",A[parent(i)]);
        }
        if(left(i)<=n){
             printf("left key = %d, ",A[left(i)]);
        }
       if(right(i)<=n){
        printf("right key = %d, ",A[right(i)]);
       }
    
        printf("\n");
    }

 return 0;
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b;
    cin>>n>>a>>b;
    if((b-a)%2==1) cout<<"Borys"<<endl;
    else cout<<"Alice"<<endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(M)]
for i in range(N):
  l = float('inf')
  min_j = -1
  for j in range(M):
    tmp = abs(ab[i][0]-cd[j][0]) + abs(ab[i][1]-cd[j][1])
    if tmp < l:
      l = tmp
      min_j = j
  print(min_j+1)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int c[1000],s[1000],f[1000];
int main()
{
    int n;
    cin>>n;

    for(int i=1;i<n;i++)
        cin>>c[i]>>s[i]>>f[i];

    for(int st=1;st<=n;st++)
    {
        if(st==n){cout<<0<<endl;break;}
        int ans=s[st];
        if(ans%f[st])
        {
            ans = (ans + f[st] - (ans%f[st]));
        }
        ans+=c[st];
        for(int i=st+1;i<n;i++)
        {
            ans = max(ans,s[i]);
            if(ans%f[i])
            {
                ans = (ans + f[i] - (ans%f[i]));
            }
            ans+=c[i];
        }
        cout<<ans<<endl;
    }

    return 0;
}


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

int main() {
  int S, a, b;
  cin >> S;
  b = S % 100;
  a = (S - b) / 100;
  if (a >= 1 && a <= 12 && b >= 1 && b <= 12) cout << "AMBIGUOUS" << endl;
  else if (a >= 1 && a <= 12) cout << "MMYY" << endl;
  else if (b >= 1 && b <= 12) cout << "YYMM" << endl;
  else cout << "NA" << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	long long ans=0;
	int a;long long b,c;cin>>a;
	cin>>b>>c;
	ans+=b/2;b%=2;a--;
	while(a--){
		while(b&&c)b--,c--,ans++;
		b=c;cin>>c;
		ans+=b/2;b%=2;
	}
	cout<<ans<<endl;
}

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

#define mp make_pair
#define ff first
#define ss second
#define pii pair <int,int>
#define pb push_back
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std ;
typedef long long ll ;
const int mx=100000+5 ;
int h[mx] ;
int dp[mx] ;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n ;
	cin >> n ;
	for(int i =1 ; i<=n ; i++){
		cin >> h[i] ;
	}
	dp[1] = 0 ;
	dp[2] = abs(h[2] - h[1]) ;
	for(int i = 3 ; i<= n ; i++){
		dp[i] = min(dp[i-1]+abs(h[i-1]-h[i]) ,  dp[i-2]+abs(h[i-2]-h[i]) ) ;
	}
	cout << dp[n] ;
	return 0 ;
}


Measured memory_bytes: 4440
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long N,K;
    cin>>N>>K;

    vector<long long>H(200010);
    for(int i=0;i<N;++i){
        cin>>H[i];
    }

    sort(H.begin(),H.end());
 

    for(int i=0;i<K;++i){
        H.pop_back();
    }

      reverse(H.begin(),H.end()); 

    long long sum=0;
    for(int i=0;i<N-K;++i){
        sum+=H[i];
    }
  
    cout<<sum<<endl;

}

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    X=input()
    Q=[]
    ans=0
    for c in X:
        if(c=='T' and Q and Q[-1]=='S'): Q.pop()
        else: Q.append(c)
    print(len(Q))
resolve()

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


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

    vector<int> l(n);
    rep(i, n) {
        cin >> l.at(i);
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (l.at(i) == l.at(j) || l.at(j) == l.at(k) || l.at(i) == l.at(k)) {
                    continue;
                }
            
                if (l.at(i) + l.at(j) > l.at(k) && l.at(j) + l.at(k) > l.at(i) && l.at(i) + l.at(k) > l.at(j)) {
                    ++res;
                }
            }
        }
    }
    cout << res << endl;

}


Measured memory_bytes: 3628
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,a) for( int i = 0; i != (a); ++i )

struct edge
{
	int from, to, cost;

	edge( int from, int to, int cost )
	:	from( from ), to( to ), cost( cost )
	{}
};

int n, m;
std::vector<edge> es;

int par[100], rank[100];

void init()
{
	rep( i, n )
		par[i] = i, rank[i] = 0;

	return;
}

int find( int x )
{
	if( x == par[x] )
		return x;
	else
		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[y] = x;
	else
	{
		par[x] = y;
		if( rank[x] == rank[y] )
			++rank[y];
	}

	return;
}

bool same( int x, int y )
{
	return find( x ) == find( y );
}

int main()
{
	while( scanf( "%d%d", &n, &m ), n|m )
	{
		es.clear();
		init();
		rep( i, m )
		{
			int a, b, c;
			scanf( "%d%d%d", &a, &b, &c );
			es.push_back( edge( a, b, c ) );
		}

		std::sort( es.begin(), es.end(), []( const edge& e1, const edge& e2 ){ return e1.cost < e2.cost; } );

		int ans = 0;
		rep( i, es.size() )
		{
			edge& e = es[i];
			if( !same( e.from, e.to ) )
			{
				ans += e.cost;
				unite( e.from, e.to );
			}
		}

		printf( "%d\n", ans );
	}

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    ll N, K; cin >> N >> K;
    vector<ll> A(N);
    REP(i, 0, N) cin >> A[i];

    int cnt[60] = {};
    REP(i, 0, N) {
        ll tmp = A[i];
        REP(j, 0, 60) {
            cnt[j] += tmp & 1;
            tmp >>= 1;
        }
    }

    ll ans = 0, k = 0;
    for (int i = 59; i >= 0; i--) {
        // cout << "# i : " << i << ", cnt : " << cnt[i] << endl;
        if (cnt[i] >= N - cnt[i]) {
            ans += cnt[i] * (1LL << i);
        } else {
            if (k + (1LL << i) <= K) {
                ans += (N - cnt[i]) * (1LL << i);
                k += (1LL << i);
            } else {
                ans += cnt[i] * (1LL << i);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3964
#include<iostream>
using namespace std;
int main(){
  char a,b,c,x,y,z;
  cin >> a >> b >> c >> x >> y >> z;
  int ans=0;
  if(a==x){
    ans++;
  }
  if(b==y){
    ans++;
  }
  if(c==z){
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
	int n ,m,s=0,a[10000];
	cin >> n >> m;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
	}
	sort(a,a+n);
	for(int i=0;i<m;i++)
	{
		s=s+a[i];
	}
	cout << s<<"\n";
	
	
}

Measured memory_bytes: 3628
///******* In the name of Allah *******///

#include <bits/stdc++.h>
using namespace std;

//long int ar[10013];
//long int gcd(long int a, long int b)
//{
//    if(b==0)
//        return a;
//    return gcd(b,a%b);
//}
//long int sieve(long long int a)
//{
//    long long int i,j,k = 0;
//    memset(ar,0,sizeof(ar));
//    ar[1] = 1;
//    for(i=2; i<=713; i++)
//    {
//        if(ar[i]==0)
//        {
//            for(j=i+i; j<=713; j+=i)
//            {
//                ar[j] = 1;
//            }
//        }
//    }
//    return ar[a];
//}

void Ok()
{
    long int a,b,c,d[100013],e,f,g,h,t,i,j,k,l,m,n;
    long int ans_1,ans_2,ans_3,cnt_1,cnt_2,cnt_3,Max,Min,flag_1,flag_2,temp,sum;
    double aa,bb,cc,dd,ee,ff,gg;
    char aaa,bbb,ccc,ddd;
    string spc,in,store[13];

    memset(d,0,sizeof(d));
    sum = 0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a;
        d[a]++;
        sum += a;
    }
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>b>>c;
        ans_1 = (d[b] * b);
        sum -= ans_1;
        ans_2 = (d[b] * c);
        sum += ans_2;
        d[c] += d[b];
        d[b] = 0;
        cout<<sum<<endl;
    }

    return;
}

int main()
{
    Ok();

    return 0;
}


Measured memory_bytes: 4404
# -*- coding: utf-8 -*-
import sys;
import string;
sys.setrecursionlimit(20000) # 再起呼び出しの最大数をセット

import copy
import itertools

from functools import lru_cache
#@lru_cache(maxsize = None)

PPP = 1000000007

# 整数の入力
#n = int(input())

# スペース区切りの整数の入力
#a = [int(x) for x in input().split()]
n, a, b = map(int, input().split())
#print("sp", n, k, file=sys.stderr)
#p, q, r = map(int, input().split())
#s = [int(x) for x in input().split()]
#t = [int(x) for x in input().split()]

# 改行区切りの整数の入力
#a = []
#for x in range(n):
#  a.append(int(input()))
#  a.append([int(x) for x in input().split()])
#p = [int(x) for x in input().split()]
#a.sort()
#print(l, file=sys.stderr)

# 文字列の入力
#s = input()

# 出力
#print("{} {}".format(a+b+c, s))
#a.sort()
#print(set(a), file=sys.stderr)
#print(len(set(a)))

#cache = dict()

import re
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
def count(c):
  r = b // c - (a - 1) // c;
  print(c, r, file=sys.stderr)
  return r

def doit():
  res = min(n * a, b)
  
  return res

#print(doit([0] * 4))
#doit(s)
#print(doit())
try:
  print(doit())
except Exception as e:
  print("e", e, file=sys.stderr)


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

a = [int(input())for i in range(n)]
s = sum(a)

if s%10 != 0:
  print(s)
else :
  f = [i for i in a if i%10 != 0]
  if len(f) == 0:
    print(0)   
  else:
    f.sort()
    print(s -f[0])
  

Measured memory_bytes: 2940
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		
		for (int i = 1; i < 10; i++) {
			if(a%i == 0 && a/i < 10) {
				System.out.println("Yes");
				break;
			} else if (i == 9){
				System.out.println("No");
			}
		}
		
		
	
	}

}


Measured memory_bytes: 22612
#include <stdio.h>

int main(void){
int n;
scanf("%d",&n);
int coin=100000;
for(int m=0;m<n;m++){
coin*=1.05;
coin=(coin/1000)*1000+((coin%1000)>0? 1000:0);
}
printf("%d\n",coin);
return 0;
}

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

using namespace std;
constexpr int NMAX = 200010;

char s[NMAX], t[NMAX];

int main() {
	scanf("%s", s);
	scanf("%s", t);
	int ans = 0;
	for (int i = 0; s[i]; ++i) if (s[i] != t[i]) ++ans;
	printf("%d\n", ans);
}


Measured memory_bytes: 4132
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<char, ll> ump;
typedef pair<ll, ll> P;

ump mp;

void solve() {
}

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        string w;
        cin >> w;
        rep(i, w.size()) mp[w[i]]++;
        each(m, mp) {
            if (m.second % 2 != 0) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;

        solve();

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
#include<numeric>

using namespace std;

int main() {
	int X = 0;
	int t = 0;

	cin >> X >> t;

	X = X - t;
	if (X<0) {
		X = 0;
	}

	cout << X << endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
v = map(int, input().split())
sortedV = sorted(v, reverse=True)

lastV = sortedV[-1]
c = 2
res = 0
for v in sortedV:
    res += v / c
    c *= 2
# 最初だけひきすぎなので
res += lastV / (c / 2)
print(res)


Measured memory_bytes: 3060
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

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

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

  int a, b, k;
  cin >> a >> b >> k;

  int count = 0, i = 100;
  while(true){
    if(a % i == 0 && b % i == 0){
      ++count;
      if(count == k) break;
    }
    --i;
  }

  cout << i << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  vector<P> a(n);
  vector<P> b(n);
  rep(i, n) {
    cin >> a[i].fr;
    a[i].sc = i;
  }
  rep(i, n) {
    cin >> b[i].fr;
    b[i].sc = i;
  }

  sort(all(a));
  sort(all(b));

  // Check the sorted state. In each i, a[i] <= b[i] must be satisfied.
  rep(i, n) {
    if (a[i].fr > b[i].fr) {
      cout << "No" << endl;
      return 0;
    }
  }

  // Check if the i exists in which a[i+1] <= b[i].
  for (ll i = 0; i + 1 < n; ++i) {
    if (a[i+1].fr <= b[i].fr) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  // Check the count of cycles. We treat the cycles as the connected components.
  vector<ll> p(n); // p[i] .. The parent of i.
  rep(i, n) {
    p[a[i].sc] = b[i].sc;
  }
  ll ans = 0;
  vector<bool> visited(n);
  rep(i, n) {
    if (visited[i]) { continue; }

    ll x = i;
    ll len = 0;
    do {
      visited[x] = true;
      x = p[x];
      ++len;
    } while (x != i);
    ans += len-1;
  }

  if (ans <= n-2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 4224
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define ALL(v) (v).begin(), (v).end()
#define REV(s) (s).rbegin(), (s).rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define X first
#define Y second

using namespace std;

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

const int N = 1000010;

int s[N];
int ss[N];

int n, q;
inline int u_b(int x){
	return upper_bound(ss, ss+n, x)-ss;
}

inline int l_b(int x){
	return lower_bound(ss, ss+n, x)-ss;
}

const int INF = (1<<30)-10;

vector<P> leader;
void check(int x){
	sort(ALL(leader));
	int lb = -1, ub = INF;
	while(ub-lb > 1){
		int r = (lb+ub)/2;
		int cnt = 0;
		int prev = 0;
		rep(i, leader.size()){
			int b = u_b(leader[i].first)-1;
			int a = l_b(max(ss[prev], leader[i].first-r));
			cnt += b-a+1;
			prev = u_b(leader[i].first);
		}
		if(n-cnt <= x) ub = r;
		else lb = r;
	}
	if(ub != INF) cout << ub << endl;
	else cout << "NA" << endl;
}

int main(){
	ios::sync_with_stdio(false);

	cin >> n >> q;
	rep(i, n) cin >> s[i], ss[i] = s[i];
	sort(ss, ss+n);
	ss[n] = INF;

	while(q--){
		int a;
		string t;
		cin >> t >> a;
		switch(t[0]){
		case 'A':
			leader.push_back(MP(s[a-1], a-1));
			break;
		case 'R':
			leader.erase(remove(ALL(leader), MP(s[a-1], a-1)));
			break;
		case 'C':
			check(a);
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 9052