akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

struct edge{
    ll to;
    ll score;
};

vector<vector<edge>> tree;
vector<ll> d;
priority_queue<ll> q;

void dfs(ll x, ll p){
    ll y = q.top();
    q.pop();
    d.at(x) = y;
    for(auto e : tree.at(x)){
        if(e.to == p){
            continue;
        }
        dfs(e.to, x);
    }
}

int main()
{
    ll N;
    cin >> N;
    tree.resize(N);
    d.resize(N);
    rep(i, N-1){
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        tree.at(a).push_back({b, INF});
        tree.at(b).push_back({a, INF});
    }
    vector<ll> c(N);
    rep(i, N) cin >> c.at(i);
    vector<pair<ll, ll>> deg(N);
    rep(i, N){
        deg.at(i) = make_pair(sz(tree.at(i)), i);
    }
    sort(all(deg));
    rep(i, N){
        q.push(c.at(i));
    }
    dfs(0, -1);
    ll M = 0;
    rep(i, N){
        for(auto e : tree.at(i)){
            ll x = min(d.at(i), d.at(e.to));
            chmin(e.score, x);
            M += e.score;
        }
    }
    cout << M / 2 << endl;
    rep(i, N-1){
        cout << d.at(i) << " ";
    }
    cout << d.at(N-1) << endl;
}

Measured memory_bytes: 4936
#include "bits/stdc++.h"
using i64 = long long;
using namespace std;

//@@@@@@@
//@ snippet modPow
//@ options head
constexpr i64 modPow(i64 n, i64 p, const int mod = int(1e9)+7)
{
    i64 ret = 1;
    while(p) {
        if (p & 1) ret = (ret * n) % mod;
        n = (n * n) % mod;
        p >>= 1;
    }
    return ret;
}
//@@@@@


//@@@@@@
// snippet ModInt
// abbr    Mint
// options head
template<int MOD> class ModInt {
private:
    long long n;
    using T = ModInt<MOD>;
public:
    static constexpr const int mod = MOD;
    constexpr inline ModInt(long long n_) : n(n_ % MOD) {}
    template<class Int> constexpr explicit inline operator Int() const { return n; }
    friend ostream& operator<<(ostream &os, T m) { os << m.n; return os; }
    constexpr inline T operator~() const { return modPow(n, MOD-2, MOD); }
    constexpr inline T& operator+=(T o) { n = (n + o.n) % MOD; return *this; }
    constexpr inline T& operator-=(T o) { n = (n - o.n + MOD) % MOD; return *this; }
    constexpr inline T& operator*=(T o) { n = (n * o.n) % MOD; return *this; }
    constexpr inline T& operator/=(T o) { n = (n * (~o).n) % MOD; return *this; }
};
using Mint = ModInt<int(1e9)+7>;
Mint operator+(Mint a, Mint b) { return Mint(a) += b; }
Mint operator-(Mint a, Mint b) { return Mint(a) -= b; }
Mint operator*(Mint a, Mint b) { return Mint(a) *= b; }
Mint operator/(Mint a, Mint b) { return Mint(a) /= b; }
//@@@@@


//@@@@@@
//@ snippet Factrial
//@ abbr    comb, perm, nCr, nPr
//@ options head
template<size_t N, int MOD=int(1e9)+7> struct Factrial {
    using Mint = ModInt<MOD>;
    i64 a[N];
    constexpr inline Factrial() : a{1} { for (int i = 1; i < N; ++i) a[i] = (a[i-1] * i) % MOD; }
    constexpr inline Mint operator[] (size_t i) const { return a[i]; }
};

Factrial<100010> fact;

Mint nCr(i64 n, i64 r) { return (r < 0 || n < r) ? 0 : (fact[n] / (fact[r] * fact[n-r])); }

Mint nPr(i64 n, i64 r) { return (r < 0 || n < r) ? 0 : (fact[n] / fact[r]); }

Mint nHr(i64 n, i64 r) { return nCr(n+r-1, r); }
//@@@@@@

struct FastIO {
    FastIO() { cin.tie(nullptr); ios::sync_with_stdio(false); }
} fastIO_ydk ;

signed main()
{
    int N;
    int a[100010];
    bool exist[100010] {};
    int twice;

    cin >> N;
    for (int i = 0; i < N+1; ++i) {
        cin >> a[i];
        if (exist[a[i]]) {
            twice = a[i];
        } else {
            exist[a[i]] = true;
        }
    }

    int l, r;
    for (l = 0; a[l] != twice; ++l);
    for (r = N; a[r] != twice; --r);

    const int M = N - (r - l);

    for (int k = 1; k <= N+1; ++k) {
        cout << nCr(N+1, k) - nCr(M, k-1) << '\n';
    }
}


Measured memory_bytes: 1664
import java.io.*;
import java.math.*;
import java.util.*;
 
public class Main {
	static final long MOD = 1000000007L;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		long X = sc.nl();
		long K = sc.nl();
		long D = sc.nl();
		if (Math.log(K)+Math.log(D) > Math.log(1e15) || K*D >= Math.abs(X)) {
			//we can go to optimal positions
			long p1 = (D+X%D)%D;
			long p2 = p1-D;
			long moves = Math.abs((X-p1)/D);
			if (moves%2 == K%2)
				pw.println(Math.abs(p1));
			else
				pw.println(Math.abs(p2));
		} else if (X < 0) {
			pw.println(Math.abs(X+K*D));
		} else {
			pw.println(Math.abs(X-K*D));
		}
		pw.close();
	}
	
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            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 ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}

Measured memory_bytes: 32992
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main()
{
  string a,b;
  int d = 0;
  cin >> a; 
  while(cin>>b,b!= "END_OF_TEXT"){
    int l = b.size();
    for(int i = 0; i < l; i++) b[i] = tolower(b[i]);
    if(a == b) d++;
  }
  cout << d << endl;
}

Measured memory_bytes: 3196
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> a(2, vector<int>(n));
	rep(i, n){
		int in;
		cin >> in;
		a.at(0).at(i) = in;
	}
	rep(i, n){
		int in;
		cin >> in;
		a.at(1).at(i) = in;
	}
	int ans = 0;
	rep(i, n){
		int add = 0;
		rep(j, n){
			if(j <= i){
				add += a.at(0).at(j);
			}
			if(i <= j){
				add += a.at(1).at(j);
			}
		}
		ans = max(ans, add);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn

object Main extends App {
  val n = StdIn.readInt
  val a = Iterator.continually(StdIn.readInt).take(n).toArray
  val odd = a.exists(i => (i & 1)==1)
  val ans = if(odd) "first" else "second"
  println(ans)
}

Measured memory_bytes: 37716
/* ALDS1_3_A_Stack */

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 200

char top;
int stack[N];

void push(int m);
int pop();

int main(void){
	char A[N];
	int x, y;
	top = 0;
	while((scanf("%s", A)) != EOF){
		if(((A[0] - '0') >= 0) && ((A[0] - '0') <= 9)) push(atoi(A));
		else{
			y = pop(); 
			x = pop(); 
			switch(A[0]){
				case '+': push(x + y); break;
				case  '-': push(x - y); break;
				case '*':  push(x * y); break;
				case '/':  push(x / y); break;
				default : break;
			}
		}
	}

	printf("%d\n", pop());

	return 0;
}

void push(int m){
	stack[top++] = m;
}

int pop(){
	int ret = stack[--top];

	return ret;
}


Measured memory_bytes: 1992
#include<stdio.h>


int main(void){

	int a,i=0,x[10001];
	do{
		i++;
		scanf("%d",&x[i]);
	}while(x[i]!=0);
	for(a=1;a<i+1;a++){
		if(x[a]==0){
			return 0;
		}else{
		printf("Case %d: %d\n",a,x[a]);
		}
	}

}
	
	

Measured memory_bytes: 636
function Main(input) {
  const lines = input.split("\n");
  const N = +lines[0].split(" ")[0]
  const X = +lines[0].split(" ")[1]
  var sum = 0;
  var min = 10001;
  for (var i = 0; i < N; i++) {
    sum += +lines[i+1]
    min = Math.min(min,  0+lines[i+1])
  }
  console.log(N + Math.floor((X - sum) / min));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29604
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vt>vvt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

//nCr mod m
#define MOD 998244353
#define M 500000
vector<ll> fact;
bool h=false;
void init(){
	h=true;
	fact=vector<ll>(M);
	fact[0]=fact[1]=1;
	loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// a^b mod MOD
ll powmod(ll a,ll b,ll m=MOD){
	ll out=1;
	ll p=a%m;
	while(b){
		if(b&1)out=out*p%m;
		p=p*p%m;
		b>>=1;
	}
	return out;
}
//nCr
ll nCr(ll n,ll r,ll m=MOD){
	if(!h)init();
	if(n<0||r<0||n<r)return 1;//??????
	ll out=fact[n]*powmod(fact[r]*fact[n-r]%m,m-2,m)%m;
	return out;
}
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
vi dp(1000,-1);
int f(int a){
	if(dp[a]+1)return dp[a];
	return dp[a]=powmod(fact[a],MOD-2,MOD);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n,m,k;
	cin>>n>>m>>k;
	int out=0;
	rep(i,k+1){
		int s=m*powmod(m-1,n-1-i)%MOD*nCr(n-1,i)%MOD;
		(out+=s)%=MOD;
	}

	cout<<out<<endl;
}


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

int main(){
	while(1){
		int n, m;
		scanf(" %d %d", &n, &m);
		if(n==0) break;
		
		string p[100];
		long prize[100];
		for(int i=0; i<n; ++i) cin >> p[i] >> prize[i];
		
		long ans=0;
		
		for(int i=0; i<m; ++i){
			string s;
			cin >> s;
			
			for(int j=0; j<n; ++j){
				bool hit=true;
				for(int k=0; k<8; ++k){
					if(p[j][k]=='*') continue;
					
					if(s[k]!=p[j][k]) hit=false;
				}
				
				if(hit) ans+=prize[j];
			}
				
		}
				
		printf("%ld\n", ans);
	}
}		

Measured memory_bytes: 1256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N, K; cin >> N >> K;
    vec a(N); readvec(a);

    int ans = 0;
    REP(i, N) ans += max(a[i], 0LL);

    int tmp = 0, tmp2 = 0;
    REP(i, K){
        tmp += a[i];
        tmp2 += max(a[i], 0LL);
    }
    int m = tmp2 - max(tmp, 0LL);
    FOR(i, K, N){
        tmp += a[i] - a[i - K];
        tmp2 += max(a[i], 0LL) - max(a[i - K], 0LL);
        m = min(m, tmp2 - max(tmp, 0LL));
    }
    ans -= m;
    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 1024
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> x >> n;
  rep(i, n) cin >> a[i];
  cnt = LINF;
  rrep(i, -1000, 1000) {
    int ok = 1;
    rep(j, n) {
      if (a[j] == i) ok = 0;
    }
    if (!ok) continue;
    b = i;
    if (cnt > abs(b - x)) {
      cnt = abs(b - x);
      ans = i;
    } else if (cnt == abs(b - x)) {
      ans = min(ans, i);
    }
  }
  Cout(ans);
  return 0;
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    vector<int> sides;
    bool check(const vector<vector<int>> &E) {
        int N = E.size();
        vector<int> visited(N);
        function<void(int)> walk_parent = [&] (int now) {
            visited[now] = true;
            for(int nxt : E[now]) {
                if(E[nxt].size() > 1 and not visited[nxt]) {
                    walk_parent(nxt);
                    return;
                }
            }
            sides.push_back(now);
        };
        int parent = -1;
        rep(i, N) if(E[i].size() > 1) {
            parent = i;
            break;
        }
        assert(parent >= 0);
        walk_parent(parent);
        walk_parent(parent);
        rep(i, N) if(E[i].size() > 1 and not visited[i]) return false;
        return true;
    }
    vector<int> build(const vector<vector<int>> &E) {
        int now = sides[0];
        vector<int> ans = {1};
        int upper = 2;
        int prev = -1;
        while(true) {
            int num = E[now].size() - 2;
            for(int i = upper + 1; i <= upper + num; i++) ans.push_back(i);
            ans.push_back(upper);
            upper = upper + num + 1;
            if(now == sides[1]) break;
            for(int nxt : E[now]) {
                if(E[nxt].size() > 1 and nxt != prev) {
                    prev = now;
                    now = nxt;
                    break;
                }
            }
        }
        ans.push_back(upper);
        return ans;
    }
    bool solve() {
        int N; cin >> N;
        vector<vector<int>> E(N);
        rep(i, N - 1) {
            int a, b; cin >> a >> b;
            E[a - 1].push_back(b - 1);
            E[b - 1].push_back(a - 1);
        }
        if(not check(E)) {
            cout << -1 << endl;
            return 0;
        }
        auto ans = build(E);
        reverse(all(sides));
        set_min(ans, build(E));
        rep(i, ans.size()) cout << ans[i] << (i == ans.size() - 1 ? "\n" : " ");

        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 8816
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ci not in v:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

    for i in range(1, N + 1):
        print(ans[i])


if __name__ == '__main__':
    main()


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

using ll=long long;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int lx = x2-x1;
  int ly = y2-y1;
  cout << x2-ly <<' '<< y2+lx <<' '<< x1-ly <<' '<< y1+lx << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

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


int main()
{
  string s;
  cin >> s;
  for (int i = 0; i < 3; i++) {
    if (s[i] == '1') cout << 9;
    else if (s[i] == '9') cout << 1;
    else cout << s[i];
  }
  cout << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}

const int MAX_N = 200005;
int bit[MAX_N+1];
int nn = MAX_N; //　1-index

void adds(int a, int w){
    for(int x = a; x <= nn; x += x & -x) bit[x] += w;
}
int sums(int a){ // bit[1,a]の和を返す.
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) ret += bit[x];  
    return ret;
}


int main() {
    int n, k;
    cin >> n >> k;
    int a[n+1] = {};
    srep(i,1,n+1)cin >> a[i];

    rep(loop,k){
        int b[MAX_N] = {};
        // rep(i,MAX_N+1)bit[i] = 0;
        srep(i,1,n+1){
            int l = max(1,i-a[i]);
            int r = min(n,i+a[i]);
            b[l]++;
            b[r+1]--;
            // adds(l,1);
            // adds(r+1,-1);
        }
        ll sum = 0;
        srep(i,1,n+1){
            if(i > 1) b[i] += b[i-1];
            a[i] = b[i];
            // a[i] = sums(i);
            sum += a[i];
        }
        if(sum == (ll)n * n)break;
    }
    srep(i,1,n+1)cout << a[i] << ' ';
    cout << endl;
    return 0;
}




Measured memory_bytes: 5200
#include <iostream>
#include <iomanip>

using namespace std;

long long int W, H, x, y;

int main() {
    cin >> W >> H >> x >> y;
    cout << fixed << setprecision(10) << W * H / 2.0 << " ";
    if (x * 2 == W && y * 2 == H) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}


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

int main()
{
    string s;
    cin >> s;
    int cnt[26] = {0};

    for (int i = 0; i < s.length(); i++)
    {
        cnt[(s[i] - 'a')] = 1;
    }
    for (int i = 0; i < 26; i++)
    {
        if (!cnt[i])
        {
            cout << char('a' + i) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <random>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;

int main() {
    int k,x; cin >> k >> x;
    int right = x+k-1;
    int left = x-(k-1);
    for (int i = left; i <= right; i++)
    {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define INF (1<<29)
using namespace std;
typedef long long ll;
string s,t;
bool ok(int a,int x){
      bool f=true;
      REP(i,s.size())if(a+x*i>=t.size()||s[i]!=t[a+x*i])f=false;
      return f;
}
int main(){
      int n;
      cin>>n;
      cin>>s;
      int ans=0;
      while(n--){
            cin>>t;
            REP(i,t.size()){
                  if(t[i]==s[0]){
                        bool f=false;
                        REP(j,t.size())if(ok(i,j))f=true;
                        if(f){
                              ans++;
                              break;
                        }
                  }
            }
      }
      cout<<ans<<endl;
}

Measured memory_bytes: 1208
A, B, H, M = gets.split.map(&:to_i)

hour_d = H / 12.0 * 360 + M / 60.0 * 30
min_d = M / 60.0 * 360
degree = (hour_d - min_d).abs
r = degree / 180 * Math::PI

dis = Math.sqrt (A**2 + B**2 - 2 * A * B * Math.cos(r))
puts dis

Measured memory_bytes: 14656
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){

    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

bool IsPrime(ll num){
    if(num < 2) return false;
    else if(num == 2) return true;
    else if(num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for(ll i = 3; i <= sqrtNum; i += 2){
        if(num%i==0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

signed main(){
  ll a,b; cin>>a>>b;
  ll ans = 1;
  priority_queue<ll> x,y;

  reps(i,pow(a,0.5)){
    if(a%i!=0) continue;
    if(IsPrime(i)) x.push(i);
    if(i==a/i) continue;
    if(IsPrime(a/i)) x.push(a/i);
  }
  reps(i,pow(b,0.5)){
    if(b%i!=0) continue;
    if(IsPrime(i)) y.push(i);
    if(i==b/i) continue;
    if(IsPrime(b/i)) y.push(b/i);
  }
  while((!x.empty())&&(!y.empty())){
    ll s = x.top(), t = y.top();
    if(s==t){
      x.pop(); y.pop(); ans++;
      // cerr << s << endl;
    }else if(s>t){
      x.pop();
    }else{
      y.pop();
    }
  }
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
const int MAX = 510000;
int fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
long long COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
int par[114514], rrank[114514];//親、木の深さ
void init(int n) {
	rep(i, n) {
		par[i] = i;
		rrank[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rrank[x] < rrank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rrank[x] == rrank[y])rrank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int n, m;
int p[114514];
signed main() {
	COMinit();
	cin >> n >> m;
	rep(i, n)cin >> p[i];
	int ans = 0;
	sort(p, p + n);
	rep(i, n - 1) {
		ans += ((COMB(n, m) - (COMB(i + 1, m) + COMB(n - i - 1, m)) + mod) % mod) * ((p[i + 1] - p[i]) % mod) % mod;
		ans %= mod;
	}
	cout << ans << endl;
	ggr
}

Measured memory_bytes: 13696
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  w,h,x,y=LI()

  if w/2==x and h/2==y:
    print(w*h/2,1)
  else:
    print(w*h/2,0)

main()


Measured memory_bytes: 6096
N = int(input())
S = str(input())

T = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
S2 = list(S)
T2 = list(T)

for i in range(len(S)):
    S2[i] = T2[int(T2.index(S2[i]) + N)]
print(''.join(S2))

Measured memory_bytes: 3060
import java.util.Scanner;

	public class Main {

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

			String str = sc.next();

			if(str.equals("AAA")||str.equals("BBB")) {
				System.out.println("No");
			}else {
				System.out.println("Yes");
			}

		}

	}




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

int main() {
    int N;
    string S;
    cin>>N>>S;
    
    set<int> s1,s2,s3;
    rep(i,N){
        int num = S[i]-'0';
        for(auto x:s2){
            s3.insert(x * 10 + num);
        }
        for(auto x:s1){
            s2.insert(x * 10 + num);
        }
        s1.insert(num);
    }
    cout<<s3.size()<<endl;
}

Measured memory_bytes: 384
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 2e5+10 , mod = 1e9+7;
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
	return f ? -x : x;
}
int n , m;
char s[N];
int sum[N] , f[N];
int main()
{
	n = read(); m = read(); scanf("%s" , s+1);
	int i , mx , ans = 0;
	for(i = 1 ; i <= m ; ++i) if(s[i] != s[1]) break;
	mx = i - 1;
	if(mx == m)
	{
		sum[0] = f[0] = ans = 1;
		for(int i = 1 ; i <= n ; ++i)
		{
			if(i >= 2) f[i] = sum[i-2];
			sum[i] = (sum[i-1] + f[i]) % mod;
		}
		for(int i = 0 ; n - i >= 2 ; ++i) (ans += (LL)f[i] * (n - i) % mod) %= mod;
		cout << ans << '\n'; return 0;
	}
	if(n & 1) return puts("0") , 0;
	if(mx % 2 == 0) mx++;
	for(int tmp = 0 ; i <= m ; ++i)
	{
		if(s[i] == s[1]) tmp++;
		else
		{
			if(tmp & 1) mx = min(mx , tmp);
			tmp = 0;
		}
	}
	mx = (mx + 1) >> 1; n >>= 1; f[0] = sum[0] = 1;
	for(int i = 1 ; i <= n ; ++i)
	{
		f[i] = (sum[i-1] - (i - mx - 1 >= 0 ? sum[i - mx - 1] : 0) + mod) % mod;
		sum[i] = (sum[i-1] + f[i]) % mod;
	}
	for(int i = 0 ; i <= n ; ++i) if(n - i <= mx) (ans += (LL)f[i] * (n - i) % mod * 2 % mod) %= mod;
	cout << ans << '\n'; return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<ld> vld;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()

int main()
{
	fastIO;
	string s, t; cin >> s >> t;
	int ans = t.length();

	for(int i = 0; i + t.length() - 1 < s.length(); i++)
	{
		int cnt = t.length();
		for(int j = 0; j < t.length(); j++)
			if(s[i + j] == t[j])
				cnt--;

		if(ans > cnt) ans = cnt;
	}
	cout << ans << endl;

	return 0;
}

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

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
 
typedef long long ll;
using namespace std;
 
int main(){
  int n;
  int a = 0;
  cin >> n;
  rep(i,1,n+1){
    a += i;
  }
  printf("%d\n", a);
  
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define pll pair<ll,ll>
vector<int> adj[100001];
bool vis[100001] ={0};
int n,m,u,v;
void dfs(int v){
	vis[v]=1;
	for(int i = 0 ;i <adj[v].size();i++){
		if(vis[adj[v][i]])continue;
		dfs(adj[v][i]);
	}
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<m;i++){
    	cin>>u>>v;
    	--u,--v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
	}
	int comp =0;
	for(int i=0;i<n;i++){
		if(vis[i])continue;
		++comp;
		dfs(i);
	}
	cout<<comp-1;
    return 0;
}

Measured memory_bytes: 9704
#include<bits/stdc++.h>
using namespace std;
#define int long long

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

signed main(){

  int n,k; cin >> n >> k;
  vector<int> v(40,0),a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
    for(int j = 0; j < 40; j++){
      if(a[i] >> j & 1) v[j]++;
    }
  }

  bool under = false;
  int ans = 0;
  for(int i = 39; i >= 0; i--){
    if(v[i]*2 < n){
      if(!under && !(k >> i & 1)) continue;
      ans += 1LL << i;
    }
    else {
      if(k >> i & 1) under = true;
    }
  }

  int res = 0;
  for(int i = 0; i < n; i++){
    res += a[i] ^ ans;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
typedef long long ll;

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

    int sm[30][100010];
    for (int i = 0; i < 26; i++) sm[i][0] = 0;
    bool p[26] = {};
    for (int i = 0; i < s.size(); i++) {
        p[int(s[i]) - 'a'] = true;

        for (int j = 0; j < 26; j++) {
            if (j == int(s[i]) - 'a') sm[j][i + 1] = sm[j][i] + 1;
            else sm[j][i + 1] = sm[j][i];
        }
    }
    for (int i = 0; i < t.size(); i++) {
        if (!p[int(t[i]) - 'a']) {
            cout << -1 << endl;
            return 0;
        }
    }

    ll round = 0, s_idx = 0, t_idx = 0;
    while (t_idx < t.size()) {
        if (sm[int(t[t_idx]) - 'a'][int(s.size())] - sm[int(t[t_idx]) - 'a'][s_idx] > 0) {
            int ng = s_idx, ok = s.size();
            while (ok - ng > 1) {
                int md = (ng + ok) / 2;
                if (sm[int(t[t_idx]) - 'a'][md] - sm[int(t[t_idx]) - 'a'][s_idx] > 0) ok = md;
                else ng = md;
            }
            s_idx = ok;
            t_idx++;
        }
        else {
            round++;
            s_idx = 0;
        }
    }

    cout << round * s.size() + s_idx << endl;


}

Measured memory_bytes: 12288
///A drunk man will find his way home, but a drunk bird may get lost forever...
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define sz(x) (long long)x.size()
#define int long long
const int mx = 2005;
char c[mx * 2];
bool b[mx][2];
int co[mx][mx][2], dp[mx][mx], s[mx * 2];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < 2 * n; i++){
		cin >> c[i] >> s[i];
		s[i]--;
	}
	for(int i = 0; i < 2 * n; i++){
		b[s[i]][c[i] == 'B'] = true;
		for(int j = n; j >= 0; j--){
			co[s[i]][j][c[i] == 'B'] = co[s[i]][j + 1][c[i] == 'B'];
			if(b[j][c[i] == 'W'])
				co[s[i]][j][c[i] == 'B']++;
		}
	}
//	for(int i = 0; i < n; i++)
//		for(int j = 0; j <= n; j++)
//			cout << co[i][j][0] << " " << co[i][j][1] << endl;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			dp[i][j] = 1e9 + 10;
	dp[0][0] = 0;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++){
			if(i)
				dp[i][j] = min(dp[i][j] , dp[i - 1][j] + co[i - 1][j][0]);
			if(j)
				dp[i][j] = min(dp[i][j] , dp[i][j - 1] + co[j - 1][i][1]);
		}
	for(int i = 0; i < 2 * n; i++)
		for(int j = 0; j < i; j++)
			if(c[i] == c[j] && s[i] < s[j])
				dp[n][n]++;
	cout << dp[n][n] << endl;
	return 0;
}


Measured memory_bytes: 94464
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
bool custom1 (pair<int, int> a, pair<int, int> b) {
  return (a.first < b.first);
}
bool custom2(pair<int, int> a, pair<int, int> b) {
  return (a.second < b.second);
}

const int MAX = 200005;
const long long MOD = 1000000007;
const long long MODMOD = 998244353;
const double PI = acos(-1);

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
  vector<int> p;
  vector<int> s;
  void init(int n) {
    p.resize(n, -1);
    s.resize(n, 1);
  }
  int find(int n) {
    if(p[n] == -1) return n;
    else return find(p[n]);
  }
  int size(int n) {
    return s[find(n)];
  }
  void unite(int n, int m) {
    int pn = find(n);
    int pm = find(m);
    if(pn == pm) return;
    if(s[pn] > s[pm]) {
      s[pn] = s[pn] + s[pm];
      p[pm]= pn;
    } else {
      s[pm] = s[pm] + s[pn];
      p[pn] = pm;
    }
  }
};

long long gcd(long long a, long long b) {
  if(a % b == 0) return b;
  else return gcd(b, a % b);
}
int main() {
  int n;
  string s;
  cin >> n >> s;
  int q;
  cin >> q;
  vector<set<int>> al(26);
  rep(i, s.size()) al[s[i]-'a'].insert(i);
  rep(i, q) {
    int type;
    cin >> type;
    if(type == 1) {
      int pos;
      char c;
      cin >> pos >> c;
      pos--;
      if(s[pos] != c) {
        al[s[pos]-'a'].erase(pos);
        al[c-'a'].insert(pos);
        s[pos] = c;
      }
    }
    else {
      int res = 0;
      int l, r;
      cin >> l >> r;
      l--;r--;
      rep(j, al.size()) {
        set<int>::iterator it = al[j].lower_bound(l);
        if(it == al[j].end()) continue;
        if(*it <= r) res++; 
      }
      cout << res << endl;
    }
  }
  return 0;
}


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

int H, W;
vector<vector<int>> field(H, vector<int>(W));
vector<vector<bool>> seen(H, vector<bool>(W));

const int dh[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dw[8] = {0, 1, 0, -1, 1, -1, 1, -1};

void dfs(int h, int w)
{
    seen[h][w] = true;
    int nh, nw;
    for (int i=0; i<8; i++)
    {
        nh = h + dh[i];
        nw = w + dw[i];
        if (nh<0 || nh>=H || nw<0 || nw>=W) continue;
        if (seen[nh][nw]) continue;
        if (field[nh][nw]==0) continue;
        dfs(nh, nw);
    }
}

int main()
{
    while (cin >> W >> H)
    {
        if (W==0 || H==0) break;
        field.resize(H);
        seen.resize(H);
        for (int h=0; h<H; h++)
        {
            field[h].resize(W);
            seen[h].resize(W);
        }
        for (int h=0; h<H; h++)
        {
            for (int w=0; w<W; w++) 
            {
                cin >> field[h][w];
                seen[h][w]=false;
            }
        }
        int answer=0;
        for (int h=0; h<H; h++)
        {
            for (int w=0; w<W; w++)
            {
                if (seen[h][w]==false && field[h][w]==1) dfs(h, w), answer++;
            }
        }
        cout << answer << endl;
    }
}


Measured memory_bytes: 3248
n = int(input())
MX = 10**4
ans = [0]*(10**4+5)

for x in range(1,MX):
    now = x*x
    for y in range(1,MX):
        now2 = now + y*y
        if(now2>MX):
            break
        for z in range(1,MX):
            now3 = now2 + z*z + x*y + y*z + z*x
            if(now3>MX):
                break
            ans[now3]+=1

for i in range(1,n+1):
    print(ans[i])

Measured memory_bytes: 74520
/************************************************************
	> File Name: a.cpp
	> Author: TSwiftie
	> Mail: 2224273204@qq.com 
	> Created Time: Sun 17 May 2020 08:04:57 PM CST
************************************************************/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/rope>
#define lowbit(x) (x&-x)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lc (o<<1)
#define rc (o<<1|1)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<LL> vll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int INF = 0x3f3f3f3f;
const LL INF_ll = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-8;
signed main(void){
	int n;
	cin >> n;
	int di = n%10;
	if(di==3) cout << "bon\n";
	else if(di==0||di==1||di==6||di==8) cout << "pon\n";
	else cout << "hon\n";
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int x;
    cin >> x;
    bool f = (x == 7) || (x == 5) || (x == 3);
    cout << (f ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

using namespace std;
const static int M_MAX = 20;

int main() {
  int m, n;
  int cont[ M_MAX ] = { 0 };
  int maxN = -1;
  cin >> m >> n;
  for( int i = 0; i < m; i++ ) {
    for( int j = 0; j < n; j++ ) {
      int score;
      cin >> score;
      cont[ i ] += score;
    }
  }
  for( int i = 0; i < m; i++ ) {
    maxN = max( maxN, cont[ i ] );
  }
  cout << maxN << endl;

  return EXIT_SUCCESS;
}

Measured memory_bytes: 1164
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
//#define DEBUG
using namespace std;

int main(){
    int N;
    cin >> N;
    vector <int> H(N);
    for(int i = 0; i < N; i++){
        cin >> H.at(i);
    }
    int ans = 1;
    int max_h = H.at(0);
    for(int i = 1; i < N; i++){

        if(H.at(0) <= H.at(i) && H.at(i-1) <= H.at(i) && max_h <= H.at(i)){
            max_h = H.at(i);
            ans++;
        }
        
        
    }
    cout << ans << endl;
}

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

int main() {
	// your code goes here
	string s;
	cin>>s;
	int hasharr[256]={0};
	for(int i=0;i<s.size();i++){
		hasharr[s[i]]++;
	}
	int flag=0;
	for(int i=0;i<256;i++){
		if(hasharr[i]!=0&&hasharr[i]!=2){
			flag=1;
			break;
		}
	}
	if(flag)
	cout<<"No"<<endl;
	else
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = np.array([lr() for _ in range(N)])
A = AB[:, 0]
B = AB[:, 1]
me_A = np.median(A)
me_B = np.median(B)
if N&1:
    answer = int(me_B - me_A) + 1
else:
    answer = int((me_B - me_A) / 0.5) + 1

print(answer)


Measured memory_bytes: 66424
#include <stdio.h>

unsigned long fight(unsigned long hitpoint) {
    if( hitpoint == 1 ) {
        return 1;
    } else {
        return 2*fight(hitpoint/2)+1;
    }
}

int main(void) {
    unsigned long h;
    scanf("%lu", &h);

    printf("%lu\n", fight(h));
    return 0;
} 


Measured memory_bytes: 128
def c_dice_and_coin(N, K):
    ans = 0.0
    for i in range(1, N + 1):
        tmp = 1
        p = 0
        while i * tmp < K:
            tmp *= 2
            p += 1
        if p >= 50:
            continue
        ans += 1 / (2**p)
    ans /= N
    return ans

N, K = [int(i) for i in input().split()]
print(c_dice_and_coin(N, K))

Measured memory_bytes: 3060
x,n = map(int,input().split())
p = list(map(int,input().split()))

if n == 0:
    print(x)

else:
    i = 1
    while True:
        t = x-i
        s = x+i
        if x not in p:
            print(x)
            break
        if t not in p:
            print(t)
            break
        if s not in p:
            print(s)
            break
        i +=1

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

int main()
{
  string s;
  cin >> s;
  for( int i=1; i<s.size(); i++){
  	if( s[i]-'a' == s[i-1]-'a'){
    	cout << "Bad" << endl;
      	exit(0);
    }
  }
  cout << "Good" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define ll long long
#define F first
#define FF first.first
#define FS first.second
#define S second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e16;
 
ll n, q=1, m, e, a[N], f[N], c[N], o, k, t, x, y, z, u, h, mx, mn, ans, Ans;
pair<ll,ll> p[N];
string s[N];
vector<int> v[N];
 
main(){ios_base::sync_with_stdio(false), cin.tie(0);
   	
	cin>>x>>y>>z>>u;
	
	if((z+y-1)/y<=(x+u-1)/u){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
}

Measured memory_bytes: 58312
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string num,s;	// num:結果　s:色
  int N;		// n:個数
  
  cin >> N;
  num = "Three";
  for(int i=0; i<N ; i++){
    cin >> s;	//色入力
    if(s == "Y"){
      num = "Four";
    }
  }
  cout << num << endl;
}

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

int main()
{
    int a, b, c, x, y;
    long long ans = 0;
    cin >> a >> b >> c >> x >> y;

    while (2 * c + 1ll * a * max(x - 1, 0) + 1ll * b * max(y - 1, 0) < 1ll * a * x + 1ll * b * y) {
        ans += 2 * c;
        x = max(x - 1, 0);
        y = max(y - 1, 0);
    }

    cout << ans + 1ll * a * x + 1ll * b * y << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

const ll P = 1e9+7;
int N, K;
ll dfs(int u, int p, vector<vector<int>> &graph){
	int i=p<0?(K-1):(K-2);
	ll ret = 1;
	for(int v: graph[u]){
		if(v==p) continue;
		ret *= (dfs(v, u, graph) * i--) % P;
		ret %= P;
	}
	debug(any{u+1, ret});
	return ret;
}

int main(){
	cin >> N >> K;
	vector<int> A(N-1), B(N-1);
	vector<vector<int>> graph(N);
	for(int i=0; i<N-1; i++){
		cin >> A[i] >> B[i];
		graph[A[i]-1].push_back(B[i]-1);
		graph[B[i]-1].push_back(A[i]-1);
	}

	cout << K * dfs(0, -1, graph) % P << endl;

	return 0;
}


Measured memory_bytes: 15872