akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }
ostream& operator<<(ostream &os, const string& s)
{ FOR(v, s) os << *v; return os; }

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

    ll A, B, C;
    std::cin >> A >> B >> C;

    if(C <= A + B) {
        std::cout << B + C << std::endl;
    }
    else {
        std::cout << B + (B + A) + 1 << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
	unsigned long long int K,N,t,a;
    scanf("%lld%lld",&N,&K);
    if(K==0) a=N;
    else{
    t=N%K;
    if(t*2>K) a=K-t;
    else a=t;
    }
    printf("%lld",a);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <limits.h>
int A[500000+5];
int swapCount = 0;

void merge(int, int, int);
void merge_sort(int, int);

int main()
{
    int i, n;
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &A[i]);
    
    merge_sort(0, n);
    for (i = 0; i < n-1; i++) printf("%d ", A[i]);
    printf("%d\n", A[i]);
    printf("%d\n", swapCount);
    return 0;
}

void merge(int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    int i, j, k;
    for (i = 0; i < n1; i++) L[i] = A[left + i];
    for (i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    
    i = 0;
    j = 0;
    for (k = left; k < right; k++){
        if (L[i] <= R[j]){
            A[k] = L[i];
            i++;
            swapCount++;
        }
        else{
            A[k] = R[j];
            j++;
            swapCount++;
        }
    }
}

void merge_sort(int left, int right){
    if (left + 1 < right){
        int mid = (left + right)/2;
        merge_sort(left, mid);
        merge_sort(mid, right);
        merge(left, mid, right);
    }
}



Measured memory_bytes: 5600
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

Measured memory_bytes: 3436
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
 
string s;
cin >> s;
if (s[0] != s[1] && s[1] != s[2] && s[2] != s[3]){
    cout << "Good" <<endl;
}
else{
    cout << "Bad" << endl;
}
 
 
 return 0; 
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define FOR(i, n) for(int i = 0; i < (n); i ++)
using namespace std;

class UFT{
private:
    vector<int> par;

    int find(int x){
        return (par[x] == x) ? x : (par[x] = find(par[x]));
    };

public:
    UFT(int n){
        par = vector<int>(n);
        for(int i = 0; i < n; i ++) par[i] = i;
    };
    bool same(int x, int y){
        return find(x) == find(y);
    };
    void unite(int x, int y){
        if(!same(x = find(x), y = find(y))) par[x] = y;
    };
    
    void print() const{
        for(int i = 0; i < par.size(); i ++) cout << par[i] << " ";
        cout << "\n";
    };
};


int main(void){
    int m, n;
    cin >> n >> m;
    vector<int> a(n);
    UFT uft(n);
    FOR(i, n){
        cin >> a[i];
        a[i] --;
    }
    
    FOR(i, m){
        int x, y;
        cin >> x >> y;
        uft.unite(x-1, y-1);
    }
    
    int ans = 0;
    FOR(i, n){
        if(uft.same(i, a[i])) ans ++;
    }
    
    cout << ans << "\n";
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

ll A, B;
ll d1[maxn], d2[maxn], c1, c2;

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    cin>>A>>B;
    for(int i=2; 1ll*i*i<=A; ++i) {
        if(A%i==0) {
            d1[++c1]=i;
            while(A%i==0) A/=i;
        }
    }
    if(A>1) d1[++c1]=A;
    int cnt=0;
    for(int i=1; i<=c1; ++i) if(B%d1[i]==0) cnt++;
    printf("%d\n", cnt+1);
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

ll Pow(ll A, ll B, ll mod){
  if (B == 0) return 1;
  else{
    if (B % 2 == 0){
      return Pow(A * A % mod, B / 2, mod) % mod;
    }else{
      return A * Pow(A * A % mod, B / 2, mod) % mod;
    }
  }
}

ll nCr(ll N, ll C, ll mod){
  ll ans = 1; C = min(C, N - C);
  for (ll i = 1; i <= C; i++){
    ans *= N - i + 1; ans %= mod;
    ans *= Pow(i, mod - 2, mod); ans %= mod;
  }
  return ans;
}


int main(){
  int H, N; cin >> H >> N;
  int sum = 0;
  for (int i = 0; i < N; i++){
    int A; cin >> A; sum += A;
  }

  if (sum < H) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


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

int main() {
	const int INF = 1 << 30;
	const int di[4] = { 0,1,0,-1 };
	const int dj[4] = { 1,0,-1,0 };
	int h, w;
	cin >> h >> w;
	vector<string> field(h);
	for (int i = 0; i < h; i++) {
		cin >> field[i];
	}
	int cnt = 0;
	rep(i, h) {
		rep(j, w) {
			if (field[i][j] == '.') {
				cnt++;
			}
		}
	}


	// BFS
	vector<vector<int> > d(h, vector<int>(w, INF));
	d[0][0] = 1;
	queue<IP> que;
	que.push(IP(0, 0));

	while (!que.empty()) {
		IP pos = que.front();
		que.pop();
		int i = pos.first, j = pos.second;
		for (int k = 0; k < 4; k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (ni < 0 || ni >= h) continue;
			if (nj < 0 || nj >= w) continue;
			if (field[ni][nj] == '#') continue;
			if (d[ni][nj] > d[i][j] + 1) {
				d[ni][nj] = d[i][j] + 1;
				que.push(IP(ni, nj));
			}
		}
	}
	if (d[h - 1][w - 1] == INF) {
		cout << -1 << endl;
	}
	else {
		cout << cnt-d[h - 1][w - 1] << endl;
	}
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-


def countingSort(A, B, k, n):
    C = [0] * (k+1)

    for i in range(1, n + 1):
        C[A[i]] += 1

    for j in range(1, k + 1):
        C[j] = C[j] + C[j - 1]

    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    lst.insert(0, 0)
    result = [0] * (n + 1)
    k = max(lst)
    countingSort(lst, result, k, n)
    result.pop(0)
    print(" ".join([str(val) for val in result]))

Measured memory_bytes: 244520
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;i++)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;



class UnionFind {
public:
	vector<int> r,p;

	UnionFind(){}
	UnionFind(int size) {
		r.resize(size, 0);
		p.resize(size, 0);
		rep(i, 0, size)makeSet(i);
	}

	void makeSet(int x) {
		p[x] = x;
		r[x] = 0;
	}

	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	void link(int x,int y) {
		if (r[x] > r[y]) {
			p[y] = x;
		}
		else {
			p[x] = y;
			if (x == y) {
				r[y]++;
			}
		}
	}


	int findSet(int x) {
		if (x == p[x]) {
			return x;
		}
		else {
			return p[x] = findSet(p[x]);
		}
	}
};




int main(){
	int n, k, l;
	cin >> n >> k >> l;

	UnionFind road = UnionFind(n);
	UnionFind train = UnionFind(n);


	int p, q;
	rep(i, 0, k) {
		cin >> p >> q;
		p--; q--;
		if(!road.same(p,q)) road.unite(p, q);
	}
	int r, s;
	rep(i, 0, l) {
		cin >> r >> s;
		r--; s--;
		if (!train.same(r, s)) train.unite(r, s);
	}


	vector< pair<int, int> > comb(n);
	map< pair<int, int>, int >dic;

	rep(i, 0, n) {
		comb[i].first = road.findSet(i);
		comb[i].second = train.findSet(i);
		dic[comb[i]]++;
	}


	rep(i, 0, n) {
		cout << dic[comb[i]] << " ";
	}

	cout << endl;
	
	return 0;
}


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

#define cnd(c, a, b) (c ? a : b);
#define fl(x,y,z) for(int x=y;x<z;x++)
#define fe(x,y,z) for(int x=y;x<=z;x++)
#define fge(x,y,z) for(int x=y;x>=z;x--)

#define debug(x) std::cerr << #x << " --> " << x << "\n";
#define fastIO std::ios_base::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define pb push_back
#define pob pop_back
 
#define ln '\n'
typedef long long int ll;

ll mod=1e9+7;

void decrypt() {
	string s,t;
	int count, min_cnt;
	min_cnt = INT_MAX;
	cin>>s>>t;
	fe(i,0,s.length()-t.length()) {
		count = 0;
		fl(j,0,t.length()) {
			if(s[i+j]!=t[j]) {
				count++;
			}
		}
		min_cnt = min(min_cnt, count);
	}
	cout<<min_cnt<<ln;
	return;
}

int main() {
    fastIO
    int t = 1;
    // cin >> t;
    fl(i,0,t) {
    	// cout << "Case #"<< i+1 <<": ";
    	decrypt();
    }
    return 0;
}

Measured memory_bytes: 3656
def smaller(x, y):
	if x < y: return x
	return y

N, M, X = map(int, input().split())
A = list(map(int, input().split()))
cnt1 = 0
cnt2 = 0
for i in range(0, M):
	if A[i] < X:
		cnt1 += 1
	else:
		cnt2 += 1
print(smaller(cnt1, cnt2))

Measured memory_bytes: 38256
k = int(input())
mod = 7 % k
counter = 1
memo = 1
mod_map = set()
mod_map.add(mod)
while mod != 0:
    memo = ((memo % k) * (10 % k)) % k
    mod = (mod + 7 * memo) % k
    if mod not in mod_map:
        mod_map.add(mod)
    else:
        counter = -1
        break
    counter += 1
    if mod == 0:
        break
print(counter)


Measured memory_bytes: 77984
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#define ll long long 
using namespace std;

int n, k;
int d[10];
int a[5];

int f(int x) {
	int count = 0;
	int y = x;
	for (int i = 0; x != 0; i++) {
		a[i] = x % 10;
		x /= 10;
		count++;
	}
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < k; j++) {
			if (a[i] == d[j]) {
				return y + 1;
			}
		}
	}
	return y;
}

int main() {
	int ans;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> d[i];
	}
	for (;;) {
		if (n == f(n)) {
			ans = n;
			break;
		} else {
			n = f(n);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<int> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e16;
int main(){
    int n,m;
    cin >> n >> m;
    vector<P>z(n);
    vector<P>c(m);
    rep(i,n){
        ll a,b;
        cin >> a >> b;
        z[i]=make_pair(a,b);
    }
    rep(i,m){
        ll e,d;
        cin >> e >> d;
        c[i]=make_pair(e,d);
    }
    rep(i,n){
        ll M = INF;
        int ans;
        rep(j,m){
            ll temp=abs(z[i].first-c[j].first)+abs(z[i].second-c[j].second);
            if(temp<M){
                ans = j+1;
                M=temp;
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; ++i)
#define REPR(i,n) for(int i = n; i >= 0; --i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = b-1;i >= a;--i)
#define p(s) cout << (s) << endl
#define p2(s,t) cout << (s) << " " << (t) << endl 
#define ALL(v) (v).begin(), (v).end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

static const ll MOD  = 1e9 + 7;
static const ll INF  = 1e18;

static const int White = 0;
static const int Gray = 1;
static const int Black = 2;

void pvector(vector<int> A){
    cout << "[vector]";
    for(int i = 0; i < A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    int N, K;
    cin >> N >> K;
    if( (N-2) * (N-1) / 2 < K){
        cout << -1 << endl;
        return 0;
    }
    vector<pair <int, int> > res;
    for(int i = 1; i <= N; i++){
        for(int j = i + 1; j <= N; j++ ){
            res.push_back({i,j});
        }
    }
    cout << N * (N- 1) / 2 - K << endl;
    for(int i = 0; i < N * (N- 1) / 2 - K; i++){
        cout << res[i].first << " " << res[i].second << endl;
    }
    return 0;
}

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

int main() {
  ll N, x; cin >> N >> x;
  ll a; cin >> a;
  ll preva = (x<a)? x: a;
  ll ans = (x<a)? a-x: 0;
  for (int i=1; i<N; i++) {
    cin >> a;
    if (preva + a <= x) {
      preva = a;
    } else {
      ll eat = preva + a - x;
      ans += eat;
      preva = a - eat;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#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 MAXLEN = 500000;

char s[MAXLEN + 1]; int n;

int dp[MAXLEN + 1][5]; // dp[i][j] = maximum score for [0..i) with j-2 characters left/remaining (need '01', need '1', nothing, have '1', have '10')

void upd(int &x, int y) { if (x == -1 || y > x) x = y; }
void run() {
	scanf("%d%s", &n, s); n = strlen(s);
	memset(dp, -1, sizeof(dp)); dp[0][2] = 0;
	REP(i, n) REP(j, 5) if (dp[i][j] != -1) {
		if (j == 0) {
			if (s[i] == '0') upd(dp[i + 1][1], dp[i][j]);
			if (s[i] == '1') upd(dp[i + 1][0], dp[i][j] + 1);
		}
		if (j == 1) {
			if (s[i] == '1') upd(dp[i + 1][2], dp[i][j]);
		}
		if (j == 2) {
			upd(dp[i + 1][2], dp[i][j]);
			if (s[i] == '1') upd(dp[i + 1][0], dp[i][j] + 1), upd(dp[i + 1][3], dp[i][j]);
		}
		if (j == 3) {
			upd(dp[i + 1][2], dp[i][j]);
			if (s[i] == '1') upd(dp[i + 1][0], dp[i][j] + 1), upd(dp[i + 1][3], dp[i][j]);
			if (s[i] == '0') upd(dp[i + 1][1], dp[i][j] + 1), upd(dp[i + 1][4], dp[i][j]);
		}
		if (j == 4) {
			upd(dp[i + 1][2], dp[i][j]);
			if (s[i] == '1') upd(dp[i + 1][4], dp[i][j] + 1), upd(dp[i + 1][3], dp[i][j]), upd(dp[i + 1][2], dp[i][j] + 1);
		}
	}
	printf("%d\n", dp[n][2]);
}

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


Measured memory_bytes: 10496
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        Solver solver = new Solver();
        solver.solve();
        return;
    }
}

class Solver
{
    public Solver()
    {
    }

    public void solve()
    {
        while (input() == 0) ;
    }

    private int input()
    {
        string[] str;
        try
        {
            str = rsa();
        }
        catch (System.IO.IOException)
        {
            return 1;
        }
        catch (System.ArgumentOutOfRangeException)
        {
            return 1;
        }
        catch (System.OutOfMemoryException)
        {
            return 1;
        }
        catch (System.NullReferenceException)
        {
            return 1;
        }

        List<double> sta = new List<double>();

        for (int i = 0; i < str.Length; i++)
        {
            double parsed;
            if (double.TryParse(str[i], out parsed)) {
                sta.Add(parsed);
            }
            else
            {
                int counter = sta.Count;
                double var1 = sta[counter - 2];
                double var2 = sta[counter - 1];
                sta.RemoveAt(counter - 1);
                sta.RemoveAt(counter - 2);
                switch (str[i].ToCharArray()[0])
                {
                    case '+':
                        //Console.WriteLine(var1 + var2);
                        sta.Add(var1 + var2);
                        break;
                    case '-':
                        //Console.WriteLine(var1 - var2);
                        sta.Add(var1 - var2);
                        break;
                    case '*':
                        //Console.WriteLine(var1 * var2);
                        sta.Add(var1 * var2);
                        break;
                    case '/':
                        //Console.WriteLine(var1 / var2);
                        sta.Add(var1 / var2);
                        break;
                    default:
                        break;
                }
            }
        }
        Console.WriteLine(sta[0].ToString("0.000000"));

        return 0;
    }

    static String rs() { return Console.ReadLine(); }
    static int ri() { return int.Parse(Console.ReadLine()); }
    static long rl() { return long.Parse(Console.ReadLine()); }
    static double rd() { return double.Parse(Console.ReadLine()); }
    static String[] rsa() { return Console.ReadLine().Split(' '); }
    static int[] ria() { return Array.ConvertAll(Console.ReadLine().Split(' '), e => int.Parse(e)); }
    static long[] rla() { return Array.ConvertAll(Console.ReadLine().Split(' '), e => long.Parse(e)); }
    static double[] rda() { return Array.ConvertAll(Console.ReadLine().Split(' '), e => double.Parse(e)); }
}

Measured memory_bytes: 5852
#include<stdio.h>
#include<math.h>
#define MAX 1000000
int count=0;
int S[MAX];
int n,k,l;
int G[MAX];
int Glen=0;

void insertSort()
{
  int i,j;
  int u;
  for(i=0;i<Glen;i++)
    {
      for(j=G[i];j<n;j++)
	{
	  u=S[j];
	  l=j-G[i];
	  while(l>=0 &&S[l]>u)
	    {
	      S[l+G[i]]=S[l];
	      l=l-G[i];
	      count++;
	    }
	  S[l+G[i]]=u;
	}
    }
}
void shellSort(int S[],int n)
{
  int i,j;
  int t;
  for(i=1;G[i-1]<=n;i++)
    {
      Glen++;
      G[i]=3*G[i-1]+1;
      if(Glen>100)break;
    }

  for(i=0;i<Glen/2;i++)
    {
      t=G[i];
      G[i]=G[Glen-i-1];
      G[Glen-i-1]=t;
    }
  insertSort();
}

int main()
{
  scanf("%d",&n);
  int i;
  for(i=0;i<n;i++)
    {
      scanf("%d",&S[i]);
    }
  G[0]=1;
  shellSort(S,n);
  printf("%d\n",Glen);
  for(i=0;i<Glen;i++)
    {
      printf("%d ",G[i]);
    }
  printf("\n");
  printf("%d\n",count);
  for(i=0;i<n;i++)printf("%d\n",S[i]);
  return 0;
}

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



int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin>>n;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end());
    cout<<a[n-1]<<' ';

    int dif=1e9+7,k=0;
    rep(i,n-1){
        if(dif>=abs(a[n-1]/2-a[i])){
            dif=abs(a[n-1]/2-a[i]);
            k=i;
        }
    }
    cout<<a[k]<<endl;

    return 0;
}


Measured memory_bytes: 640
import sys
input=sys.stdin.readline
a,b,c,d=map(int,input().split())
for i in range(10000):
    a-=d
    c-=b
    if a <= 0 and c <= 0:
        print("Yes")
        exit(0)
    elif a <= 0:
        print("No")
        exit(0)
    elif c<=0:
        print("Yes")
        exit(0)

Measured memory_bytes: 61536
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        String cha = sc.next();
        
        int ans = 0;
        int sum = 0;
        
        for(int x=0; x<num; x++){
            if(cha.charAt(x) == 'I'){
                sum++;
                if(sum > ans){
                    ans = sum;
                }
            }else if(cha.charAt(x) == 'D'){
                sum--;
            }
        }
        
        System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, M;

int main()
{
	scanf("%d%d", &N, &M);

	int once = 1900 * M + (N - M) * 100;
	once <<= M;
	printf("%d\n", once);
	return 0;
}


Measured memory_bytes: 256
'use strict';

function main(arg) {
    let N = arg.split("\n")[0];
    let L = arg.split("\n")[1].split(" ").map(n=>parseInt(n));
    
    let max    = Math.max(...L);
    let others = L.reduce((m,n)=>m+n) - max;
    
    console.log(max < others ? 'Yes' : 'No');
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
x, y = map(int, input().split())
if 0 <= x <= y or x <= y <= 0:
    print(y - x)
elif x <= 0 <= y or y <= 0 <= x:
    print(abs(abs(y) - abs(x)) + 1)
else:
    print(abs(abs(y) - abs(x)) + 2)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

ll l[200000],r[200000];
ll a[200000];
int main(){
	int n;cin>>n;
	rep(i,n){
		scanf("%lld",&a[i]);
	}
	l[0]=a[0];
	r[n-1]=a[n-1];
	for(int i=1;i<n;i++){
		l[i]=__gcd(l[i-1],a[i]);
	}
	for(int i=n-2;i>=0;i--){
		r[i]=__gcd(r[i+1],a[i]);
	}
	ll Max=0;
	rep(i,n){
		if(i==0)Max=max(Max,r[1]);
		else if(i==n-1)Max=max(Max,l[n-2]);
		else Max=max(Max,__gcd(l[i-1],r[i+1]));
	}
	cout<<Max<<endl;
}

Measured memory_bytes: 3584
s = input()
n = len(s)
#dp[i][j] = ｓのi文字目までで、最後からｊ文字とったものを分割文字列としたときの最大の分割数
dp = [[0]*3 for i in range(n+1)]
dp[0][1] = 1
dp[0][2] = -1
for i in range(1,n):
    if s[i] == s[i-1]:
        dp[i][1] = dp[i-1][2]+1
    elif s[i] != s[i-1]:
        dp[i][1] = max(dp[i-1][1],dp[i-1][2])+1
    if i>=2:
        dp[i][2] = max(dp[i-2][1],dp[i-2][2])+1
ans = max(dp[n-1][1],dp[n-1][2])
print(ans)

Measured memory_bytes: 36328
if __name__ == '__main__':

	while True:

		n = int(input())
		
		if n == 0:
			break

		A = [[0 for _ in range(n+1)]for _ in range(n)]
		B = [0 for _ in range(n+1)]

		for i in range(n):
			tmp = list(map(int,input().split()))
			
			for j,k in enumerate(tmp):
				A[i][j] += k
				B[j] += k

			A[i][n] = sum(A[i])
			B[n] = sum(B[:n])
		
		for m in A:
			tmp2 = ""
			for g in m:
				tmp2 += '{:>5}'.format(str(g))
			print(tmp2)
		tmp3 = ""
		for y in B:
			tmp3 += '{:>5}'.format(str(y))
		print(tmp3)



Measured memory_bytes: 5616
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(){
    string S;

    cin >> S;

    int cnt = 0;
    int ans = 0;
    
    for(int i = 0;i < S.length();i++){
        if(S[i] == 'R'){
            cnt++;
        }else{
            cnt = 0;
        }
        ans = max(ans,cnt);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3132
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
abc113 C
"""

# from collections import defaultdict

n, m = map(int, input().split())

perflist = [[] for i in range(n+1)]
ans = ["" for i in range(m+1)]

for i in range(m):
    p, y = map(int, input().split())
    perflist[p].append((i+1, y))

for i in range(1, n+1):
    perflist[i].sort(key=lambda x: x[1])

for p in range(1, n+1):
    for i, (c, _) in enumerate(perflist[p]):
        ans[c] = '{0:06d}'.format(p) + '{0:06d}'.format(i+1)

for c in range(1, m+1):
    print(ans[c])


Measured memory_bytes: 36016
import sys 
n = int(input())
lst = []
for i in range(n):
  x,y = map(int,input().split())
  if x == y:
    lst.append(i)
for i in range(len(lst)-2):
  if lst[i+1] == lst[i] +1 and lst[i+2] == lst[i+1] +1:
    print('Yes')
    sys.exit()
print('No')    
    
  



Measured memory_bytes: 9208
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;


namespace atPra
{
    class Class1
    {
        static void Main()
        {
            string[] str = Console.ReadLine().Split(null);
            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);
            int diff = b - a;
            int x = calc(diff)-b;
            Console.WriteLine(x);
        }

        static int calc(int y){
            int sum = 0;
            for (int i = 1; i <= y;i++){
                sum += i;
            }
            return sum;
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>

using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++ )

int main()
{
  int w, a, b, work, ans;
  cin >> w >> a >> b;
  if(a < b) {
    work = a + w;
    ans = b - work;
  }else{
    work = b + w;
    ans = a - work;
  }
  if(ans > 0) cout << ans << endl;
  else cout << 0 << endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if ((a * b) % 2 == 0)
            System.out.println("Even");
        else
            System.out.println("Odd");
    }
}

Measured memory_bytes: 35808
using System.Linq;
using System;
using System.IO;
using System.Collections.Generic;
using static System.Console;

class Program
{
  static void Main(string[] args) =>
    new Program().solve();

  private void solve()
  {
    var pram = ReadLine().Split(' ').Select(long.Parse).ToArray();
    var a = pram[0];
    var b = pram[1];
    var k = pram[2];

    var ans = new long[2];
    ans[0] = (a < k) ? 0 : a - k;
    var k2 = Math.Max(k - a, 0);
    ans[1] = (b < k2) ? 0 : b - k2;

    WriteLine(String.Join(" ", ans));
  }
}

Measured memory_bytes: 13396
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main(){
	int n, k;
	string s;
	cin>>n>>k>>s;

	if(s[k-1] == 'A')
	s[k-1] = 'a';
	else if(s[k-1] == 'B')
	s[k-1] = 'b';
	else
	s[k-1] = 'c';

	cout<< s <<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n,a,b;
cin>>n>>a>>b;
string s;
cin>>s;
ll k=0;
ll g=0;
for(ll i=0; i<s.size(); i++){
if(s.at(i)=='a'&&k+g<a+b){
cout << "Yes" << endl;
k++;}
else if(s.at(i)=='b'&&(k+g<a+b)&&g<b){
cout << "Yes" << endl;
g++;}
else{
cout << "No" << endl;}}}




Measured memory_bytes: 3700
class Node
  attr_accessor :parent, :sibling, :depth, :degree, :height, :type, :child
  def initialize()
    @parent = -1
    @sibling = -1
    @degree = 0
    @depth = 0
    @height = 0
    @type = "leaf"
    @child = []
  end
end

def set_depth_height(tree, depth, child)
  if child.size != 0 then
    height = 0
    child.each{|i|
      tree[i].depth = depth
      h = set_depth_height(tree, depth+1, tree[i].child)
      tree[i].height = h
      height = h if height < h
    }
    return height + 1
  else
    return 0
  end
end

n = gets.to_i
tree = Array.new(n){Node.new()}

n.times{
  i, l, r = gets.split.map(&:to_i)
  if l != -1  && r != -1then
    tree[i].type = "internal node"
    tree[i].degree = 2
    tree[i].child = [l, r]
    tree[l].parent = i
    tree[l].sibling = r
    tree[r].parent = i
    tree[r].sibling = l
  elsif l != -1 then
    tree[i].type = "internal node"
    tree[i].degree = 1
    tree[i].child = [l]
    tree[l].parent = i
  elsif r != -1 then
    tree[i].type = "internal node"
    tree[i].degree = 1
    tree[i].child = [r]
    tree[r].parent = i
  end
}

#find root
0.upto(n-1){|i|
  if tree[i].parent == -1 then
    tree[i].type = "root"
    tree[i].depth = 0
    #calc depth
    tree[i].height = set_depth_height(tree, 1, tree[i].child);
    break
  end
}

0.upto(n-1){|i|
  printf "node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", i, tree[i].parent, tree[i].sibling, tree[i].degree, tree[i].depth, tree[i].height, tree[i].type
}

Measured memory_bytes: 8640
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}


ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

int main(){
  ll n;
  cin>>n;
  vl a(n);
  rep(i,n) cin>>a[i];
  sort(all(a));
  bool ok =false;
  rep(i,n-1){
    if(a[i]==a[i+1]) ok=true; 
  }
    
  if(ok) cout<<"NO"<<endl;
  else{
    cout<<"YES"<<endl;
  }
}




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

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const ll INF = 2e18;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;

int N, M, V, P, A[MAXN];

bool chk(int idx) {
	int x = A[idx], a = idx - 1;
	if(V-P-a <= 0) return (x + M >= A[N-P+1]);
	if(A[N-P+1] > x + M) return 0;
	ll sum = 0;
	for(int i=idx+1; i<=N-P+1; i++) sum += x + M - A[i];
	return (sum >= 1LL * (V-P-a) * M);
}

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

	cin >> N >> M >> V >> P;
	for(int i=1; i<=N; i++) cin >> A[i];
	sort(A+1, A+1+N);

	int l = 1, r = N - P, ans = P;
	while(l <= r) {
		int mid = l + r >> 1;
		if(chk(mid)) {
			r = mid - 1;
			ans = N - mid + 1;
		}
		else l = mid + 1;
	}

	cout << ans;
}

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

bool comp_a(pair<long long, long long> x, pair<long long, long long> y) {
	return x.second < y.second;
}

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

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

	vector<pair<long long, long long>> AB(N);

	for (int i = 0; i < N; i++) {
		scanf("%lld %lld", &(AB[i].first), &AB[i].second);
	}

	sort(AB.begin(), AB.end(), comp_a);

	// printf("%lld %lld \n", AB[0].first, AB[0].second);

	long long time = 0;
	for (int i = 0; i < N; i++) {
		time += AB[i].first;
		if (time > AB[i].second) {
			printf("No");
			return 0;
		}
	}
	printf("Yes");

	return 0;
}

Measured memory_bytes: 3456
S = input().rstrip()
Q = int(input().rstrip())
reversed = False
from collections import deque
q = deque()
q.extend(list(S))
for _ in range(Q):
    l = input().rstrip()
    if l.startswith('1'):
        reversed = False if reversed else True
    else:
        _, F, C = l.split()
        if F == '1':
            if reversed:
                q.append(C)
            else:
                q.appendleft(C)
        elif F == '2':
            if reversed:
                q.appendleft(C)
            else:
                q.append(C)
ret = ''.join(list(q)[::-1]) if reversed else ''.join(list(q))
print(ret)


Measured memory_bytes: 72680
import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
A = collections.Counter(a)

keys, conts = zip(*A.most_common()[::-1])
ans = 0
x = len(set(a))

for cont in conts:
    if x > k:
        ans += cont
    x -= 1

print(ans)

Measured memory_bytes: 53552
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int k;
  cin >> k;
  if (k <= 9) {
    cout << k << endl;
    return 0;
  }
  priority_queue<pair<ll, ll>, vector<pii>, greater<pii>> pq;
  for (int i = 1; i <= 9; i++)
    pq.push({i, i});
  k -= 9;
  while (true) {
    pii e = pq.top();
    pq.pop();
    for (int i = max(0LL, e.second - 1); i <= min(9LL, e.second + 1); i++) {
      ll num = e.first * 10 + i;
      k--;
      if (!k) {
        cout << num << endl;
        return 0;
      }
      pq.push({num, i});
    }
  }
}

Measured memory_bytes: 2420
n = int(input())
a = [int(i) for i in input().split()]

def trace(a):
    a = map(str, a)
    print(' '.join(a))

def insertion(a):
    for i in range(1, n):
        v = a[i]
        j = i -1
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        trace(a)
    


trace(a)
insertion(a)


Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std;
char s[1005];
int w,n;
int main()
{
    scanf("%s",s);
    scanf("%d",&w);
    int n=strlen(s);
    for(int i=0;i<n;i+=w) printf("%c",s[i]);
    printf("\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include<cmath>
#define pb push_back
#define nax (int)2e5+2
#define ll long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
using namespace std;
 



int main() 
{ 
	int n,m;
	cin>>n>>m;
	ll temp1 = n*(n-1);
	temp1 = temp1/2;
	ll temp2 = m*(m-1);
	temp2 = temp2/2;
	cout<<temp1+temp2;
	
	
	
	return 0; 
} 


Measured memory_bytes: 256
class UF():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


n,m,k=map(int,input().split())
F=[set()for _ in range(n)]
uf=UF(n)
for i in range(m):
      a,b=map(int,input().split())
      uf.union(a-1,b-1)
      F[a-1].add(b-1)
      F[b-1].add(a-1)
B=[0]*n
for i in range(k):
      c,d=map(int,input().split())
      if uf.same(c-1,d-1):
            B[c-1]-=1
            B[d-1]-=1
ans=[]
for i in range(n):
      ans.append(uf.size(i)+B[i]-1-len(F[i]))
print(*ans)

Measured memory_bytes: 124008
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[10005],b[1005][1005],c[1005][1005];
int main()
{
	int h,w,n,t=1,k=1;
	scanf("%d%d",&h,&w);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=h;i++)
	{
		for(int j=w;j>=1;j--)
		{
			if(i%2!=0)
			b[i][j]=t;
			else b[i][w+1-j]=t; 
			k++;
			if(k>a[t]) t++,k=1;
		}
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
			cout<<b[i][j]<<" ";
		cout<<endl;
	}
}

Measured memory_bytes: 4480
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;


//ABC158_C
int main() {
	int A, B;
	cin >> A >> B;

	int n = 2000;
	for (int i=1; i<n; i++) {
		int x1 = i * 0.08;
		int x2 = i * 0.10;
		if (x1 == A and x2 == B) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "-1" << endl;
}

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

const int INF = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

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

	vector<int> dp(n,INF);
	dp[0] = 0;
	dp[1] = abs(h[1]-h[0]);
	//dp[i] is min cost to reach i 

	for(int i=2;i<n;i++){
		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
	}

	cout<<dp[n-1]<<"\n";

	return 0;
}

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

using namespace std;

int dig[10];

int main()
{
    int n, k; cin >> n >> k;
    for(int i = 0; i < k; i++)
    {
        int x; cin >> x;
        dig[x] = 1;
    }
    for(int i = n; i <= 1000000; i++)
    {
        int x = i;
        bool ok = true;
        while(x)
        {
            int d = x%10;
            if(dig[d])
                ok = false;
            x /= 10;
        }
        if(ok)
            return !(cout << i << endl);
    }
}



Measured memory_bytes: 3600
#include <stdio.h>
 int main(void) {
 int k, a, b;

 scanf("%d", &k);
 scanf("%d%d", &a, &b);

 int largest = (b / k) * k;
 if (a <= largest) {
 puts("OK");
 } else {
 puts("NG");
 }

 return 0;
 }

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



int a[3][3], n, b[101];
bool d[3][3];
void solve(){
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			cin >> a[i][j];
		}
	}
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> b[i];
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				if(a[j][k] == b[i]){
					d[j][k] = 1;
				}
			}
		}
	}
	
	bool ok = 0;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(!d[i][j]){
				ok = 0;
				break;
			}
			ok = 1;
		}
		if(ok){
			cout << "Yes" << endl;
			return;
		}
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(!d[j][i]){
				ok = 0;
				break;
			}
			ok = 1;
		}
		if(ok){
			cout << "Yes" << endl;
			return;
		}
	}
	for(int i = 0; i < 3; i++){
		if(!d[i][i]){
			ok = 0;
			break;
		}
		ok = 1;
	}
	if(ok){
		cout << "Yes" << endl;
		return;
	}
	for(int i = 0; i < 3; i++){
		if(!d[i][2-i]){
			ok = 0;
			break;
		}
		ok = 1;
	}
	if(ok){
		cout << "Yes" << endl;
		return;
	}
	cout << "No" << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  int ans = 0;
  int C = 0;
  
  for(int i =0; i < N; i++){
		int A;
    	cin >> A;
    	
   
   
    	while(A % 2 == 0){
        
          A /= 2;
    	
          C++;
        
        
        
        
    }
    if(i == 0){
    ans = C;
    C = 0;
    }
    else{
		if(ans >= C && C != 0){
        ans = C;
        C = 0;
        }
    	else{
        C = 0;
        
        }
   
    } 
   
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
typedef long long ll; 
using namespace std;

ll n, m, ans; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	n = read <ll> (), m = read <ll> ();
	if(m < n * 2) { printf("%lld\n", m / 2); return 0; }
	ans = n, m -= n * 2;
	printf("%lld\n", ans + m / 4); 
	return 0; 
}


Measured memory_bytes: 3228
N,A,B=map(int,input().split())
if abs(A-B) % 2 == 0:
    print(abs(A-B)//2)
else:
    # Aが1まで行って時間稼ぎ
    c = A-1 + 1 + abs(1-(B-(A-1+1)))//2
    # BがNまで行って時間稼ぎ
    d = N-B + 1 + abs(N-(A+(N-B+1)))//2
    print(min(c,d))

Measured memory_bytes: 38256
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))
subX = []

if N >= M:
  print(0)
else:
  for i in range(M-1):
    subX.append(X[i+1]-X[i])
  
  subX = sorted(subX)  
  ans = sum(subX)

  if N>= 2:
    for i in range(N-1):
      ans -= subX[-i-1]

  print(ans)

Measured memory_bytes: 58280
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	l := make([]int, n+1)
	l[0], l[1] = 2, 1
	for i := 2; i <= n; i++ {
		l[i] = l[i-1] + l[i-2]
	}
	fmt.Println(l[n])
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const int N=200010;
int n;
int top;
int l[N],r[N],c[N],a[N];
int check(int v)
{
	top=0;
	for(int i=1;i<=n;i++)
	{
		while(r[top]>a[i])
		{
			if(l[top]>a[i])
				top--;
			else
				r[top]=a[i];
		}
		if(r[top]==a[i])
		{
			int ch=c[top]+1;
			if(r[top]==l[top])
				top--;
			else
				r[top]--;
			top++;
			r[top]=l[top]=r[top-1]+1;
			c[top]=ch;
			int _r=r[top];
			while(top&&c[top]>v)
			{
				top--;
				if(r[top]==l[top])
					c[top]++;
				else
				{
					if(c[top]==v)
						top--;
					else
					{
						r[top]--;
						top++;
						c[top]=c[top-1]+1;
						l[top]=r[top]=r[top-1]+1;
					}
				}
			}
			if(!top)
				return 0;
			if(r[top]<_r)
			{
				top++;
				l[top]=r[top-1]+1;
				r[top]=_r;
				c[top]=1;
			}
		}
		else
		{
			top++;
			l[top]=r[top-1]+1;
			r[top]=a[i];
			c[top]=1;
		}
	}
	return 1;
}
int main()
{
//	open("c");
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=1,r=2e5;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 3328
N, M = map(int, input().split())

UV = []
for _ in range(M):
    u, v = map(int, input().split())
    UV.append((u, v))
    
S, T = map(int, input().split())

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

from collections import defaultdict
graph = defaultdict(lambda: {})

for a,b in UV:
    graph[a][b+N] = 1
    graph[a+N][b+N*2] = 1
    graph[a+N*2][b] = 1
    
shortest = dijkstra(graph, S, N*3)
#print(shortest)
if shortest[T] % 3 == 0 and shortest[T] != 0:
    print(shortest[T]//3)
else:
    print(-1)
        

Measured memory_bytes: 161276
#include <iostream>
using namespace std;
long long n, m, s, M=1e9+7;
int main() {
	cin>>n>>m;
	if(n==m) s=2;
	else if(n-m==-1 || n-m==1) s=1;
	while(n) s = (s*n--) % M;
	while(m) s = (s*m--) % M;
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
using System;

class Program
{
	static void Main()
	{
		int[, ,] A = new int[4, 3, 10];
		int D = int.Parse(Console.ReadLine());
		for (int i = 0; i < D; i++)
		{
			string[] sD = Console.ReadLine().Split(' ');
			A[int.Parse(sD[0]) - 1, int.Parse(sD[1]) - 1, int.Parse(sD[2]) - 1] += int.Parse(sD[3]);
		}
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				for (int k = 0; k < 10; k++)
				{
					Console.Write(" " + A[i, j, k]);
				}
				Console.WriteLine();
			}
			if (i != 3)
			{
				Console.WriteLine("####################");
			}
		}
	}
}

Measured memory_bytes: 19932
import heapq
x, y, z, K = map(int, input().split())
k = min(x * y * z, K)
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

results = []
pque = [(-(a[0] + b[0] + c[0]), (0, 0, 0))]
visited = {}
cnt = 0
while pque:
    value, position = heapq.heappop(pque)
    if visited.get(position) is None:
        visited[position] = True
        cnt += 1
        if cnt > K:
            break
    else:
        continue

    print(-value)
    results.append(value)
    for pattern in [[0, 0, 1], [0, 1, 0], [1, 0, 0]]:
        i, j, k = [v1 + v2 for v1, v2 in zip(pattern, position)]
        if i < x and j < y and k < z:
            heapq.heappush(pque, (-(a[i] + b[j] + c[k]), (i, j, k)))


Measured memory_bytes: 4852