akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define ppb pop_back()
#define ppf pop_front()
#define all(vec) vec.begin(), vec.end()
#define fol(i,a,b) for(int i=a;i<b;i++)
#define loop(i,a,b) for(int i=a;i>=b;i--)
#define forr(x,arr) for(auto& x:arr)
#define mod 1000000007
#define INF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-7
#define sz(x) ((lli)(x).size())

using   lli     =   long long;
using   lld     =   long double;
using   ulli    =   unsigned long long int;
using   pll     =   pair<lli, lli>;
using   ttt     =   pair<lli, pll>;
using   vttt    =   vector<ttt>;
using   vll     =   vector<pll>;
using   vl      =   vector<lli>;
using   vi      =   vector<int>;
using   vvi     =   vector<vector<int>>;
using   cd      =   complex<lld>;
const double PI = acos(-1);

#ifndef tejasp
#define trace(...) {}
#define cotra(...) {}
#define end_routine() {}
#define localsys 0
#define endl '\n'
#endif

#define MAXN 100010
vvi adj(MAXN);
vl val(MAXN,mod);
vll lim(MAXN,{-INF,INF});

pll dfs1(int v, int p)
{
    forr(x,adj[v])
    {
        if(x!=p)
        {
            auto cur=dfs1(x,v);
            lim[v].ff=max(lim[v].ff,cur.ff);
            lim[v].ss=min(lim[v].ss,cur.ss);
        }
    }
    return make_pair(lim[v].ff-1,lim[v].ss+1);
}

bool flag=0;

void dfs2(int v, int p)
{
    if(lim[v].ff>lim[v].ss) { flag=1; return; }
    if(v!=1)
    {
        if(val[p]+1>=lim[v].ff&&val[p]+1<=lim[v].ss)
            val[v]=val[p]+1;
        else if(val[p]-1>=lim[v].ff&&val[p]-1<=lim[v].ss) val[v]=val[p]-1;
        else flag=1;
    }
    forr(x,adj[v]) if(x!=p) dfs2(x,v);
}

int tejas_919(int kkkk)
{
    lli n, m, k, q, u, v, temp=0, ans=0;
    cin>>n;
    fol(i,1,n)
    {
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin>>k;
    fol(i,0,k)
    {
        cin>>u>>v;
        lim[u]={v,v};
        val[u]=v;
    }
    dfs1(1,0);
    val[1]=0;
    if(val[1]>lim[1].ss) val[1]=lim[1].ss;
    if(val[1]<lim[1].ff) val[1]=lim[1].ff;
    dfs2(1,0);
    if(flag) return cout<<"No"<<endl, 0;
    cout<<"Yes"<<endl;
    fol(i,1,n+1) cout<<val[i]<<endl;
    return 0;
}

signed main()
{
    #ifdef tejasp
            freopen("input.txt", "rt", stdin);
            freopen("output.txt", "wt", stdout);
    #endif
    if(!localsys) { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); }
    cout << fixed << setprecision(10);
    int t=1;
    //cin>>t;
    fol(i,0,t) { tejas_919(i+1); }
    end_routine();
    if(localsys) system("pause");
}

Measured memory_bytes: 13440
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:16777216")
#pragma warning( disable : 6031)
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <limits>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-9)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef tuple<int, int, int> tiii;


int main()
{
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n;
	cin >> n;
	long long res = 0;
	map<vi, int> mp;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		vi cur(26, 0);
		for (int j = 0; j < sz(s); j++)
			cur[s[j] - 'a']++;
		res += mp[cur];
		mp[cur]++;

	}
	cout << res;
	return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

    cout << (x < 1200 ? "ABC" : "ARC") << endl;
    return 0;
}


Measured memory_bytes: 3560
import re
c=0
p=input().upper()
ptn=re.compile(r'^'+p+r'$')

while True:
    s=input()
    if s =='END_OF_TEXT':
        break
    a=s.upper().split()
    for i in a:
        if re.match(ptn, i):
            c+=1
print(c)

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

int main()
{
    int n, m, i;
    string o, e;
    
    cin >> o >> e;
    
    n = o.size();
    m = e.size();
    
    for(i = 0; i < n; i++) {
        if(i != m) {
            cout << o[i] << e[i];
        } else {
            cout << o[i];
        }
    }
    
    cout << "\n";
    
    return 0;
}

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

int main()
{
	int a,b,c,i;
	while(cin>>a>>b)
	{
		c=0;
		for(i=1;i<a;i++){
			c++;
		}
		if(b>=a)
		c++;
		cout<<c<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n, m;
  cin >> n >> m;
  cout << (n == m ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7


count  = 0
l, r, d = multi_int_input()

for i in range(l, r+1):
    if i%d == 0:
        count+=1

print (count)

Measured memory_bytes: 9596
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<stack>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
using ll = long long;
using p_i = pair<int, int>;
int main() {
	int K, T; cin >> K >> T;
	vector<int> a(T);
	rep(i, T)cin >> a[i];
	int maxx = *max_element(a.begin(), a.end());
	cout << max(0, 2 * maxx - K - 1) << endl;
}

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

namespace Volume0_0013
{
	class Program
	{
		static void Main(string[] args)
		{
			Stack<int> vs = new Stack<int>();

			for(int i = 0; i < 100; i++) {
				string str = Console.ReadLine();
				if(str == null) {
					break;
				}

				int v = int.Parse(str);

				if(v == 0) {
					Console.WriteLine(vs.Pop());
				}
				else {
					vs.Push(v);
				}
			}
		}
	}
}



Measured memory_bytes: 16372
#include<bits/stdc++.h>
#include<cmath>
#define SZ(x) ((int)x.size())
#include<vector>
#include<set>
#include<map>
#define ll long long
#define lli long long int
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#include<string>
#include<cctype>
#include<queue>
#define ii pair<int,int>
#include <sstream>
#define lli long long int
#define pairs pair<int,int>
#define mod 1000000007
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
ll pows(ll a,ll n,ll m)
{
	ll res=1;
	while(n)
	{
	if(n%2!=0)
	{
		res=(res*a)%m;
		n--;
		}
		else
		{
			a=(a*a)%m;
			n=n/2;
			}	
	}
	return res%m;
}
ll  gcd(ll a,ll b)
{
	if(b==0)
	return a;
	else 
	return gcd(b,a%b);
}
bool isprime(ll n)
{
	if(n==1)
	{
		return false;
	}
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
bool istrue(string s)
{
	int i=0;
	int j=s.size()-1;
	while(i<j)
	{
	if(s[i]==s[j])
	{
		i++;
		j--;
		}
		else
		{
			return false;
			}	
	}
	return true;
}
int check(string s,string t)
{
	int cnt=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]!=t[i])
		{
			cnt++;
		}
	}
	return cnt;
}
int main()
{
   ios::sync_with_stdio(false);
	 cin.tie(0);
    cout.tie(0);
string s,t;
cin>>s>>t;
int ans=mod;
for(int i=0;i<=s.size()-t.size();i++)
{
	string p=s.substr(i,t.size());
	int l=check(p,t);
	ans=min(ans,l);
}
cout<<ans<<endl;
}
 

Measured memory_bytes: 3660
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <list>
#define MOD 1000000007
#define INF 1000000000
typedef long long ll;
using namespace std;
typedef pair<int,int> P;

int main(void){
    int a,b;
    cin>>a>>b;
    if(a==1)a=14;
    if(b==1)b=14;
    if(a>b)printf("Alice\n");
    else if(a<b)printf("Bob\n");
    else printf("Draw\n");
    return 0;
}


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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define endl        "\n"
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a,b) 	for(int i=a;i<=b;i++)
#define IOS         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


const int M=1e9 + 7;
vi v;

void isPrime(int N)
{
	int i;
	int c=0;
	v.pb(1);
	for(i=2;i*i<=N;i++)    // O(sqrt(n))
	{
		if(N%i==0)
		{
			if(i*i==N)
			{
				v.pb(i);
			}
			else
			{
				v.pb(i);
				v.pb(N/i);
			}
		}
	}
	v.pb(N);
}

int32_t main()
{
	IOS;
	//memset(dp,-1,sizeof(dp));
	int best = 1e18;
	int n;
	cin >> n;
	isPrime(n);
	repp(i,0,v.size())
	{
		int x = v[i];
		int y = n/v[i];
		int tot = (x-1) + (y-1);
		best = min(best,tot);
	}
	cout << best << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define pb push_back
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	string a[] = {"+++","++-","+-+","-++","+--","-+-","--+","---"};
	for(auto it:a)
	{
		string t="";
		int ans = s[0]-'0';
		t.push_back(s[0]);
		t.push_back(it[0]);
		t.push_back(s[1]);
		t.push_back(it[1]);
		t.push_back(s[2]);
		t.push_back(it[2]);
		t.push_back(s[3]);
		int g = s[1]-'0';
		if(it[0]=='+')
			ans += g;
		else
			ans -= g;
		g = s[2]-'0';
		if(it[1]=='+')
			ans += g;
		else
			ans -= g;
		g = s[3]-'0';
		if(it[2]=='+')
			ans += g;
		else
			ans -= g;
		if(ans == 7)
		{
			cout<<t<<"=7"<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input().rstrip()

memo = [None] * n
ans = 0

for i in range(n):
    if t[i] == 'r':
        if i - k < 0 or (0 <= i - k and memo[i - k] != 'p'):
            ans += p
            memo[i] = 'p'
        elif n <= i + k or (i + k < n and t[i + k] != 's'):
            memo[i] = 'r'
        else:
            memo[i] = 's'

    if t[i] == 's':
        if i - k < 0 or (0 <= i - k and memo[i - k] != 'r'):
            ans += r
            memo[i] = 'r'
        elif n <= i + k or (i + k < n and t[i + k] != 'p'):
            memo[i] = 's'
        else:
            memo[i] = 'p'

    if t[i] == 'p':
        if i - k < 0 or (0 <= i - k and memo[i - k] != 's'):
            ans += s
            memo[i] = 's'
        elif n <= i + k or (i + k < n and t[i + k] != 'r'):
            memo[i] = 'p'
        else:
            memo[i] = 'r'

print(ans)


Measured memory_bytes: 10192
//A==0,B==1,W==2,X==3,Y==4,Z==5としてグラフ構築
#include<iostream>
#include<string.h>
using namespace std;
#define A 0
#define B 1
#define W 2
#define X 3
#define Y 4
#define Z 5
struct Node{
	int edge_to[2];
};
char *ans[100],cor = 0;

int main(){
	char str[102];
	int i;
	int now;
	Node town[6];
	town[A].edge_to[0] = X;
	town[A].edge_to[1] = Y;
	town[B].edge_to[0] = Y;
	town[B].edge_to[1] = X;
	town[W].edge_to[0] = B;
	town[W].edge_to[1] = Y;
	town[X].edge_to[0] = -1;
	town[X].edge_to[1] = Z;
	town[Y].edge_to[0] = X;
	town[Y].edge_to[1] = -1;
	town[Z].edge_to[0] = W;
	town[Z].edge_to[1] = B;
	while(cin >> str){
		if(str[0] == '#')
			break;
		//探索開始
		now = A;
		int len = strlen(str);
		for(i = 0;i < len;i++){
			int t = str[i]-48;
			if(town[now].edge_to[t] == -1)
				break;
			else
				now = town[now].edge_to[t];
		}
		if(i == len && now == B)
			ans[cor] = "Yes";
		else
			ans[cor] = "No";
		cor++;
	}
	for(i = 0;i < cor;i++)
		cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 1136
#include <bits/stdc++.h>
using namespace std;
 
//Made with <3 by MinumCoklatPanas
typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double INFD = 1E9;
const double EPS = 1e-9;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a,b;
	cin >> a >> b;
	int ans = -1;
	for (int i = 1 ; i <= 1000000 ; i++)
	{
		double aa = floor(1.0 * i * 0.08);
		double bb = floor(1.0 * i * 0.1);
		if (aa == a && bb == b)
		{
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    int n, k; cin >> n >> k;
    k--;
    string s; cin >> s;

    for(int i = 0; i < n; i++){
        if(i == k){
            char c = s[i] + 32;
            cout << c;
            // if(s[i] == 'A') cout << 'a';
            // if(s[i] == 'B') cout << 'b';
            // if(s[i] == 'C') cout << 'c';
        }else{
            cout << s[i];
        }
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)

void solve(long long N, std::vector<long long> A, std::vector<long long> B){
    rep(i, N){
        A[i]-=B[i];
    }
    sort(A.begin(), A.end());
    ll negat = 0;
    ll cnt =0 ;
    rep(i, N){
        if(A[i]<0){
            negat += A[i];
            cnt ++;
        }
    }
    reverse(A.begin(), A.end());
    rep(i, N){
        if(A[i]>0 && negat<0){
            cnt ++;
            negat += A[i];
        }
    }
    if(negat < 0){
        cout << -1 << endl;
    }
    else{
        cout << cnt << endl;
    }

}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


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

long long nC2(long long n) {
    return n*(n-1)/2;
}

int main() {
    int n; cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
        cnt[a[i]]++;
    }
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += nC2(cnt[i]);
    }
    for (int i = 0; i < n; i++) {
        long long ans = total;
        ans -= nC2(cnt[a[i]]);
        cnt[a[i]]--;
        ans += nC2(cnt[a[i]]);
        cout << ans << endl;
        cnt[a[i]]++;
    }
    return 0;
}

Measured memory_bytes: 4096
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.typecons;
import core.bitop;

void log(A...)(A arg) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

long modPow(long x, long n, long mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) return modPow(x * x % mod, n / 2, mod);
    else return x * modPow(x, n - 1, mod) % mod;
}

bool isPrime(long n) {
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    long s = bsf(n);
    long t = (n - 1) / (1L<<s);
    bool test() {
        long b = uniform(2, n, rndGen);
        if (modPow(b, t, n) == 1) return true;
        foreach (r; 0 .. s) {
            if (modPow(b, (1L<<r) * t, n) == n - 1) return true;
        }
        return false;
    }
    foreach (_; 0 .. 100) {
        if (! test()) return false;
    }
    return true;
}

void main() {
    int N = readln.chomp.to!int;
    int ans = 0;
    foreach (i; 0 .. N) {
        int x = readln.chomp.to!int;
        if (isPrime(x)) ans++;
    }
    writeln(ans);
}

Measured memory_bytes: 2480
#include <iostream>
using namespace std;
const int MOD = 1000000007;

long long mod(long long a) {
	a %= MOD;
	return a >= 0 ? a : a+MOD;
}

long long pow2(long long n) {
	return (1ll << n) % MOD;
}

int main() {
	int n;
	cin >> n;
	long long one[60] = {0};
	for (int i = 0; i < n; i++) {
		long long a;
		cin >> a;
		for (int j = 0; a != 0; j++) {
			if (a & 1) one[j]++;
			a >>= 1;
		}
	}
	long long ans = 0;
	for (int i = 0; i < 60; i++) {
		long long x = one[i] * (n-one[i]) % MOD;
		ans = mod(ans + pow2(i) * x % MOD);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  	string s;
  	cin >> s;
  	map<char, int> mp;
  	for(int i = 0; i < s.size(); i++) {
      	mp[s[i]]++;
    }
  	if((mp.size() == 4 && s[2] == s[3] && s[4] == s[5]) || (mp.size() == 3 && s[2] == s[3] && s[3] == s[4] && s[4] == s[5]))
      	cout << "Yes" << endl;
  	else
      	cout << "No" << endl;
  	return 0;
}

Measured memory_bytes: 256
s = input()
n = int(input())

for i in range(n):
    p = input().split()

    a, b = [int(x) for x in p[1:3]]
    if p[0]=="print":
        print(s[a:b+1])
    elif p[0]=="replace":
        s = s[:a] + p[3] + s[b+1:]
    elif p[0]=="reverse":
        s = s[:a] + s[a:b+1][::-1] + s[b+1:]

Measured memory_bytes: 7716
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(ll i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
constexpr char ln = '\n';

const int mx=200010;
const ll mod=1e9+7;

struct UnionFind {  
  vector<int> par,sizes;                     // par[i]:iの親の番号(ex)par[3]=2 : 3の親が2
  UnionFind(int n) : par(n),sizes(n,1)  {    //最初は全てが根であるとして初期化
    for(int i=0; i<n; i++){ par[i]=i; }  
  }
  int root(int x) {                       //xが属する木の根を再帰で得る:root(x)={xの木の根}
    if(par[x]==x){ return x; }
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {                 // xとyの木を併合
    int rx = root(x);                        //xの根をrx
    int ry = root(y);                        //yの根をry
    if(rx == ry){ return; }                  //xとyの根が同じ(=同じ木にある)時はそのまま
    if(sizes[rx]<sizes[ry]){ swap(rx, ry); } //xの木をおおきくする
    par[ry] = rx; 
    sizes[rx] += sizes[ry];                  //sizes[ry]はもう使わない
  }
  bool check(int x, int y) {                 // x,yが属する木が同じならtrueを返す
    return root(x) == root(y);
  }
  int size(int x){                           //xが含まれる木の大きさを返す
    return sizes[root(x)];
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<pair<ll,int>> a(n);
  rep(i,n){
    cin >> a[i].F;
    a[i].S = i;
  }
  sort(a.begin(),a.end());
  UnionFind uf(n+1);
  int x,y;
  rep(i,m){
    cin >> x >> y;
    uf.unite(x,y);
  }

  set<int> sz;
  rep(i,n){
    sz.insert(uf.root(i));
  }
  if(sz.size()==1){ cout << 0 << ln; return 0; }
  int more = (sz.size()-1)*2-sz.size();
  ll ans = 0;
  set<int> al;
  for(int i=0; i<n && !(more<=0 && al.size()==sz.size()); i++){
    if(al.find(uf.root(a[i].S))==al.end()){
      ans += a[i].F;
      al.insert(uf.root(a[i].S));
      uf.unite(a[i].S, n);
    } else {
      if(more>0){
        ans += a[i].F;
        more--;
      }
    }
  }

  if(more>0 || uf.size(n)!=n+1){
    cout << "Impossible" << ln;
  } else {
    cout << ans << ln;
  }

  return 0;
}

Measured memory_bytes: 14872
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

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

A=A+A

count=[0]*2*N

for i in range(N):
    for j in range(i,2*N):
        if A[i]>A[j]:
            count[j]+=1
a=(sum(count[0:N]))
b=(sum(count[N:2*N]))
c=(int((a*K+b*K*(K-1)//2)))
print(c%(10**9+7))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using vi=vector<int>;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int h,w;
    cin >> h >> w;
    vector<vector<int>> dp(w+5,vector<int>(h+5,0));
    vector<vector<int>> t(w),y(h);
    rep(i,h){
        int x=i;
        y[x].push_back(0);
    }
    rep(i,w){
        int z=i;
        t[z].push_back(0);
    }
    rep(i,h){
        string s;
        cin >> s;
        rep(j,w){
            if(s[j]=='.') continue;
            int x=i, z=j;
            t[z].push_back(x+1);
            y[x].push_back(z+1);
        }
    }
    rep(i,h){
        int x=i;
        y[x].push_back(w+1);
    }
    rep(i,w){
        int z=i;
        t[z].push_back(h+1);
    }
    rep(i,w){
        for(size_t j=1; j<t[i].size(); ++j){
            if((t[i][j-1]+1)==t[i][j]) continue;
            for(int k=t[i][j-1];k<t[i][j]-1;++k){
                dp[i][k]=t[i][j]-t[i][j-1]-1;
            }
        }
    }
    rep(i,h){
        for(size_t j=1; j<y[i].size(); ++j){
            if((y[i][j-1]+1)==y[i][j]) continue;
            for(int k=y[i][j-1];k<y[i][j]-1;++k){
                dp[k][i]+=y[i][j]-y[i][j-1]-2;
            }
        }
    }
    int ans=0;
    rep(i,h){
        rep(j,w){
            ans=max(ans,dp[j][i]);
        }
    }
    cout << ans << "\n";
    return 0;
}   

Measured memory_bytes: 53492
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int N = 1e5+10;
int main(){
ll n,a,b;
    cin >> n >> a >> b;
    ll k = (n/(a+b))*a;
    if(n%(a+b)!=0){
        ll rm = n%(a+b);
        if(rm > a){
            k += a;
        }else{
            k += rm;
        }
    }
    cout << k << '\n';




    return 0;
}

Measured memory_bytes: 256
#define REP(i, n) for (int i = 0;i < (n); ++i)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int H, W, h, w;
    ios::sync_with_stdio(false);
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
    int a,b,n;
    cin>>a>>b>>n;
    if(a==0&&b==0&&n==0) break;
    int count=0,s=0,ans;
    for(int j=a;count!=n;j+=b){
      s=0;
      for(int k=2;k<=sqrt(j)+1;k++){
	if(j==1) {
	  s=1;
	  break;
	}
	if(j==2){
	  break;
	}
	if(j%k==0){
	  s=1;
	  break;
	}
      }
      if(s==0){
	count++;
	ans=j;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> a(N);
  REP(i, N) cin >> a[i];
  int ans = 0;
  for(int i = 0; i < N; i++) {
    while(a[i] % 2 == 0) {
      a[i] = a[i] / 2;
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}

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

int main() {
	string s;
	cin >> s;
	for (int i = 1; i < s.length(); i++) {
		string t = s.substr(i - 1, 2);
		if (t == "AC") {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
import sys
 
def main():
    for line in iter(sys.stdin.readline, ""):
        a = line.rstrip("\n").split(" ")
        b = []
        b.append(int(a[0]))
        b.append(int(a[1]))
        if (b[0] == 0 and b[1] == 0):
            return
 
        print(str(min(b)) + " " + str(max(b)))
      
if __name__ == "__main__":
    main()

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

int main(){
  int n,l;
  cin >> n >> l;
  int sum=0;
  int mini=500;
  for (int i = 1; i < n+1; i++)
  {
    sum+=i+l-1;
    if(abs(mini)>abs(i+l-1)) mini=i+l-1;
  }
  cout << sum-mini << endl;
  
}

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

class Main {

    public static void main(String[] args) throws Exception {

        try {

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

            String[] pillarHeightList = br.readLine().split(" ");
            int firstPillar = Integer.parseInt(pillarHeightList[0]);
            int secondPillar = Integer.parseInt(pillarHeightList[1]);
            int thirdPillar = Integer.parseInt(pillarHeightList[2]);

            String isPillarsBeautiful = "NO";

            if ((secondPillar - firstPillar) == (thirdPillar - secondPillar)) {
                isPillarsBeautiful = "YES";
            }

            System.out.println(isPillarsBeautiful);

        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 20308
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr ld inf<ld> = 1e30;

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha;
  cout.imbue(loc);

  int n; cin >> n;
  vector<int> up(n), down(n);
  REP(i, n) { cin >> up[i]; }
  REP(i, n) { cin >> down[i]; }

  vector<int> dpu(n), dpd(n);
  dpu[0] = up[0];
  dpd[0] = up[0] + down[0];
  REP(i, n-1){
    dpu[i + 1] = dpu[i] + up[i + 1];
    dpd[i + 1] = max(dpu[i + 1], dpd[i]) + down[i + 1];
  }

  cout << dpd[n - 1] << endl;
  return 0;
}

Measured memory_bytes: 888
# 基本は３で割ったあまり毎に変換コストを計算する.
# a[i][j] i種類目がj色に変わる時のコストと計算し、それの合計のminを取る

import numpy as np
N,C = map(int,input().split())
a = np.zeros((3,C))
D = np.array([ list(map(int,input().split())) for i in range(C)])
c = np.array([ list(map(int,input().split())) for i in range(N)])


for i in range(N):
    for j in range(N):
        a[(i+j)%3] += D[c[i][j]-1]

sum_arr = []
for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                sum_arr.append(a[0][C1]+a[1][C2]+a[2][C3])

print(int(min(sum_arr)))


Measured memory_bytes: 18920
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[p[0]][p[1]] + 1
                que.append((ny, nx))

    return dist


# Input params and answer
H, W = map(int, input().split())
Map = [list(input()) for i in range(H)]
dist = [[-1] * W for i in range(H)]

# Initial Black Point
que = deque([])
for h in range(H):
    for w in range(W):
        if Map[h][w] == "#":
            que.append((h, w))
            dist[h][w] = 0

# BFS
nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)


Measured memory_bytes: 121436
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String T = sc.next();
        int ans = 0;

        for (int i = 0; i < 3; i++) {
            if (S.charAt(i) == T.charAt(i)) ans++;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 25172
#!/usr/bin/env python3
import sys


def solve(n: int, a: "List[int]"):
    from collections import deque

    d = deque()
    for i in range(n):
        if(i%2 == 0):
            d.append(a[i])
        else:
            d.appendleft(a[i])

    if(n%2 == 1):
        d.reverse()

    d = map(str, d)
    print(' '.join(d))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 45400
typedef struct{int I,U,A,P;}Team;
M(Team*a,Team*b){
	if(a->A!=b->A)return b->A-a->A;
	if(a->P!=b->P)return a->P-b->P;
	return a->I-b->I;
}
Team t[300];
w[1001],W;
main(n){
	int i;
	for(;scanf("%d",&n)*n;){
		for(i=n;i--;)
			scanf("%d%d%d%d",&t[i].I,&t[i].U,&t[i].A,&t[i].P);
		qsort(t,n,sizeof(*t),M);
		memset(w,0,sizeof(w));
		W=0;
		for(i=0;i<n;i++){
			if(W<10&&w[t[i].U]<3||W<20&&w[t[i].U]<2||W<26&&w[t[i].U]<1){
				printf("%d\n",t[i].I);
				w[t[i].U]++;
				W++;
			}
		}
	}
}

Measured memory_bytes: 0
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

main = do
  [a, b, c, d] <- map head <$> readInts 4
  put $ min a b + min c d


Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  char c; cin >> c;
  cout << (char)(c + 1) << endl;
}

Measured memory_bytes: 256
INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush
from bisect import bisect_left

def main():
    s = int(input())
    a = int(s ** 0.5)
    while (a + 1) * (a + 1) <= s:
        a += 1

    b,c = 0,0
    flag = False
    while a <= INF:
        tmp = a * a - s
        if tmp == 0:
            b,c = 0,0
            break
        for i in range(1,tmp):
            if tmp%i == 0:
                j = tmp//i
                if i <= INF and j <= INF:
                    b = i
                    c = j
                    flag = True
                    break
        if flag:
            break
        else:
            a += 1
        
    print(0,0,a,c,b,a)
if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.*;

// DDCC 2017-D
// http://ddcc2017-qual.contest.atcoder.jp/tasks/ddcc2017_qual_d	

public class Main {

	public static void main (String[] args) throws InterruptedException {
		Scanner in = new Scanner(System.in);
		String s = in.next();
		int index = s.lastIndexOf("FESTIVAL");
		System.out.println(s.substring(0, index));
	}
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
// greater<int>()
typedef long long ll;
ll GCD(ll x, ll y) { return y ? GCD(y, x%y) : x; }
ll LCM(ll x, ll y) { return x * y / GCD(x, y); }

using namespace std;


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

	int x = stoi(a + b);
	bool OK = false;
	for (int i = 0; i <= 100100; i++)
	{
		if (x == i * i) {
			OK = true;
			break;
		}
	}


	if (OK) cout << "Yes" << endl;
	else cout << "No" << endl;

}

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

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))

#define SI(n) scanf("%d",&n)
#define PI(n) printf("%d\n",n)
#define SL(n) scanf("%lld",&n)
#define PL(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TRACE

#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif
#include <ext/pb_ds/assoc_container.hpp>    
#include <ext/pb_ds/tree_policy.hpp>        
using namespace __gnu_pbds;                 
typedef tree< pair< int,int>,null_type, less<pair<int,int> >,rb_tree_tag,
        tree_order_statistics_node_update> ord_set;


//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
typedef long long int 	LL;
typedef long double 	LD;
typedef pair<int,int>   II;
typedef vector<int>     VI;
const int MOD = 1e9 + 7;
const int N = 300011;
int a[N];
multiset<LL >sf, sb;

LL add(int v, LL ans, multiset<LL> &s) {
    if(v > *s.rbegin()) s.find(s.erase(v));
    else {
        ans -= *s.rbegin();
        s.erase(s.find(*s.rbegin()));
        ans += v;
        s.insert(v);
    }
    return ans;
}

LL rem(int v, LL ans, multiset<LL> &s) {
    if(s.find(v) != s.end()) s.erase(s.find(v));
    else ans -= v, ans += *s.rbegin(), s.erase(s.find(*s.rbegin()));
    return ans;
}

int main() {
    int n;
    cin>>n;
    LL fsum = 0, ssum = 0;
    for(int i = 1;i <= 3*n; ++i) {
        int x; cin>>x;
        a[i] = x;
        if(i <= 2*n)
            sf.insert(x), fsum += x;
        else 
            sb.insert(x), ssum += x;
    }
    int cnt = n;
    auto it = sf.begin();
    while(cnt--) fsum -= *it, it++;
    cnt = n;
    while(cnt--) sf.erase(sf.find(*sf.rbegin()));

    LL ans = -1e16;
    ans = max(ans, fsum - ssum);
    for(int i = 2*n; i > n; --i) {
        ssum = add(a[i], ssum, sb);
        fsum = rem(a[i], fsum, sf);
        ans = max(ans, fsum - ssum);
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 15488
S=[input() for i in range(2)]
if len(S[0])>len(S[1]):
    L=len(S[0])-1
else:
    L=len(S[0])
for i in range(L):
    print(S[0][i]+S[1][i],end='')
if len(S[0])>len(S[1]):
    print(S[0][-1])

Measured memory_bytes: 3060
import Control.Applicative

main = do s <- getLine
          _ <- getLine
          xs <- map words . lines <$> getContents
          putStr . unlines . filter (/= "") $ solve s xs

solve :: String -> [[String]] -> [String]
solve _ [] = []
solve s (x:xs) = s' : solve s'' xs
            where (s',s'') = run s x

run :: String -> [String] -> (String,String)
run s (x:a:b:p) | x == "print" = (s',s)
                | x == "reverse" = ("",s'')
                | x == "replace" = ("",s''')
        where s' = take ((read b)-(read a)+1) $ drop (read a) s
              s'' = bf ++ (reverse s') ++ af
              s''' = bf ++ (head p) ++ af
              bf = take (read a) s
              af = drop ((read b)+1) s

Measured memory_bytes: 5444
def main():
    S = input()
    T = input()
    max_cnt = 0
    for i in range(len(S) - len(T) + 1):
        cnt = 0
        for j in range(len(T)):
            if S[i + j] == T[j]:
                cnt += 1
        max_cnt = max(max_cnt, cnt)
    return len(T) - max_cnt

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 67524
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<map>
#include<random>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include <queue>
#include<boost/multiprecision/cpp_int.hpp>


using namespace std;
using namespace boost::multiprecision;

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldb = long double;

#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIF(v, n) printf("%."#n"f\n", v)
#define PRIY PRI("Yes")
#define PRIN PRI("No")
template<typename A, typename B>
void mins(A& a, const B& b) { a = min(a, (A)b); };
template<typename A, typename B>
void maxs(A& a, const B& b) { a = max(a, (A)b); };




struct unionfind {
	int N;
	vector<ll> par;
	vector<ll> size;
	unionfind(int N) : N(N) {
		par.resize(N);
		size.resize(N);
		REP(i, 0, N) {
			par[i] = i;
			size[i] = 1;
		}
	}

	ll getpar(ll ind) {
		while (par[ind] != ind) {
			ind = par[ind];
		}
		return ind;
	}

	void merge(ll ind1, ll ind2) {
		ll p1 = getpar(ind1);
		ll p2 = getpar(ind2);
		if (p1 == p2)return;
		if (size[p1] <= size[p2])par[p1] = p2;
		else par[p2] = p1;
		size[p1] = size[p1] + size[p2];
		size[p2] = size[p1];
	}
};


int main() {
	ll N;
	cin >> N;
	vector<pair<ll, ll>> p(N);
	unionfind t{ (int)N };
	REP(i, 0, N) cin >> p[i].first >> p[i].second;
	vector<ll> ind(N); REP(i, 0, N)ind[i] = i;
	auto scmp = [&](ll a, ll b) {return p[a].first < p[b].first; };
	set<ll, decltype(scmp)> s(scmp);
	auto cmp = [&](ll a, ll b) { return p[a].second > p[b].second; };
	sort(ind.begin(), ind.end(), cmp);
	REP(aaa, 0, N) {
		ll i = ind[aaa];
		auto itr = s.upper_bound(i);
		if (itr != s.end()) {
			for (; itr != s.end(); ++itr)t.merge(i, *itr);
		}
		else {
			s.insert(i);
		}
	}
	REP(i, 0, N)PRI(t.size[t.getpar(i)]);
	return 0;
}


Measured memory_bytes: 11868
#include <stdio.h>
 
int main(){
    int a,b,c,d,i;
    while (scanf("%d %d\n",&a,&b) !=EOF){
        c=a+b;
        d=1;
        if (c==0) {printf("1\n");}
        else {for (i=1;i<=7;i++) {
            if (c<d*10 && c>=d) {printf("%d\n",i);}
            d*=10;
        }
        }
    }
    return 0;
}

Measured memory_bytes: 604
//Created by Kira

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

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

int mod = 1e9 + 7;

ll pwr(ll a, ll b);
   



int main(){
   IOS

   int n; 
   cin>>n;
   string s; cin>>s;


   //preprocessing
   vector<int> f(n + 1);
   f[0] = 0;

   for(int i = 1; i <= n; i++){
      int val = i;
      int b = __builtin_popcount(val);
      val %= b;
      f[i] = 1 + f[val];
   }

  

   int cnt = 0;
   for(int i = 0; i < n; i++){
      if(s[i] == '1')cnt++;
   }

   mod = cnt + 1;
   int val1 = 0, val2 = 0;
   for(int i = 0; i < n; i++){
      if(s[i] == '0'){
         val1 = (val1 * 2) % mod;
      }
      else{
         val1 = (2 * val1 + 1) % mod;
      }
   }

   mod = cnt - 1;
   if(cnt > 1){
      for(int i = 0; i < n; i++){
         if(s[i] == '0'){
            val2 = (val2 * 2) % mod;
         }
         else{
            val2 = (2 * val2 + 1) % mod;
         }
      }
   }
   int ans = -1;
   for(int i = 0; i < n; i++){
      if(s[i] == '0'){
         //add 2 ^ i
         mod = cnt + 1;
         ans = (val1 + pwr(2ll, n - i - 1) % mod) % mod;     
      }else{
         mod = cnt - 1;
         if(cnt == 1){
            cout<<0<<"\n";
            continue;
         }
         ans = (val2 - pwr(2ll, n - i - 1) % mod + mod) % mod;
      }
      cout<<1 + f[ans]<<"\n";
   }








}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
   if(b&1) res = res * a % mod;
        a = a * a % mod;
   b >>= 1;
    }

    return res;
}



Measured memory_bytes: 4372
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include <cstdio>

#include <algorithm>
#define mx 9*1000000000LL*1000000000

using namespace std;
    long long h,w,n;
    int a, b;
int main(){
    cin>>h>>w>>n;
    map<pair<int,int>,int > nz; nz.clear();
    for(int i=0; i<n; i++){
	scanf("%d %d", &a, &b); a--; b--;
	for(int j=-2; j<=0; j++)
	    for(int k=-2; k<=0; k++){
		if(a+j<0 || b+k<0 || a+j+3>h || b+k+3>w)continue;
		pair<int, int> pp = make_pair(a+j, b+k);
		if(!nz[pp])nz[pp]=1; else nz[pp]++;
	    }
    }
    vector<long long> res(10, 0);
    int sum=0;
    for(auto it = nz.begin(); it!=nz.end(); it++){
	res[it->second]++;
//	cout<<it->first.first<<" "<<it->first.second<<" "<<it->second<<" "<<res[it->second]<<"\n";
	sum++;
    }
    res[0] = (h-2)*(w-2)-sum;
    for(int i=0; i<10; i++){
	cout<<res[i]<<"\n";
    }
}

Measured memory_bytes: 56448
import math

S=int(input())
z = 10**9+7
if S>= 7:
    ans = 1
    n = S//3
    b = S%3
    a = 3+b
    
    c = n-1
    for i in range(n-2):
        # s=math.factorial(a+c-1)/(math.factorial(a)*math.factorial(c-1))
        y = max([a,c-1])
        r = min([a,c-1])
        # print(y,r,a+c)
        s = 1
        for k in range(y+1,a+c):
            s*=k
        # print(s)
        s//=math.factorial(r)
        s%=z
        ans += s
        a +=3
        c-=1
        # print(s)
    if b==0:
        ans+= 1
    if b==1:
        ans += n
    if b == 2:
        ans += n*(n-1)//2 +n
elif S==6:
    ans = 2
elif 3<=S<6:
    ans =1
else:
    ans= 0
print(ans%z)


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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main()
{
    ll N;
    cin >> N;
    vector<ll> divVecN = divisor(N);
    vector<ll> divVecNminusOne = divisor(N - 1);
    vector<ll> ans;
    REPV(iter, divVecN)
    {
        if ((*iter) != 1)
        {
            ll num = N / (*iter);
            while(num % (*iter) == 0) num /= (*iter);
            if (num == 1) ans.push_back(*iter);
            if (num > (*iter)) if (num % (*iter) == 1) ans.push_back(*iter);
        }
    }
    REPV(iter, divVecNminusOne)
    {
        if (N % (*iter) == 1) ans.push_back(*iter);
    }

    cout << ans.size() << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int k, x;
    cin >> k >> x;

    if(500*k >= x) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256