akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

void encode(char *p, int n ){
	for(;*p!='\0';p++){ 
		if('A'<=*p&&*p<='Z'){
			*p = (*p-'A'+n)%('Z'-'A'+1)+'A';
		} else if ('a'<=*p&&*p<='z') {
			*p = (*p-'a'+n)%('z'-'a'+1)+'a';
		}
	}
}

int main(void){
	char str[1024];
	int n=23;
	scanf("%s",str);
	//scanf("%d",&n);
	encode(str,n);
	printf("%s\n",str);
return 0;
}

Measured memory_bytes: 0
import sys

class Node():
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left, self.right = None, None
        
    def __str__(self):
        return " " + str(self.key)

def insert(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == None:
        root = Node(z)
    elif z < y.key:
        y.left = Node(z)
    else:
        y.right = Node(z)
        
def find(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        elif z > x.key:
            x = x.right
        else:
            print("yes")
            return
    print("no")
        
def preorder(x):
    return str(x) + preorder(x.left) + preorder(x.right) if x else ""

def inorder(x):
    return inorder(x.left) + str(x) + inorder(x.right) if x else ""
        
input()
root = None
for s in sys.stdin:
    if s[0] == "p":
        print(inorder(root))
        print(preorder(root))
    elif s[0] == "f":
        find(int(s[5:]))
    else:
        insert(int(s[7:]))


Measured memory_bytes: 55688
X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, list(input().split()))), reverse=True)
Q = sorted(list(map(int, list(input().split()))), reverse=True)
R = sorted(list(map(int, list(input().split()))), reverse=True)

toEat = P[:X] + Q[:Y]
toEat.sort()

for i in range(min(X + Y, len(R))):
    if R[i] > toEat[i]:
        toEat[i] = R[i]
    else:
        break

print(sum(toEat))

Measured memory_bytes: 23464
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long; using P = pair<int,int>;
using vl = vector<ll>; using vvl = vector<vl>;
#define mp make_pair
#define pb push_back
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for (int i=(n-1);i >= 0;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)((v).size())
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
#define Sort(v) sort(all(v))
#define Rev(v) reverse(all(v))
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << H << " ";
    debug_out(T...);
}
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
    for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
    return os;
}
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
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;}
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const int dx[8] = {1,0,-1,0,1,1,-1,-1}; const int dy[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n,x,m;
    cin >> n >> x >> m;
    vector<ll> cnt(m);
    vector<ll> a;
    while(1) {
        if(cnt[x] > 1 || a.size() >= n) break;
        cnt[x]++;
        a.push_back(x);
        x = x*x%m;
    }
    ll ans = 0;
    if(a.size() >= n) {
        for(auto v : a) ans += v;
        cout << ans << endl;
        return 0;
    }
    auto itr = find(a.begin(), a.end(), x);
    ll idx = distance(a.begin(), itr);
    ll loop = 0;
    for(ll i = 0;i < a.size();i++) {
        if(i < idx) ans += a[i];
        else loop += a[i];
    }
    ll cycle = a.size() - idx;
    ans += (n-idx)/cycle * loop;
    for(ll i = 0;i < (n-idx)%cycle;i++) {
        ans += a[idx+i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5052
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 200005

int N;
int A[SIZE];
int table[SIZE];


int main(){

	scanf("%d",&N);
	for(int i = 1; i <= N; i++){

		scanf("%d",&A[i]);
	}
	for(int i = 1; i <= N; i++){

		table[i] = 0;
	}

	int num = 0;
	stack<int> S;

	for(int i = N; i >= 1; i--){

		int sum = 0;
		for(int k = 2*i; k <= N; k += i){

			sum += table[k];
		}
		if(sum%2 == A[i]){

			//Do noghint
		}else{
			num++;
			table[i] = 1;
			S.push(i);
		}
	}

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

	if(num == 0){
		return 0;
	}

	printf("%d",S.top());
	S.pop();

	while(!S.empty()){

		printf(" %d",S.top());
		S.pop();
	}
	printf("\n");

	return 0;
}


Measured memory_bytes: 3072
#!/usr/bin/env python3

import decimal


BTC2JPY = 380000


def main():
    n = int(input())
    s = 0
    for _ in range(n):
        x0, u = input().split()
        x = decimal.Decimal(x0)
        if u == "BTC":
            x *= BTC2JPY
        s += x
    print(s)


if __name__ == "__main__":
    main()

Measured memory_bytes: 5588
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>(b);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n-1,-1)

int main(void) {
	auto start = chrono::system_clock::now();
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, a, b;
	cin >> n >> m;
	vector<P> v;
	vector<int> cnt(n);
	vector<set<int>> gr(n);
	REP(i, m) {
		cin >> a >> b;
		a--;
		b--;
		v.push_back(P(a, b));
		gr[a].insert(b);
		cnt[a]++;
	}
	vector<double> es(n);
	RREP(i, n - 1) {
		for (auto j : gr[i]) es[i] += 1 + es[j];
		es[i] /= cnt[i];
	}
	vector<double> maxval(n);
	vector<int> cand(n);
	REP(i, n) cand[i] = -1;
	REP(i, m) {
		a = v[i].first;
		b = v[i].second;
		if (maxval[a] < es[b]) {
			maxval[a] = es[b];
			cand[a] = i;
		}
	}
	random_shuffle(cand.begin(), cand.end());
	double res = es[0];
	vector<double> es2(n);
	for (int skip : cand) {
		if (skip == -1) continue;
		a = v[skip].first;
		b = v[skip].second;
		if (cnt[a] == 1) continue;
		gr[a].erase(b);
		cnt[a]--;
		FOR(i, a + 1, n) es2[i] = es[i];
		RFOR(i, a, -1) {
			es2[i] = 0;
			for (auto j : gr[i]) es2[i] += 1 + es2[j];
			es2[i] /= cnt[i];
		}
		res = min(res, es2[0]);
		gr[a].insert(b);
		cnt[a]++;
		if (chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() > 1980) break;
	}
	cout << fixed << setprecision(10) << res;
	return 0;
}

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

int A, B, C, D, E, F;

int main()
{
    cin >> A >> B >> C >> D >> E >> F;

    int maxW = A, maxS = 0;
    for (int a = 0; a * A <= F / 100; a++)
    {
        for (int b = 0; a * A + b * B <= F / 100; b++)
        {
            int water = a * A + b * B;
            int s_max = min(E * water, F - water * 100);
            int tmp = 0;
            for (int c = 0; c * C <= s_max; c++)
            {
                for (int d = 0; d * D + c * C <= s_max; d++)
                {
                    tmp = max(tmp, c * C + d * D);
                }
            }
            if (maxS * water < tmp * maxW)
            {
                maxW = water;
                maxS = tmp;
            }
        }
    }
    cout << maxW * 100 + maxS << " " << maxS << endl;
}


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

ll K;
bool isOK_n(ll trial,vl &p,vl &m) {
    ll num=0;
    ll ps=p.size(),ms=m.size();
    int pi=0,mi=ms-1;
    while(pi<ps&&mi>=0){
        if(p[pi]*m[mi]<=trial){
            num+=mi+1;
            pi++;
        }else mi--;
    }
    if (num>=K) return true;
    else return false;
}
ll less_num(ll trial,vl &vec){
    ll num=0;
    ll vs=vec.size();
    if(vs<2)return 0;
    int l=0,r=vs-1;
    while(l<vs-1){
        if(r==l)break;
        if(vec[l]*vec[r]<=trial){
            num+=r-l;
            l++;
        }else r--;
    }
    return num;
}
bool isOK_p(ll trial,vl &p,vl &m){
    if(less_num(trial,p)+less_num(trial,m)>=K)return true;
    else return false;
}
int main() {
    ll N; cin>>N>>K;
    vl p,m;
    ll zero=0;
    for (int i = 0; i < N; i++){
        int A; cin>>A;
        if(A>0)p.push_back(A);
        else if(A<0)m.push_back(A);
        else zero++;
    }
    ll ps=p.size(),ms=m.size();
    if(K<=ps*ms){
        sort(p.begin(),p.end(),greater<ll>());
        sort(m.begin(),m.end());
        ll ng=p[0]*m[0]-1;
        ll ok=p[ps-1]*m[ms-1]+1;
        while (abs(ok - ng) > 1) {
            ll mid = (ok + ng) / 2;
            if (isOK_n(mid,p,m)) ok = mid;
            else ng = mid;
        }
        cout<<ok<<endl;
    }else if(K<=ps*ms+(ps+ms)*zero+zero*(zero-1)/2){
        cout<<0<<endl;
    }else{
        K-=ps*ms+(ps+ms)*zero+zero*(zero-1)/2;
        sort(p.begin(),p.end());
        sort(m.begin(),m.end(),greater<ll>());
        ll ng=0,ok=0;
        if(ps>=2){
            ng=p[0]*p[1]-1;
            ok=p[ps-1]*p[ps-2]+1;
        }
        if(ms>=2){
            ng=min(ng,m[0]*m[1]-1);
            ok=max(ok,m[ms-1]*m[ms-2]+1);
        }
        while (abs(ok - ng) > 1) {
            ll mid = (ok + ng) / 2;
            if (isOK_p(mid,p,m)) ok = mid;
            else ng = mid;
        }
        cout<<ok<<endl;
    }
}

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

typedef long long ll;

ll N;

int main() {
    cin >> N;
    vector<ll> x(N), y(N), h(N);

    rep(i, N) cin >> x[i] >> y[i] >> h[i];


    for (ll i = 0; i <= 100; i++) {
        for (ll j = 0; j <= 100; j++) {

            ll tmp = -1;
            for (ll k = 0; k <= N - 1; k++) {
                if (h[k] <= 0) continue;

                ll tmp_h = abs(x[k] - i) + abs(y[k] - j) + h[k]; 
                if (tmp == -1) {
                    tmp = tmp_h;
                } else if (tmp != tmp_h) {
                    tmp = -2;
                    break;
                }
            }

            if (tmp == -2) continue;

            // 0のケース
            for (ll k = 0; k <= N - 1; k++) {
                if (h[k] > 0) continue;
                ll dist = max(tmp - abs(i - x[k]) - abs(j - y[k]), 0LL);
                if (dist != 0) {
                    tmp = -2;
                    break;
                }
            }

            if (tmp == -2) continue;

            printf("%lld %lld %lld\n", i, j, tmp);
        }
    }
}

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

int main()
{
    int H, W;
    int dist[15][15] = {};

    cin >> H >> W;
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            cin >> dist[i][j];
        }
    }
    for(int k = 0; k < 10; k++) {
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            int A;
            cin >> A;
            if(A != -1) {
                sum += dist[A][1];
            }
        }
    }

    cout << sum << endl;

    return (0);
}

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

int main(void) {

	int n, m;

	std::cin >> n >> m;

	if (n == 0) {
		if (m == 100) {
			std::cout << 101 << std::endl;
		}
		else {
			std::cout << m << std::endl;
		}
	}
	else {
		int ans = 100;

		if (n == 2) {
			ans *= 100;
		}

		ans *= m;
		if (m == 100) {
			if (n == 1) {
				ans += 100;
			}
			else {
				ans += 10000;
			}
		}
		std::cout << ans << std::endl;
	}

	return 0;
}

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



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

    double prex;

    double prea,preb;
    int inta,intb;
    double iprea,ipreb;

    prea = n/1.08;
    preb = (n+1)/1.08;

    inta = (int)prea;
    intb = (int)preb;
    
    iprea = prea -inta;
    ipreb = preb -intb;


    if(iprea ==0){
        cout << inta << endl;
        return 0;
    }else{
        if(inta == intb){
            cout << ":(" << endl;
            return 0;
        }else if(ipreb ==0){
            cout << ":(" << endl;
            return 0; 
        }else{
            cout << intb << endl;
            return 0;
        }
    }
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int h,w;
vector<vector<char>> vec;
vector<pair<int,int>> s;

vector<vector<int>> bfs() {
    vector<vector<int>> d(h,vector<int>(w,INF));
    queue <pair<int,int>> q;
    
    for(auto p:s){
        int sy,sx;
        tie(sy,sx)=p;
        q.push(make_pair(sy,sx));
        d[sy][sx]=0;
    }
    
    while(!(q.empty())) {
        pair<int,int> now=q.front(); q.pop();
        
        rep(i,4) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            
            if(0<=ny && ny<h && 0<=nx && nx<w && vec[ny][nx]!='#' && d[ny][nx]==INF) {
                q.push(pair<int,int> (ny,nx));
                d[ny][nx] = d[now.first][now.second] + 1;
            }
        }
    }
    
    return d;
}

int main(){
    cin>>h>>w;
    vec.resize(h);
    rep(i,h){
        vec[i].resize(w);
        rep(j,w){
            cin>>vec[i][j];
            if(vec[i][j]=='#') s.emplace_back(i,j);
        }
    }
    
    auto d=bfs();
    
    int ans=0;
    rep(i,h) rep(j,w) ans=max(ans,d[i][j]);
    cout<<ans<<endl;
}


Measured memory_bytes: 21244
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1000000000
#define  pow(x) pow(10,(x)) 
typedef long long int LL;
const int MOD = 1000000007;
//sort(all(x))とするとソートできるよ

int main(){
    int N;cin >> N;
    vector<LL> H(N);
    rep(i,N){
        cin >> H[i];
    }
    LL ma;
    ma = H[0];
    bool res = true;
    rep(j,N){
        ma = max(ma,H[j]);
        if(ma - 2 >= H[j])res = false;
    }
    if(res){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 1024
n=int(input())
dp=[10**10]*(n+1)
dp[0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]+1
  x=0
  while 9**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-9**x]+1)
  x=0
  while 6**(x+1)<=i:
    x+=1
  dp[i]=min(dp[i],dp[i-6**x]+1)
print(dp[n])
  
    
    


Measured memory_bytes: 42732
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000;
const int MOD = (int)1e9 + 7;
template <class T>
inline T in()
{
    T x;
    cin >> x;
    return x;
}

signed main()
{
    string s = in<string>();
    string a = s.substr(0, 2);
    string b = s.substr(2, 2);
    bool fa = 1 <= stoi(a) && stoi(a) <= 12;
    bool fb = 1 <= stoi(b) && stoi(b) <= 12;
    if (fa && fb)
    {
        cout << "AMBIGUOUS" << "\n";
    }
    else if (fa)
    {
        cout << "MMYY" << "\n";
    }
    else if (fb)
    {
        cout << "YYMM" << "\n";
    }
    else
    {
        cout << "NA" << "\n";
    }
    
}

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

int r[101][101];
int d[101], f[101], num, visit[101], p=0;

void dfs(int n){
    if(!visit[n]){
        visit[n]++;
        d[n] = ++p;
        for(int i=1; i<num+1; i++)
            if(r[n][i]) dfs(i);
        f[n] = ++p;
    }
}

int main(void){
    int u, k, v;
    cin >> num;
    for(int i=0; i<num; i++){
        cin >> u >> k;
        for(int j=0; j<k; j++){
            cin >> v;
            r[u][v]++;
        }
    }
    for(int i=1; i<num+1; i++){
        if(!visit[i]) dfs(i);
    }
    for(int i=1; i<num+1; i++)
        cout << i << " " << d[i] << " " << f[i] << endl;
}



Measured memory_bytes: 3136
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val (n, k) = readIntegerList()
    val aList = readLongList().sorted()

    val mod = 1000000007L
    val combination = Combination(n, mod)

    var minSum = 0L
    for ((i, a) in aList.dropLast(k - 1).withIndex()) {
        val right = n - i - 1
        val comb = combination.value(right, k - 1)
        minSum = (minSum + ((a * comb) % mod)) % mod
    }

    var maxSum = 0L
    for ((i, a) in aList.drop(k - 1).withIndex()) {
        val left = k - 1 + i
        val comb = combination.value(left, k - 1)
        maxSum = (maxSum + ((a * comb) % mod)) % mod
    }

    var ans = (maxSum  - minSum) % mod
    if (ans < 0) {
        ans += mod
    }
    out.println(ans)
}

/** n <= 20000000
 * MODは素数（フェルマーの小定理を利用するため）
 */
class Combination(n: Int = 20000000, val MOD: Long = 1000000007L) {
    val fact = LongArray(n + 1)
    val ifact = LongArray(n + 1)

    /** O(n) */
    init {
        fact[0] = 1L
        for (i in 1..n) { fact[i] = (fact[i - 1] * i) % MOD }
        ifact[n] = inverse(fact[n], MOD)
        for (i in n downTo 1) { ifact[i - 1] = (ifact[i] * i) % MOD }
    }

    /** O(1) */
    fun value(n: Int, k: Int) = if (k < 0 || k > n) 0 else (((fact[n] * ifact[k]) % MOD) * ifact[n-k]) % MOD

    /** O(log(m)) */
    fun pow(n: Long, m: Long, MOD: Long): Long {
        var ret = 1L
        var x = n
        var k = m
        while (k > 0) {
            if ((k and 1L) == 1L) { ret = (ret * x) % MOD }
            x = (x * x) % MOD
            k = k shr 1
        }
        return ret
    }

    /** O(log(MOD)) */
    fun inverse(n: Long, MOD: Long) = pow(n, MOD - 2L, MOD)
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 64952
#include<bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define ll long long
const int MAX=1e5+8;
using namespace std;

int main() 
{ 
//	#ifndef ONLINE_JUDGE
//	freopen("inp.txt" ,"r",stdin);
//	freopen("out.txt", "w", stdout);
//	#endif
	int mat[4][4];
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++)
			cin>>mat[i][j];
	}
	int hash[200];
	int n;
	cin>>n;
	memset(hash , 0 , sizeof(hash));
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		hash[a]=1;
	}
	int f=0;
	for(int i=1;i<=3;i++){
		if(hash[mat[i][1]]&&hash[mat[i][2]]&&hash[mat[i][3]])
			f=1;
	}
	for(int j=1;j<=3;j++){
		if(hash[mat[1][j]]&&hash[mat[2][j]]&&hash[mat[3][j]])
			f=1;
	}
	if(hash[mat[1][1]]&&hash[mat[2][2]]&&hash[mat[3][3]])
		f=1;
	if(hash[mat[1][3]]&&hash[mat[2][2]]&&hash[mat[3][1]])
		f=1;
	if(f)
		cout<<"Yes";
	else
		cout<<"No";
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

int N,M;
int boss[SIZE],height[SIZE];

//自分のボスのindexを取得しつつ、経路圧縮を行う関数
int get_boss(int id){
	if(boss[id] == id)return id; //自分が代表なら、自分の値を返す
	else{
		return boss[id] = get_boss(boss[id]); //代表でないなら、自分が所属する組織の代表を返しつつ、経路圧縮
	}
}


void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	//既に同じグループなら何もしない
	if(boss_x == boss_y)return;

	//高さが高い方に吸収する
	if(height[boss_x] > height[boss_y]){

		boss[boss_y] = boss_x;

	}else if(height[boss_x] < height[boss_y]){

		boss[boss_x] = boss_y;

	}else{ //height[boss_x] == height[boss_y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

int main(){

	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++){

		boss[i] = i;
		height[i] = 0;
	}

	int a,b,z;

	for(int i = 0; i < M; i++){

		scanf("%d %d %d",&a,&b,&z);
		a--;
		b--;

		unite(a,b);
	}

	int ans = 0;
	for(int i = 0; i < N; i++){

		if(get_boss(i) == i){
			ans++;
		}
	}

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

	return 0;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		int K = sc.nextInt();
		char key = S.charAt(K-1);
		StringBuilder ans = new StringBuilder();
		for(int i = 0; i < N; i++) {
			if(S.charAt(i) == key)
				ans.append(key);
			else
				ans.append("*");
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 21844
import java.util.*;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    boolean q = true;

    for (int i = 1 ; i < 10 ; i++ ) {
      if (n%i==0 && n/i < 10) {
        q = false;
        break;
      } else {
        continue;
      }
    }

    if (q == false) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }
}


Measured memory_bytes: 22228
l=[[[0 for i in range(10)] for i in range(3)] for i in range(4)]
n=int(input())
for i in range(n):
    a,b,c,d=input().split()
    l[int(a)-1][int(b)-1][int(c)-1]+=int(d)
for i in range(120):
    print('',l[i//30][i%30//10][i%10],end='')
    if (i+1)%10==0:print()
    if (i+1)%30==0 and i!=119:print('#'*20)


Measured memory_bytes: 5632
n,k = map(int, input().split())
al = list(map(int, input().split()))

bit_cnts = [0]*41
for a in al:
    for i in range(41):
        if a&(1<<i) > 0:
            bit_cnts[i] += 1


dp_same = [-1]*42
dp_small = [-1]*42
dp_small[41] = -1
dp_same[41] = -1
for i in range(41,0,-1):
    curr_bit = i-1
    kbit = 0
    if k&(1<<curr_bit) > 0: kbit = 1
    if kbit == 0:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*bit_cnts[curr_bit]
        # dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*bit_cnts[curr_bit]
        if dp_small[i] > -1:
            dp_small[i-1] = dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))
    else:
        dp_same[i-1] = dp_same[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit])
        dp_small[i-1] = max(0, dp_same[i]+pow(2,curr_bit)*(bit_cnts[curr_bit]))
        if dp_small[i] > -1:
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(n-bit_cnts[curr_bit]))
            dp_small[i-1] = max(dp_small[i-1], dp_small[i] + pow(2,curr_bit)*(bit_cnts[curr_bit]))


ans = max(dp_same[0],dp_small[0])
print(ans+1)

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

int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<int>> pic(h+2,vector<int>(w+2));
  for (int i=0; i<h+2; i++){
    for (int j=0; j<w+2; j++){
      if(i==0 or i==h+1 or j==0 or j==w+1){
        pic[i][j]=0;
      }
      else{
        char p;
        cin >>p;
        if (p=='.') pic[i][j]=0;
        else if (p=='#') pic[i][j]=1;
        else cout << "err" << endl;
      }
    }
  }
  bool f = 1;
  for(int i=1; i<h+1; i++){
    for (int j=1; j<w+1; j++){
      if(pic[i][j]==1 and pic[i][j]+pic[i-1][j]+pic[i+1][j]+pic[i][j-1]+pic[i][j+1]==1){
        f=0;
        break;
      }
    }
    if (f==0) break;
  }        
  cout <<(f ?"Yes":"No") << endl;
}

Measured memory_bytes: 256
fold -1|awk '++C[S[NR]=a=/R/+2*/G/+4*/B/]*a{for(i=0;i++<NR/2;)m+=7==S[NR-i]+S[NR-i*2]+a;}END{printf "%.f",C[1]*C[2]*C[4]-m;}'

Measured memory_bytes: 4572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<class U, class V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}

const int MAXN = 3000;
int N, T;
pii dish[MAXN];
int cache[MAXN][MAXN + 1];

int happiness(int n, int r) {
    if(n >= N || r <= 0) return 0;
    int &ret = cache[n][r];
    if(ret != -1) return ret;
    return ret = max(happiness(n + 1, r), happiness(n + 1, r - dish[n].first) + dish[n].second);
}

int main() {
    cin >> N >> T;
    rep(i, N) cin >> dish[i].first >> dish[i].second;
    sort(dish, dish + N, [](const pii &a, const pii &b) {
        if(a.first == b.first) {
            return a.second > b.second;
        }
        return a.first < b.first;
    });
    memset(cache, -1, sizeof(cache));
    cout << happiness(0, T) << "\n";
    // rep(i, N) cout << dish[i] << "\n";
}

Measured memory_bytes: 35584
n = int(input())
m = int(input())
lines = [list(map(int, input().split())) for _ in range(n)]
# print(lines)
subs = [m]
adds = m

for i, line in enumerate(lines):
    adds += line[0] - line[1]
    # print(adds)
    if adds < 0:
        adds = 0
        break
    else:
        subs.append(adds)

if adds == 0:
    print(adds)
else:
    print(max(subs))
# print(subs)
# adds = 0
# for i in range(len(subs)):
#     adds += subs[i]
#     if adds < 0:
#         answer = 0
#         break
#     else:
#         answer = adds
# print(answer)



Measured memory_bytes: 6984
#include<bits/stdc++.h>
 
using namespace std;
 
int n;
string s, c;
 
int main () {
    cin >> n;
    cout << 0 << '\n';
    cout.flush();
    cin >>s;
    if(s == "Vacant") {
        cout << 0 << '\n';
        fflush(stdout);
    }
    else {
        int l = 1, r = n - 1;
        while(l < r) {
            int mid = l + r >> 1;
            cout << mid << '\n';
            fflush(stdout);
            cin >> c;
            if(c == "Vacant") {
                cout << mid << '\n';
                fflush(stdout);
                return 0;
            }
            string rem;
            if(mid % 2 == 0) rem = s;
            else {
                if(s == "Male") rem = "Female";
                else rem = "Male";
            }
            if(c == rem) l = mid + 1;
            else r = mid;
        }
        cout << l << '\n';
        fflush(stdout);
    }
}

Measured memory_bytes: 852
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define int long long
using namespace std;
using P=pair<int,int>;
using Graph=vector<vector<int>>;
using ll=long long;


ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
bool root(string s){
    int n=s.length();
    if(n==2){
        if(s[0]==s[1]){
            return true;
        }
        else return false;
    }
    if(n==3){
        if(s[0]==s[2]){
            return true;
        }
        else return false;
    }
 
    return false;
}
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

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

    // 素数である
    return true;
}

//深さ優先
vector<int> seen;
vector<ll> h;
 
//普通の深さ優先探索seenを返す感じ
void dfs(const Graph &G,int v){

    seen[v] = 0; //v探索済み
 
    P good=make_pair(v,h[v]);
    for(auto next_v :G[v]){
        if(seen[next_v]!=-1) continue;//もう探索していた
        if(h[next_v]>good.second){
            good=make_pair(next_v,h[next_v]);
        }
        dfs(G,next_v);
    }
 
    if(!(h[v]==good.second && v==good.first)){
        seen[good.first]=1;
    }
}


int n;

void dfs(string s, char mx){
    if(s.length()==n){
        cout<<s<<endl;
    }else{
        for(char c='a';c<=mx;c++){
            dfs(s+c,((c==mx) ? (char)(mx+1) : mx));
        }
    }
}

const long double PI=3.14159265358979323846;
signed main(){ 
    int a,b,h,m;
    cin>>a>>b>>h>>m;
    pair<long double,long double> A;
    pair<long double,long double> B;

    long double radA=2*PI/720;
    long double radB=2*PI/60;

    A=make_pair(a*cos(radA*(h*60+m)),a*sin(radA*(h*60+m)));
    B=make_pair(b*cos(radB*m),b*sin(radB*m));

    long double dis;
    dis=pow(pow(A.first-B.first,2)+pow(A.second-B.second,2),0.5);
    
    cout<<fixed<<setprecision(12);
    cout<<dis<<endl;
}  

Measured memory_bytes: 4188
//made by Sert
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int)1e9 + 34;
const int N = (int)3e5 + 34;
const int M = (int)1e4 + 34;

void solve() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i] -= i + 1;
    }
    sort(a.begin(), a.end());
    int kek = a[n / 2];
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - kek);
    }
    cout << ans << "\n";
}

int main() {
#ifdef MADE_BY_SERT
    freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    solve();
    solve();
    solve();
#endif
    solve();
    return 0;
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


int main(){
    int N, M; cin >> N >> M;
    cout << N*(N-1) / 2 + M*(M-1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int a,b,c,i;
	scanf("%d %d %d",&a ,&b ,&c);
	if(a>b){
		i=a;
		a=b;
		b=i;
	}
	if(b>c){
		i=b;
		b=c;
		c=i;
	}
	if(a>b){
		i=a;
		a=b;
		b=i;
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
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; }
const ll MOD = 1e9+7;

int main(){
    int M;
    cin >> M;
    ll K;
    cin >> K;

    ll lim = (1LL << M);
    if(lim <= K){
        cout << -1 << endl;
        return 0;
    }

    if(K == 0){
        for(int i = 0; i < lim; i++){
            printf("%d ", i);
        }
        for(int i = lim-1; i >= 0; i--){
            printf("%d ", i);
        }
        printf("\n");
        return 0;
    }

    ll x = 0;
    for(int i = 0; i < lim; i++){
        if(i == K) continue;
        x ^= i;
    }

    if(x != K){
        cout << -1 << endl;
        return 0;
    }

    vector<ll> ans;
    ans.push_back(K);
    for(int i = 0; i < lim; i++){
        if(i == K) continue;
        ans.push_back(i);
    }
    ans.push_back(K);
    for(int i = lim-1; i >= 0; i--){
        if(i == K) continue;
        ans.push_back(i);
    }

    REP(i, ans.size()){
        printf("%lld ", ans[i]);
    }
    printf("\n");
    return 0;
}


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

using namespace std;


template<typename T>
class UF
{
public:
	UF() {
		size = 0;
	}

	//値を挿入する
	void push( T a ) {
		M[a] = size;
		V.push_back( size );
		rank.push_back( 0 );
		C.push_back( 1 );
		size++;
	}

	//同じグループにする
	void unite( T a, T b ) {
		long long int x = find( M[a] );
		long long int y = find( M[b] );
		if( x == y )return;
		if( rank[x] < rank[y] ) {
			V[x] = y;
			C[y] += C[x];
		} else {
			V[y] = x;
			C[x] += C[y];
			if( rank[x] == rank[y] )rank[x]++;
		}
	}

	void merge( T a, T b ) {
		unite( a, b );
	}

	//同じグループにいるかどうか判定する
	bool same( T a, T b ) {
		return find( M[a] ) == find( M[b] );
	}

	//今何グループあるか数を返す
	long long int group() {
		set<long long int >S;
		for( long long int i = 0; i < V.size(); i++ ) {
			S.insert( find( V[i] ) );
		}
		return S.size();
	}

	//グループに属している数を返す
	long long int count( T a ) {
		return C[find( M[a] )];
	}

private:
	vector<long long int>
		C, V, rank;
	map < T, long long int>M;
	long long int size;

	//祖先までたどる
	long long int find( long long int x ) {
		if( V[x] == x )return x;
		else return V[x] = find( V[x] );
	}
};



int main() {
	UF<long long int>uf;
	long long int N, M;
	cin >> N >> M;
	for( size_t i = 0; i < N + M; i++ ) {
		uf.push( i );
	}
	for( size_t i = 0; i < N; i++ ) {
		long long int K;
		cin >> K;
		for( size_t j = 0; j < K; j++ ) {
			long long int L;
			cin >> L;
			L--;
			uf.merge( i, L + N );
		}
	}
	bool f = true;
	for( size_t i = 1; i < N; i++ ) {
		f = f&&uf.same( 0, i );
	}
	cout << (f ? "YES" : "NO") << endl;
}

Measured memory_bytes: 17492
#include<stdio.h>
#include<string.h>

void myans(char ans[]);
int hantei(char str[],int n);

char table[100][5];

int main(void){
    int limit=50,i;
    
    char str[3],myret[5],ans[5]="a";
    for(i=0;i<50;i++){
        myans(ans);/*??????*/
        strcpy(table[2*i],ans); //?????¶??????
        scanf("%s", str);
        strcpy(table[2*i+1],str); //?????????
        /*????????????????????????*/
        if(hantei(str,2*i+1) || str[0]!=ans[strlen(ans)-1]) break;/*???????????±?????????????????????*/
        myret[0]=str[strlen(str)-1];
        myret[1]='a'+(i/26);
        myret[2]='a'+(i%26);
        myret[3]='a';
        strcpy(ans,myret);
    }
    puts("!OUT");
    fflush(stdout);
    return 0;
}

void myans(char ans[]){
    printf("?%s\n",ans);
    fflush(stdout);
}

int hantei(char str[],int n){
    int i;
    for(i=0;i<n;i++){
        if (!strcmp(table[i],str)) return 1;
    }
    return 0;
}

Measured memory_bytes: 1264
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;
const int MAXM=100000;

int n,m;
int ghead[MAXN],gnxt[2*MAXM],gto[2*MAXM];

bool done[MAXN];
int col[MAXN];
int q[MAXN],qhead,qtail;
int cnt[3],haven,havem;
ll process(int s) {
	qhead=qtail=0; cnt[0]=cnt[1]=cnt[2]=haven=havem=0; done[s]=true,col[s]=0,q[qhead++]=s,++cnt[0];
	bool ok=true;
	while(qtail<qhead) {
		int at=q[qtail++]; ++haven;
		for(int x=ghead[at];x!=-1;x=gnxt[x]) {
			++havem;
			int to=gto[x];
			if(ok) {
				int want=(col[at]+1+x%2)%3;
				if(col[to]==-1) col[to]=want,++cnt[want]; else if(col[to]!=want) ok=false;
			}
			if(!done[to]) done[to]=true,q[qhead++]=to;
		}
	}
	//printf("%d ok=%d haven=%d havem=%d cnt=%d %d %d\n",s,ok?1:0,haven,havem,cnt[0],cnt[1],cnt[2]);
	if(!ok) return (ll)haven*haven;
	if(cnt[0]==0||cnt[1]==0||cnt[2]==0) return havem/2;
	return (ll)cnt[0]*cnt[1]+(ll)cnt[1]*cnt[2]+(ll)cnt[2]*cnt[0];
}

void run() {
	scanf("%d%d",&n,&m); REP(i,n) ghead[i]=-1,done[i]=false,col[i]=-1;
	REP(i,m) {
		int a,b; scanf("%d%d",&a,&b); --a,--b;
		gnxt[2*i+0]=ghead[a],ghead[a]=2*i+0,gto[2*i+0]=b;
		gnxt[2*i+1]=ghead[b],ghead[b]=2*i+1,gto[2*i+1]=a;
	}
	ll ret=0;
	REP(i,n) if(!done[i]) ret+=process(i);
	printf("%lld\n",ret);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>
int main(void){
  int n,i,j;
  double p[2999],dp[2999][3000],ans=0;
  scanf("%d",&n);
  for (i=0;i<n;i++) scanf("%lf",&p[i]);
  dp[0][0]=1-p[0];
  dp[0][1]=p[0];
  for (i=1;i<n;i++){
    for (j=0;j<=i+1;j++){
      if (j==0) dp[i][0]=dp[i-1][0]*(1-p[i]);
      else if (j==i+1) dp[i][i+1]=dp[i-1][i]*p[i];
      else dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
    }
  }
  for (j=(n+1)/2;j<=n;j++) ans+=dp[n-1][j];
  printf("%.12lf\n",ans);
  return 0;
}

Measured memory_bytes: 70400
require 'matrix'

class Array
	def accum
		inject([0]){|a, x| a + [a[-1] + x]}
	end

	def accum!
		(1..size-1).each{|i|
			self[i] += self[i-1]
		}
		self.unshift(0)
	end

	def accum_2d
		ac = map{|r| r.accum}
		(1..size-1).each{|i|
			(1..ac[0].size-1).each{|j|
				ac[i][j] += ac[i-1][j]
			}
		}
		ac.unshift([0] * ac[0].size)
		ac
	end

	def accum_2d!
		each{|r| r.accum!}
		(1..size-1).each{|i|
			(1..self[0].size-1).each{|j|
				self[i][j] += self[i-1][j]
			}
		}
		unshift([0] * self[0].size)
	end
		
	def bsearch_first_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_first_index(l, c-1, &pred) || c
		else
			bsearch_first_index(c+1, r, &pred)
		end
	end

	def bsearch_first_item(l = 0, r = size - 1, &pred)
		i = bsearch_first_index(l, r, &pred)
		i ? self[i] : nil
	end

	def bsearch_last_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_last_index(c+1, r, &pred) || c
		else
			bsearch_last_index(l, c-1, &pred)
		end
	end

	def bsearch_last_item(l = 0, r = size - 1, &pred)
		i = bsearch_last_index(l, r, &pred)
		i ? self[i] : nil
	end
end

class Matrix
	def []=(i, j, x)
		@rows[i][j] = x	
	end

	def %(mod)
		map{|x| x % mod}
	end
end

def exp(n, k, mod = nil)
	x = 1	
	r = n
	while k > 0
		x *= r if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
end

MOD = 1_000_000_009

start = Time.new
loop.with_index {|_, itr|
	#break if itr > 20
	w, h, n = gets.split.map &:to_i
	break if w == 0
	obs = (1..n).map{ gets.split.map &:to_i }
	obs.sort_by!(&:last)
	obs.shift while obs[0] && obs[0][1] == 1

	a = Matrix.build(w, w){|i, j|
		(0 <= j && j < w && i-1 <= j && j <= i+1) ? 1 : 0
	}

	mats = []
	memo = []
	
	prev_y = 1
	until obs.empty?
		x, y = obs.shift
		if y - prev_y > 1
			k = y - prev_y
		#	l, m = memo.bsearch_last_item{|l, m| l <= k-1}
		#	if l
		#		mats << m * exp(a, k-1-l, MOD)
		#	else
		#		mats << exp(a, k-1, MOD)
		#	end
		#	memo << [k-1, mats[-1]]
		#	memo.sort_by(&:first)
			mats << k-1
		end

		xs = [x]
		while obs[0] && obs[0][1] == y
			xs << obs.shift[0]
		end
		b = Marshal.load(Marshal.dump(a))
		xs.each{|x|
			b[x-2, x-1] = 0 if x-2 >= 0
			b[x-1, x-1] = 0
			b[x, x-1] = 0 if x <= w-1 
		}
		mats << b
		
		prev_y = y
	end	

	if prev_y < h
		mats << h-prev_y
	end

	v = [0] * w
	v[0] = 1
	
	t = mats.count{|x| x.class != Matrix}
	last_m = 1
	last_k = 0
	t.times {
		i = (0..mats.size-1).min_by{|i| mats[i].class == Matrix ? h : mats[i]}
		k = mats[i]
		mats[i] = exp(a, k-last_k, MOD) * last_m
		last_m = mats[i]
		last_k = k
	}
	#p mats
	
	v = Matrix[v]
	until mats.empty?
		v = v * mats.shift % MOD
	end
	c = v.to_a[0][-1]
	puts "Case #{itr+1}: #{c}"
}

Measured memory_bytes: 13252
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

   ll n,m,C;
   cin>>n>>m>>C;
   ll arr[n+5][m+5]={0};
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<m;j++)
       {
           cin>>arr[i][j];
       }
   }
   ll x=0;
   ll ans=0;
   for(int i=1;i<=n;i++)
   {
       ll cnt=0;
       ll c=0;
       for(int j=0;j<m;j++)
       {
           cnt+=arr[i][j]*arr[0][c];
           c++;


       }
       cnt+=C;
       if(cnt>0)
       {
           ans++;
       }
   }
   cout<<ans<<endl;

}



Measured memory_bytes: 3632
N,X,M=map(int,input().split())
A=[0 for i in range(10**5)]
A[X]=1
c=[]
d=[]
now=X
for i in range(2,N+1):
  now=now**2%M
  if A[now]==0:
    A[now]=i
  else:
    s=A[now]
    p=i-s
    cycle=[0 for i in range(p)]
    f=[]
    for j in range(10**5):
      if s<=A[j]<i:
        cycle[A[j]-s]=j
      if A[j]<s and A[j]!=0:
        f.append(j)
    c=cycle
    d=f
    break
if c==[]:
  ans=0
  for i in range(len(A)):
    if A[i]!=0:
      ans+=i
  print(ans)
else:
  x=len(d)
  y=len(c)
  ccount=(N-x)//y
  amari=(N-x)%y
  ans=sum(d)+sum(c)*ccount+sum(c[:amari])
  print(ans)


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define f first
#define s second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

const ll INF = (ll)1e18;
const ll mod = (ll)1e9 + 7;

const db eps = (db)1e-9;
const db pi = acos(-1.0);

const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};
const int inf = (int)1e9;

const int N = 300500;

int n, mn[N][2];
ll a[N], b[N], ans = INF;
vector <pair <ll, pair <int, int> > > vv;
vector <int> v[4];
multiset <ll> st;
ll sum;

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	//freopen(".err", "w", stderr);

	//srand(time(NULL));

	//cin.tie(NULL);
	//cout.tie(NULL);
	//ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;
	
	cin >> n;

	for(int i = 1; i <= n; ++i){
		cin >> a[i] >> b[i];
		vv.pb(mp(a[i], mp(i, 0)));
		vv.pb(mp(b[i], mp(i, 1)));
	}

	sort(all(vv));

	for(int i = 0; i < n; ++i){
		mn[vv[i].s.f][vv[i].s.s] = 1;
	}

	for(int i = 1; i <= n; ++i){
		if(mn[i][0] && mn[i][1]){
			v[3].pb(i);
		}else if(!mn[i][0] && !mn[i][1]){
			v[0].pb(i);
		}else{
			if(mn[i][0])
				v[1].pb(i);
			else v[2].pb(i);
		}
	}

	if(v[3].size() && v[0].size()){
		ans = 0;
		for(int i = 0; i < n; ++i)
			ans += vv[i].f;
		cout << ans;
		return 0;
	}

	if(!v[2].size() || !v[1].size()){
		ans = 0;
		for(int i = 0; i < n; ++i)
			ans += vv[i].f;
		cout << ans;
		return 0;
	}

	for(int i = 0; i < v[1].size(); ++i)
		st.insert(a[v[1][i]]), sum += a[v[1][i]];

	for(int i = 0; i < v[2].size(); ++i)
		st.insert(b[v[2][i]]), sum += b[v[2][i]];

	for(int i = 0; i < v[1].size(); ++i){
		st.erase(st.find(a[v[1][i]]));
		ll x = *st.rbegin();
		ans = min(ans, sum - x + b[v[1][i]]);
		st.insert(a[v[1][i]]);
	}

	for(int i = 0; i < v[2].size(); ++i){
		st.erase(st.find(b[v[2][i]]));
		ll x = *st.rbegin();
		ans = min(ans, sum - x + a[v[2][i]]);
		st.insert(b[v[2][i]]);
	}

	cout << ans;

	//cerr << (clock() + 0.0) / CLOCKS_PER_SEC;

	return 0;
}

Measured memory_bytes: 14060
/*
 * じょえチャンネル
 * 高評価・チャンネル登録よろしくおねがいします！
 * https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
 */
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)
template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}

int N;
signed main(){
	cin>>N;
	rep(i,N-1){
		for(int j=i+1;j<N;j++){
			rep(k,10){
				if((i>>k&1)!=(j>>k&1)){
					cout<<k+1<<" ";
					break;
				}
			}
		}
		cout<<endl;
	}
}


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

using namespace std;
using namespace __gnu_pbds;

  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define int long long
  #define endl "\n"
  #define all(v) v.begin(),v.end()
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<< ": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  const int N = 200005;


const double EPS = 1e-8;


int32_t main()
{




    int x;
    cin >> x;

    double curr = 100;

    int ans = 0;

    while(curr < x)
    {
        curr = curr*1.01;
        curr = (floor)(curr);
        ans++;
    }

    cout << ans;


    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
#define MAXX 500005
 
#define PI   3.14159265358979323846264338327950
 
#define PB push_back 
#define PF push_front
#define F first
#define S second
 
#define fixx(n) fixed << setprecision(n)
 
#define ll 	  long long 
 
#define mod  1000000007



int main()
{
	FAST;
	int n, k;
	cin >> n >> k;
	
	int h = n / k;
	if(n % k){
		h ++;
	}
	cout << h;
	return 0;
}

Measured memory_bytes: 3644