akhauriyash/Code-Regression huggingface dataset:
import scala.io.{StdIn => in}

object Main extends App {
  val s = in.readLine

  val t1 = s.head
  val t2 = s.drop(2).init
  val t3 = s.tail.filter(_ != 'C')
  val ans = if(t1 == 'A' && t2.count(_ == 'C') == 1 && t3.forall(_.isLower)) "AC"
    else "WA"
  println(ans)
}

Measured memory_bytes: 27212
import math

def tri_num(num):
    t = c = 0
    while t + c < num:
        c += 1
        t += c
    return c

def main():
    N = int(input())

    pf = {}
    m = N
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1

    ans = 0
    for i in pf.values():
        ans += tri_num(i)

    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9464
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl
#define INF 1000000;
#include <map>
#include <math.h>
 
using ll = long long;
using namespace std;

ll n, k;
const ll mod = 1000000007;


int main(){
   int a, b;
   cin >> a >> b;
   if(a/10>0||b/10>0) out(-1);
   else out(a*b);
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define dd double
#define ull unsigned long long
#define mes(x,y) memset(x,y,sizeof(x))
#define si(i) scanf("%d",&i)
#define ss(i) scanf("%s",(i))
#define sd(i) scanf("%lf",&i)
#define INF 0x3f3f3f3f
#define eps 1e-16
#define PI acos(-1)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

const int maxn=2e5+9;
const int mod=1e9+7;

ll gar(ll a,ll b){//最大公约数
    return b==0?a:gar(b,a%b);
}
int main(){
    FAST_IO;
    ll x,y;
    while(cin>>x>>y){
        if(y==1){
            cout<<"0"<<endl;continue;
        }
        else{
            ll z=x-y;
            cout<<z<<endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n;
llong x[105];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    llong ans = 1ll << 60ll;
    for (int i = 0; i <= 100; i++) {
        llong sans = 0;
        for (int j = 0; j < n; j++) {
            sans += (x[j] - i) * (x[j] - i);
        }

        ans = min(ans, sans);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define ll long long


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

	int a, b, c;
	cin >> a >> b >> c;
	int ans = b + c;
	if (ans > a) ans = a;
	ans -= b;
	ans = c - ans;
	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define lb(s,x) (lower_bound(all(s),x)-s.begin())
#define ub(s,x) (upper_bound(all(s),x)-s.begin())
#define uniq(a) a.erase(unique(all(a)),a.end())
#define bit(k) (1LL<<(k))
const int INF = 1e9;

#define debug(x) cerr<<(#x)<<": "<<(x)<<endl
template<class T,class U>
ostream& operator<<(ostream& o, const pair<T,U> &p){
    o<<"("<<p.first<<", "<<p.second<<")";
    return o;
}
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }


int main(void){
    int n;
    cin >> n;
    bool b1 = (n/100) <= 12 && (n/100) >= 1;
    bool b2 = (n%100) <= 12 && (n%100) >= 1;
    if (b1 && b2) {
        cout << "AMBIGUOUS" << endl;
    } else if (b1 && !b2) {
        cout << "MMYY" << endl;
    } else if (!b1 && b2) {
        cout << "YYMM" << endl;
    } else if (!b1 && !b2) {
        cout << "NA" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res=res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}


signed main() {
	int t = 0,a=0;
	string s;
	cin >> s;
	if (s[0] != 'A') {
		cout << "WA" << endl;
		return 0;
	}
	for (int i = 1; i < s.size(); i++) {
		if (s[i] < 'Z') {
			if (i > 1 && i < s.size() - 1 && a == 0 && s[i] == 'C') {
				a = 1;
			}
			else {
				cout << "WA" << endl;
				return 0;
			}
		}
	}
	if (a == 0) {
		cout << "WA" << endl;
		return 0;
	}
	cout << "AC" << endl;
}


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

typedef pair<string,int> bug;

bool check(string insect) {
  for ( int i = 1; i < insect.size(); i++ ) {
    if ( insect[0] != insect[i] ) return 0;
  }
  return 1;
}

char change( char a, char b ) {
  if ( a > b ) swap(a,b);
  if ( a == 'b' && b == 'g' ) return 'r';
  else if ( a == 'b' && b == 'r' ) return 'g';
  else return 'b';
}

void bfs ( string str ) {
  map<string,int> close;
  queue<bug> open;
  open.push(make_pair(str,0));
  close.insert(make_pair(str,1));
  int cnt = -1;
  while ( !open.empty() ) {
    bug b = open.front(); open.pop();
    string insect = b.first;
    if ( check(insect) ) {
      cnt = b.second;
      break;
    }
    
   
    for ( int i = 0; i < insect.size()-1; i++ ) {
      string tmp = insect;   
      if ( tmp[i] != tmp[i+1] ) {
	char nc = change( tmp[i],tmp[i+1] );
	tmp[i] = nc;
	tmp[i+1] = nc;
	if ( close[tmp] ) continue;
	open.push(make_pair(tmp,b.second+1));
	close[tmp] = 1;
      }
    }

  }
  
  if ( cnt == -1 ) cout << "NA" << endl;
  else cout << cnt << endl;
}

int main() {
  string str;
  while( cin >> str, str != "0" ) {
    bfs(str);
  }
  return 0;
}

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

int main()
{
    string s;
    cin >> s;
    int len = s.size();
    rep(i, len)
    {
        s[i] = 'x';
    }
    cout << s << endl;
    return 0;
}

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

string s;
int i,cnt=0;

int main(void){
  cin >> s;
  for(i=0 ; i<4 ; i++){
    if(s[i]=='-'){
      cnt--;
    }
    else{
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

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

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string a, b="";
cin >> a;
for (char i : a){
if (i == ','){
  b += " ";
}else{
b += i;
}
}

cout << b << "\n";
return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=100005;
int i,j,k,l,n,m,fx,fy;
int tmp[4],fa[inf],dis[inf];
bool f;
int find(int x)
{
	if (fa[x]!=x)
	{
		int org=fa[x];
		fa[x]=find(fa[x]);
		dis[x]+=dis[org];
		return fa[x];
	} 
	else return x;
}
void unite(int x,int y,int z)
{
	fx=find(x);
	fy=find(y);
	if (fx==fy)
	{
		if (dis[y]-dis[x]!=z)
			f=0;
	}
	else
	{
		dis[fy]=z+dis[x]-dis[y];
		fa[fy]=fx;
	}
}
int main()
{
	f=1;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		fa[i]=i;
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&tmp[1],&tmp[2],&tmp[3]);
		unite(tmp[1],tmp[2],tmp[3]);
		if (!f)
			break;
	}
	if (f)
		printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 896
package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
  "strings"
)

const size = 1000000
var reader = bufio.NewReaderSize(os.Stdin,size)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for ;isPrefix; {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func GetInput() (int,[]int64) {
  _ = NextLine()
  var s []string = strings.Split(NextLine()," ")
  var n int = len(s)
  var a []int64 = make([]int64,n)
  for i:=0;i<n;i++ {
    a[i],_ = strconv.ParseInt(s[i],10,64)
  }
  return n,a
}

func main() {
  var n,k int
  var a []int64
  n,a = GetInput()
  var d []string = make([]string,n)
  var s,m int64
  for i:=0;i<n;i++ {
    s += a[i]
  }
  k = len(strconv.FormatInt(s,2))
  for i:=0;i<n;i++ {
    d[i] = strconv.FormatInt(a[i],2)
    for ;len(d[i])<k; {
      d[i] = "0" + d[i]
    }
  }
  var v []int = make([]int,k)
  var l,r int
  for {
    ok := true
    for i:=0;i<k;i++ {
      if d[r][i:i+1] == "1" {
        v[i]++
        if v[i] == 2 { ok = false }
      }
    }
    if !ok {
      for {
        ok = true
        for i:=0;i<k;i++ {
          if d[l][i:i+1] == "1" {
            v[i]--
          }
          if v[i] == 2 { ok = false }
        }
        l++
        if ok { break }
      }
    }
    r++
    m += int64(r-l)
    if r == n { break }
  }
  fmt.Println(m)
}

Measured memory_bytes: 29184
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

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

  int n; cin >> n;
  vector<ll> a(n), b(n);
  ll tmp = 0;
  rep(i, n) {
    cin >> a[i];
    tmp -= a[i];
  }
  rep(i, n) {
    cin >> b[i];
    tmp += b[i];
  }
  ll sumA = 0, sumB = 0;
  rep(i, n) {
    ll dif = b[i]-a[i];
    if(dif > 0) sumA += (dif+1)/2;
    else sumB += -dif;
  }
  
  string ans = "Yes";
  if(sumA > tmp || sumB > tmp) ans = "No";
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 384
n = input()
s = ''
i = 1
while True:
    x = i
    if (x % 3 == 0):
        s = s + ' ' + str(i)
    else:
        while True:
            if (x % 10 == 3):
                s = s + ' ' + str(i)
                break
            x = int(x / 10)
            if x == 0:
                break
    i = i + 1
    if (i > n):
        break
print s

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

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

    int lmax = 1, rmin = n;

    for(int i=0;i<m;i++){
        int l, r;
        cin >> l >> r;
        if(lmax < l) lmax = l;
        if(rmin > r) rmin = r;
    }

    int ans = rmin - lmax + 1;
    if(ans < 0) ans = 0;

    cout << ans << endl;

    return 0;
}

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

int main(){
  int N;
  cin >> N;
  
  vector<int> d(N);
  for (int i = 0; i < N; i++) cin >> d.at(i);
  
  vector<int> num(101); //バケット
  for (int i = 0; i < N; i++) {
    num.at(d.at(i))++;
  }
  
  int res = 0;
  for (int i = 0; i < 101; i++) 
    if (num.at(i)) res++;
  
  cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

main()
{
int i[2],temp;

while(1)
 {
 scanf("%d %d",&i[0],&i[1]);
 if((i[0] == 0) && (i[1] == 0)) break;
 if(i[0]>i[1])
   {
    temp=i[0];i[0]=i[1];i[1]=temp;
   }
 printf("%d %d\n",i[0],i[1]);
 }
}

Measured memory_bytes: 1028
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
long long ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=k+1;i<=n;i++)
	{
		ans=ans+(i-k)*(n/i);
		if(k)ans=ans+max((n%i)-k+1,0);
		else ans=ans+max((n%i)-k,0);
	}
	printf("%lld\n",ans);return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>
#include<sstream>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cout << '\n';}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << '[' << *it << " = " << a << "]  ";
    err(++it, args...);
}

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<lli, lli> tii;
typedef tuple<lli, lli, lli> tiii;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;


void solve(){
	string sa,sb,sc; cin>>sa>>sb>>sc;
	int ca=0,cb=0,cc=0;
	int t=0;
	while(1){
		if(t==0){
			if(ca==sa.size()){
				cout<<"A";
				break;
			}
			t=sa[ca++]-'a';
		}else if(t==1){
			if(cb==sb.size()){
				cout<<"B";
				break;
			}
			t=sb[cb++]-'a';		
		}else{
			if(cc==sc.size()){
				cout<<"C";
				break;
			}
			t=sc[cc++]-'a';		
		}	
	}
}

int main(){
	fast_io
	int tc=1;
	//cin>>tc;
	while(tc--){solve();}
	return 0;
}

Measured memory_bytes: 888
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define LL long long
LL N;

int main(){
    cin>>N;
    if(N==0){cout<<0<<endl;return 0;}
    LL L=1,R=N,Ans=0;
    while(L<=R){
        LL mid=(L+R)>>1;
        if(mid*(mid+1LL)>=2LL*N){Ans=mid;R=mid-1;}
        else L=mid+1;
    }
    cout<<Ans<<endl;
    
    return 0;
}

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


int main() {
  
  string S;
  cin >> S;

  int N = S.size();

  long long dp[N + 1][13];
  for(int i = 0;i <= N;i++) {
    for(int j = 0;j < 13;j++) {
      dp[i][j] = 0;
    }
  }
  
  dp[0][0] = 1;


  for(int i = 0;i < N;i++) {
    int n;
    if(S.at(i) == '?') {
      n = -1;
    }else {
      n = S.at(i) - '0';
    }

     //cout << n << endl;

    for(int j = 0;j < 10;j++) {
      if(n != -1 && n != j) continue;
      
      for(int k = 0;k < 13;k++) {
        dp[i+1][(k * 10 + j) % 13] += dp[i][k];
      }
    }
    for(int j = 0;j < 13;j++) dp[i+1][j] %= MOD;
  }

  // for(int i = 0;i <= N;i++) {
  //   for(int j = 0;j < 13;j++) {
  //      if(j) cout << " ";
  //      cout << dp[i][j]; 
  //   }
  //   cout << endl;
  // }

  cout << dp[N][5] << endl;
}

Measured memory_bytes: 10624
from itertools import accumulate, chain
 
n, c = map(int, input().split())
xs, vs = zip(*(map(int, input().split()) for _ in range(n)))
 
ds = [j - i for i, j in zip(chain([0], xs), chain(xs, [c]))]
 
clockwise1      = chain([0], (v - d*2 for v, d in zip(accumulate(vs), accumulate(ds))))
anticlockwise1  = chain([0], (v - d for v, d in zip(accumulate(vs[::-1]), accumulate(ds[::-1]))))
clock_anticlock = (x + y for x, y in zip(clockwise1, reversed(list(accumulate(anticlockwise1, func=max)))))
 
anticlockwise2  = chain([0], (v - d*2 for v, d in zip(accumulate(vs[::-1]), accumulate(ds[::-1]))))
clockwise2      = chain([0], (v - d for v, d in zip(accumulate(vs), accumulate(ds))))
anticlock_clock = (x + y for x, y in zip(anticlockwise2, reversed(list(accumulate(clockwise2, func=max)))))
 
print(max(chain(clock_anticlock, anticlock_clock)))

Measured memory_bytes: 59224
n=int(input())
ans=float("inf")
for i in range(1,n):
    sum=0
    j=n-i
    ii=str(i)
    jj=str(j)
    for k in range(len(ii)):
        sum+=int(str(i)[k])
    for k in range(len(jj)):
        sum+=int(str(j)[k])
    ans=min(ans,sum)
print(ans)

Measured memory_bytes: 3064
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    ll N;

    cin >> N;
    ll sum = 0;
    for (ll i = 1; i <= N; i++)
    {
        if (i % 15 == 0)
        {
            continue;
        }
        else if (i % 5 == 0)
        {
            continue;
        }
        else if (i % 3 == 0)
        {
            continue;
        }
        else
        {
            sum += i;
        }
    }
    cout << sum << endl;
    return (0);
}

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

int main () {
    int a, b;
    cin >> a >> b;
    if (a < 9 && b < 9) {
        cout << "Yay!";
    }
    else
        cout << ":(";
}

Measured memory_bytes: 256
fn main() {
    let n = read::<i32>();

    let str = match n % 10 {
        2 | 4 | 5 | 7 | 9 => "hon",
        0 | 1 | 6 | 8 => "pon",
        3 => "bon",
        _ => panic!("unreachable")
    };
    
    println!("{}", str);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

Measured memory_bytes: 2112
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int find(int a,vector<int>& uf){
  if(uf[a]<0) return a;
  return uf[a]=find(uf[a],uf);
}

void unite(int a,int b,vector<int>& uf){
  a=find(a,uf); b=find(b,uf);
  if(a==b) return ;
  if(uf[a]>uf[b]) swap(a,b);
  uf[a]+=uf[b];
  uf[b]=a;
}

int size=1e5+2;

int main(){
  int n; cin >>n;
  vector<vector<int>> x(size),y(size);
  rep(i,n){
    int a,b; cin >> a >> b;
    x[a].push_back(b);
    y[b].push_back(a);
  }
  if(df) print("done");
  vector<int> ufx(size,-1),ufy(size,-1);
  rep(i,size){
    if(x[i].size()==0)continue;
    int a=x[i][0];
    for(int v:x[i]) unite(a,v,ufy);
  }
  rep(i,size){
    if(y[i].size()==0)continue;
    int a=y[i][0];
    for(int v:y[i]) unite(a,v,ufx);
  }
  if(df) print("done");

  li ans=0;
  rep(i,size){
    if(i!=find(i,ufx)) continue;
    if(x[i].size()==0) continue;
    int j=find(x[i][0],ufy);
    ans+=(li)ufx[i]*ufy[j];
  }
  print(ans-n);
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<vpll> vvpll;
typedef unordered_map<ll, ll> um;
typedef unordered_set<ll> us;

#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ts ll t; in(t) while (t--) solve();
#define ks ll t; in(t) FOR(i, 1, t+1) out("Case #" << i << ": " << solve());
#define endl '\n'
#define ln cout << endl;
#define in(x) cin >> x;
#define out(x) cout << x << endl;
#define flush cout << flush;
#define reset(a, b) memset(a, b, sizeof(a));
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define FORI(i, a, b, c) for (ll i = a; i < b; i += c)
#define FORD(i, a, b) for (ll i = a; i > b; --i)
#define FOREACH(it, v, r) for (auto it = v.begin() + r; it != v.end(); it++)
#define FORALL(it, v) for (auto it : v)
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define vin(v, x) vll v(x); FOR(i, 0, x) in(v[i])
#define all(v) v.begin(), v.end()
#define allr(v, r) v.begin(), v.begin() + r
#define showv(v) FORALL(it, v) cout << it << ' '; ln
#define printv(v) FORALL(it, v) out(it)
#define show2d(v) FORALL(it, v) { FORALL(j, it) cout << j << ' '; ln}
#define showm(v) FORALL(it, v) cout << it.F << ": " << it.S << ' '; ln
#define sortv(v) sort(all(v));
#define revv(v) reverse(all(v));
#define maxv(v) *max_element(all(v))
#define minv(v) *min_element(all(v))
#define gcd __gcd
#define checkbit(n, i) (n >> i) & 1               // check ith bit
#define bitcount __builtin_popcount               // count set bits
#define firstbitindex __builtin_ctz               // count trailing zeros
#define lastbitindex __builtin_clz                // count leading zeros
#define bitparity __builtin_parity                // check set bits are even or odd
#define findv(v, x) (find(all(v), x) != v.end())
#define findsm(u, x) (u.find(x) != u.end())
#define findstr(s, x) (s.find(x) != string::npos)
#define sz(a) a.size()
#define precise(x) cout << fixed << setprecision(x);

const ll MAXN = 2e5, MOD = 998244353, SIZE = 2e7, INF = 0x7f7f7f7f7f7f7f7f;
const double EPS = 1e-9, PI = acos(-1);
const int INFi = 0x7f7f7f7f;

//<<------Declare Variables Here----->>//
ll n, a[MAXN], x;

//<<-----Implement Functions Here---->>//
void solve()
{
    in(n)
	x = 0;
	FOR(i, 0, n)
		cin >> a[i], x ^= a[i];
	FOR(i, 0, n)
		cout << (a[i] ^ x) << ' ';
}

//<<----------Start of Main---------->>//
int main()
{
    fastio
    //ts
    solve();
    return 0;
}


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

int dp[3333][6666];

int main(){
	int N,T;
	cin >> N >> T;
	vector<int> A(N);
	vector<int> B(N);
	vector<pair<int,int>> AB(N);
	for(int i=0;i<N;i++)cin >> AB[i].first >> AB[i].second;
	sort(AB.begin(),AB.end());
	for(int i=0;i<N;i++){
		A[i]=AB[i].first;
		B[i]=AB[i].second;
	}
	int ma=A[N-1];
	for(int i=0;i<N;i++)for(int t=0;t<T+ma;t++){
		if(t-A[i]>=0 && t-A[i]<T)dp[i+1][t]=max(dp[i][t],dp[i][t-A[i]]+B[i]);
		else dp[i+1][t]=dp[i][t];
	}
	int ans=0;
	for(int t=T;t<T+ma;t++){
		ans=max(ans,dp[N][t]);
		//cout << dp[N][t] << " ";
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;
  
  vector<pair<int,int>> now;//現在の座標
  for(int i=0;i<n;i++){
      int a,b;
      cin >> a >> b;
      pair<int,int>p = make_pair(a,b);
      now.push_back(p);
  }

  vector<pair<int,int>> check;//チェックポイントの座標
  for(int i=0;i<m;i++){
      int c,d;
      cin >> c >> d;
      pair<int,int>p = make_pair(c,d);
      check.push_back(p);
  }

  //全探索
  
  for(int i=0;i<n;i++){
    int ans = 1000000000;
    int index = 0;
    for(int j=0;j<m;j++){
      int dis = abs(now[i].first-check[j].first) + abs(now[i].second-check[j].second);
      if(ans>dis){
          ans = dis;
          index = j+1;
      }
    }
    cout << index << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<stdlib.h>
using namespace std;

struct Node{
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node *find(Node *a, int k) {
    while (a != NIL && k != a->key) {
        if(k < a->key) {
            a = a->left;
        } else {
            a = a->right;
        }
    }
    return a;
}

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node* )malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    
    while(x != NIL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        }else {
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inParse(Node *a) {
    if (a == NIL) return;
    inParse(a->left);
    cout << " " << a->key;
    inParse(a->right);
}
void preParse(Node *a) {
    if (a == NIL) return;
    cout << " " << a->key;
    preParse(a->left);
    preParse(a->right);
}

int main() {
    int n, i, x;
    string com;
    
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) {
        cin >> com;
        if (com == "find") {
            scanf ("%d", &x);
            Node *t = find(root, x);
            if (t != NIL) cout << "yes" << endl;
            else cout << "no" << endl;
        } else if (com == "insert" ) {
            scanf("%d", &x);
            insert(x);
        } else if (com == "print") {
            inParse(root);
            cout << endl;
            preParse(root);
            cout << endl;
        }
    }
    
    return 0;
}



Measured memory_bytes: 21980
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
const LL mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
int n, fa[maxn], cnt;
 
struct edge{
   int u, v, cost;
   edge(int cu, int cv, int ccost){u=cu, v=cv, cost=ccost;}
   edge(){}
   bool operator<(const edge &cmp) const{
       return cost<cmp.cost;
   }
}E[maxn*4];
 
struct point{
   int x, y, id;
}P[maxn];;
 
bool cmpx(point c1, point c2){return c1.x<c2.x;}
 
bool cmpy(point c1, point c2){return c1.y<c2.y;}
 
int Find(int x){
   return x==fa[x]?x:fa[x]=Find(fa[x]);
}
 
LL Kruskal(){
   for(int i=0;i<=n;i++)fa[i]=i;
   sort(E, E+cnt);
   LL ans=0;
   for(int i=0;i<cnt;i++){
       int fu=Find(E[i].u);
       int fv=Find(E[i].v);
       if(fu!=fv){
           ans+=E[i].cost;
           fa[fu]=fv;
       }
   }
   return ans;
}
 
int main()
{
   while(~scanf("%d", &n)){
       for(int i=0;i<n;i++){
           scanf("%d%d", &P[i].x, &P[i].y);
           P[i].id=i;
       }
       cnt=0;
       sort(P, P+n, cmpx);
       for(int i=1;i<n;i++){
           E[cnt++]=edge(P[i-1].id, P[i].id, P[i].x-P[i-1].x);
       }
       sort(P, P+n, cmpy);
       for(int i=1;i<n;i++){
           E[cnt++]=edge(P[i-1].id, P[i].id, P[i].y-P[i-1].y);
       }
       printf("%lld\n", Kruskal());
   }
   return 0;
}

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

int main()
{
	long long n, res;
	cin >> n;
	map<long long, long long>count;
	for (long long x = 1; x <= n; ++x)
	{
		for (long long y = 1; y <= n - x; ++y)
		{
			for (long long z = 1; z <= n - y; ++z)
			{
				res = x * x + y * y + z * z + x * y + y * z + z * x;
				if (res <= n)
				{
					count[res]++;
				}
				else break;
			}
		}
	}
	for (long long i = 1; i <= n; ++i) cout << count[i] << endl;
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	return 0;
}

Measured memory_bytes: 4160
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int h[n];
	for(int i=0; i<n; ++i){
		cin>>h[i];
	}
	
	int dp[n];
	dp[0] = 0;
	dp[1] = abs(h[0]-h[1]);
	for(int i=2; i<n; ++i){
		int mnm = INT_MAX;
		for(int j = max(0,i-k); j<i; ++j){
			mnm = min(dp[j] + abs(h[j] - h[i]), mnm);
		}
		dp[i] = mnm;
		
	}
	cout<<dp[n-1]<<"\n";
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N; cin>>N;
    vector<ll> A(N+2);
    A[0]=0;
    A[N+1]=INF;
    rep1(i,N) cin>>A[i];
    sort(all(A));
    ll ans=0;
    
    vector<bool> X(1000005,false);
    rep1(i,N){
        if(X[A[i]]==false){
            if(A[i-1]!=A[i] && A[i]!=A[i+1]) ans++;
            rep1(j,1000000/A[i]) X[j*A[i]]=true;
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 4748
#include "bits/stdc++.h"
using namespace std;
#include"ext/pb_ds/assoc_container.hpp"
#include"ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<typename T>
using pbds = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

/*
insert(logN)
erase(logN)
find_by_order(logN)//k番目の要素のイテレータを返す
order_of_key(logN)//k以上で最初の数が何番目かを返す
(K未満の個数が何個あるかが分かるらしい）
gp_hash_table<int,int>m//高速なmap
*/
#define int long long
#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 FOR(i,s,n) for(int i = s;i < (int)n;++i)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;--i)
#define ALL(a) a.begin(),a.end()
#define IN(a, x, b) (a<=x && x<b)
template<class T>inline void out(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout<<t<<" ";out(ts...);}
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}
constexpr int INF = 1e18;


signed main(){
	string s,t = "hi";
	cin >> s;
	FOR(i,1,5 + 1){
		string tmp = "";
		REP(j,i)tmp += t;
		if(s == tmp){
			out("Yes");
			return 0;
		}
	}
	out("No");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))//memset only use to initialize 0 or -1 no other number.
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INF 1e9
#define INFL 1e18
#define mod 1000000007
//#define mod 998244353
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> os_pair;

ll power(ll x,ll n){ll res =1;while(n>0){if(n%2==1){res=res*x;}x=x*x;n=n/2;}return res;}
ll powm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

//cout<< fixed << setprecision(10)

int main(){

    fast;
    int T;
    T=1;
    //cin>>T;
    while(T--){
    	int a,b,c;
    	cin>>a>>b>>c;
    	swap(a,b);
    	swap(a,c);
    	cout<<a<<" "<<b<<" "<<c;
    	
    	

    }

}

Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <iterator>
#include <set>


using namespace std;



int main() {

    string S, T;
    cin >> S >> T;

    if ((S + T[T.size() - 1]) == T) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;

}

Measured memory_bytes: 3036
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

int main() {
  int n,a,b,c,d;
  scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
  n--;
  rep(i,1,n+1) {
    LL r = i * 1LL * d - (n - i) * 1LL * c + a;
    LL l = i * 1LL * c - (n - i) * 1LL * d + a;
    if(b >= l && b <= r) {
      printf("YES\n");
      return 0;
    }
  }
  printf("NO\n");
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>


using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

map<int,int> res;

void prime_factor(int n) {
    FOR(i,2,n) {
        while(n%i==0) {
            ++res[i];
            n /= i;
        }
    }
    if(n!=1) res[n]++;
}

int main() {
    int N; cin>>N;
    i64 ans = 1;
    FOR(i,2,N+1) prime_factor(i);
    for(auto itr=res.begin();itr!=res.end();++itr) {
        ans *= (itr->second)+1;
        ans %= INF;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
 
int main() {
  int c;
  cin >> c;

  vector<int> h(c);
  int k=0;

  cin >> h[0];
  k = h[0];
  int ans = 1;
  for(int i=1; i<c; i++) {
    cin >> h[i];
    if(k <= h[i]) {
      ans++;
      k = h[i];
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N,M,ac,A[1<<17],B[1<<17];
pair<int,int>AB[1<<17];
vector<pair<int,int> >G[1<<17];
bool used[2<<17],vis[1<<17];
bool dfs(int u)
{
	B[u]=(u&&AB[u-1].second)^(u<N&&AB[u].second);
	vis[u]=true;
	for(pair<int,int>e:G[u])
	{
		int v=e.first;
		if(!vis[v]&&dfs(v))
		{
			B[u]++,B[v]++,ac++;
			used[e.second]=true;
		}
	}
	return B[u]%=2;
}
main()
{
	cin>>N>>M;
	for(int i=0;i<N;i++)cin>>AB[i].first>>AB[i].second;
	sort(AB,AB+N);
	for(int i=0;i<M;i++)
	{
		int L,R;cin>>L>>R;
		L=lower_bound(AB,AB+N,make_pair(L,0))-AB;
		R=upper_bound(AB,AB+N,make_pair(R,2))-AB;
		G[L].push_back({R,i});
		G[R].push_back({L,i});
	}
	for(int i=0;i<=N;i++)if(!vis[i]&&dfs(i))
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<ac<<endl;
	for(int i=0;i<M;i++)if(used[i])cout<<i+1<<endl;
}

Measured memory_bytes: 14720
s = input()
b1 = ''
b2 = ''
n = 0
for i, c in enumerate(s):
  if i == 0:
    b1 = c
    n += 1
    continue
  if c != b1 and b2 == '':
    b2 = c
    continue
  if c == b1:
    n += 1
    continue
  if c == b2:
    continue
  if c != b1 and c != b2:
    print('No')
    break
else:
    print('Yes' if n == 2 else 'No')


Measured memory_bytes: 3060
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
N = int(input())
S = input().split()
print("".join([S[0][i]+S[1][i]for i in range(N)]))

Measured memory_bytes: 4336
n=int(input())
ans1=[0,1]
for i in range(1,n+1):
  count=0
  N=i
  while True:
    if N%2==0:
      N//=2
      count+=1
    else:
      break
  if ans1[0]<count:
    ans1=[count,i]
print(ans1[1])

Measured memory_bytes: 3060
N = int(input())
A = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, m, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        m : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.m = m
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


gcd = lambda x, y: gcd(y, x) if x < y else gcd(y, x % y) if y else x
e = 0
size = N
ST = SegmentTree(A, m=gcd, e=e, size=size)
ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)


Measured memory_bytes: 128732
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
const string V = "Vacant";
int main() {
  ll N;
  cin >> N;
  string l, r;
  cout << 0 << endl << flush;
  cin >> l;
  cout << endl;
  if (l == V) return 0;
  cout << N - 1 << endl << flush;
  cin >> r;
  cout << endl;
  if (r == V) return 0;
  int l_num = 0, r_num = N - 1;
  while (true) {
    int mid_num = (l_num + r_num) / 2;
    string mid;
    cout << mid_num << endl << flush;
    cin >> mid;
    cout << endl;
    if (mid == V) return 0;
    int num = mid_num - l_num;
    if (num % 2 == 1 && mid == l) {
      r_num = mid_num;
      r = mid;
      continue;
    } else if (num % 2 == 0 && mid != l) {
      r_num = mid_num;
      r = mid;
      continue;
    }
    l = mid;
    l_num = mid_num;
  }
}

Measured memory_bytes: 3808
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

void display(vector<int> &v){
  cout <<v[0];
  FOR(i, 1, v.size()) cout <<" " <<v[i];
  cout <<endl;
}

void insertionSort(vector<int> &v, int &idx){
  int num = v[idx], i = idx - 1;
  while(i >= 0 && v[i] > num) { v[i + 1] = v[i]; i--; }
  v[i + 1] = num;
  display(v);
}
 
int main() {
  int N; cin >>N;
  vector<int> v(N);
  REP(i, N) cin >>v[i];
  display(v);
  for(int i = 1; i < N; ++i) insertionSort(v, i);
  return 0;
}

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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string g;
  while ( cin >> g, g != "#" ) {
    int y, m, d;
    cin >> y >> m >> d;
    if ( y == 31 ) {      
      if ( m <= 4 ) {
	cout << g << " " << y << " " << m << " " << d;      
      } else {
	cout << '?' << " " << y-30 << " " << m << " " << d;      
      }
    } else if ( y < 31 ) {
      cout << g << " " << y << " " << m << " " << d;      
    } else {
      cout << '?' << " " << y-30 << " " << m << " " << d;      
    }
    cout << endl;    
  }
  
  return 0;
}



Measured memory_bytes: 3176
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<char,int> dat[50];
map<char,int> ans;
char alp[27] = "abcdefghijklmnopqrstuvwxyz";

string str;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){ 
        cin >> str;
        for(int j = 0; j < str.length(); j++){
            dat[i][str[j]]++;
        }
    }
  
int min = 99999;
    for(int j = 0; j < 26; j++){
        for(int i = 0; i < n; i++){
            if(min > dat[i][alp[j]]){
                min = dat[i][alp[j]];
            }
        }
        ans[alp[j]] = min;
        min = 99999;
    }

    for(auto e:ans){
        if(e.second > 0){
            for(int i = 0; i < e.second; i++){
                cout << e.first;
            }
        }
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b) cout<< c << endl;
  else if(b==c) cout<< a << endl;
  else if(c==a) cout<< b << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader; 
import java.io.*;
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
import java.util.*;
import java.math.*;
public class Main 
{ 
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader()
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next()
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine();
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
   public static void main(String args[]) throws Exception
    {
        FastReader sc=new FastReader();
         PrintWriter pw=new PrintWriter(System.out);
        int t=1;//sc.nextInt();
        while(t-->0)
        {
           String s=sc.next();long sum=0;
           for(char w:s.toCharArray())
           {
             sum+=(w-'0');
           }
           pw.println((sum%9==0)?"Yes":"No");
        }
           pw.close();
    }
}
  

Measured memory_bytes: 37036
#include <bits/stdc++.h>
#define endl '\n'
#define sync_cin                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0)
using namespace std;

#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;



int main()
{
    sync_cin;
    int n, k; cin >> n >> k;
    string s; cin >> s;
    vector<ii> ind;
    ind.push_back({0, 0});
    for (int i = 0; i < n;)
    {
        if (s[i] == '0') 
        {
            i++;
            continue;
        }
        int l = i;
        while (s[l] == '1' && l < n) l++;
        if (l > i) ind.push_back({i + 1, l});
        i = l;
    }

    if (k > 0) ind.push_back({n, n});

    int cur = 0;
    int ans = 0;
    for (int i = 0; i < ind.size(); i++)
    {
        cur = ind[i].second - (i - k >= 0 ? ind[i - k].first : 0) + (i - k > 0 ? 1 : 0);
        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>

using namespace std;

int main(){
    int N;
    string S;
    cin >> N;
    int left = 0;
    int right = N;
    char l, r, m;
    cout << 0 << endl;
    cin >> S;
    if(S[0] == 'V') return 0;
    l = S[0];
    r = S[0];
    int cnt = 1;
    int mid = (right+left)/2;
    while(true){
        cout << mid << endl;
        cin >> S;
        if(S[0] == 'V') return 0;
        m = S[0];
        if(((mid - left)%2 == 0 && l!=m) || ((mid - left)%2 == 1 && l==m)){
            right = mid;
            r = m;
            mid = (left+mid)/2;
        }else{
            left = mid;
            l = m;
            mid = (right+mid)/2;
        }
        cnt++;
        if(cnt > 20) break;
    }
}

Measured memory_bytes: 852
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main(){
	int n;
	scanf("%d", &n);
	if(n%2==0){
		printf("0.5");
	}
	else{
		printf("%f", (double)(n+1)/2/n);
	}
	
	
	return 0;
}

Measured memory_bytes: 128
from math import sqrt
from math import ceil

min_move = 10**12

n = int(input())

for i in range(1,ceil(sqrt(n)+0.1)):
  if n%i == 0:
    #print(n,i)
    b = n//i
    if min_move >  i+b-2:
      min_move = i+b-2

print(min_move)      

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

int main() {
	int n;
	cin >> n;
	
	int val;
	cin >> val;
	int min, max;
	long sum;
	min = max = sum = val;
	for(int i = 1; i < n; ++i) {
		cin >> val;
		max = (val > max) ? val : max;
		min = (val < min) ? val : min;
		sum += val;
	}
	printf("%d %d %ld\n", min, max, sum);

	return 0;
}

Measured memory_bytes: 3220
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <cmath>
#include <bits/stdc++.h>
#include <limits>

#define MOD 1000000007

using namespace std;

int main(void){
    // Your code here!
    long long n, m;
    string op;
    
    cin >> n >> op >> m;
    
    if(op == "+")
        cout << n + m << endl;
    else
        cout << n - m << endl;
    
    return 0;
}

Measured memory_bytes: 256