akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(const T a, const T b){return a>=0 ? a/b : (a+1)/b-1;}
template<class T> T div_ceil(const T a, const T b){return a>=0 ? (a-1)/b+1 : a/b;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

lint gcd(lint p, lint q){
    if(p < 0) p *= -1;
    if(q < 0) q *= -1;
    if(p < q) swap(p, q);
    while(q){
        lint r = p % q;
        p = q;
        q = r;
    }
    return p;
}

pll add(pll a, pll b){
    lint s = a.fi*b.se + b.fi*a.se, t = a.se*b.se;
    lint g = gcd(s, t);
    return {s/g, t/g};
}

pair<pll, int> eval(int i, string &s){
    if(s[i] == 'n'){
        if(i == s.size()-5) return {{0, 1}, 1};
        pll a;
        int n;
        tie(a, n) = eval(i+5, s);
        return {add(a, {-90, 1<<n}), n+1};
    }
    else{
        if(i == s.size()-4) return {{90, 1}, 1};
        pll a;
        int n;
        tie(a, n) = eval(i+4, s);
        return {add(a, {90, 1<<n}), n+1};
    }
}

int main(){
    string s;
    while(cin >> s && s != "#"){
        lint a, b;
        int i = 0;
        tie(a, b) = eval(i, s).fi;
        if(b == 1) printf("%lld\n", a);
        else printf("%lld/%lld\n", a, b);
    }
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>pii;
int n;
vector<pair<pii,int> >v;
int main(){
	int L;
	cin>>L;
	int t1=L;
	while(t1){
		n++;
		t1>>=1;
	}
	int sum=0,c=1;
	for(int i=1;i<n;i++){
		v.eb(mp(i,i+1),0);
		v.eb(mp(i,i+1),c);
		sum+=c;
		c<<=1;
	}
	int p=1,k=1;
	while(L!=1){
		if(L%2==1){
			v.eb(mp(p,n),sum+1);
			sum+=k;
		}
		L>>=1;
		p++;
		k<<=1;
	}
	cout<<n<<' '<<v.size()<<endl;
	for(auto i:v){
		cout<<i.first.first<<' '<<i.first.second<<' '<<i.second<<endl;
	}
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  string S;
  string J = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  //cout << J[6];
  cin >> S;
  vector<char> data(S.size());
  for (int i=0;i<S.size();i++){
    data.at(i) = S.at(i);
  }
  int n =0;
  n = N % 26;
  for (int j=0;j<data.size();j++){
    for (int k=0;k<J.size();k++){
      if (data.at(j) == J.at(k)){
        if ((n+k)>25){
          data.at(j) = J.at(n+k-25-1);
          break;
        }
        else{
          data.at(j) = J.at(n+k);
          break;
        }
      }
      else{
        continue;
      }
    }
  }
  for (int i=0;i<data.size();i++){
    cout << data.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int S, hour, minute;

  scanf("%d", &S);
  hour = S/3600;
  S -= 3600*hour;
  minute = S/60;
  S -= 60*minute;
  printf("%d:%d:%d\n", hour, minute, S);
  return 0;
}



Measured memory_bytes: 2048
#include <stdio.h>
#define I 100000
int partition(int,int);
int n,A[I];
int main(){
  int k,q,i;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  q=partition(0,n-1);

  for(k=0;k<q;k++){
    printf("%d ",A[k]);
  }
  printf("[%d] ",A[q]);
  for(k=q+1;k<n-1;k++){
    printf("%d ",A[k]);
  }
  printf("%d\n",A[n-1]);
  return 0;
}

int partition(int p,int r) {
  int x,i,j,b,c,k;
  x=A[r];
  i =p-1;

  for(j=p;j<r;j++){
    if(A[j]<=x){
      i=i+1;
      b=A[i];
      A[i]=A[j];
      A[j]=b;
    }
  }
  
  c=A[i+1];
  A[i+1]=A[r];
  A[r]=c;

  return i+1;
}

Measured memory_bytes: 988
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1000000000;
const double PI = acos(-1);

int main() {
	int r, w, C, R;
	while(cin >> r >> w >> C >> R&&r&&w&&C&&R) {
		int ans = 0;
		while (double(r / w) < C) {
			r += R;
			ans++;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3072
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
		//int d=scan.nextInt();
		//int e=scan.nextInt();
		int ans=0;
		if(a<c&&b>c||a>c&&b<c) {
			ans=1;
		}
		else {
			
		}
		System.out.println(ans==1?"Yes":"No");
	}
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
#define fil(x) memset(x, 0, sizeof(x))
#define fillb(x) memset(x,false,sizeof(x))
#define fillm(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define pll pair<int, int>
#define pf printf
#define sf scanf
#define all(x) x.begin(),x.end()
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define fo(i,n) for(int i=0;i<n;i++)
#define of(i,n) for(int i=n-1;i>=0;i--)
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
#define nl endl

typedef unsigned long long lll;
typedef long long ll;
int knigtx8[] = {2, 2, -2, -2, 1, 1, -1, -1}; ///knight move in chess
int knigty8[] = {1, -1, 1, -1, 2, -2, 2, -2}; ///knight move in chess
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}; ///for 8 directions
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1}; ///for 8 directions
int dx4[] = {0, 0, 1, -1}; ///for 4 directions
int dy4[] = {1, -1, 0, 0}; ///for 4 directions
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}

int atoz(){
    int frnt,bck,nibo,present,i;string s;
        frnt = abs(s[i]-present);
        bck = 26-frnt;
        nibo = min(frnt,bck);
}

template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

int main()
{
    IOS;
    ll n;
    cin>>n;
    ll a[n+1];
    fil(a);
    int x;
    for(int i=1;i<n;i++)
    {
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<n;i++)
    {
        cout<<a[i]<<endl;
    }
    cout<<0<<endl;
    return 0;
}


Measured memory_bytes: 5180
def resolve():
    def lcs(s1, s2):
        """
        文字列S, Tのlongest common subsequenceの長さを返す
        なお、longest common substringではない
        （要素同士がとなりあっていなくてもいい）ことに注意！
        """

        dp = []
        for s2_k in s2:
            bgn_idx = 0
            for i, cur_idx in enumerate(dp):
                # bgn_idx以降でs2_kを探す
                chr_idx = s1.find(s2_k, bgn_idx) + 1
                if not chr_idx:
                    break
                dp[i] = min(cur_idx, chr_idx)
                bgn_idx = cur_idx
            else:
                chr_idx = s1.find(s2_k, bgn_idx) + 1
                if chr_idx:
                    dp.append(chr_idx)
        return len(dp)

    q = int(input())
    for i in range(q):
        S = str(input())
        T = str(input())
        print(lcs(S, T))


resolve()


Measured memory_bytes: 5624
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;
    cin >> h >> w;
    vector<string> grid(h); 
    rep(i,h) cin >> grid[i];
    bool ok = 1;
    rep(i,h){
        rep(j,w){
            if (grid[i][j] == '#'){
                bool yes = 0;
                rep(k,4){
                    int xn = i+nx[k],yn = j+ny[k];
                    if (xn >= 0 && xn < h && yn >= 0 && yn < w && grid[xn][yn] == '#') yes = 1;
                }
                if (!yes) ok = 0;
            }
        }
    }
    Yes(ok);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,u,v,a,b,y[100010],ans,mx;
vector<int> g[100010],z;
bool f[100010],ff;
void dfs(int x){
	if (x==v){
		ff=1;
		return ;
	}
	for (int i=0;i<g[x].size();i++)
		if (f[g[x][i]]==0){
			f[g[x][i]]=1;
			z.push_back(g[x][i]);
			dfs(g[x][i]);
			if (ff==1) return ;
			z.erase(z.end()-1);
		}
}
void dfs2(int x,int deep,int j){
	y[j]=max(y[j],deep);
	for (int i=0;i<g[x].size();i++)
		if (f[g[x][i]]==0){
			f[g[x][i]]=1;
			dfs2(g[x][i],deep+1,j);
		}
}
int main(){
	cin>>n>>u>>v;
	for (int i=0;i<n-1;i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	z.push_back(u);f[u]=1;dfs(u);
	for (int i=0;i<z.size();i++){
		memset(f,0,sizeof(f));
		if (i>0) f[z[i-1]]=1;
		if (i<z.size()-1) f[z[i+1]]=1;
		f[z[i]]=1;
		dfs2(z[i],0,i);
	}
	a=0;b=z.size()-1;
	while (b-a>2){
		a++;b--;ans++;
	}
	for (int i=0;i<=a;i++) mx=max(mx,y[i]+a-i);
	cout<<ans+mx+b-a-1<<endl;
	return 0;
}

Measured memory_bytes: 9588
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.next());
        int K = Integer.parseInt(scanner.next());
        int S = Integer.parseInt(scanner.next());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            if (i < K) {
                sb.append(S);
            } else {
                if (S == 1_000_000_000) {
                    sb.append(S - 1);
                } else {
                    sb.append(S + 1);
                }
            }
            sb.append(' ');
        }

        System.out.println(sb.toString().trim());
    }
}



Measured memory_bytes: 33836
#include <stdio.h>
#include <stdlib.h>

int main() {
  int x, a, b, la, lb;
  scanf("%d %d %d", &x, &a, &b);
  la = abs(x - a);
  lb = abs(x - b);
  if(la > lb) printf("B");
  else printf("A");
  return 0;
}


Measured memory_bytes: 128
def resolve():
    import sys
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    x1, y1, x2, y2 = [int(x) for x in input().rstrip().split(" ")]
    x = x2 - x1
    y = y2 - y1
    print(x2 - y, y2 + x, x1 - y, y1 + x)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 61932
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<limits>
#include<map>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define ll_INF 	9223372036854775807
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
using namespace std;

ll five_frac(ll x){
  ll temp = 0;
  while(x){
    temp += (x / 5);
    x /= 5;
  }

  return temp;
}
int main(){
  ll N;
  cin >> N;
  ll ans;
  if(N%2){
    ans = 0;
  }
  else{
    ll k;
    k = (N / 2);
    ans = five_frac(k);
  }

  cout << ans << endl;
}


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

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(ll)(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) reps(i,0,((n)+1))
#define repst(i,s,n) reps(i,s,((n)+1))
#define reprt(i,n,t) for(ll (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ');}}

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// 最終的に作る回分をtとし、s[i]がt[p[i]]になるとする
// 事前に各アルファベットの個数を求めておけばsの各文字がtの①左半分②ちょうど真ん中③右半分のどこに属するかは決められる
// とりあえずこの属する場所に順序関係を保ったまま移動させたものをxとすると、s->tのswap回数はs->xとx->tのswap回数の和になる
// ①内のある要素をswapするのとそれに対応する③内の要素をswapさせるのは同じことだから①内の要素はswapしないことにしても問題ない
// すると③内の要素の順番も定まるからあとはBITでバブルソートするだけ

int n;
ll ans;
vi c[26];
vpii p;
string s;

// [1,n]
int bit[200200];
int sum(int i) {
	i++;
	int s = 0;
	while (i>0) {
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(int i, int x) {
	i++;
	while (i<=n) {
		bit[i] += x;
		i += i & -i;
	}
}

signed main() {
	cin >> s;
	n = s.length();
	rep(i,n) c[s[i]-'a'].pb(i);
	// 奇数回現れる文字種のカウントと同じ文字種の対応付け
	int odds = 0;
	rep(i,26) {
		int t = c[i].size();
		rep(j,t) {
			if (j*2>=t) break;
			if (j*2+1==t) {
				odds++;
				p.pb({c[i][j],c[i][j]});
			} else p.pb({c[i][t-1-j],c[i][j]});
		}
	}
	if (odds>=2) return cout << -1 << ln, 0;
	sort(all(p));
	each(i,p) {
		ans += sum(i.se-1) / (i.fi==i.se ? 2 : 1);
		add(i.fi,1);
		if (i.fi!=i.se) add(i.se,1);
	}
	cout << ans << ln;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll k,x; cin >> k >> x;
    bool isfirst = true;
    for(int i = -1000000;i<=1000000;i++){
        if(x-k < i && i<x+k){
            if(!isfirst) cout << " ";
            else isfirst = false;
            cout << i;
        }
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=100005;
int k;
int a[N];
LL n1,n2;
int main(){
	k=read();
	For(i,1,k)
		a[i]=read();
	n1=n2=2;
	Fod(i,k,1){
		int x=a[i];
		LL lb=(n1-1)/x+1;
		LL ub=n2/x;
		if (lb>ub)
			return puts("-1"),0;
		n1=lb*x;
		n2=ub*x+x-1;
	}
	cout<<n1<<" "<<n2<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const int mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; ++i)  cin >> a[i];

    vector<vector<int>> cnt(41, vector<int>(2, 0));
    for(int i = 0; i < n; ++i){
        for(int d = 0; d <= 40; ++d){
            if(a[i] & (1ll << d))   ++cnt[d][1];
            else    ++cnt[d][0];
        }
    }
    
    ll remain = k;
    ll res = accumulate(a.begin(), a.end(), 0ll);
    for(int i = 40; i >= 0; --i){
        ll base = 1ll << i;
        if(remain <= 0) break;
        if(base > remain)   continue;
        
        if(cnt[i][0] > cnt[i][1]){
            remain -= base;
            res += base * (cnt[i][0] - cnt[i][1]);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 1024
arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
    


Measured memory_bytes: 24888
#include <cstdio>

int main(void)
{
	int b, r, g, c, s, t;
	
	while (scanf("%d %d %d %d %d %d", &b, &r, &g, &c, &s, &t)){
		if (b == 0 && r == 0 && g == 0 && c == 0 && s == 0 && t == 0){
			break;
		}
		int res = 100;
		int bonus = b * 5 + r * 3;
		
		res += (g * 7) + (c * 2) + (b * 15) + (r * 15);
//		printf("res >> %d\n", res);
		res -= bonus * 2;
//		printf("res >> %d\n", res);
		res += bonus * 15;
//		printf("res >> %d\n", res);
		res -= (t - bonus) * 3;
//		printf("res >> %d\n", res);
		res += s * 3;
		
		
		
		printf("%d\n", res);
	}
	
	return (0);
}

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

int main() {
  ll X;
  cin >> X;

  for (int i = -200; i <= 200; i++) {
    for (int j = -200; j <= 200; j++) {
      if (pow(i, 5) - pow(j, 5) == X) {
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3980
#include<stdio.h>

int main(){
	int maisuu,num,i,j;
	char gara;
	int s[13]={0};
	int h[13]={0};
	int c[13]={0};
	int d[13]={0};
	
	//printf("?????°?????\?????????????????????:");
	scanf("%d",&maisuu);
	
	for(i=0;i<maisuu;i++){
		
		scanf("%s %d",&gara ,&num);
		
		switch(gara){
			
			case 'S': s[num-1]=num;
				break;
			
			case 'H': h[num-1]=num;
				break;
			
			case 'C': c[num-1]=num;
				break;
			
			case 'D': d[num-1]=num;
				break;
			
		}
		
	}
	
	//printf("\n");
	
	for(i=0;i<4;i++){
		for(j=0;j<13;j++){
			
			switch(i){
				
			case 0: 
				if(s[j]==0){
					printf("S %d\n",j+1);
				}
				break;
			
			case 1:
				if(h[j]==0){
					printf("H %d\n",j+1);
				}
				break;
			
			case 2: 
				if(c[j]==0){
					printf("C %d\n",j+1);
				}
				break;
			
			case 3: 
				if(d[j]==0){
					printf("D %d\n",j+1);
				}
				break;
				
			}
			
		}
		
	}
	
	return 0;
}

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


using namespace std;

typedef long long ll;



int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll>arr( n + 1);
    for(ll i = 1; i <= n; i++)cin >> arr[i];
    vector<ll> dp(n + 1);
    dp[2] = abs(arr[1] - arr[2]);
    for(ll i = 3; i <= n; i++){
        dp[i] = (ll)INT_MAX;
        for(int j = 1; j <= k; j++){
            if(j < i){
               dp[i] = min(dp[i], abs(arr[i] - arr[i - j]) + dp[i - j]);
            }
        }
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 4828
#include<stdio.h>

int main(){
  int i;
  char str;
  char alphabet[26];

   for(i=0; i<26; i++){
      alphabet[i]=0;
   }
   
   while(scanf("%c",&str)!=EOF){
     if(str>=65 && str<=90){
       alphabet[str-65]++;
     }else if(str>=97 && str<=122){
       alphabet[str-97]++;
       }
   }
   for(i=0; i<26; i++){
     printf("%c : %d\n",i+97,alphabet[i]);
   }
   return 0; 
}



Measured memory_bytes: 2048
N = int(input())
S = []
S.append([c for c in input()])
S.append([c for c in input()])
S.append([c for c in input()])

count = 0
for i in range(N):
    if S[0][i] == S[1][i] and S[1][i] == S[2][i]: continue
    elif S[0][i] == S[1][i] or S[1][i] == S[2][i] or S[0][i] == S[2][i]: count += 1
    else: count += 2
print(count)


Measured memory_bytes: 3064
var lines = []; var f;
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {

    /* --TLE-- */

    var N = Number(lines[0].split(" ")[0]);
    var X = Number(lines[0].split(" ")[1]);

    var result = 0;

    // バーガーの厚さの数列
    // an+1 = 2an + 3
    // (an+1 + 3) = 2(an +3)
    // 2(an + 3) = 2^n(a1 + 3)
    // an =  2^(n+2) - 3

    // パティの量
    // bn+1 = 2bn + 1
    // bn+1 + 1 = 2(bn + 1)
    // 2(bn + 1) = 2^n(b1 + 1)
    // bn = 2^(n+1) - 1

    console.log(dfs(N, X));
});

// 第nバーガー， 第x層までルンルンが食べる
function dfs(n, x) {
    var len = Math.pow(2, n + 1) - 3; // バーガーの厚さ
    var num = Math.pow(2, n) - 1; // パティの厚さ

    if (n === 0) { return (1); } // 0段バーガーのパティは1枚

    if (x === 1) { return (0); } // ルンルンが1層しか食べない場合，それはパン
    else if (x <= len + 1) { return (dfs(n - 1, x - 1)) }
    else if (x == len + 2) { return (num + 1) }
    else if (x <= (len + 1) * 2) { return (num + 1 + dfs(n - 1, x - len - 2)); }
    else { return (num * 2 + 1) }

}

Measured memory_bytes: 7628
N = int(input())
A = list(map(int,input().split()))
counter = 0
for i in range(N):
    if A[i]<0:
        counter += 1
        
B = []
for i in range(N):
    B.append(abs(A[i]))
    
if counter % 2 == 0:
    print(sum(B))
else:
    print(sum(B)-2*min(B))

Measured memory_bytes: 14412
/*
    _____
  .'|||||'.
 /  >   <  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
    |||||
*/

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
int n,a[200010],num[400010],vis[200010];
vector<int> ans;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=n;i>=1;i--)
    {
        int o=num[i];
        if (o%2==a[i])
        {
            vis[i]=0;
        } else
        {
            vis[i]=1;
            for (int j=1;j<=sqrt(i);j++)
                if (i%j==0)
            {
                num[j]++;
                if (i/j!=j)
                    num[i/j]++;
            }
        }
    }
    for (int i=1;i<=n;i++)
        if (vis[i]==1) ans.push_back(i);
        printf("%d\n",(int)ans.size());
        for (int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
    return(0);
}


Measured memory_bytes: 3832
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int ans = 0;
    for(int i = 0; i <= A; i++) {
        for(int j = 0; j <= B; j++) {
            if((X-500*i-100*j)%50==0 && 0<=(X-500*i-100*j)/50 && (X-500*i-100*j)/50<=C) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
j=0
c=sorted([int(i) for i in input().split()])
M=sum(c)-max(c)
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
print(M)
print(" ".join([str(i) for i in d]))


Measured memory_bytes: 6252
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextInt();
        TreeMap<Long, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            long key = sc.nextLong();
            int val = sc.nextInt();
            if(map.containsKey(key)) {
                map.put(key, map.get(key) + val);
            }else {
                map.put(key, val);
            }
        }
        long ans = 0l;
        for(Entry<Long, Integer> entry : map.entrySet()) {
            long key = entry.getKey();
            int val = entry.getValue();
            if(m >= val) {
                ans += key * val;
                m = m - val;
            } else if(m < val) {
                ans += m * key;
                break;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 65416
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
px = [LIST() for _ in range(Q)]

graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

ans = [0]*N

for p, x in px:
	ans[p-1] += x

check = [1]*N
check[0] = 0

q = deque([0])

while q:
	n = q.popleft()
	for node in graph[n]:
		if check[node]:
			ans[node] += ans[n]
			check[node] = 0
			q.append(node)

print(*ans)


Measured memory_bytes: 145564
#include<stdio.h>

int main(){
	int num;
	int count[100] = {0};
	int ans[100];
	int top = 0;
	int i = 0;

	while((scanf("%d",&num)) == 1){
		count[num-1]++;
		if(top < count[num - 1]) top = count[num - 1];
	}

	i = 0;
	while(1){
		if(top == count[i]) printf("%d\n", i + 1);
		if(i == 100) break;
		i++;
	}

	return 0;
}

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

int main() {
	// your code goes here
	int W,H,x,y,r;
	cin >> W >> H >> x >> y >> r;
	
	if( x-r < 0 || x+r > W || y-r < 0 || y+r > H ) cout << "No";
	else cout << "Yes";
	
	cout << endl;
	return 0;
}

Measured memory_bytes: 3096
package main

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

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	es := make([][]Edge, n)
	for i := 0; i < n; i++ {
		es[i] = make([]Edge, 0)
	}

	for i := 0; i < n-1; i++ {
		a := nextInt() - 1
		b := nextInt() - 1
		c := nextInt()
		es[a] = append(es[a], Edge{b, c})
		es[b] = append(es[b], Edge{a, c})
	}

	q := nextInt()
	k := nextInt() - 1

	ds := make([]int, n)
	for i := 0; i < n; i++ {
		ds[i] = -1
	}
	ds[k] = 0

	var dfs func(v int)
	dfs = func(v int) {
		for _, e := range es[v] {
			if ds[e.to] != -1 {
				continue
			}
			ds[e.to] = ds[v] + e.cost
			dfs(e.to)
		}
	}
	dfs(k)

	for i := 0; i < q; i++ {
		x := nextInt() - 1
		y := nextInt() - 1
		fmt.Println(ds[x] + ds[y])
	}
}

// Edge .
type Edge struct {
	to, cost int
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 43392
N=int(input())
L=[0]*N
for i in range(N):
    L[i]=list(map(int,input().split()))
x=0
y=0
for i in range(N):
    t=abs(x-L[i][1])+abs(y-L[i][2])
    t=L[i][0]-t
    if(t<0):
        print("No")
        exit()
    if(t%2!=0):
        print("No")
        exit()
    if(i+1!=N):
        x=L[i+1][1]
        y=L[i+1][1]

print("Yes")




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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
// range add/range min
struct SegTree {
	int n;
	std::vector<int> data;
	std::vector<int> added;
	SegTree (int n_) {
		for (n = 1; n < n_; n <<= 1);
		data.resize(n << 1, 1000000000);
		added.resize(n << 1);
	}
	void flush(int i) {
		if (added[i]) {
			data[i] += added[i];
			if (i < n) {
				added[i << 1] += added[i];
				added[i << 1 | 1] += added[i];
			}
			added[i] = 0;
		}
	}
	void chmin(int i, int val, int node = 1, int node_l = 0, int node_r = 0) {
		if (!node_r) node_r = n;
		flush(node);
		if (node_l == i && node_r == i + 1) {
			data[node] = std::min(data[node], val);
			return;
		}
		int mid = node_l + ((node_r - node_l) >> 1);
		if (i < mid) chmin(i, val, node << 1, node_l, mid);
		else chmin(i, val, node << 1 | 1, mid, node_r);
		if (node < n) flush(node << 1), flush(node << 1 | 1);
		data[node] = std::min(data[node << 1], data[node << 1 | 1]);
	}
	void add(int l, int r, int val, int node = 1, int node_l = 0, int node_r = 0) {
		if (!node_r) node_r = n;
		flush(node);
		if (l >= node_r || r <= node_l) return;
		if (l <= node_l && r >= node_r) {
			added[node] = val;
			flush(node);
		} else {
			int mid = node_l + ((node_r - node_l) >> 1);
			add(l, r, val, node << 1, node_l, mid);
			add(l, r, val, node << 1 | 1, mid, node_r);
			data[node] = std::min(data[node << 1], data[node << 1 | 1]);
		}
	}
	int min(int l, int r, int node = 1, int node_l = 0, int node_r = 0) {
		if (!node_r) node_r = n;
		flush(node);
		if (l >= node_r || r <= node_l) return 1000000000;
		if (l <= node_l && r >= node_r) return data[node];
		else {
			int mid = node_l + ((node_r - node_l) >> 1);
			int res = std::min(min(l, r, node << 1, node_l, mid), min(l, r, node << 1 | 1, mid, node_r));
			data[node] = std::min(data[node << 1], data[node << 1 | 1]);
			return res;
		}
	}
};
 
int main() {
	int n = ri();
	int a[n];
	for (auto &i : a) i = ri();
	
	int q = ri();
	std::pair<int, int> qs[q];
	for (auto &i : qs) i.first = ri() - 1, i.second = ri();
	std::sort(qs, qs + q, [] (auto i, auto j) {
		if (i.first != j.first) return i.first < j.first;
		return i.second > j.second;
	});
	
	int head = 0;
	SegTree tree(n + 1);
	tree.chmin(0, 0);
	for (int i = 0; i < n; i++) {
		while (head < q && qs[head].first <= i) {
			tree.chmin(qs[head].second, tree.min(0, qs[head].second));
			head++;
		}
		if (a[i]) tree.add(0, i + 1, 1);
		else tree.add(i + 1, tree.n, 1);
	}
	printf("%d\n", tree.min(0, tree.n));
	return 0;
}


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

int main() {
 UL N;scanf("%u",&N);
 int A[1000]; rep(i,N) scanf("%d",&A[i]);
 int B[1000];
 UL Q; scanf("%d",&Q);
 rep(q,Q){
  UL b,m,e; scanf("%u%u%u", &b,&m,&e);
  rep(k,e-b)B[b+k]=A[b+k];
  rep(k,e-b)A[b+((k+(e-m))%(e-b))]=B[b+k];
 }
 rep(i,N) {if(i)printf(" "); printf("%d",A[i]);}
 printf("\n");
 return 0;
}




Measured memory_bytes: 3156
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  int N;
  std::cin >> N;
  std::vector<int> A(N + 2);
  A[0] = 0;
  for (int i = 1; i <= N; ++i)
    std::cin >> A[i];
  A[N + 1] = 0;

  // Main
  int total = 0;
  for (int i = 1; i <= N + 1; ++i)
    total += std::abs(A[i] - A[i - 1]);

  std::vector<int> gain(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    gain[i] = std::abs(A[i] - A[i - 1]) + std::abs(A[i + 1] - A[i]) -
              std::abs(A[i + 1] - A[i - 1]);
  }

  // Output
  for (int i = 1; i <= N; ++i) {
    std::cout << total - gain[i] << std::endl;
  }

  return 0;
}


Measured memory_bytes: 2048
#include <stdio.h>
#include <math.h>

#define PI 3.141592653589793

int main(void){
    int a,b,c;
    double s,l,h;
    
    scanf("%d%d%d",&a,&b,&c);
    
    s = sin(c * PI / 180.0)*a*b/2;
    l = a + b + sqrt(a*a + b*b - 2*a*b * cos(c * PI / 180.0));
    h = s/a*2;
    
    printf("%lf %lf %lf\n" ,s,l,h);
    
    return 0;
}


Measured memory_bytes: 2096
#include <iostream>

using namespace std;

string S[100000];
string T;

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> S[i];
    cin >> T;
    int a = 0, b = 0, c = 0;
    for(int i = 0; i < N; i++) {
        string tmp1 = S[i];
        for(int j = 0; j < tmp1.size(); j++){
            if(tmp1[j] == '?') tmp1[j] = 'a';
        }
        string tmp2 = S[i];
        for(int j = 0; j < tmp2.size(); j++){
            if(tmp2[j] == '?') tmp2[j] = 'z';
        }
        if(tmp1 > T) c++;
        else if(T <= tmp2) b++;
        else a++;
    }
    for(int i = 0; i < b; i++){
        cout << a+i+1 << ' ';
    }
    cout << a+b+1 << endl;
}

Measured memory_bytes: 3192
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A,B,C;
    std::cin >> A >> B;
    if(A==1 && B==2){
        C=3;
    }
    else if(A==1 && B==3){
        C=2;
    }
    else if(A==2 && B==1){
        C=3;
    }
    else if(A==2 && B==3){
        C=1;
    }
    else if(A==3 && B==1){
        C=2;
    }
    else if(A==3 && B==2){
        C=1;
    }
    std::cout << C << std::endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int dp[100100][3], a[100100][3];
int n;

int max(int a, int b){
    return (a > b ? a : b);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++) scanf("%d", &a[i][j]);
    }

    for(int i = 0; i < 3; i++) dp[1][i] = a[1][i];
    for(int i = 2; i <= n; i++){
        for(int j = 0; j < 3; j++){
            int mx = 0;
            for(int k = 0; k < 3; k++){
                if(k != j) mx = max(mx, dp[i - 1][k]);
            }
            dp[i][j] = mx + a[i][j];
        }
    }

    int ans = 0;
    for(int i = 0; i < 3; i++) ans = max(ans, dp[n][i]);
    printf("%d\n", ans);
}

Measured memory_bytes: 2560
#include <stdio.h>
int main(void){
 int n,m;
    scanf("%d%d",&n,&m);
 int a[n],i,sum=0,count=0;
     for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
     }
     for(i=0;i<n;i++){
     if((double)a[i]>=(double)sum/(4*m)) count++;
     }
     if(count>=m) puts("Yes");
     else puts("No");    
return 0;
}

Measured memory_bytes: 1628
require "prime"
q=gets.to_i
a=[0]
pr=[0]*(10**5+1)
prime=Prime.each(10**5).to_a
prime.each do |pp|
  pr[pp]=1
end
aa=0
1.upto(10**5) do |i|
  if pr[i]==1&&pr[(i+1)/2]==1
    a[i]=a[i-1]+1
  else
    a[i]=a[i-1]
  end
end
q.times do
  l,r=gets.split.map(&:to_i)
  puts a[r]-a[l-1]
end


Measured memory_bytes: 4532
package main

import "fmt"

func main() {
	var n string
	fmt.Scan(&n)
	ans := ""
	for i := 0; i < 3; i++ {
		if n[i:i+1] == "1" {
			ans += "9"
		} else if n[i:i+1] == "9"{
			ans += "1"
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long n,a=0,b,sum;
    cin>>n;
    vector <long long> y;
    for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            y.push_back(i);
        }
    }
     while(1){
        f(i,0,y.size()){
            b=a-y[i];
            sum=a*a*a*a+a*a*a*b+a*a*b*b+a*b*b*b+b*b*b*b;
            if(sum==n/y[i]){
                cout<<a<<" "<<b<<endl;
                return 0;
            }
        }
        a++;
    }
}


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

const int N = 200233;
int n, c[N];
vector<int> G[N];

int reach(int x, int fa, int lim) {
  int ret = 0;
  for (auto y : G[x]) if (y != fa) {
    if (y < lim) {
      ret += reach(y, x, lim) + 1;
    }
  }
  return ret;
}
void dfs(int x, int fa, int m0, int m1) {
  if (x > m1) {
    c[x] = c[fa] + 1 + reach(x, fa, m0);
  } else if (m0 > m1) {
    c[x] = c[fa] + reach(x, fa, m0) - reach(x, fa, m1);
  } else {
    c[x] = c[fa];
  }
  for (auto y : G[x]) if (y != fa) {
    dfs(y, x, max(m0, x), max(m1, fa));
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  c[1] = 0;
  dfs(1, 0, 1, 1);
  for (int i = 2; i <= n; i++) {
    printf("%d%c", c[i], i == n ? '\n' : ' ');
  }
}


Measured memory_bytes: 25856
/*
AtCoder ABC150 C "Count Order".
next_permutation().
*/
#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
using namespace std;
typedef vector<int>   vi;

int n;

bool jud_same(vi a,vi b){
	REP(i,n){
		if(a[i]==b[i]){}
		else return false;
	}
	return true;
}

int main(){
	cin>>n;
	
	vi p(n),q(n);
	REP(i,n) cin>>p[i];
	REP(i,n) cin>>q[i];
	
	vi v=p;
	sort(ALL(v));
	
	int cnt=1;
	int pn,qn;
	do{
		if(jud_same(v,p)) pn=cnt;
		if(jud_same(v,q)) qn=cnt;
		cnt++;
	}while(next_permutation(ALL(v)));

	cout<<abs(pn-qn)<<endl;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
x = gets.chomp.split(" ").map(&:to_i)
total = nil
(x.min..x.max).map do |c|
  sum = x.map{ |e| (c - e)**2 }.inject(:+)
  total = sum if c == x.min
  if sum <= total
    total = sum
  else
    break
  end
end
p total


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

int N;
string S;
vector<int> L, R;

signed main() {
  cin >> S;
  N = S.size();
  for(int i=0; i<N; i++) {
    if(S[i]=='L') L.push_back(i);
    else R.push_back(-i);
  }
  sort(R.begin(), R.end());
  vector<int> ans(N,0);
  for(int i=0; i<N; i++) {
    if(S[i]=='R') {
      int stop = *upper_bound(L.begin(), L.end(), i);
      int dist = stop - i;
      if(dist % 2 == 0) ans[stop]++;
      else ans[stop-1]++;
    }
    else {
      int stop = *upper_bound(R.begin(), R.end(), -i) * -1;
      int dist = i - stop;
      if(dist % 2 == 0) ans[stop]++;
      else ans[stop+1]++;
    }
  }
  for(int i=0; i<N; i++) {
    cout << ans[i] << (i==N-1 ? "\n" : " ");
  }
}


Measured memory_bytes: 1532
import java.util.Scanner;

class Main{
	public static void main(String[] ag) {
		Scanner sc=new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int C=sc.nextInt();

		for(int i=1; i<10000; i++) {
			if(A*i%B==C) {
				System.out.println("YES");
				System.exit(0);
			}
		}

		System.out.println("NO");
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct node{
    int r,c,a;
    friend bool operator<(node a,node b){
        return a.a>b.a;
    }
}st[maxn];
int fa[maxn],S[maxn],T[maxn];
int n,H,W;
int init(){
    for(int i=1;i<=H+W;i++){
        fa[i]=i;
        T[i]=1;
    }
}
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>H>>W;
    init();
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&st[i].r,&st[i].c,&st[i].a);
    }
    sort(st+1,st+1+n);
    ll ans=0;
    for(int i=1;i<=n;i++){
//        printf("%d %d %d\n",st[i].r,st[i].c,st[i].a);
        int fr=find(st[i].r),fc=find(H+st[i].c);
        if(fr==fc){//两个在同一集合内
            if(T[fc]>=S[fc]+1){
                S[fc]++;
                ans=ans+st[i].a;
            }
        }
        else{//两个不在同一集合内，要合并
            if(T[fr]+T[fc]>=S[fr]+S[fc]+1){
                fa[fr]=fc;
                T[fc]+=T[fr];
                S[fc]=S[fr]+S[fc]+1;
                ans=ans+st[i].a;
            }
        }
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

vector<pair<ll,ll>> output;
void process(ll x,ll y,vector<ll>& vec_x,vector<ll>& vec_y,vector<ll>& tgt) {
  output.push_back({x,y});
  auto itr_x=lower_bound(vec_x.begin(), vec_x.end(),x);
  vec_x.erase(itr_x);
  auto itr_y=lower_bound(vec_y.begin(), vec_y.end(),y);
  vec_y.erase(itr_y);
  // tgt.push_back(x-y);
  tgt.insert(tgt.begin(),x-y);
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin>>n;
  if (n==2) {
    vector<ll> tmp(2);
    cin>>tmp[0]>>tmp[1];
    sort(tmp.begin(), tmp.end());
    cout<<tmp[1]-tmp[0]<<endl;
    cout<<tmp[1]<<" "<<tmp[0]<<endl;
    return 0;
  }
  vector<ll> plus,minus;
  for (ll i = 0; i < n; ++i)
  {
    ll a;
    cin>>a;
    if (a>0) plus.push_back(a);
    else minus.push_back(a);
  }

  sort(plus.begin(), plus.end());
  sort(minus.begin(), minus.end());

  if (minus.empty()) {
    process(plus.front(),plus.back(),plus,plus,minus);
  } else if (plus.empty()) {
    process(minus.back(),minus.front(),minus,minus,plus);
  }

  // while (minus.size()!=1) {
  //   process(plus.back(),minus.front(),plus,minus,plus);
  // }

  // while (plus.empty()!=1) {
  //   process(minus.front(),plus.front(),minus,plus,minus);
  // }

  // process(plus.front(),minus.front(),plus,minus,plus);

  while (plus.size()!=1) {
    process(minus.front(),plus.front(),minus,plus,minus);
  }


  while (!minus.empty()) {
    process(plus.front(),minus.front(),plus,minus,plus);
  }


  cout<<plus.front()<<endl;
  for (ll i = 0; i < output.size(); ++i)
  {
    cout<<output[i].first<<" "<<output[i].second<<endl;
  }
}

Measured memory_bytes: 7124
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()



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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    int A,B,C;cin>>A>>B>>C;
    cout<<max(0,C-(A-B))<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n), y(n), h(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> h[i];
    }
    for (int i = 0; i < n; ++i) {
        if (h[i] != 0) {
            swap(x[i], x[0]);
            swap(y[i], y[0]);
            swap(h[i], h[0]);
            break;
        }
    }
    for (int i = 0; i <= 100; ++i) {
        for (int j = 0; j <= 100; ++j) {
            bool ok = true;
            int hh  = -1;
            for (int k = 0; k < n; ++k) {
                if (hh == -1) {
                    hh = h[k] + abs(x[k] - i) + abs(y[k] - j);
                } else {
                    if (max(hh - abs(x[k] - i) - abs(y[k] - j), 0) != h[k])
                        ok = false;
                }
            }
            if (ok) {
                cout << i << " " << j << " " << hh << "\n";
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#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;
const int INF = 1000000001;

int LIS(int N, int *a){
  int dp[N];
  fill(dp, dp + N, INF);
  REP(i, N) *lower_bound(dp, dp + N, a[i]) = a[i];
  return lower_bound(dp, dp + N, INF) - dp;
}

int main() {
  int N; cin >>N;
  int a[N];
  REP(i, N) cin >>a[i];
  cout <<LIS(N, a) <<endl;
  return 0;
}

Measured memory_bytes: 1940
n,m=map(int,input().split())
P=list(map(int,input().split()))
par=list(range(n+1))

def find(x):
    if par[x]==x:
        return x
    a=find(par[x])
    par[x]=a
    return a

for i in range(m):
    x,y=map(int,input().split())
    bx,by=find(x),find(y)
    par[y]=bx
    par[by]=bx

ans=0

for i in range(1,n+1):
    if find(i)==find(P[i-1]):
        ans+=1
print(ans)

Measured memory_bytes: 14008