akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
typedef long long ll;
const int INF = (((1<<30)-1)<<1)+1;
const ll lINF = 0x3f3f3f3f3f3f3f3fLL;
const int nINF = 1<<31;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

/////////////////////////////////////////////////////////////////////

const int N = 410;
int n, a[N];
ll dp[N][N]; //dp[i][j] - solution for a[i..j]

ll rec(int l, int r) {
	if(l == r) return 0;
	ll& memo = dp[l][r];
	if(memo != -1) return memo;
	ll s = 0;
	FOR(i, l, r) s += a[i];
	ll res = lINF;
	FOR(i, l, r-1) res = min(res, rec(l, i)+rec(i+1, r));
	return memo = res+s;
}

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    cout << rec(1, n) << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE)
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - integer division (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting min to 0 instead of -INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
#include<cassert>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

/////////////////////////////////////

int main() {
	ll N, X, M;
	cin >> N >> X >> M;

	vll see(M, 0);

	ll now = X;
	ll pri = 0;
	while (see[now] == 0) {
		pri++;
		see[now] = pri;
		now = now * now % M;
	}

	pri = pri - see[now] + 1;

	ll T = now;
	ll sum = 0;
	while (1) {
		sum += now;
		now = now * now % M;
		if (now == T) { break; }
	}

	if (see[T] >= N) {
		ll ans = 0;
		now = X;
		rep(i, N) {
			ans += now;
			now = now * now % M;
		}
		cout << ans << endl;
	}
	else {
		ll ans = sum *( (N - see[T]) / pri);
		ll rem = N -= (N - see[T]) / pri * pri;
		now = X;
		rep(i, rem) {
			ans += now;
			now = now * now % M;
		}
		cout << ans << endl;
	}



}

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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    vector<ll> A(n);
    ll t = 0, ret = 0, l = 0,r=0;
    for(auto &x:A)cin >> x;
    for(l=0;l<n;l++){
        while(r!=n && (t&A[r])==0){
            t^=A[r];
            r++;
        }
        ret+= r-l;
        t^=A[l];
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 1920
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = 1000000007;
        int[][][][] dp = new int[101][4][4][4];
        dp[0][3][3][3] = 1;
        for(int len = 0; len < n; len++) {
            for(int c1 = 0; c1 < 4; c1++) {
                for(int c2 = 0; c2 < 4; c2++) {
                    for(int c3 = 0; c3 < 4; c3++) {
                        if(dp[len][c1][c2][c3] == 0) continue;
                        for(int newC = 0; newC < 4; newC++) {
                            if(newC == 2 && c1 == 1 && c2 == 0) continue;
                            if(newC == 2 && c1 == 0 && c2 == 1) continue;
                            if(newC == 1 && c1 == 2 && c2 == 0) continue;
                            if(newC == 2 && c1 == 1 && c3 == 0) continue;
                            if(newC == 2 && c2 == 1 && c3 == 0) continue;

                            dp[len + 1][newC][c1][c2] += dp[len][c1][c2][c3];
                            dp[len + 1][newC][c1][c2] %= mod;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int c1 = 0; c1 < 4; c1++) {
            for (int c2 = 0; c2 < 4; c2++) {
                for (int c3 = 0; c3 < 4; c3++) {
                    ans += dp[n][c1][c2][c3];
                    ans %= mod;
                }
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
float ans;
int main() {
    int n; cin >> n;
    int odds = 0;
    for(int i = 1; i <= n; i++) {
        if(i & 1) odds++;
    }
    ans = ((float)odds/n);
    printf("%.6f", ans);
    return 0;
}

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

ll gcd(ll a,ll b,ll &x,ll &y){
  ll d=a;
  if(b==0){
    x=1;	y=0;
  }
  else {
    d=gcd(b,a%b,y,x);
    y-=a/b*x;
  }
  return d;
}

int main() {
  ll a,b,x,y;
  cin >> a >> b;
  gcd(a,b,x,y);
  cout<< x<<" " << y << endl;
}


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

#define rep(i, n) for (int(i) = 0; (i) < (int)(n); (i)++)
#define repr(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define repf(i, m, n) for (int(i) = (m); (i) < (n); (i)++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define inf 1e9

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

using namespace std;
using ll = long long;

int main(int argc, char const *argv[])
{
    int a, b, x;
    cin >> a >> b >> x;

    int ans = 0;

    while (x > 0)
    {
        if (x <= 500)
        {
            if (a < b)
            {
                ans += a;
                x -= 1000;
            }
            else
            {
                ans += b;
                x -= 500;
            }
        }
        else
        {
            if (a < 2 * b)
            {
                ans += a;
                x -= 1000;
            }
            else
            {
                ans += b;
                x -= 500;
            }
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3116
from collections import Counter

n = int(input())
v = list(map(int, input().split()))

v0 = v[0:n-1:2]
v1 = v[1:n:2]

c0 = Counter(v0).most_common()
c1 = Counter(v1).most_common()

if len(set(v0)) == len(set(v1)) == 1:
    if c0[0] == c1[0]:
        res = len(v0)
    else:
        res = 0

else:
    if c0[0] != c1[0]:
        res = n - c0[0][1] - c1[0][1]
    else:
        res = min(n - c0[0][1] - c1[1][1], n - c0[1][1] - c1[0][1])

print(res)

Measured memory_bytes: 105472
BUILDING = 4
FLOOR = 3
ROOM = 10

resident = []
for i in range(BUILDING):
	building = []
	for j in range(FLOOR):
		floor = []
		for k in range(ROOM):
			floor.append(0)
		building.append(floor)
	resident.append(building)

n = input()
for i in range(n):
	b, f, r, v = map(int, raw_input().split())
	resident[b-1][f-1][r-1] += v

for i in range(BUILDING):
	for j in range(FLOOR):
		output_line = ""
		for k in range(ROOM):
			output_line += " " + str(resident[i][j][k])
		print output_line
	if i != BUILDING-1:
		print "####################"

Measured memory_bytes: 6480
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;



int main()
{
	int a, b, h;
	int res;

	cin >> a >> b >> h;
	res = (a + b) * h / 2;

	cout << res << endl;


}

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

int main()
{
  string S;
  cin >> S;
  map<char, int> mp = {{'N', 0}, {'W', 0}, {'S', 0}, {'E', 0}};
  for (int i = 0; i < (int)S.size(); i++)
  {
    mp[S[i]]++;
  }
  if (!abs(min(1, mp['N']) - min(1, mp['S'])) && !abs(min(1, mp['E']) - min(1, mp['W'])))
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    long n, m;
    scan(n, m);
    auto ab = new long[][](n, 2);
    auto cd = new long[][](m, 2);
    // writeln(ab);
    // writeln(cd);
    auto ans = new long(100);
    auto check_i = new long[](n);
    foreach (i; 0 .. n)
    {
        long a, b;
        scan(a, b);
        ab[i][0] = a;
        ab[i][1] = b;
    }
    // writeln(ab);
    foreach (i; 0 .. m)
    {
        long c, d;
        scan(c, d);
        cd[i][0] = c;
        cd[i][1] = d;
    }
    // writeln(cd);
    foreach (i; 0 .. n)
    {
        long ans_x = 10 ^^ 9;
        foreach (j; 0 .. m)
        {
            long tmp;
            tmp = abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1]);
            if (tmp < ans_x)
            {
                check_i[i] = j + 1;
                ans_x = tmp;
            }

        }
    }
    foreach (i; 0 .. n)
    {
        writeln(check_i[i]);
    }

}
//https://rclone.org/

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


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

#define rep(i, N) for(int (i) = 0; (i) < (N); i++)
#define all(v) v.begin(), v.end()
using i64 = int_fast64_t;

i64 gcd(i64 n,i64 m){return m?gcd(m,n%m):n;}
i64 lcm(i64 n,i64 m){return n*m/gcd(n,m);} 

int main(){
    i64 A, B;
    cin >> A >> B;

    cout << lcm(A, B) << endl;
}

Measured memory_bytes: 256
n = int(input()) + 1
l = [int(input()) for i in range(n-1)]
length = sum(l)+1
dp = [[0]*length for i in range(n)]
dp[0][0] = 1

for i in range(1, n):
  for j in range(length):
    if dp[i-1][j] == 1:
      dp[i][j] = 1
    elif j-l[i-1] >= 0:
      if dp[i-1][j-l[i-1]] == 1:
        dp[i][j] = 1
temp = dp[-1]
ans = 0
for i in range(length-1, -1, -1):
  if temp[i] == 1 and not i % 10 == 0:
    ans = i
    break

print(ans)

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

    #define ll long long
    #define ff first
    #define ss second
    #define pb push_back
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define MOD 1000000007
    #define pll pair<ll,ll>
constexpr ll INF = 1999999999999999997; 
    #define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
    int main() {
        fastio;
        
        int n;
        cin>>n;
        ll mx=0;
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ll x;
            cin>>x;
            mx=max(x,mx);
            ans+=(mx-x);

        }
        cout<<ans<<endl;

    }

Measured memory_bytes: 3512
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
//#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
#define puts(x) cout << x << endl
using namespace std;
int input() {
	int r;
	cin >> r;
	//scanf("%lld", &r);
	return r;
}
int n, m, q, a[60], b[60], c[60], d[60], e[15];
int f(int i) {
	int r = 0;
	if (i == n + 1) {
		for1(i, q)if (e[b[i]] - e[a[i]] == c[i])r += d[i];
		return r;
	}
	for (e[i] = e[i - 1]; e[i] <= m; e[i]++)r = max(r, f(i + 1));
	return r;
}
signed main() {
	e[0] = 1;
	cin >> n >> m >> q;
	for1(i, q)cin >> a[i] >> b[i] >> c[i] >> d[i];
	puts(f(1));
}

Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();//チームの個数
		int team[] = new int[x+1];//勝ち点
		int i,j;
		for(i = 0; i < x*(x-1)/2; i++){
			int ta = sc.nextInt();//Aチーム
			int tb = sc.nextInt();//Bチーム
			int pa = sc.nextInt();//Aチーム得点
			int pb = sc.nextInt();//Bチーム得点
			if(pb < pa){
				team[ta]+=3;
			}
			else if(pb == pa){
				team[ta]+=1;
				team[tb]+=1;
			}
			else{
				team[tb]+=3;
			}
		}
		for(i = 1; i < x+1; i++){
			int rank = 1;//順位
			for(j = 1; j < x+1; j++){
				if(team[i] < team[j]){
					rank++;
				}
			}
			System.out.println(rank);
		}	
	}

}

Measured memory_bytes: 42136
#include <stdio.h>

int main() {
	int n, i, j;
	int d[101];
	int sum = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &d[i]);

	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			sum += (d[i] * d[j]);
		}
	}

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

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

ll factorial(ll n) {
  ll answer = 1;
  while (n > 1) {
    answer *= n;
    answer %= mod;
    n--;
  }
  return answer;
}

ll calcNumOfCombination(ll n, ll r) {
  return factorial(n) / (factorial(r) * factorial(n - r));
}

ll calcNumOfPermutation(ll n, ll r) { return factorial(n) / factorial(n - r); }

int main() {
  ll n, m;
  cin >> n >> m;
  if (abs(n - m) > 1) {
    cout << 0 << endl;
    return 0;
  }
  ll nc, mc;
  if ((n + m) % 2 == 0) {
    nc = calcNumOfPermutation(n, n);
    mc = calcNumOfPermutation(m, m);
    cout << 2 * (nc * mc) % mod << endl;
  } else {
    nc = calcNumOfPermutation(n, n);
    mc = calcNumOfPermutation(m, m);
    cout << nc * mc % mod << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int n;
    cin >> n;
    map<string, int> m;
    map<string, int>::iterator it;
    for(int i=0; i<n; i++){
        string tmp_s;
        cin >> tmp_s;
        if(m[tmp_s] == 0){
            m[tmp_s] = 1;
        }
        else{
            m[tmp_s] += 1;
        }
    }
    int max_n = 0;
    set<string> s;
    for(auto it = m.begin(); it!=m.end(); it++){
        if( (it->second) > max_n){
            max_n = it->second;
            s.clear();
            s.insert(it->first);
        }
        else if( (it->second) == max_n){
            s.insert(it->first);
        }
    }
    set<string>::iterator itr;
    for(auto itr=s.begin(); itr!=s.end(); itr++){
        cout << *itr << "\n";
    }
    return 0;
}

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

using namespace std;

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

    if(k == 1 && n == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    if(k == 1)
    {
        cout << 0 << endl;
        return 0;
    }

    int ans = k*pow(k-1,n-1);

    cout << ans << endl;
}

Measured memory_bytes: 384
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	const maxWord = (1 << 30)
	buf := []byte{}
	sc.Buffer(buf, maxWord)
	sc.Split(bufio.ScanWords)
}

func input() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	n, _ := strconv.Atoi(input())
	a := make([]int, n)
	b := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(input())
		b[i], _ = strconv.Atoi(input())
	}

	ans := 0
	for i := n - 1; i >= 0; i-- {
		rem := (a[i] + ans) % b[i]
		if rem != 0 {
			ans += b[i] - rem
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4736
#include <stdio.h>

int main() {
        int n, m;
        int i;
        int a[100];
        int nr_vote = 0;
        int nr_fav = 0;

        if (scanf("%3d %3d", &n, &m) == 0) {
                perror("scanf");
                return 1;
        }

        for (i = 0; i < n; i++) {
                if (scanf("%4d", &a[i]) == 0) {
                        perror("scanf");
                        return 1;
                }
        }

        for (i = 0; i < n; i++) {
                nr_vote += a[i];
        }

        for (i = 0; i < n; i++) {
                if (a[i] * 4 * m >= nr_vote) {
                        nr_fav++;
                }
        }

        if (nr_fav >= m) {
                printf("Yes\n");
        } else {
                printf("No\n");
        }

        return 0;
}


Measured memory_bytes: 128
use proconio::input;
use proconio::marker::Usize1;
use std::collections::BinaryHeap;
fn main() {
    input! {
        n: usize,
        es: [(Usize1, Usize1, i64); n-1],
        q: usize, k: Usize1,
        qs: [(Usize1, Usize1); q]
    };
    let mut edges: Vec<Vec<(usize, i64)>> = vec![Vec::new(); n];
    for (a,b,c) in es {
        edges[a].push((b,c));
        edges[b].push((a,c));
    }
    let inf = std::i64::MAX;
    let mut d = vec![inf; n];
    let mut heap = BinaryHeap::new();
    d[k] = 0;
    heap.push(((0, k)));
    while  !heap.is_empty() {
        let (dist, i) = heap.pop().unwrap();
        if d[i] < -dist {
            continue;
        } else {
        for &(j, w) in &edges[i] {
            if d[j] > d[i] + w {
                d[j] = d[i] + w;
                heap.push(((-d[j], j)));
            } else {}
        }}
    }
    for (x,y) in qs {
        println!("{}", d[x]+d[y]);
    }
}

Measured memory_bytes: 16792
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    a = LIR(3)
    n = II()
    c = [0] * 9
    for i in range(n):
        b = II()
        for i in range(3):
            for j in range(3):
                c[i * 3 + j] |= a[i][j] == b
    ans = (c[0] & c[1] & c[2]) | (c[3] & c[4] & c[5]) | (c[6] & c[7] & c[8])
    for i in range(3):
        ans |= c[i] & c[3 + i] & c[6 + i]
    ans |= c[0] & c[4] & c[8]
    ans |= c[2] & c[4] & c[6]
    print("Yes" if ans else "No")
    return



#main
if __name__ == '__main__':
    solve()


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

ll gcd(ll x, ll y){
	if(y==0) return x;
	else return gcd(y, x%y);
}

int main(){
	int N;
	ll K;
	cin >> N >> K;
	vector<ll> A(N);
	for(int i=0; i<N; i++) cin >> A[i];

	if(N==1) {
		if(A[0] == K) cout << "POSSIBLE" << endl;
		else cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	ll d = gcd(A[0], A[1]);
	for(int i=2; i<N; i++){
		d = gcd(d, A[i]);
	}

	for(int i=0; i<N; i++){
		if(A[i]==K || A[i]>K && (A[i]-K)%d==0){
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,sum=0;
  cin >>N;
  vector<int> a(N),b(N);
  for(int i=0;i<N;i++){
  cin >> a.at(i);
  }
  for(int i=0;i<N;i++){
  cin >> b.at(i);
  }   
  for(int i=0;i<N;i++){
  if (a.at(i) > b.at(i)){ 
    sum+=a.at(i)-b.at(i);
    
  } 
  }
  cout <<sum<<endl;

}

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

int main(){
  int N,a;
  cin >> N;
  vector<int> nums;
  rep(i,N){
    cin >> a;
    nums.push_back(a);
  }
  sort(nums.begin(),nums.end());
  bool ans = true;
  rep(i,N-1){
    if(nums.at(i) == nums.at(i+1)) ans = false;
  }
  puts(ans ? "YES" : "NO");
}
                   


Measured memory_bytes: 1400
use std::cell::Cell;

const MOD: i32 = 1000000007;

fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	let mut edges = vec![vec![]; n];
	for _ in 0..n - 1 {
		let a = s.next().unwrap().parse::<usize>().unwrap() - 1;
		let b = s.next().unwrap().parse::<usize>().unwrap() - 1;
		edges[a].push(b);
		edges[b].push(a);
	}
	let tree = Tree::new(edges);
	tree.dfs(0, std::usize::MAX);
	let y = tree.calc(0, std::usize::MAX);
	let x = mod_pow(tree.two_power[n] as i64, MOD as u32 - 2, MOD as i64);
	println!("{}", y as i64 * x % MOD as i64);
}

struct Tree {
	edges: Vec<Vec<usize>>,
	children: Vec<Cell<u32>>,
	two_power: Vec<i32>,
}

impl Tree {
	fn new(edges: Vec<Vec<usize>>) -> Tree {
		let n = edges.len();
		let pow: Vec<_> = (0..n + 1)
			.scan(1, |s, _| {
				let a = *s;
				*s = a * 2 % MOD;
				Some(a)
			})
			.collect();
		Tree { edges: edges, children: vec![Cell::new(0); n], two_power: pow }
	}

	fn dfs(&self, v: usize, p: usize) -> u32 {
		let mut c = 0;
		for e in self.edges[v].iter() {
			if *e == p {
				continue;
			}
			c += self.dfs(*e, v);
		}
		self.children[v].set(c);
		c + 1
	}

	fn calc(&self, v: usize, p: usize) -> i32 {
		let mut r = 0;
		let mut pat = 0;
		let mut csum = 0;
		for e in self.edges[v].iter() {
			if *e == p {
				continue;
			}
			r = (r + self.calc(*e, v)) % MOD;
			let c = self.children[*e].get() + 1;
			pat = (pat + self.two_power[c as usize] - 1) % MOD;
			csum += c;
		}
		let n = self.edges.len();
		pat = (pat + self.two_power[n - 1 - csum as usize] - 1 + 1) % MOD;
		pat = (self.two_power[n - 1] + MOD - pat) % MOD;
		(r + pat) % MOD
	}
}

fn mod_pow(a: i64, n: u32, m: i64) -> i64 {
	let mut r = 1;
	let mut a = a;
	let mut n = n;
	while n > 0 {
		if n & 1 != 0 {
			r = r * a % m;
		}
		a = a * a % m;
		n >>= 1;
	}
	r
}


Measured memory_bytes: 33908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define INF 1000000001

int main() {
    int n;
    cin >> n;
    vector<int> a(n);for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    int m=a[n-1];
    double b=m;
    b/=2;
    double c=INF;
    int x=-1;
    for(int i = 0; i < n; i++) {
        if(c>abs(a[i]-b)){
            c=abs(a[i]-b);
            x=i;
        }
    }

    cout << m << ' ' << a[x] << endl;

    return 0;
}

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

const int INF = 1001001001;

int main(){
  int mn10 = INF;
  int n;
  cin >> n;

  int sum = 0;
  rep(i, n){
    int in;
    cin >> in;
    sum += in;
    if(in % 10 != 0){
      mn10 = min(mn10, in);
    }
  }
  if(sum % 10 != 0) cout << sum << endl;
  else{
    if(mn10 == INF) cout << 0 << endl;
    else cout << sum-mn10 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
H = gets.chomp.to_i
W = gets.chomp.to_i
N = gets.chomp.to_i

if H > W
  if N%H ==0
    puts N.div(H)
  else
    puts N.div(H) +1
  end
else
  if N%W ==0
    puts N.div(W)
  else
    puts N.div(W)+1
  end
end

Measured memory_bytes: 1788
// AOJ 1240

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

// “aB23d” to “B23da”.
// 1文字←にずらす
string J(string str)
{
	string ret = str.substr(1);
	ret += str[0];
	return ret;
}

// “aB23d” to “daB23”.
// 一文字→にずらす
string C(string str)
{
	string ret; ret += str[str.length()-1];
	ret += str.substr(0, str.length()-1);
	return ret;
}

// “e3ac” to “ace3”, and “aB23d” to “3d2aB”.
// 真ん中で分けて swap
// bugbug
string E(string str)
{
	string ret;
	if (str.length() % 2 == 0){
		ret = str.substr(str.length()/2);
		ret += str.substr(0, str.length()/2);
	}
	else {
		ret = str.substr(((str.length()-1)/2) + 1);
		ret += str[str.length()/2];
		ret += str.substr(0, (str.length()-1)/2);
	}

	return ret;
}

// “aB23d” to “d32Ba”.
// 反転
string A(string str)
{
	string ret = str;
	reverse(ret.begin(), ret.end());
	return ret;
}

// “aB23d” to “aB34d”, and “e9ac” to “e0ac”.
// 1足す
string P(string str)
{
	string ret;
	for (int i = 0; i < str.length(); i++){
		if (isdigit(str[i])){
			if (str[i] == '9'){
				ret += '0';
			}
			else {
				ret += str[i] + 1;
			}
		}
		else {
			ret += str[i];
		}
	}
	return ret;
}

// “aB23d” to “aB12d”, and “e0ac” to “e9ac”.
// 1引く
string M(string str)
{
	string ret;
	for (int i = 0; i < str.length(); i++){
		if (isdigit(str[i])){
			if (str[i] == '0'){
				ret += '9';
			}
			else {
				ret += str[i] - 1;
			}
		}
		else {
			ret += str[i];
		}
	}
	return ret;
}

int main(void)
{
	int n;
	cin >> n;
	while (n--){
		string person, str;
		cin >> person >> str;
		reverse(person.begin(), person.end());
		// JCPEAM
		// puts("");
		for (int i = 0; i < person.length(); i++){
			if (person[i] == 'J') str = C(str);
			else if (person[i] == 'C') str = J(str);
			else if (person[i] == 'P') str = M(str);
			else if (person[i] == 'E') str = E(str);
			else if (person[i] == 'A') str = A(str);
			else if (person[i] == 'M') str = P(str);
			// cout << str << endl;
		}
		// puts("");
		cout << str << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int n,x; int i=0; int xxx=0;
cin >> n >> x;
vector<int> l(n);
while(i<n){
    cin >> l.at(i++); 
}
 
i=0;
while(xxx<=x){
    i++;
if(i<=n){
xxx += l.at(i-1);
}else{
    break;
}
}
cout << i << endl;
return 0;
}


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

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

    if (n % 2 == 0)
    {
        cout << n / 2 << endl;
    }
    else
    {
        cout << (n - 1) / 2 + 1 << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 
using namespace std;
int main()
{
    int y,m,d;
    while (~scanf("%d/%d/%d", &y,&m,&d)) {
        if (y<=2018 || y<=2019&&m<=4) {
            puts("Heisei");
        } else {
            puts("TBD");
        }
    }
    
    return 0;
}



Measured memory_bytes: 256
from itertools import product

bit = [0, 1]

lst = list(product(bit, repeat=10))

n = int(input())
F = [list(map(int, input().split())) for i in range(n)]
P = [list(map(int, input().split())) for j in range(n)]

res = -1 << 30
for v in lst:
	if v.count(0) == 10: continue
	fund = 0
	for i in range(n):
		cnt = 0
		for x in range(10):
			if F[i][x] == 1 and v[x] == 1:
				cnt += 1
		fund += P[i][cnt]
	res = max(res, fund)

print(res)

Measured memory_bytes: 42220
n = int(input())
v = [ list(map(int, input().split())) for _ in range(n) ]
dp = [ [0]*3 for _ in range(n) ]
for i in range(n):
  for j in range(3):
    if i == 0:
      dp[i][j] = v[i][j]
    else:
      for k in range(3):
        if j != k:
          dp[i][j] = max(dp[i][j], dp[i-1][k]+v[i][j])
print(max(dp[n-1]))

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

/*
(の方が多いやつを左に、)の方が多いやつを右に置きたい
(を一時的にたくさん必要とするやつが、
*/
typedef pair<int,int> P;
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  int n;cin>>n;
  int LL=0,RR=0;
  vector<P> vl,vr;//vl:)))((((((
  for(int i=0;i<n;i++){
    string s;cin>>s;
    int L,R,l=0,r=0;
    for(char p:s){
      if(p==')'){
        if(!r)l++;
        else r--;
      }
      else r++;
    }
    R=l;l=r=0;
    reverse(s.begin(),s.end());
    for(char p:s){
      if(p=='('){
        if(!r)l++;
        else r--;
      }
      else r++;
    }
    L=l;
    if(!R)LL+=L;
    else if(!L)RR+=R;
    else if(L>R)vl.push_back(P(R,L-R));
    else vr.push_back(P(L,R-L));
  }
  sort(vl.begin(),vl.end());
  sort(vr.begin(),vr.end());
  for(P p:vl){
    if(LL<p.first)fin("No");
    LL+=p.second;
  }
  for(P p:vr){
    if(RR<p.first)fin("No");
    RR+=p.second;
  }
  if(LL!=RR)fin("No");
  fin("Yes");
}


Measured memory_bytes: 5336
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

// BinaryIndexedTree(Fenwick-Tree); フェニック木
// ：BIT<long long> bit(xx)で初期化、bit.sum(n)で0~n番目までの累積和を計算
template<typename T> class BIT {
private:
    const long long n; vector<T> bit;
public:
    BIT(long long size) : n(size+1), bit(n, 0){}
    BIT(const vector<T>& v) : n((long long)v.size()+1), bit(n, 0){ for(long long i = 0; i < n-1; i++) add(i,v[i]); }
    T sum(long long i){ i++; T s = 0; while(i > 0){ s += bit[i], i -= i & -i; } return s; }
    void add(long long i, T x){ i++; while(i < n) bit[i] += x, i += i & -i; }
    void print(){ for(long long i = 0; i < n-1; i++) cout << sum(i)-sum(i-1) << (i != n-2 ? " " : "\n"); }
    void print_sum(){ for(long long i = 0; i < n; i++) cout << sum(i-1) << (i != n-1 ? " " : "\n"); }
};

int main(){
    Init();
    ll n, q;
    cin >> n >> q;
    vi c(n);
    rep(i, n){
        cin >> c[i];
        c[i]--;
    }

    // クエリの先読み
    vector<pair<pair<ll, ll>, ll>> rli(q);
    rep(i, q){
        ll l, r;
        cin >> l >> r;
        l--; r--;
        rli[i] = make_pair(make_pair(r, l), i);
    }

    // クエリを昇順に処理
    sort(all(rli));
    vi ans(q, 0);
    
    // 最も右にある玉を1、それ以外を0
    BIT<long long> bit(n);
    // 最も右のある位置を管理
    vi pos(n, -1);

    // クエリの答えは、(r-l+1)個から重複している個数を減算したもの（重複していないものを足し合わせたもの）    
    ll cur = 0;
    rep(i, q){
        ll l = rli[i].first.second;
        ll r = rli[i].first.first;
        ll Idx = rli[i].second;

        for(; cur <= r; cur++){
            // まだ未出現だったなら
            if(pos[c[cur]] == -1){
                bit.add(cur, 1);
                pos[c[cur]] = cur;
            }
            // すでに存在するなら
            else{
                bit.add(pos[c[cur]], -1);
                bit.add(cur, 1);
                pos[c[cur]] = cur;
            }
        }
        ans[Idx] = bit.sum(r) - bit.sum(l-1);
    }
    for(auto &num: ans) cout << num << endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> Vector;
typedef vector<vector<ll>> DVector;

#define fi          first
#define se          second
#define pb          push_back
#define INF         INT_MAX/3
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define dbg(x)      cout<<#x"="<<x<<endl
#define ub(x,y)     upper_bound(all(x),y)
#define lb(x,y)     lower_bound(all(x),y)
#define uni(x)      x.erase(unique(all(x)),x.end())
#define rep(i,n)    repl(i,0,n-1)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<int>())
#define mkp(x,y)    make_pair(x,y)

int main(){
  cin.sync_with_stdio(false);
  string num;
  cin >> num;
  cout << "ABC" << num << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++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 DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

map<pair<string, string>, int> mp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	REP(i, 1<<n){
		string t, u;
		REP(j, n){
			if((i>>j)&1){
				t+=s[j];
			}
		}
		FORR(j, 0, n){
			if((~i>>j)&1){
				u+=s[j];
			}
		}
		// DEBUG(t);
		// DEBUG(u);
		++mp[make_pair(t, u)];
	}
	reverse(ALL(s));
	ll ans=0;
	REP(i, 1<<n){
		string t, u;
		REP(j, n){
			if((i>>j)&1){
				t+=s[j];
			}
		}
		FORR(j, 0, n){
			if((~i>>j)&1){
				u+=s[j];
			}
		}
		// DEBUG(t);
		// DEBUG(u);
		if(mp.count(make_pair(t, u))){
			ans+=mp[make_pair(t, u)];
		}
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 46080
#include <iostream>
  #include <limits.h>
#define ll long long
  using namespace std;

  int main()
  {
    int n,W;

    cin>>n>>W;    // no. of elements and maxm. Weight
    ll v[n+1],w[n+1];   // array for value and weight 
    ll dp[n+1][100001];  // dp array with size n+1 and 10^5+1 (for v max value 1000, and for n 100)

    // Initializing arrays

    v[0]=1e17; w[0]=1e17;

    for (int i = 0; i < n+1; ++i)
    {
      for (int j = 0; j < 100001; ++j)
      {
        dp[i][j]=INT_MAX;      
      }
    }

    for (int i = 1; i < n+1; ++i){
      cin>>w[i]>>v[i];
    }
    
    dp[0][0]=0; // for 0 value, no value for weight

    for (int i = 1; i < n+1; ++i) 
    {
      dp[i][0]=0;
      
      for (int j = 0; j < 100001; ++j)
      {
        dp[i][j]=dp[i-1][j]; // excluding the element

        if(j-v[i]>=0){ 
          dp[i][j]=min(dp[i][j],w[i]+dp[i-1][j-v[i]]); // min of including and excluding element
        }
      }
    }

    // to find the max value for which weight is <=W
    for(int i=100000; i>=0; i--){
      if(dp[n][i]<=W){
        cout<<i; break;
      }
    }

    return 0;
  }

Measured memory_bytes: 82528
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		boolean answer = true;
		String[] A = new String[N];
		String[] B = new String[N];
		for(int i = 0;i < N;i++){
			A[i] = sc.next();
		}
		for(int i = 0;i < M;i++){
			B[i] = sc.next();
		}
		for(int i = 0;i < N-M+1;i++){
			for(int j = 0;j < N-M+1;j++){
				for(int k = 0;k < M;k++){
					for(int l = 0;l < M;l++){
						if(A[i+k].charAt(j+l)!=B[k].charAt(l)){
							answer = false;
							break;
						}
					}
				}
				if(answer == true){
					System.out.println("Yes");
					System.exit(0);
				}
				answer = true;
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 22228
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n, k;
    cin >> n >> k;
    cout << n - k + 1 << endl;
}

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

int main() {
 string s;
  int ans = 0;
  cin >> s >> ans;
  for(int i =0; i < 4; ++i){
  if(s.at(i) == '+') ++ans;
  if(s.at(i) == '-') --ans;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())

last_a = 0
last_b = 0
last_c = 0

for _ in range(N):
    a, b, c = map(int, input().split())
    last_a, last_b, last_c = a + max(last_b, last_c), b + max(last_c, last_a), c + max(last_a, last_b)

print(max(last_a, last_b, last_c))


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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

const lli mod = 1000000007;

lli n,x,y,z;
mat dp;

lli pow(lli x,lli r,lli mod = 1000000007){
  lli ret = 1;
  for(;r != 0;r >>= 1){
    if(r&1 != 0) ret *= x,ret %= mod;
    x *= x,x %= mod;
  }
  return ret;
}

int main(){
  cin >> n >> x >> y >> z;
  lli ub = 1ll << (x+y+z);
  dp = mat(n+1,vll(ub));
  lli c = (((1ll << x) | (1ll << x+y) | (1ll << x+y+z))) >> 1;
  // cout << bitset<32>(c) << endl;
  dp[0][0] = 1;
  for(lli i = 0;i < n;i++){
    for(lli j = 0;j < ub;j++){
      for(lli k = 1;k <= 10;k++){
        lli shift = ((j<<k)|(1ll<<(k-1)));
        if((c&shift) != c){
          dp[i+1][shift%ub] += dp[i][j];
          dp[i+1][shift%ub] %= mod;
        }
      }
    }
  }
  // for(lli i = 0;i < ub;i++){
  //   if(dp[n][i]) cout << bitset<64>(i) << " " << dp[n][i] << endl;
  // }
  cout << ((pow(10ll,n)-(accumulate(dp[n].begin(),dp[n].end(),0ll)%mod)+mod)%mod) << endl;
  return 0;

}


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

int main() {
	
	int n,m;
	cin>>n>>m;
	int heights[n];
	for(int i = 0; i < n; i++) cin>>heights[i];
	map<int, vector<int>> adjacencyList;
	map<int, int> maxHeight;
	for(int i = 0; i < m; i++) {
		int a, b;
		cin>>a>>b;
		adjacencyList[a].push_back(b);
		adjacencyList[b].push_back(a);
		if(maxHeight.find(a) == maxHeight.end()) {
			maxHeight[a] = heights[b-1];
		} else {
			maxHeight[a] = max(maxHeight[a], heights[b-1]);
		}
		if(maxHeight.find(b) == maxHeight.end()) {
			maxHeight[b] = heights[a-1];
		} else {
			maxHeight[b] = max(maxHeight[b], heights[a-1]);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(adjacencyList.find(i) == adjacencyList.end() || maxHeight[i] < heights[i-1])
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(){

  int n;

  while(cin>>n,n){

	int cnt=0;

	while(1){
	  if(n==1)
		break;
	  else if(n%2==0){
		cnt++;
		n=n/2;
	  }
	  else if(n%2==1){
		cnt++;
		n=n*3+1;
	  }
	  
	}

	cout<<cnt<<endl;
	
  }

}



Measured memory_bytes: 2992
n,k=map(int,input().split())
a=list(map(int,input().split()))

visited = [-1]*(n+1)
pos = 1
visited[pos] = 0
loop = 0
root=[1]
for i in range(1,n+1):
  pos = a[pos-1]
  if visited[pos] == -1:
    visited[pos] = i
    root.append(pos)
  else:
    loop = i - visited[pos]
    mae = visited[pos]
    break
if k < mae:
  print(root[k])
else:
  index=(k-mae)%loop
  print(root[index+mae])

Measured memory_bytes: 32372
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int w, h;
	P s, g;
	int map[][];

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			w = sc.nextInt();
			h = sc.nextInt();
			if( (w|h) == 0) break;
			map = new int[h+2][w+2];
			for(int[] a: map) fill(a, -1);
			for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) {
				int s = sc.nextInt();
				if( s == 2 ) {
					map[i][j] = 0;
					this.s = new P(j,i,0);
				}
				else if( s == 3 ) {
					map[i][j] = 0;
					this.g = new P(j, i, 0);
				}
				else map[i][j] = s;
			}
			System.out.println(bfs());
		}
	}
	int dx[] = {-1,0,1,0};
	int dy[] = {0,-1,0,1};
	
	int bfs() {
		LinkedList<Pair> que = new LinkedList<Pair>();
		Pair now = new Pair(s);
		que.add(now);
		for(;!que.isEmpty();) {
			now = que.removeFirst();
			if(isGoal(now.p)) return now.p.cnt;
			if(now.p.cnt == 10 ) continue;
			for(int i=0;i<4;i++) {
				if( !now.del.contains(new P(now.p.x + dx[i], now.p.y+dy[i], 0)) && (
						map[now.p.y+dy[i]][now.p.x+dx[i]] == -1 || map[now.p.y+dy[i]][now.p.x+dx[i]] == 1 ) )
					continue;
				int sdx = dx[i];
				int sdy = dy[i];
				while(  now.del.contains(new P(now.p.x+sdx, now.p.y+sdy, 0)) || ( 
						map[now.p.y+sdy][now.p.x+sdx] != -1 && map[now.p.y+sdy][now.p.x+sdx] != 1 ) ) {
					if(isGoal(now.p.x + sdx, now.p.y+sdy)) {
						que.addLast(new Pair( new P(now.p.x+sdx, now.p.y+sdy, now.p.cnt+1), now.del));
						break;
					}
					sdx += dx[i];
					sdy += dy[i];
				}
				if(map[now.p.y+sdy][now.p.x+sdx] == 1) {
					LinkedList<P> tmp = new LinkedList<P>(now.del);
					tmp.add(new P(now.p.x+sdx, now.p.y+sdy, 0));
					que.add(new Pair( new P(now.p.x+sdx-dx[i], now.p.y+sdy-dy[i], now.p.cnt+1), tmp));
				}
			}
		}
		
		return -1;
	}
	
	boolean isGoal(P p) {
		return p.x == g.x && p.y == g.y;
	}
	boolean isGoal(int x, int y) {
		return x == g.x && y == g.y;
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
	
	class Pair {
		LinkedList<P> del = new LinkedList<P>();
		P p;
		Pair( P p) {
			this.p = new P(p);
		}
		Pair (P p, LinkedList<P> del) {
			this.p = new P(p);
			for(P tmp: del) this.del.add(tmp);
		}
	}
	
	class P {
		int x, y, cnt;
		P(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
		P (P p) {
			x = p.x;
			y = p.y;
			cnt = p.cnt;
		}
		@Override
		public boolean equals(Object o) {
			if(o instanceof P) {
				P p = (P) o;
				return x == p.x && y == p.y;
			}
			return false;
		}
	}
}

Measured memory_bytes: 53000
#include <bits/stdc++.h>
#define fr first
#define se second
#define r_0 return 0
#define ll long long
#define pb push_back
using namespace std;

const long long INF = 1e7;
const long long N = 1e5+ 7;
const long long mod = 1e9 + 7;
const long double eps = 1E-7;

long double a, n, b, c = 1, d , cnt , m , ans;
string s , s1 , s2;
set<char>st;
ll used[N];
vector<int>v;
int main()
{
   /// freopen("symposium.in" ,"r" ,stdin);
///freopen("symposium.out" , "w" ,  stdout);
    ios_base::sync_with_stdio(0);
cin >> s >> s1;
cin >> n >> m;
cin >> s2;
if( s2 == s )
    n --;
else
    m --;
cout << n << " " << m;
}


Measured memory_bytes: 256
//#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
const int maxn = 3e5 + 33, mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void quit() {cout << "No"; exit(0);}
struct dsu {
	vi r, p;
	int k;
	void init(int n) {
		k = n;
		r.resize(n);
		p.resize(n);
		for(int i = 0; i <n ; i++) p[i] = i;
	}
	int par(int i) {
		if(i==p[i]) return i;
		return p[i] = par(p[i]);
	}
	void unite(int i, int j) {
		i = par(i), j = par(j);
		if(i==j) return;
		if(r[i] < r[j]) swap(i, j);
		p[j] = i;
		r[i] += r[i] == r[j];
		--k;
	}
	bool con(int i, int j) {return par(i) == par(j);}
};
ll n, m, q;
vpi a[2];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int x, b, c, i = 0; i < q; i++) {
		cin >> x >> b >> c;
		a[c].pb({x, b});
	}
	if(n==m+1) return cout << (a[1].empty()?"Yes":"No"), 0;
	dsu d;
	d.init(n);
	for(auto i : a[0]) d.unite(i.first, i.second);
	for(auto i : a[1]) if(d.con(i.first, i.second)) quit();
	ll M = n - d.k + d.k*1ll*(d.k-1)/2;
	cout << (m<=M?"Yes":"No");
}



Measured memory_bytes: 3564
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
{	
	int N, K;
	char S[60];

	cin >> N >> K >> S;

	if (S[K - 1] == 'A') S[K - 1] = 'a';
	else if (S[K - 1] == 'B') S[K - 1] = 'b';
	else if (S[K - 1] == 'C') S[K - 1] = 'c';

	cout << S;

	return 0;
}


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

const int N = 200010;
ll a[N];
bool vis[N];

vector<ll> vec;

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

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

    ll buffer = 1;

    for (int i = 0; i < n; i++) {
		vis[buffer] = 1;
        vec.push_back(buffer);
		buffer = a[buffer - 1];
        if (vis[buffer] == 1) {
            break;
        }
    }

    auto it = find(vec.begin(), vec.end(), buffer);

    ll Length = vec.end() - it;

    ll step = it - vec.begin();

    ll now;
    if (k > step) {
        now = (k - step) % Length;
    } else {
        now = (k - step);
    }
    printf("%lld\n", vec[step + now]);
}

Measured memory_bytes: 7020