akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...U>void _(const char*s,T h,U...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}//break continue pop_back
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...)
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}

int32_t main(){

    int x;
    cin>>x;
    cout<<3*x*x<<'\n';        

    return 0;
}


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

using namespace std;
const int mod = 1000000007;

int add(int a, int b)
{
	int c = a + b;
	if (c >= mod)c -= mod;
	return c;
}

int dif(int a, int b)
{
	int c = a - b;
	if (c < 0)c += mod;
	return c;
}

int mlt(int a, int b)
{
	long long c = a * 1LL * b;
	return c % mod;
}

int bp(int a, int b)
{
	if (b == 0)return 1;
	if (b % 2 == 0)
	{
		int val = bp(a, b / 2);
		return mlt(val, val);
	}
	if (b % 2 == 1)
	{
		int val = bp(a, b - 1);
		return mlt(val, a);
	}
}

int inv(int a)
{
	return bp(a, mod - 2);
}

int ibit(int mask, int i)
{
	return (mask >> i) % 2;
}

void outp(vector<vector<int>> &v)
{
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v[i].size(); j++)cout << v[i][j] << ' ';
		cout << endl;
	}
	cout << endl;
}
int main()
{
	long long a,b,v,w,t;
	cin>>a>>v>>b>>w>>t;
	if(w>=v)cout<<"NO"<<endl;
	else{
		long long dst=abs(a-b), mv=abs(v-w);
		if(mv*t>=dst)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
/*	int n, q;
	cin>>n>>q;
	vector<int>v(n),w(n);
	for(int i=0; i<n; i++)cin>>v[i]>>w[i];*/
}

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

int main(){
  string s;
  cin >> s;
  int a = s.length();
  rep(i,a) cout << 'x';
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var nx = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
            var n = (int)nx[0];
            var pi = new long[n];
            pi[0] = 1;
            var ai = new long[n];
            ai[0] = 1;
            for (var i = 1; i < nx[0]; i++)
            {
                pi[i] = pi[i - 1] * 2 + 1;
                ai[i] = ai[i - 1] * 2 + 3;
            }
            Console.WriteLine(F(ai, pi, n, nx[1]));
        }

        static long F(long[] all, long[] patties, int n, long x)
        {
            if (n == 0) return x <= 0 ? 0 : 1;
            else if (x <= 1 + all[n - 1]) return F(all, patties, n - 1, x - 1);
            else return patties[n - 1] + 1 + F(all, patties, n - 1, x - 2 - all[n - 1]);
        }
    }
}


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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int x = a, y = b, z = c; 
	if (a > b){
		a = y, b = x, x = a, y = b;
	}
	if (b > c){
		b = z, c = y, y = b, z = c;
	}
	if (a > b){
		a = y, b = x;
	}
	cout << a << " " << b << " " << c << endl;
	return 0;
}

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

using namespace std;

long long a,b,c,d,e,f,s,w;

int main()
{
	std::ios_base::sync_with_stdio(false);
	cin>>a>>b>>c>>d>>e>>f;
	w=min(a,b)*100;
	s=0;
	for (int i=0;i<=f/100;++i)
	{
		for (int j=0;j<=f/100;++j)
		{
			if ((i*a+j*b)*100>f) break;
			for (int k=0;k<=f;++k)
			{
				if ((i*a+j*b)*100+k*c>f) break;
				for (int l=0;l<=f;++l)
				{
					if ((i*a+j*b)*100+k*c+l*d>f) break;
					int wa=(i*a+j*b)*100,su=k*c+l*d;
					if (wa/100*e<su) continue;
					if ((wa+su)*s<(w+s)*su)
					{
						w=wa;
						s=su;
					}
				}
			}
		}
	}
	cout<<w+s<<' '<<s<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> muchie;

const ll NMAX = 61 * 200;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;

ll calc(ll x){
    ll z = sqrt(x);
    while(z * (z + 1) > x)
        z--;
    return z;
}

int main() {
    ll sum = 0,n,d = 2;
    cin >> n;
    while(d * d <= n){
        ll exp = 0;
        while(n % d == 0){
            n /= d;
            exp++;
        }
        ll rez = calc(exp * 2);
        sum += rez;
        d++;
    }
    if(n > 1){
        sum += calc(2);
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 3680
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> edge;
vector<ii> adjlist[100000];
vector<edge> edgelist;
int K = 0;
void dfs(int v, int p, int c) {
	int cnt = 1;
	for (ii i: adjlist[v]) {
		if (i.second == p) continue;
		if (cnt == c) ++cnt;
		edgelist[i.first].first = cnt;
		dfs(i.second, v, cnt++);
	}
}
int main() {
	int N, a, b;
	scanf("%d", &N);
	for (int i = 0; i < N - 1; ++i) {
		scanf("%d %d", &a, &b);
		adjlist[a - 1].push_back(ii(i, b - 1));
		adjlist[b - 1].push_back(ii(i, a - 1));
		edgelist.push_back(edge(0, ii(a - 1, b - 1)));
	}
	for (int i = 0; i < N; ++i) K = max(K, (int) adjlist[i].size());
	printf("%d\n", K);
	dfs(0, -1, 0);
	for (edge i: edgelist) printf("%d\n", i.first);
	return 0;
}

Measured memory_bytes: 9784
n = int(input())
lis = list(map(int,input().split()))
num = [0 for i in range(n)]
ans = 1
for nu in lis:
    if nu == 0:
        ans *= (3-num[0])
    else:
        ans *= (num[nu-1]-num[nu])
    ans %= 10 ** 9 + 7
    num[nu] += 1
print(ans)

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

inline long long read(){
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
const int m = 1e9 + 7;
long long n, k, ans;
int main(){
    n = read(), k = read();
    for (long long i = k; i <= n + 1; i++){
        unsigned long long s = (i - 1) * i >> 1;
        unsigned long long b = (n + n - i + 1) * i >> 1;
        //cout << i << ' ' << s << ' ' << b << endl;
        ans += (b - s + 1) % m;
        ans = ans % m;
    }
    cout << ans << endl;
    return 0;
}

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

#define pb         push_back

const int INF = 100000000;

int main(void) {
	while(1){
		int n;
		vector<int> vec;
		cin >> n;
		if(n == 0) break;

		for(int i=0; i<n; i++){
			int t;
			cin >> t;
			vec.pb(t);
		}
		sort(vec.begin(), vec.end());

		int ans = 0;
		for(int i=1; i<n-1; i++){
			ans += vec[i];
		}
		ans /= (n-2);

		cout << ans << endl;
	}

	
	return 0;
}

Measured memory_bytes: 1220
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] s = new String[n];
		long[] t = new long[n];
		for(int i = 0; i < n; i++) {
			s[i] = sc.next();
			t[i] = sc.nextLong();
		}
		String x = sc.next();
		boolean flag = true;
		long ans = 0;
		for(int i = 0; i < n; i++) {
			if(flag) {
				if(s[i].equals(x)) {
					flag = false;
				}
			} else {
				ans += t[i];
			}
		}
		System.out.println(ans);
	}

}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
	int N, K; cin >> N >> K;
	vector<ll> rem(K);
	REP(i, 1, N+1) rem[i%K]++;

	ll ans = 0;
	REP(a, 0, K) {
		int b = (K - a) % K;
		int c = (K - a) % K;

		if ((b+c)%K == 0)
			ans += rem[a] * rem[b] * rem[c];
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#pragma GCC optimize("O3")

#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/rope"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define f first
#define s second

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

struct custom_hash 
{
    static uint64_t splitmix64(uint64_t x) 
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const 
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    if(k > ((n - 2) * (n - 1))/2)
    {
        cout << "-1";
        return 0;
    }
    else
    {
        vector<pair<int, int>> res;
        FOR(i, 2, n + 1)
        {
            res.pb({1, i});
        }
        ll cnt = ((n - 1) * (n - 2))/2;
        vector<pair<int, int>> p;
        FOR(i, 2, n)
        {
            FOR(j, i + 1, n + 1)
            {
                p.pb({i,j});
            }
        }
        // cout << "\n";
        // F0R(i, sz(p)) cout << p[i].f << " " << p[i].s << "\n";
        F0R(i, cnt - k)
        {
            res.pb({p[i].f, p[i].s});
        }
        cout << sz(res) << "\n";
        F0R(i, sz(res)) cout << res[i].f << " " << res[i].s << "\n";
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100005
#define INF 1000000005
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 998244353;
int modPow(long long a, long long n) {
    if(n==0) return 1;
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}

long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算 COMinit()を先に使用すること
long long COM(int n, int k){
	if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    COMinit();
    ll ans=0;
    REP(i,n){
        if(n-1-i>k)continue;
        ll tmp=1;
        tmp=(ll)m*modPow((m-1),i);
        tmp%=MOD;
        tmp*=(ll)COM(n-1,i);
        tmp%=MOD;
        ans+=tmp;
        ans%=MOD;
    }
    OUT(ans);
    return 0;
}

Measured memory_bytes: 27032
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1e9 + 7

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

    int n;
    long long ans = 0;

    cin >> n;

    vector<int> a(n);

    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
        if(a[i]>i){ cout << "-1"; return 0; }
        if(i==0) continue;
        if(a[i]-a[i-1]>1){ cout << "-1"; return 0; }
        if(a[i]-a[i-1]==1) ans++;
        else ans+=a[i];
    }

    cout << ans;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T &a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T &a, T b) {
	a = std::min(a, b);
}

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)
			return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)
		return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i;
		res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)
		return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod ;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int> engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/

int n,m,lo,p;
int a[100005];
signed main() {
	cin>>n>>m>>lo>>p;
	rep(i,n)cin>>a[i];
	sort(a,a+n,greater<>());
	int ok=p-1,ng=n;
	int gen=a[p-1]-m;
	while(ng-ok>1){
		int mid=(ok+ng)/2;
		if(a[mid]<gen)ng=mid;
		else {
			int rem=(p-1+n-mid)*m;
			rep(i,n){
				if(i<p-1)continue;
				else if(i>=mid)continue;
				else {
					rem+=a[mid]+m-a[i];
				}
			}
			if(rem>=m*lo)ok=mid;
			else ng=mid;
		}
	}
	cout<<ok+1<<endl;
}


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

int main(void) {
  int n, c;
  cin >> n >> c;
  vector< vector< int > > d(c, vector< int >(c));
  vector< vector< int > > m(n, vector< int >(n));
  for (int i=0; i<c; ++i) {
    for (int j=0; j<c; ++j) cin >> d[i][j];
  }
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) cin >> m[i][j];
  }
  vector< vector< int > > a(3, vector< int >(c, 0));
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
      for (int k=0; k<c; ++k) a[(i+j)%3][k] += d[m[i][j]-1][k];
    }
  }
  int ans = a[0][0] + a[1][1] + a[2][2];
  for (int i=0; i<c; ++i) {
    for (int j=0; j<c; ++j) {
      for (int k=0; k<c; ++k) {
        if (i==j || j==k || k==i) continue;
        ans = min(ans, a[0][i] + a[1][j] + a[2][k]);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
  int A, B, C;

  cin >> A >> B >> C;

  if (A == B) {
    cout << C << endl;
  } else if (A == C) {
    cout << B << endl;
  } else {
    cout << A << endl;
  }
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

int[][10^^5] G;
bool[3][10^^5] F;

alias S = Tuple!(int, "p", int, "c");

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];
    foreach (_; 0..M) {
        auto uv = readln.split.to!(int[]);
        G[uv[0]-1] ~= uv[1]-1;
    }
    auto st = readln.split.to!(int[]);
    auto S = st[0]-1;
    auto T = st[1]-1;

    auto ss = [S];
    F[S][0] = true;
    int c;
    while (!ss.empty) {
        ++c;
        int[] nss;
        foreach (s; ss) {
            foreach (n; G[s]) {
                if (F[n][c%3]) continue;
                F[n][c%3] = true;
                if (c % 3 == 0 && n == T) {
                    writeln(c/3);
                    return;
                }
                nss ~= n;
            }
        }
        ss = nss;
    }
    writeln(-1);
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back
pii p[100005];
int x[100005], y[100005];
int r[100005];
int root(int a){
    return r[a] == a?a:(r[a]=root(r[a]));
}
void merge(int a, int b){
    a = root(a), b = root(b);
    if(a != b) r[a] = b;
}
int main(){
    int n;
    scanf("%d", &n);   
    for(int i=1;i<=n;i++){
        scanf("%d%d", &x[i], &y[i]);
        p[i] = pii(x[i], i);
        r[i] = i;
    }
    sort(p+1, p+1+n);
    vector<pipii> edges;
    for(int i=2;i<=n;i++) edges.eb(pipii(p[i].fi-p[i-1].fi, pii(p[i].se, p[i-1].se)));
    sort(all(edges));
    for(int i=1;i<=n;i++) p[i] = pii(y[i], i);
    sort(p+1, p+1+n);
    for(int i=2;i<=n;i++) edges.eb(pipii(p[i].fi-p[i-1].fi, pii(p[i].se, p[i-1].se)));
    sort(all(edges));
    int ans = 0;
    for(int i=0;i<sz(edges);i++){
        if(root(edges[i].se.fi) != root(edges[i].se.se)){
            merge(edges[i].se.fi, edges[i].se.se);
            ans += edges[i].fi;
        }
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 6772
#include <bits/stdc++.h>
#define LL __int128
#define ll long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PII pair<int, int>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
ll POW(ll a, ll b){
	ll ans = 1;
	b %= (mod - 1);
	while(b){
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll inv(ll a){
	return POW(a, mod - 2);
}
ll fac[maxn], ifac[maxn];
void init(){
	fac[0] = fac[1] = 1;
	for(int i = 2; i < maxn; i ++) fac[i] = fac[i - 1] * i % mod;
	ifac[maxn - 1] = inv(fac[maxn - 1]);
	for(int i = maxn - 2; i >= 0; i --) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
ll getc(int n, int m){
	if(n < m || m < 0) return 0;
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main(){
	int n;
	cin >> n;
	init();
	if(n == 1) cout << 0 << endl;
	else if(n == 2) cout << 2 << endl;
	else{
		ll ans = POW(10, n);
		ans = (ans + mod - POW(8, n)) % mod;
		ll res = 1;
		for(int i = 1; i <= n; i ++){
			res = (res + getc(n, i) % mod * POW(8, n - i) % mod) % mod;
		}
		ans = (ans + mod - res * 2 % mod) % mod;
		cout << (ans + 2) % mod << endl; 

	}
	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<string> s(N);
  REP(i, N) cin >> s[i];

  int M;
  cin >> M;
  vector<string> t(M);
  REP(i, M) cin >> t[i];

  int ans = 0;
  for(int i = 0; i < N; i++) {
    int sum = 0;
    for(int j = 0; j < N; j++) {
      if(s[i] == s[j]) sum++;
    }
    for(int k = 0; k < M; k++) {
      if(s[i] == t[k]) sum--;
    }
    ans = max(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

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

bool OK[10];
int main(){
	for(int i=0;i<10;i++){
		OK[i]=true;
	}

	int n;	cin>>n;
	int k;	cin>>k;
	for(int i=0;i<k;i++){
		int x;	cin>>x;
		OK[x]=false;
	}


	for(int i=n;i<100000;i++){
		int x=i;
		bool flag=true;
		while(x>0){
			int d=x%10;
			if(OK[d]==false){
				flag=false;
				break;
			}
			x/=10;
		}

		if(flag){
			if(n<=i){
				cout<<i<<endl;
				return 0;
			}
		}
	}

	return 0;
}


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

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define mp make_pair
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(s) s.begin(),s.end()
#define vll vector<ll>
#define vi vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define vd vector<double>
#define vull vector<ull>
#define vc vector<char>
#define vs vector<string>
#define fi first
#define se second
#define sz(x) x.size()
#define cinarr(n,a) for(int i = 0; i < n; i++) cin >> a[i];
#define coutarr(n,a) for(int i = 0; i < n; i++) cout << a[i] << (i+1==n?'\n':' ');
#define fori(i,a,b,x) for(int i = a; i <= b; i+=x)
#define ford(i,a,b,x) for(int i = a; i >= b; i-=x)
#define tc int t; cin >> t; for(int cs = 1; cs <= t; cs++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL);
#define ld long double
#define reset(x,y) memset(x,y,sizeof x);
#define sqr(x) 1LL*(x)*(x)
#define cube(x) 1LL*(x)*(x)*(x)
#define ub(v, a) upper_bound(all(v), a)
#define lb(v, a) lower_bound(all(v), a)
#define EPS 1e-10
#define INF 2000000000
#define mod 1000000007
#define minof(a) min_element(all(a))
#define maxof(a) max_element(all(a))
#define debug(val) cerr << "The value of " << #val << " is = " << val << endl;
#define testing cerr << "--------------------------\n";

//input space ---> scanf("%[^\n]%*c",s);

string s,t,res="";
int dp[3005][3005];

int main() {
	IOS
	cin >> s >> t;
	int n = sz(s),m = sz(t);
	fori(i,0,n,1) {
		fori(j,0,m,1) {
			if(i == 0 or j == 0) {
				dp[i][j] = 0;
			} else if(s[i-1] == t[j-1]) {
				dp[i][j] = 1+dp[i-1][j-1];
			} else {
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	string res="";
	int i=n,j=m;
	while(i != 0 and j != 0) {
		if(s[i-1] == t[j-1]) {
			res = s[i-1]+res;
			i--;
			j--;
		} else if(dp[i-1][j] >= dp[i][j-1]) {
			i--;
		} else {
			j--;
		}
	}
	cout << res << endl;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, long long K, std::vector<long long> H){
    sort(ALL(H));
    cout << accumulate(H.begin(), H.begin() + max(0LL, N - K), 0LL) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> H(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&H[i]);
    }
    solve(N, K, std::move(H));
    return 0;
}


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

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

  int n,m;
  cin >> n >> m;

  int dig[n];
  rep(i, n) {
    dig[i] = -1;
  }

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

  rep(i, m) {
    int s,c;
    cin >> s >> c;
    if(dig[n-s] != -1 && dig[n-s] != c) {
      cout << -1 << endl;
      return 0;
    }
    dig[n-s] = c;
  }

  int ans = 0;
  rep(i, n) {
    if(dig[i] > 0) {
      ans += dig[i] * int(pow(10, i));
    }
    if(dig[i] == -1 && (i+1) == n) {
      ans += int(pow(10, i));
    }
    if(dig[i] == 0 && (i+1) == n && n != 1) {
      cout << -1 << endl;
      return 0;
    }
  }

  if(ans == 0 && n != 1) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 256
use std::io::{stdin, Read};

macro_rules! parse {
    ($iter: ident) => {
        $iter.next().unwrap().parse().unwrap()
    };
    ($iter: ident,2) => {
        (parse!($iter), parse!($iter))
    };
    ($iter: ident,3) => {
        (parse!($iter), parse!($iter), parse!($iter))
    };
    ($iter: ident,4) => {
        (parse!($iter), parse!($iter), parse!($iter), parse!($iter))
    };
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut iter = s.split_whitespace();
    let (m, k) = parse!(iter, 2);
    if m == 0 {
        if k == 0 {
            print!("0 0");
            return;
        } else {
            print!("-1");
            return;
        }
    }
    if m == 1 {
        if k == 0 {
            print!("0 0 1 1");
            return;
        } else {
            print!("-1");
            return;
        }
    }
    if k >= 2usize.pow(m) {
        print!("-1");
        return;
    }
    let mut b = vec![];
    for i in (0..(2usize.pow(m))) {
        if i == k {
            continue;
        }
        b.push(i);
    }
    for &i in &b {
        print!("{:} ", i);
    }
    print!("{:} ", k);
    b.reverse();
    for i in b {
        print!("{:} ", i);
    }
    print!("{:}", k);
}


Measured memory_bytes: 5884
#include<iostream>
using namespace std;
const int inf=1e8;
int memo[20000+1][256];

void hoge(int N, int M){

   int c[M];
   for(int i=0; i<M; i++) cin>> c[i];
   int x[N];
   for(int i=0; i<N; i++) cin>> x[i];
   for(int i=0; i<N+1; i++){
      for(int j=0; j<256; j++){
         memo[i][j]=inf;
      }
   }

   memo[0][128]=0;
   for(int i=0; i<N; i++){
      for(int j=0; j<256; j++){
         if(memo[i][j]==inf) continue;
         for(int k=0; k<M; k++){
            int p=max(0, min(255, j+c[k]));
            memo[i+1][p]=min(memo[i][j]+(p-x[i])*(p-x[i]), memo[i+1][p]);
         }
      }
   }
   int mi=1e8;
   for(int j=0; j<256; j++) mi=min(mi, memo[N][j]);
   cout<< mi<< endl;

}


int main(){

   while(1){
      int N, M;
      cin>> N>> M;
      if(!(N||M)) break;
      hoge(N, M);
   }
   return 0;
}

Measured memory_bytes: 23080
use std::io::stdin;

fn read_int() -> i32 {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().parse().unwrap()
}

fn main () {
    let mut n = read_int() as i64;

    let mut base2 = 1 as i64;
    let mut basem2 = 1 as i64;

    let mut digits: Vec<i32> = vec![];

    for _bit in 0..35 {
        if n & base2 != 0 {
            n -= basem2;
            digits.push(1);
        } else {
            digits.push(0);
        }

        base2 *= 2;
        basem2 *= -2;
    }

    digits.reverse();

    let mut seen = false;
    for &digit in digits.iter() {
        if digit == 1 {
            seen = true;
        }
        if seen {
            print!("{}", digit);
        }
    }
    if seen {
        println!();
    } else {
        println!("0");
    }
}

/*
base2, base -2
00001 = 00001  1
00010 = 00110  2
00100 = 00100  4
01000 = 11000  8
10000 = 10000 16
*/

Measured memory_bytes: 4352
using System;
public class Simple {
    public static void Main() { new Simple().Solve(); }
    char[] s;
    int K;
    void Solve() {
        //input
        s = Console.ReadLine().ToCharArray();
        K = int.Parse(Console.ReadLine());

        for(int i = 0; i < s.Length; ++i) {
            if (s[i] != 'a' && ('z' - s[i] + 1) <= K) {
                K -= 'z' - s[i] + 1;
                s[i] = 'a';
            }
        }
        int last = s[s.Length - 1] + K % 26;
        if (last > 'z') last -= 26;
        s[s.Length - 1] = (char)last;
        //res
        Console.WriteLine(new string(s));
    }
}

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

int main() {
  int n, y;
  cin >> n >> y;
  if (10000 * n < y) {
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n - i; j++)
      if (10000 * i + 5000 * j + 1000 * (n - i - j) == y) {
        cout << i << " " << j << " " << n - i - j << endl;
        return 0;
      }
  cout << -1 << " " << -1 << " " << -1 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int x,y,z,Max=0;
    scanf("%d%d%d",&x,&y,&z);
    int ans=x+y+z;
    if(Max<x)
        Max=x;
    if(Max<y)
        Max=y;
    if(Max<z)
        Max=z;
    printf("%d\n",ans-Max);
    return 0;
}


Measured memory_bytes: 128
N = int(input())
t = []
y = []
for i in range(N):
  t.append(int(input()))
t.append(1)
  
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	return a * b // gcd (a, b)

for j in range(N):
  t[j+1] = lcm(t[j],t[j+1])
  
print(t[N])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb emplace_back
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<ii> vii;

int a, b, c;
int dis[100][100][100];
queue<tuple<int, int, int>> q;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> a >> b >> c;
	memset(dis, -1, sizeof(dis));
	dis[a][b][c] = 0;
	q.emplace(a, b, c);

	while (q.size()) {
		tie(a, b, c) = q.front();
		q.pop();

		if (a == b && b == c) {
			cout << dis[a][b][c] << endl;
			return 0;
		}

		if (a < 100 && b < 100 && dis[a+1][b+1][c] == -1) {
			dis[a+1][b+1][c] = dis[a][b][c] + 1;
			q.emplace(a+1, b+1, c);
		}

		if (a < 100 && c < 100 && dis[a+1][b][c+1] == -1) {
			dis[a+1][b][c+1] = dis[a][b][c] + 1;
			q.emplace(a+1, b, c+1);
		}

		if (b < 100 && c < 100 && dis[a][b+1][c+1] == -1) {
			dis[a][b+1][c+1]= dis[a][b][c] + 1;
			q.emplace(a, b+1, c+1);
		}

		if (a < 100 && dis[a+2][b][c] == -1) {
			dis[a+2][b][c] = dis[a][b][c] + 1;
			q.emplace(a+2, b, c);
		}

		if (b < 100 && dis[a][b+2][c] == -1) {
			dis[a][b+2][c] = dis[a][b][c] + 1;
			q.emplace(a, b+2, c);
		}

		if (c < 100 && dis[a][b][c+2] == -1) {
			dis[a][b][c+2] = dis[a][b][c] + 1;
			q.emplace(a, b, c+2);
		}
	}

	return 0;
}

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

using namespace std;
using ll = long long int;
using lc = complex<double>;

template<typename T>
struct Convex {
    using P = complex<T>;
    ll n;
    vector<ll> conv;
    vector<P> v;

    T cross(P a, P b) {
        return (a * conj(b)).imag();
    }

    Convex(const vector<P> &_v) {
        // incremental method
        n = _v.size();
        v = _v;

        auto comp = [&](P a, P b) {
            return make_tuple(real(a),imag(a)) < make_tuple(real(b), imag(b));
        };
        sort(v.begin(), v.end(), comp);

        conv.resize(n+1);
        ll k = 0;
        for(ll i=n-1; i>=0; conv[k++] = i--) // up
            while(k>=2 && cross(v[i] - v[conv[k-1]], v[conv[k-2]] - v[conv[k-1]]) > 0) k--;
        for(ll i=1, t=k+1; i<n; conv[k++] = i++) // dn
            while(k>=t && cross(v[i] - v[conv[k-1]], v[conv[k-2]] - v[conv[k-1]]) > 0) k--;
        conv.resize(k-1);
    }

    P operator[](ll i) {
        return v[conv[i]];
    }
    ll size() {
        return conv.size();
    }

    double diam() {
        ll i = 0, j;
        j = find(conv.begin(), conv.end(), n-1) - conv.begin();
        T res = norm((*this)[i] - (*this)[j]);
        for(ll k=0; k<10*n; k++) {
            if(cross((*this)[(i+1)%size()] - (*this)[i], (*this)[(j+1)%size()] - (*this)[j]) >= 0)
                j = (j+1) % size();
            else
                i = (i+1) % size();
            res = max(res, norm((*this)[i] - (*this)[j]));
        }
        return sqrt(res);
    }
};

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    constexpr double PI = acos(-1);
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;

    vector<complex<ll>> a(n);
    for(ll i=0; i<n; i++) {
        ll x, y;
        cin >> x >> y;
        a[i] = complex<ll>(x, y);
    }
    Convex<ll> cva(a);

    ll k = 0;
    for(ll i=0; i<cva.size(); i++) {
        tuple<ll,ll> pi = make_tuple(imag(cva[i]), real(cva[i]));
        tuple<ll,ll> pk = make_tuple(imag(cva[k]), real(cva[k]));
        if(pi < pk) k =i;
    }

    cout << cva.size() << endl;
    for(ll t=0; t<cva.size(); t++)
        cout << real(cva[(k+t)%cva.size()]) << ' ' << imag(cva[(k+t)%cva.size()]) << endl;
}



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

int main(){
    int N;
    cin >> N;
    int dp[100001][3];
    rep(i, 3) dp[0][i] = 0;
    for (int i = 1; i <= N; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        dp[i][0] = a + max(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = b + max(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = c + max(dp[i - 1][1], dp[i - 1][0]);
    }
    cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << endl;
}

Measured memory_bytes: 4728
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define tc(t) for (int tc=1; tc<=t; tc++)
typedef vector<int> VI;
typedef vector<long long int> VLLI;
typedef vector<pair<int, int> > VPI;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll, ll> PLL;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll modInverse (ll a) {ll p = mod - 2; return powmod(a, p);}
// head

int main() {
    ll n;
    cin >> n;
    unordered_set<ll> data;
    for (ll i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            data.insert(i);
            data.insert(n/i);
        }
    }
    data.insert(n);

    ll ans = 0, temp;
    for (auto x : data) {
        temp = n;
        while (temp%x == 0)
            temp/=x;
        ans += (temp%x == 1);
    }
    data.clear();

    for (ll i = 2; i*i <= (n-1); i++) {
        if ((n-1)%i == 0) {
            data.insert(i);
            data.insert((n-1)/i);
        }
    }
    if (n-1 > 1)
        data.insert(n-1);
    ans += data.size();
    cout << ans << "\n";
}



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

using namespace std;

int main() {
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  vector<int> mins(n, m);
  for (int i = 0; i < q; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    mins[x] = min(mins[x], y);
  }
  int right = 0;
  for (int i = 1; i < n; ++i) {
    if (right >= mins[i]) {
      printf("%d\n", i);
      return 0;
    }
    if (right + 1 < mins[i]) {
      ++right;
    }
  }
  printf("%d\n", n);
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a,b;
    char op;
    
    scanf("%d %c %d",&a,&op,&b);
    
    while(op != '?') {
        if(op == '+') {
            printf("%d\n",a+b);
        } else
            if(op == '-') {
            printf("%d\n",a-b);
        } else
            if (op == '*'){
            printf("%d\n",a*b);
        } else
            if(op == '/') {
            printf("%d\n",a/b);
        }
        scanf("%d %c %d",&a ,&op, &b);
        
    }
    return 0;
}



Measured memory_bytes: 2100
#include <iostream>
#include <vector>

int main() {
    int N;
    std::cin >> N;

    std::vector<int> A;
    for (int i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        A.push_back(a);
    }

    int result = 0;
    while (true) {
        if (std::all_of(A.begin(), A.end(), [](int a) {
            return a % 2 == 0;
        })) {
            std::transform(A.begin(), A.end(), A.begin(), [](int a) {
                return a / 2;
            });
            ++result;
        } else {
            break;
        }
    }

    std::cout << result << std::endl;

    return 0;
}

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

int main()
{
	int a,b,c;
	int countr=0;
	int countb=0;
	string Sin;
	cin>>a;
	cin>>Sin;
	for(int i=0;i<a;i++)
	{
		if(Sin[i]=='R')
		countr++;
		else
		countb++;
	}
	if(countr>countb)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u; return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


void Main() {
	int N, M;
	vint digit(3, -1);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int s, c;
		cin >> s >> c; --s;
		if (digit[s] != -1 && c != digit[s]) {
			cout << -1 << endl;
			return;
		}
		digit[s] = c;
	}
	if (N > 1) {
		if (digit[0] == 0) {
			cout << -1 << endl;
			return;
		}
		if (digit[0] == -1) {
			digit[0] = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (digit[i] == -1) {
			cout << 0;
		} else {
			cout << digit[i];
		}
	}
	cout << el;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#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
using namespace std;
int a, b, c, d, m, n, ans;
int ar[234567];
string s;
bool b1, b2;
signed main() {
	cin >> m >> n;
	for1(i, n)cin >> ar[i];
	if (m == 2) {
		int ans1 = 0, ans2 = 0;
		for1(i, n) {
			if (ar[i] % 2 == i % 2) {
				ans1++;
			}
			else ans2++;
		}
		cout << min(ans1, ans2) << endl;
	}
	else {
		for1(i, n) {
			if (i > 1 && ar[i] == ar[i - 1]) {
				ans++; i++;
			}
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 3948
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;


int main () {

  ll N, K;
  cin >> N;
  cin >> K;
  vector<double> p;
  double temp;
  double kitai;
  REP(i, 0, N) {
    cin >> temp;
    kitai = (1.0 + temp) / 2.0;
    p.push_back(kitai);

    //debug
    // cout << kitai << " ";
  }
  // cout << endl;

  double first_kitai = 0;
  REP(i, 0, K) {
    // cout << "hoge" << endl;
    // cout << p[i] << endl;
    first_kitai += p[i];
  }

  // cout << "first_kitai: " << first_kitai << endl;

  // compare kitai
  double max_kitai = first_kitai;
  double current_kitai = first_kitai;
  REP(i, 1, N - K + 1) {
    current_kitai = current_kitai - p[i-1] + p[K+i-1];
    if (max_kitai < current_kitai) {
      max_kitai = current_kitai;
    }
  }

  cout << fixed << setprecision(2) << max_kitai << endl;

  return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>

using namespace std;

int main(){

	int h,w;
	cin >> h >> w;
	char masu[h][w];
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> masu[i][j];
		}
	}
	for(int i = 0; i < h; i++){
		for(int k = 0; k < 2; k++){
			for(int j = 0; j < w; j++){
				cout << masu[i][j];
			}
			cout << '\n';
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define int long long
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int mod=1000000007;
ll f[100];
set<PI> s[100];
vector<PI> ycl[100];
void dfs(int x,int a,int b){
	if(x>=90)return; 
	//if(x<=4)cout<<x<<" "<<a<<" "<<b<<endl;
	if(a+b>f[x+3])return;
	ycl[x].push_back(mp(b,a));
	dfs(x+1,b,b+a); dfs(x+1,b,b*2+a); //dfs(x+1, b,b*3+a);
}
signed main(){
	f[0]=0; f[1]=1;
	for(int i=2;i<100;i++){
		f[i]=f[i-1]+f[i-2];
	}
	ycl[1].push_back(mp(1,0));
	dfs(2,1,2); dfs(2,1,3);
	int q=read();
	for(int i=1;i<=q;i++){
		ll x=read(),y=read(),ans=0,tot=0;
		if(x<y)swap(x,y);
		for(int i=1;i<=100;i++)if(f[i]>y||f[i+1]>x){
			ans=i-2; break;
		}
		if(y==1){
			write(1); putchar(' '); writeln(x%mod); continue;
		}
		for(unsigned i=0;i<ycl[ans].size();i++){
			if(ycl[ans][i].first<=x&&ycl[ans][i].first+ycl[ans][i].second<=y)tot=(tot+(y-ycl[ans][i].second)/ycl[ans][i].first)%mod;
			if(ycl[ans][i].first<=y&&ycl[ans][i].first+ycl[ans][i].second<=x)tot=(tot+(x-ycl[ans][i].second)/ycl[ans][i].first)%mod;
			//if(ans==4)cout<<ycl[ans][i].first<<" jb d "<<ycl[ans][i].second<<" "<<tot<<endl;
		}
		write(ans); putchar(' '); writeln(tot);
	}
}
/*
1
5 1000000000000000000
*/

Measured memory_bytes: 4096
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#include<set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<n; i++)
#define per(i, n) for(int i=n-1; i>=0; i--)
#define reps(i, n) for(int i=1; i<n; i++)
#define pers(i, n)  for(int i=n-1; i>=1; i--)

const int INF = 1001001001;

void solve(){
  int N;  cin >> N;
  string S; cin >> S;
  ll ok = 0;
  ll ng = 0;
  map<char, ll> mp;
  for(int i=0; i<N; i++)  mp[S[i]]++;
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      if((i+j)%2==1)  continue;
      if(S[i]!=S[j] && S[j]!=S[(i+j)/2] && S[(i+j)/2]!=S[i])  ng++;
    }
  }
  ok = mp['R']*mp['G']*mp['B'];
  cout << ok-ng << endl;
}

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


Measured memory_bytes: 3608
<?php 
  
//fscanf(STDIN,"%s%s",$s,$t);
fscanf(STDIN,"%s",$s);

$len=strlen($s);
$alive=array();
$alive[0]=$s[0];
$c=0;
for($i=1;$i<$len;$i++){
 // echo end($alive)." ".$s[$i]."\n";
  if(count($alive)==0){
    $alive[]=$s[$i];
  }elseif(end($alive)==$s[$i]){
    $alive[]=$s[$i];
   }else{
    $c++;
    array_pop($alive);
  }
}

echo ($c*2)."\n";


Measured memory_bytes: 12792
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
n, d = map(int, input().split())
if n % (2*d + 1) == 0:
  ans = n // (2*d + 1)
else:
  ans = n // (2*d + 1) + 1
# 出力
print(ans)

Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;

// #define int long long
struct Fast { Fast(){ std::cin.tie(0); std::cout.tie(0); ios::sync_with_stdio(false); }} fast;

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

int h, w;
vector<vector<int>> g;

map<tuple<int, int, int, int>, int> mem; // (y, x, dy, dx) -> val

vector<vector<vector<int>>> m;

int f(int y, int x, int dy, int dx) {
  int val;

  int d = 0;
  if (dx == 1 && dy == 0) d = 1;
  if (dx == 0 && dy == -1 ) d = 2;
  if (dx == -1 && dy == 0) d = 3;

  if (m[y][x][d] != -1) {
    return m[y][x][d];
  } else {
    if (y + dy < 0 || y + dy >= h || x + dx < 0 || x + dx >= w) 
      val = 0;
    else if (g[y + dy][x + dx] != 0) val = 0;
    else val = 1 + f(y + dy, x + dx, dy, dx);
    m[y][x][d] = val;
  }
  return val;

}

signed main(void) {

  int num;
  cin >> h >> w;
  g = vector<vector<int>>(h);
  for (auto it = g.begin(); it != g.end(); ++it) {
    string s; cin >> s;
    (*it) = vector<int>(w, 0);
    for (int i = 0; i < w; ++i) {
      if (s[i] == '#') (*it)[i] = 1;
    }
  }

  m = vector<vector<vector<int>>>(h);
  for (auto y = m.begin(); y != m.end(); ++y) {
    *y = vector<vector<int>>(w);
    for (auto x = (*y).begin(); x != (*y).end(); ++x) {
      *x = vector<int>(4, -1);
    }
  }
  
  num = 0;
  for (int y = 0; y < h; ++y) {
    for (int x = 0; x < w; ++x) {
      if (g[y][x] != 0) continue;

      int tmp = 1;
      tmp += f(y, x, -1 , 0);
      tmp += f(y, x, 0, -1);
      tmp += f(y, x, 0 , 1);
      tmp += f(y, x, 1, 0);

      // cout << x << ", " << y << ": " << tmp << endl;
      num = max(num, tmp);
      
    }
  }

  cout << num << endl;
  
}


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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    long long k;
    cin >> n >> k;

    vector<long long> arr;

    for(int i = 0; i < n; ++i){
        long long j;
        cin >> j;
        arr.push_back(j);
        if(j == k){
            cout << "POSSIBLE";
            return 0;
        }
    }

    sort(arr.begin(), arr.end());

    long long gcd = arr[0];

    for(int i = 1; i < n; ++i){
        gcd = GCD(arr[i], gcd);
    }

    if(k % gcd == 0 && k <= arr[n - 1]){
        cout << "POSSIBLE";
    } else {
        cout << "IMPOSSIBLE";
    }

    return 0;
}


Measured memory_bytes: 1400
d1,n=map(int,input().split())
if d1==0:
	i=0
	d=0
	while i<n:
		d+=1
		if d%100!=0:
			i+=1
	print(d)
if d1==1:
	i=0
	d=0
	while i<n:
		d+=100
		if d%100==0 and d%10000!=0:
			i+=1
	print(d)
if d1==2:
	i=0
	d=0
	while i<n:
		d+=10000
		if d%10000==0 and d%1000000!=0:
			i+=1
		#d+=10000
	print(d)



Measured memory_bytes: 3064