akhauriyash/Code-Regression huggingface dataset:
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}

module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust, fromMaybe )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import           Data.Char
import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as UA
import Data.Bits
import Control.Monad.State.Strict
import qualified Data.Array.ST as STA
import qualified Data.Array.IO as IOA
import qualified Data.Array.MArray as MA
import Control.Monad.ST
import System.IO (stdin)
import Control.Arrow
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Generic as GV
import qualified Data.Vector.Mutable as MV
import Data.Ix
import Data.Ord (Down(Down))
import qualified Data.Sequence as Seq
import Data.Foldable (toList)
import Data.Fixed

debug = False

ts :: Show a => a -> a
ts a = if debug then traceShowId a else a


readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- readInts
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- readInts
    return (a, b, c)


readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

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

readIntV :: Int -> IO (UV.Vector Int)
readIntV n = GV.unfoldrN n (fmap (fmap BC.tail) . BC.readInt) <$> BC.getLine

readIntegersV :: Int -> IO (V.Vector Integer)
readIntegersV n = GV.unfoldrN n (fmap (fmap BC.tail) . BC.readInteger) <$> BC.getLine

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

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

solve :: Int -> [Int] -> Int
solve x ps = head $ filter (\a -> S.notMember a pset) ([0..] >>= mkTwo) where
  pset = S.fromList ps
  mkTwo n = [x - n, x + n]

main :: IO ()
main = do
  (x, n) <- readTuple2
  ps <- readInts
  print $ solve x ps


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

using namespace std;

#define lp(i,n) for(int i = 0; i <n;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define SZ(v) ((int)((v).size()))
typedef long long ll;

const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;

void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    init();
    ll n;
    cin>>n;
    string aa,bb,ans;
    vector<int>a(n);
    vector<int>b(n);
    int i=1;
    for(int &x:a){
        cin>>x;
        aa+=x+'0';
        ans+=i+'0';
        i++;
    }
    for(int &x:b){
        cin>>x;
        bb+=x+'0';
    }
    vector<string>res;
    do{
        res.push_back(ans);
    }while(next_permutation(all(ans)));
    sort(all(res));
    int pos1=0,pos2=0;
    bool f=false,f2=false;
    for(int i=0;i<res.size();i++){
        if(res[i]==aa&&!f){
            pos1=i;
            f=true;
        }
        if(res[i]==bb&&!f2){
            pos2=i;
            f2=true;
        }
        if(f&&f2)break;
    }
    cout<<abs(pos1-pos2);
    return 0;
}

Measured memory_bytes: 2424
#include <bits/stdc++.h>
using namespace std;
#define MaxN 55556

int prosti[MaxN];

void eratostenovoSito()
{
    for (int i = 0; i < MaxN; i++)
        prosti[i] = 1;
    prosti[0] = 0, prosti[1] = 0;
    for (int i = 2; i*i <= MaxN; i++)
        if (prosti[i])
        for (int j = i * i; j <= MaxN; j += i)
            prosti[j] = 0;
}

int main()
{
    int n;
    vector<int> v;
    vector<int> v1;
    cin >> n;
    eratostenovoSito();
    for (int i=0;i<MaxN;i++)
        if(prosti[i])
            v.emplace_back(i);
    for (int i=0;i<v.size();i++)
    {
        if(v[i]%10==1)
            v1.emplace_back(v[i]);
    }
    for (int i=0;i<n;i++)
        cout << v1[i] << " ";
    return 0;
}


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

int main() {
	int N, V, C;
	cin >> N;
	int total = 0;
	vector<int> value(N);
	vector<int> cost(N);
	for (int i = 0; i < N; i++) {
		cin >> V;
		value.at(i) = V;
	}
	for (int j = 0; j < N; j++) {
		cin >> C;
		cost.at(j) = C;
	}
	for (int k = 0; k < N; k++) {
		if (value.at(k) > cost.at(k)) {
			total += value.at(k) - cost.at(k);
		}
		else {
			continue;
		}
	}
	cout << total << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
using ll = long long;

int main() {
	int n, x; cin >> n >> x;
	vector<int> m(n); rep(i, 0, n) cin >> m[i];

	int ans = 0, src = x;
	rep(i, 0, n) {
		ans++;
		x -= m[i];
	}
	SORT(m);
	while (x >= 0) {
		ans++;
		x -= m[0];
	}

	cout << ans - 1 << endl;

	return 0;
}

Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = 0
    for i, a in enumerate(A):
        if (i+1)%2==1 and a%2==1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9048
#include<iostream>
#include<stdio.h>

using namespace std;

int main(void)

{
    int a, i, j, c, n;
    string s;
    cin>>n>>s;
    int b = s.size();
    for(i = 0; i < b; i++){
        j = s[i]-64;
        //cout<<j<<endl;
        j += n;
        a = j%26;
        if(a == 0)
            a = 26;
        c = 'A'+a;
        printf("%c", ('A'+a-1));
    }
    cout<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include<vector>
#include<utility>
#include<fstream>
#include<queue>
#include <iomanip>
#include<numeric>
#include<set>
#include<map>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i,n) for(int i=0;i<n;i++)
char ca;
const int MOD = 1000000007;
ll  c = 0, d = 0, e = 0, f = 0,g=0, n, m,i, j, k, h, w, o, a[100005], b[10000] = {};
queue<ll> q;
string s;
pair<ll, ll> p[20][20];
vector<vector<ll>> v;
const int MAX = 2005;
long long fac[MAX], finv[MAX], inv[MAX];

int main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n) {
		if (a[i] % 2 == 1)continue;		
		if (a[i] % 3 != 0 && a[i] % 5 != 0) {
			cout << "DENIED";
			return 0;
		}
	}
	cout << "APPROVED";

	return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

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

    for(int i = 0; i < s.size(); i++){
        cout << s[i] << t[i] ;
    }
}

Measured memory_bytes: 3632
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <stdlib.h>
#include <ctype.h>
#include <stack>
#include <bitset>
#include <iterator>
using namespace std;
#define ull unsigned long long
#define ll long long
const int maxn=1e5+5;
int id[maxn],b[maxn];
ll a[maxn],cost;
int n,m;
bool cmp(int i,int j){
	return a[i]<a[j];
}
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) scanf("%lld%d",&a[i],&b[i]);
	for(int i=0;i<n;++i) id[i]=i;
	sort(id,id+n,cmp);
	for(int i=0;i<n;++i){
		int u=id[i];			
		if(m>b[u]) cost+=b[u]*a[u],m-=b[u];
		else{
			cost+=a[u]*m;
			break;
		}
	}
	printf("%lld\n",cost);
}

Measured memory_bytes: 1920
import java.util.Scanner;
class Main {
	public static void main(String args[]){
		int[] card = new int[3];
		Scanner scan = new Scanner(System.in);
		int i;
		
		while(scan.hasNext()){
			for(i=0;i<3;i++){
				card[i] = scan.nextInt();
			}
			double y=0;
			for(i=1;i<=10;i++){
				if(i!=card[0] && i!=card[1] && i!=card[2]){
					if(card[0]+card[1]+i<=20){
						y++;
					}
				}
			}
			if(y/7*100 >= 50){
				System.out.println("YES");
			}else{
				System.out.println("NO");
			}
		}
	}
}

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

void dfs(string& buf, char max_, size_t at) {
  // cout << buf.size() << " " << max_ << " " << at << endl;
  if (buf.size() <= at) {
    cout << buf << endl;
  } else {
    for (char c = 'a'; c <= max_; ++c) {
      buf[at] = c;
      dfs(buf, max_, at + 1);
    }
    buf[at] = max_ + 1;
    dfs(buf, max_ + 1, at + 1);
  }
}

void solve() {
  int n;
  cin >> n;
  string buf(n, '\0');
  assert(buf.size() == n);
  dfs(buf, 'a' - 1, 0);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}


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

int main(){
  int n,m,q;
  cin>>n>>m>>q;
  
  vector<vector<int>> ans(n+2, vector<int>(n+1,0));
  vector<vector<int>> city(n+1,vector<int>(n+1,0));
  
  for(int i=0; i<m; i++){
    int in1,in2;
    cin>>in1>>in2;
    city[in1][in2]++;
  }
  for(int i=0; i<n+1; i++){
    for(int j=1; j<n+1; j++){
      city[i][j] += city[i][j-1];
    }
  }
  
  for(int i=n; i>=0; i--){
    for(int j=i; j<n+1; j++){
      ans[i][j] = ans[i+1][j] + city[i][j];
    }
  }
  
  for(int i=0; i<q; i++){
    int q1,q2;
    cin>>q1>>q2;
    cout<<ans[q1][q2]<<endl;
  }
//  for(int i=0; i<n+1, i++){
//    sort(city[i].begin(), city[i].end());
//  }
  
  for(int i=1; i<n+1; i++){
    for(int j = 0; j<n+1; j++){
      
    }
  }
}



Measured memory_bytes: 2944
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
      if(n % 1000 == 0){
                    System.out.println(0);
      }else {
            System.out.println(1000 - (n % 1000));
      }
	}
}

Measured memory_bytes: 35680
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1 << 28;
const int MAX   = 100;

int n, m;
int sum[2];
int card[2][MAX];

void solve(){
    int t, h;
    int min_val = INF;
    
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(sum[0] - card[0][i] + card[1][j] == sum[1] + card[0][i] - card[1][j]){
                if(card[0][i] + card[1][j] < min_val){
                    t       = card[0][i];
                    h       = card[1][j];
                    min_val = t + h;
                }
            }
        }
    }
    
    if(min_val < INF){
        printf("%d %d\n", t, h);
    }
    
    else {
        printf("-1\n");
    }
}

int main(){
    
    while(scanf("%d %d", &n, &m), n > 0){
        
        fill_n(sum, 2, 0);
        
        for(int i = 0; i < 2; ++i){
            for(int j = 0, l = (i == 0 ? n : m); j < l; ++j){
                scanf("%d", &card[i][j]);
                sum[i] += card[i][j];
            }
        }
        
        solve();
    }
    
    return 0;
}

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

#define ll long long

int main()
{
	ll n, m, mod = 1e9 + 7;	cin >> n >> m;
	char a[n][m]; ll dp[n][m];	memset(dp, 0, sizeof dp);
	for (ll i = 0; i < n; i ++){
		for (ll j = 0; j  < m; j ++){
			cin >> a[i][j];
		}	
	}	
	dp[0][0] = 1;
	for (ll i = 0; i < n; i ++){
		for (ll j = 0; j < m; j ++){
			if (a[i][j] == '.'){
				if (i > 0)
					dp[i][j] = (dp[i][j] + dp[i - 1][j]%mod)%mod;
				if (j > 0)
					dp[i][j] = (dp[i][j] + dp[i][j - 1]%mod)%mod;
			}
		}
	}
	cout << (dp[n - 1][m - 1]%mod + mod)%mod << "\n";
}

Measured memory_bytes: 9088
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int num = 0;
		int heightBorder = 0;
		int count = 0;

		// 数の入力
		num = scan.nextInt();
		heightBorder = scan.nextInt();
		for (int i = 0; i < num; i++) {
			if (scan.nextInt() >= heightBorder) {
				count++;
			}
		}

		System.out.println(count);
	}
}


Measured memory_bytes: 46612
#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=100005;
    const ll inf=1000LL*1000*1000;
    int n,m,f[N];ll mx[N],mn[N],dis[N];
    int F(int x){
    	if(x==f[x])return x;
    	int t=F(f[x]);
    	dis[x]+=dis[f[x]];
    	f[x]=t;
    	return f[x];
    }
    int main(){
    	//freopen("aa.in","r",stdin);
    	int i,j;
    	scanf("%d%d",&n,&m);
    	for(i=1;i<=n;++i)f[i]=i,mx[i]=-inf*2,mn[i]=inf*2;
    	int ok=1;
    	for(i=1;i<=m;++i){
    		int l,r,d;
    		scanf("%d%d%d",&l,&r,&d);
    		if(!ok)continue;
    		int x=F(l),y=F(r); 
    		if(x==y){
    			if(dis[r]-dis[l]!=d)ok=0;
    		}else{
    			f[y]=x;
    			dis[y]=d+dis[l]-dis[r];
    		}
    	}
    	for(i=1;i<=n;++i){
    		F(i);
    		mx[f[i]]=max(mx[f[i]],dis[i]);
    		mn[f[i]]=min(mn[f[i]],dis[i]);
    		if(mx[f[i]]-mn[f[i]]>inf)ok=0;
    	}
    	puts(ok?"Yes":"No");
    	return 0;
    }

Measured memory_bytes: 2944
/*
 Abu Jafor Mohammad Saleh
 ios_base :: sync_with_stdio(false);
 cin.tie(NULL);
 */

#include<cstdio>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include <algorithm>
#include <unordered_map>
#include<fstream>
#define f first
#define s second
#define MOD 1000000007

#define INF (int)1e9
#define PI 3.1415926535897932384626433832795
#define BOUNDARY(i, j) ((i >= 0 && i < rows) && (j >= 0 && j < coloums))
#define mx 6e5 + 100;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//#include<bits/stdc++.h>
#define ll long long
const int maxn = 20005;
using namespace std;
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
int rows,coloums;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}


int main ()
{
    fast;
    ll a,b;
    cin>>a>>b;
    ll arr[a+1];
    map<ll,ll> mp;
    ll s =0;
    for(int i=0;i<a;i++)
    {
        cin>>arr[i];
     //   mp[arr[i]]++;
       // s += arr[i];
    }
    
    //if(s>=a)
      //  cout<<"Yes"<<endl;
   // else
       // cout<<"No"<<endl;
    sort(arr,arr+a);
    reverse(arr,arr+a);
    
    for(int i=b;i<a;i++)
    {
        s+= arr[i];
    }
    
    cout<<s<<endl;
    
    
    
    
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int nil=-1;

struct node{
    int p,l,r;
};
struct node t[10000];
int n;

void preparse(int u){
    if(u==nil)return;
    cout<<" "<<u;
    preparse(t[u].l);
    preparse(t[u].r);
}

void inparse(int u){
    if(u==nil)return;
    inparse(t[u].l);
    cout<<" "<<u;
    inparse(t[u].r);
}

void postparse(int u){
    if(u==nil)return;
    postparse(t[u].l);
    postparse(t[u].r);
    cout<<" "<<u;
}

int main(){
    int v,l,r,root;
    
    cin>>n;
    for(int i=0;i<n;i++){
        t[i].p=nil;
    }
    for(int i=0;i<n;i++){
        cin>>v>>l>>r;
        t[v].l=l;
        t[v].r=r;
        if(l!=nil)t[l].p=v;
        if(r!=nil)t[r].p=v;
    }
    for(int i=0;i<n;i++){
        if(t[i].p ==nil){
            root=i;
        }
    }
    cout<<"Preorder"<<endl;
    preparse(root);
    cout<<endl;
    cout<<"Inorder"<<endl;
    inparse(root);
    cout<<endl;
    cout<<"Postorder"<<endl;
    postparse(root);
    cout<<endl;
    
    return 0;
}



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

int main(){
  int n; cin>>n;
  string b;
  if(n==1){
    int a; cin>>a;
    cout<<a<<endl;
    return 0;
  }
  vector<string> s(n+1);
  rep(i,n){
    cin>>s[i+1];
  }
  if(n%2==0){
    for(int i=n; i>=2; i-=2){
      cout<<s[i]<<" ";
    }
    for(int i=1; i<=n-1; i+=2){
       cout<<s[i]<<" ";
    }
  }else{
    for(int i=n; i>0; i-=2){
      cout<<s[i]<<" ";
    }
    for(int i=2; i<=n-1; i+=2){
      cout<<s[i]<<" ";
    }
  }
  cout<<endl;
}

Measured memory_bytes: 9580
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

class ARatingGoal {
public:
	void solve(istream& in, ostream& out) {
        int a, b; in >> a >> b;
        out << 2 * b - a << endl;
	}
};

int main() {
	ARatingGoal solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S, T;
  cin >> S >> T;
  int sousa = 0; //操作回数
  int size = S.size();
  for (int i = 0; i < size; i++) {
    if (S[i] != T[i]) {
      sousa++; //異なる文字数を追加
    }
  }
  cout << sousa << endl;
}

Measured memory_bytes: 3836
import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
   Scanner kbd = new Scanner(System.in);
   long n=kbd.nextLong();
   long a=kbd.nextLong();
   long b=kbd.nextLong();

   if(a==0){
     System.out.println(a);
   }else if(b==0){
     System.out.println(n);
   }else{
   long k=a+b;
   long x;
   if(n%k>a){
     x=a;
   }else{
     x=n%k;
   }
   System.out.println(n/k*a+x);
 }
}
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define DEBUG

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

	for(int i = n; i < 1000; i++)
	{
		vi num;
		int nx = i;
		while(nx != 0)
		{
			num.push_back(nx % 10);
			nx /= 10;
		}
		reverse(all(num));
		if(num[0] == num[1] && num[0] == num[2])
		{
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
ans = [0]*(10**5)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            ans[a] += 1
for i in range(n):
    print(ans[i+1])


Measured memory_bytes: 69396
str = gets.chomp
gets.to_i.times do
	line = gets.chomp.split
	if (start_pos = line[1].to_i) == 0 then
		head = ""
	else
		head = str[0..start_pos - 1]
	end
	if (end_pos = line[2].to_i) == str.length - 1 then
		foot = ""
	else
		foot = str[(end_pos + 1)..(str.length - 1)]
	end
	body = str[start_pos..end_pos]
	if line[0] == "print" then
		puts body
		elsif line[0] == "replace" then
		str = head + line[3] + foot
	else
		str = head + body.reverse + foot
	end
end

Measured memory_bytes: 8836
Module Module1
    
    Dim X, A, B As Integer
    Dim bf As Integer

    Sub Main()
        X = Console.ReadLine
        A = Console.ReadLine
        B = Console.ReadLine
    
        bf = X - A
    
        Do
            If bf < B Then Exit Do
            bf = bf - B
        Loop
    
        Console.WriteLine(bf)
    
    End Sub

End Module


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

template<class T> class segtree{
public:
    int n;
    vector<T> dat,sum; //区間の和,区間に一様に足された値
    segtree(int size,T x){
        n=1;
        while(n<size) n*=2;
        dat.assign(2*n-1,0);
        sum.assign(2*n-1,0);
        add(0,size,x);
    }
    void add(int a,int b,T x){ add(a,b,x,0,0,n); }
    T add(int a,int b,T x,int k,int l,int r){
        if(b<=l or r<=a) return dat[k];
        if(a<=l and r<=b){
            sum[k]+=x;
            return dat[k]+=x;
        }
        int m=(l+r)/2;
        return dat[k]=max(add(a,b,x,2*k+1,l,m),add(a,b,x,2*k+2,m,r))+sum[k];
    }
    T query(int a,int b){ return query(a,b,0,0,n); }
    T query(int a,int b,int k,int l,int r){
        if(b<=l or r<=a) return -inf64;
        if(a<=l and r<=b) return dat[k];
        int m=(l+r)/2;
        return max(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r))+sum[k];
    }
};

void solve(){
    i64 N,M;
    cin >> N >> M;
    
    vector<pair<i64,i64>> ps;
    rep(i,0,N){
        i64 L,R;
        cin >> L >> R;
        ps.push_back(make_pair(L,R));
    }
    sort(ps.begin(),ps.end());

    segtree<i64> seg(M+2,0);
    rep(i,1,M+1) seg.add(1,i+1,-1);
    i64 ans=0;
    for(auto &p:ps){
        i64 l=p.first,r=p.second;
        seg.add(l+1,r+1,1);
        ans=max(ans,seg.query(l+1,M+2)-l);
    }
    ans=max(ans,N-M);
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


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

using ll = long long;
using Pii = std::pair<int, int>;
using Pll = std::pair<ll, ll>;

const ll INF = (ll)1e16;
const int MOD = 1000000007;

using namespace std;

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

    int N, M;
    cin >> N >> M;

    vector<int> A(N+10, 0), dp(N+1, 0);
    for (int i = 0, a; i < M; ++i) {
        cin >> a;
        A[a] = 1;
    }

    dp[0] = 1;
    for (int i = 1; i <= N; ++i) {
        if (A[i]) continue;
        
        if (!A[i-1]) {
            dp[i] += dp[i-1];
            dp[i] %= MOD;
        }
        if (i > 1 && !A[i-2]) {
            dp[i] += dp[i-2];
            dp[i] %= MOD;
        }
    }

    cout << dp[N] << endl;

    return 0;
}


Measured memory_bytes: 1024
#define SORT(v) sort(v.begin(), v.end())
#include "iostream"
#include "map"
#include "vector"
#include <stack>
#include "cstdlib"
#include <algorithm>
#include <cstdarg>
#include "cstdio"
// #include "ane.cpp"

#define INF (int)1e9
#define LLINF (long long)1e18
#define NMAX 200
#define MMAX 200
#define MOD 100000
using namespace std;

// コメントアウトするとdb_printf()を実行しない
#define DEBUG
// デバッグ用printf
void db_printf(const char* format, ...){
    #ifndef DEBUG
    return;
    #endif
    va_list arg;
    va_start(arg, format);
    vprintf(format, arg);  // コンソールに出力
    va_end(arg);
}
// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
typedef pair<int, int> p;
typedef long long ll;

ll N,M,K,A,B,C,D,E;
int dp[NMAX][MMAX] = {};

static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};

string T, ans[] = {"SS","SW","WS","WW"};

void solve(){
    // 解答アルゴリズム
    for (int k = 0; k < 4; ++k)
    {
        for (int i = 1; i <= N; ++i)
        {
            if (T[i-1] == 'o')
            {
                if(ans[k].substr(i-1, 2) == "SS"){
                    ans[k] += 'S';
                }
                else if (ans[k].substr(i-1, 2) == "SW"){
                    ans[k] += 'W';
                }
                else if(ans[k].substr(i-1, 2) ==  "WS"){
                    ans[k] += 'W';
                }
                else if(ans[k].substr(i-1, 2) == "WW"){
                    ans[k] += 'S';
                }
                else {
                    cerr << "error\n";
                }
            }
            else
            {
                if(ans[k].substr(i-1, 2) == "SS"){
                    ans[k] += 'W';
                }
                else if (ans[k].substr(i-1, 2) == "SW"){
                    ans[k] += 'S';
                }
                else if(ans[k].substr(i-1, 2) ==  "WS"){
                    ans[k] += 'S';
                }
                else if(ans[k].substr(i-1, 2) == "WW"){
                    ans[k] += 'W';
                }
                else {
                    cerr << "error\n";
                }
            }
        }
        if (ans[k][0] == ans[k][N] && ans[k][1] == ans[k][N+1])
        {
            cout << ans[k].substr(1, N) << endl;
            return;
        }
    }
    cout << "-1\n";
}
void debug(){
    // デバッグ用出力
    cout << "debug /*\n";

    for (int k = 0; k < 4; ++k)
    {
        cout << "ans[" << k << "]: " << ans[k] << endl;
    }

    cout << "*/ debug\n";
}
void answer(){
    // 解答出力
    // cout << ans << endl;
}
int main(int argc, char const *argv[])
{
    // 入力の読み込み，番兵法
    ios::sync_with_stdio(false);

    Fill(dp, -1);

    cin >> N >> T;
    solve();
    #ifdef DEBUG
    // debug();
    #endif
    answer();

    return 0;
}

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

int main () {
  int N; cin >> N;
  vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i];
  vector<bool> visited(100001); for (int i = 1; i <= N; i++) visited[i] = false;
  
  int ans = 0;
  int aa = 1;
  while (aa != 2) {
    if (visited[aa]) break;
    visited[aa] = true;
    aa = a[aa-1];
    ans++;
  }
  if (ans > 0 && aa == 2) cout << ans << endl;
  else cout << -1 << endl;
}
  
  
    
    

Measured memory_bytes: 768
n, m = map(int, input().split())
X = sorted([int(x) for x in input().split()])
Y = []


def main() -> None:
    global Y
    for i in range(m - 1):
        Y += [X[i + 1] - X[i]]

    Y.sort()
    for i in range(n - 1):
        if len(Y) == 0:
            break
        Y.pop()

    if len(Y) == 0:
        print(0)
    else:
        print(sum(Y))


if __name__ == "__main__":
    main()


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

string N;

int main() {
    cin >> N;

    bool f = false;
    for (int i = 0; i < 2; i++) {
        if (N[i] == N[i+1] && N[i+1] == N[i+2]) {
            f = true;
            break;
        }
    }

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

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll mod=998244353;
const int maxn=310;
int n,m,cnt;
ll mi[maxn],ans;
bitset<maxn> a,p[maxn];
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(m); mi[0]=1; int x;
	for (int i=1;i<=max(n,m);i++) mi[i]=mi[i-1]*2%mod;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<m;j++) read(x),a.set(j,x);
		for (int j=m-1;j>=0;j--) {
			if (a[j]==0) continue;
			if (p[j].none()) { p[j]=a; cnt++; break; }
			a^=p[j];
		}
	}
	ans=(mi[n]-mi[n-cnt]+mod)*mi[m-1]%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
#define MAX 30

int dx[6] = {1, 1, 0, -1, -1, 0};
int dy[6] = {0, 1, 1, 0, -1, -1};

int main() {
	int t, n, x, y;
	bool m[MAX * 4 + 1][MAX * 4 + 1];
	queue<pair<int, pair<int, int>>> q;
	while (cin >> t >> n, t) {
		fill(m[0], m[MAX * 4 + 1], false);
		for (int i = 0; i < n; i++) {
			cin >> x >> y;
			x += MAX * 2; y += MAX * 2;
			m[y][x] = true;
		}
		cin >> x >> y;
		x += MAX * 2; y += MAX * 2;
		int c = 1;
		m[y][x] = true;
		q.push(make_pair(t, make_pair(x, y)));
		while (!q.empty()) {
			auto e = q.front();
			q.pop();
			t = e.first; x = e.second.first; y = e.second.second;
			if (t > 0) {
				for (int i = 0; i < 6; i++) {
					if (!m[y + dy[i]][x + dx[i]]) {
						c++;
						m[y + dy[i]][x + dx[i]] = true;
						q.push(make_pair(t - 1, make_pair(x + dx[i], y + dy[i])));
					}
				}
			}
		}
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 3096
require 'pp'

def gets; ARGF.gets; end

class Solver

  def initialize
  end

  def main
    a, b = gets.chomp.split
    if a < b
      puts "<"
    elsif a == b
      puts "="
    else
      puts ">"
    end
  end
end

if __FILE__ == $0
  Solver.new.main
end


Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int A,B,C;
    cin >> A>>B>>C;
    int N;
    cin >>N;
    int counta=0;
    for(int i=0;i<10;i++){
        if(A<B){
            break;
        }
        B*=2;
        counta++;
    }
    
    for(int i=0;i<10;i++){
        if(B<C){
            break;
        }
        C*=2;
        counta++;
    }
    if(counta<=N)  {
        cout << "Yes"<<endl;
    }
    else if (counta>N)
        cout <<"No"<<endl;
    
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define fcout cout << fixed << setprecision(10)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acos(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


int A, B, C;


signed main(){
    cin >> A >> B >> C;

    if(A == B and B != C) Yes;
    else if(A == C and C != B) Yes;
    else if(B == C and C != A) Yes;
    else No;

    return 0;
}

Measured memory_bytes: 256
S = list(input())
N = len(S)


def dfs(count, str):
    if count == N:
        return eval(str)
    plus = dfs(count + 1, str + '+' + S[count])
    noaction = dfs(count + 1, str + S[count])
    return plus + noaction


print(dfs(1, S[0]))


Measured memory_bytes: 3060
import collections


def resolve():
    N = int(input())
    S = [input() for _ in range(N)]

    group = collections.Counter(S)

    print('AC x ' + str(group['AC']))
    print('WA x ' + str(group['WA']))
    print('TLE x ' + str(group['TLE']))
    print('RE x ' + str(group['RE']))


resolve()

Measured memory_bytes: 16488
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = std::numeric_limits<long long>::max();
const double PI = acos(-1);
#define fir first
#define sec second
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m,k, s, t, q, ans, sum, a, last;
struct Edge { LL to,cost; };
vector<LL>v;
string str, ss;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
int main() {
	cin >> n >> m >> s;
	if (n + 1 < m + s)cout << -1 << endl;
	else if (n > m*s)cout << -1 << endl;
	else {
		rep(i, s)v.push_back(s - i);
		sum = s;
		m--;
		while (m > 0) {
			if (n - sum - s < m) {
				rep(i, n - sum - m + 1)v.push_back(n - m + 1 - i);
				sum += n - sum - m + 1;
			}
			else if (n - sum == m) {
				sum++;
				v.push_back(sum);
			}
			else {
				rep(i, s)v.push_back(sum + s - i);
				sum += s;
			}
			m--;
		}
		rep(i, v.size()) {
			cout << v[i];
			if (i != v.size() - 1)cout << " ";
		}
		cout << endl;
	}
	return 0;
}


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

int main() {
   int k;
   cin >> k;
   int arr[32] = {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};
   cout << arr[k - 1] << "\n";
	return 0;
}


Measured memory_bytes: 256
/*
 *
 *
 */

#include <bits/stdc++.h>

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for(int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SQ(n) (n) * (n)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vc> vvc;
typedef vector<vll> vvll;

double dist(double x1, double y1, double z1, double x2, double y2, double z2) {
  return sqrt(SQ(x1 - x2) + SQ(y1 - y2) + SQ(z1 - z2));
}

struct Station {
  double x, y, z, r;
};

int main() {
  int n;
  while(cin >> n, n) {
    vector<Station> stations;
    REP(i, n){
      Station st;
      cin >> st.x >> st.y >> st.z >> st.r;
      stations.push_back(st);
    }

    double ans = 0;
    set<int> cell;

    multimap<double, int> corridor;
    corridor.insert({0, 0});

    while (cell.size() < n) {
      double len = corridor.begin()->first;
      int c = corridor.begin()->second;
      corridor.erase(corridor.begin());

      if (!cell.insert(c).second) continue;
      ans += len;

      for (int i = 0; i < n; i++) {
        if (cell.find(i) == cell.end()) {
          Station st = stations[i];
          Station stc = stations[c];
          corridor.insert({max(0.0, dist(st.x, st.y, st.z, stc.x, stc.y, stc.z) - st.r - stc.r), i});
        }
      }
    }

    printf("%.3f\n", ans);
  }
}

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
vector<long long> a[n+1];
for(int i=1;i<=n;++i)
{long long d;cin>>d;
a[i].push_back(d);a[i].push_back(i);
}
sort(a+1,a+n+1);
long long b[n+1];
for(int i=1;i<=n;++i)
{
    if(i<=(n)/2)
    {
        b[a[i][1]]=a[(n+2)/2][0];
    }
    else
    {b[a[i][1]]=a[(n)/2][0];
    }
}
for(int i=1;i<=n;++i)
    cout<<b[i]<<"\n";
}


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

int main(){
	double n;
	while(cin >> n){
		if(n <= 48.00) cout << "light fly" << endl;
		else if(48.00 < n && n <= 51.00) cout << "fly" << endl;
		else if(51.00 < n && n <= 54.00) cout << "bantam" << endl;
		else if(54.00 < n && n <= 57.00) cout << "feather" << endl;
		else if(57.00 < n && n <= 60.00) cout << "light" << endl;
		else if(60.00 < n && n <= 64.00) cout << "light welter" << endl;
		else if(64.00 < n && n <= 69.00) cout << "welter" << endl;
		else if(69.00 < n && n <= 75.00) cout << "light middle" << endl;
		else if(75.00 < n && n <= 81.00) cout << "middle" << endl;
		else if(81.00 < n && n <= 91.00) cout << "light heavy" << endl;
		else if(91.00 < n) cout << "heavy" << endl;
	}
}

Measured memory_bytes: 1228
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
int Adj[MAXN],V[MAXN*2],nxt[MAXN*2],c;
void AddEdge(int u,int v)
{
	c++;V[c]=v,nxt[c]=Adj[u];Adj[u]=c;
}
int dp[MAXN][21],n,ans;
void dfs(int u,int p)
{
	for(int i=Adj[u];i;i=nxt[i])
		if(V[i]!=p)
		{
			int v=V[i];
			dfs(v,u);
			for(int j=0;j<=20;j++)
				dp[u][j]+=dp[v][j];
		}
	int k=0;
	for(int i=20;i>=0;i--)
		if(dp[u][i]>1)
		{
			k=i+1;
			break;
		}
	while(dp[u][k]) k++;
	dp[u][k]++;
	for(int i=0;i<k;i++)
		dp[u][i]=0;
	ans=max(ans,k);
}
int main()
{
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		AddEdge(u,v);
		AddEdge(v,u);
	}
	dfs(1,0);
	printf("%d\n",ans);
}

Measured memory_bytes: 16000
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
res = []


def resolve():
    n, k = map(int, input().split())
    D = set(list(map(int, input().split())))
    Available = []

    for i in range(10):
        if i not in D:
            Available.append(str(i))


    def dfs(Price):
        if len(Price) == 5:
           return

        for value in Available:
            Price.append(value)
            res.append(int("".join(Price)))
            dfs(Price)
            Price.pop()

    dfs([])

    ans = f_inf
    for i in res:
        if i >= n:
            ans = min(ans, i)
    
    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 5784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define endl "\n"
using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;
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; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

Graph G;
vector<int> ans;

void dfs(int v, int p, int c) {
  ans[v] = c;
  for (auto nv : G[v]) {
    if (nv.first == p) continue;
    if (nv.second & 1) dfs(nv.first, v, 1-c);
    else dfs(nv.first, v, c);
  }
}

int main(void){
  int n; cin >> n;
  G.assign(n, vector<Edge>());
  FOR(i,0,n-2){
    int u,v,w; cin >> u >> v >> w;
    --u; --v;
    G[u].PB(Edge(v,w));
    G[v].PB(Edge(u,w));
  }
  ans.assign(n,0);
  dfs(0,-1,1);
  for(auto v: ans) cout << v << endl;
}




Measured memory_bytes: 8960
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)



int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<char>>A(H, vector<char>(W));
	rep(i, H) {
		rep(j, W) {
			cin >> A[i][j];
		}
	}
	int nx = 0;
	int ny = 0;
	while (1) {
		if (nx == H - 1 && ny == W - 1) {
			A[nx][ny] = '.';
			break;
		}
		else if (nx + 1 < H&&A[nx + 1][ny] == '#') {
				A[nx][ny] = '.';
				nx++;
			}
		else if (ny + 1 < W&&A[nx][ny + 1] == '#') {
				A[nx][ny] = '.';
				ny++;
			}
		else {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	
	rep(i, H) {
		rep(j, W) {
			if (A[i][j] == '#') {
				cout << "Impossible" << endl;
				return 0;
			}
		}
	}
	cout << "Possible" << endl;


}


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

#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<std::endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)
#define PI 3.14159265358979323846
#define EPS 1e-10
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())

int D = 365;
const int T = 26;

vector<int> c(T);
vector<vector<int>> s(D, vector<int>(T)); 

long long compute_score(vector<int> out) {
    long long score = 0;
    vector<int> last(T, 0);
    REP(d, (int)out.size()) {
        last[out[d]-1] = d+1;
        REP(i, T) {
            score -= (long long)(d+1 - last[i]) * c[i];
        }
        score += s[d][out[d]-1];

        // cout << score << endl;
    }

    return score;
}

vector<int> solve() {
    vector<int> out;
    REP(_, D) {
        int best_i = 1;
        long long max_score = -(1e18);
        FOR(i, 1, T+1) {
            out.emplace_back(i);
            long long score = compute_score(out);
            if (max_score < score) {
                max_score = score;
                best_i = i;
            }

            out.pop_back(); 
        }
        out.emplace_back(best_i);
    }

    return out;
}

void test_score() {
    vector<int> t(D);
    REP(i, D) cin >> t[i];
    compute_score(t);
}

int main(int argc, char const *argv[])
{
    int d_;
    cin >> d_;
    D = d_;
    
    REP(i, T) cin >> c[i];
    REP(i, D) REP(j, T) cin >> s[i][j];

    vector<int> out = solve();
    assert(out.size() == D);
    for (int t : solve()) {
        cout << t << endl;
    }

    return 0;
}


Measured memory_bytes: 3716
/** author: __nishad__ **/

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


typedef long long ll ;
typedef vector<ll> vll ;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(v) (v).begin(),(v).end()
#define precision(k) cout<<setprecision(k)<<fixed;
#define loop(i,a) for(int i=0; i<a;i++)
#define loop2(i,a,b) for(int i=(a);i<=(b);++i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define pb push_back
#define pi 3.14159265358979323
#define endl "\n"

int main()
{
    IOS;

    ll x, i, j;
    vll v;
    cin>>x;

    if(x == 1)
        cout<<"1";
    else{
        for(i=1; i<=x; i++){
            for(j=2; j<=x; j++){
                if(pow(i, j) == int(pow(i, j)) && (pow(i, j) <= x)){
                    v.pb(pow(i, j));
                }
            }
        }
        sort(all(v));

        cout<<v[v.size()-1];
    }



}



Measured memory_bytes: 640
#pragma GCC optimize("O2")
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<cmath>
#include<climits>
#include<random>
#include <iomanip>
#include <bitset>
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);

/////////////////////////////////////////////

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

///////////////////////////////
#define int long long

void solve(){

	char c;
	cin>>c;

	if(c >= 'a')
		cout<<'a'<<endl;
	else cout<<'A'<<endl;

}

signed main(){

	fast;
	int t = 1;
	//cin>>t;
	for(int i = 1 ; i <= t ; ++i)
		solve();
}

Measured memory_bytes: 3648
#include "bits/stdc++.h"

using namespace std;

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

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	string s;
	cin >> s;

	for (int i = 0; i < s.size() - 2; i++) {
		if (s[i] == s[i + 1] &&
			s[i] == s[i + 2]) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(true){
            int n=sc.nextInt();
            if(n==0) break;
            int max=0,min=1000,sum=0;
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                sum+=a;
                if(a>max) max=a;
                if(a<min) min=a;
            }
            sum=sum-max-min;
            System.out.println(sum/(n-2));
        }
    }
}


Measured memory_bytes: 29484