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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define MOD 1000000007

int main()

{

    string s, t;
    cin >> s >> t;
    string in = s;
    while(1)
    {

        char c = s[s.size()-1];
        for(ll i = s.size()-1; i >= 1; i--) s[i] = s[i-1];
        s[0] = c;
        if(s==t)
        {

            cout << "Yes";
            return 0;
        }
        if(s==in) break;
    }
    cout << "No";
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a,b,c = LI()
if a <= c <= b:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int n;
void init(){
    n = read();
}
void solve(){
    ll x = read(), y = read();
    ll maxi1 = x + y, mini1 = x + y;   // plus
    ll maxi2 = x - y, mini2 = x - y;   // minus
    ll ans = LLONG_MIN;
    --n;
    while (n--){
        x = read(), y = read();
        ans = max(ans, (x + y) - mini1);
        ans = max(ans, maxi1 - (x + y));
        mini1 = min(mini1, x + y);
        maxi1 = max(maxi1, x + y);
        ans = max(ans, (x - y) - mini2);
        ans = max(ans, maxi2 - (x - y));
        mini2 = min(mini2, x - y);
        maxi2 = max(maxi2, x - y);
    }
    printf("%lld\n", ans);
}
int main(){
    int T = 1;
    while (T--){
        init();
        solve();
    }
    return 0;
}

Measured memory_bytes: 3800
n, a = gets.split.map(&:to_i)
xs = gets.split.map(&:to_i).sort

dp = Array.new(51).map { Array.new(51).map { Array.new(4000, 0) } }

dp[0][0][0] = 1

(1..n).each do |i|
  dp[i][0][0] = 1
  (1..i).each do |j|
    (0..3000).each do |k|
      if k - xs[i-1] >= 0
        dp[i][j][k] = dp[i-1][j-1][k-xs[i-1]] + dp[i-1][j][k]
      else
        dp[i][j][k] = dp[i-1][j][k]
      end
    end
  end
end

ans = 0
(1..n).each do |i|
  ans += dp[n][i][i*a]
end

puts ans

Measured memory_bytes: 85116
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef vector<int>vi;
typedef pair<int,int>pi;
typedef vector<pi>vpi;
typedef vector<vi>vvi;
#define double long double
#define pow powl
#define sqrt sqrtl
#define cbrt cbrtl
#define floor floorl
#define ceil ceill
#define pb push_back
#define ep emplace_back
#define PB pop_back
#define pf push_front
#define ef emplace_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)-a.begin()
#define lb(a,b) lower_bound(all(a),b)-a.begin()
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) FOR(i,0,n-1) cin>>a[i]
#define in1(a,n) FOR(i,1,n) cin>>a[i]
#define ff first
#define ss second
#define out(a,n) FOR(i,0,n-1) cout<<a[i]<<" ";cout<<endl;
#define out1(a,n) FOR(i,1,n) cout<<a[i]<<" ";cout<<endl;
#define clr(a) a.clear()
#define pow2(a) (1LL<<a)
#define all(a) a.begin(),a.end()
#define all1(a) a.begin()+1,a.end()
#define rall(a) a.rbegin(),a.rend()
#define rall1(a) a.rbegin(),a.rend()
#define sz(a) ((int)a.size())
#define FOR(i,a,b) for(auto i=a;i<=b;i++)
#define NFOR(i,a,b) for(auto i=a;i>=b;i--)
const int mod=1e9+7;

inline int add(int a,int b){return (a%mod + b%mod)%mod;}
inline int sub(int a ,int b){return (a%mod - b%mod + mod)%mod;}
inline int mul(int a,int b){return (a%mod * b%mod)%mod;}
inline int power(int a,int b,int MOD){int res=1;while(b){if(b&1){res*=a;res%=MOD;}a=a*a;a%=MOD;b>>=1;}return res;}

#define trace(x) cout<<#x<<" :: "<<x<<endl;
#define trace2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define trace3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define trace4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
clock_t time_p = clock();
void time()
{
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (double)(time_p)/CLOCKS_PER_SEC <<endl;
}
signed main()
{
     SPEED;
     int n;
     cin>>n;
     vi v(n);
     in(v,n);
     int res=1e18;
     for(int x=-1000;x<=1000;x++)
     {
     	   int ans=0;
     	   for(auto y:v)
     	   	ans+=(y-x)*(y-x);
     	   res=min(res,ans);
     }
     cout<<res<<endl;
     time();
     return 0;
}

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

using namespace std;

const int maxn=1e5+5;

int n,s[maxn];

int partition(int p,int r)
{
    int x=s[r];
    int i=p-1;
    for(int j=p;j<r;j++){
        if(s[j]<=x){
            i++;
            swap(s[i],s[j]);
        }
    }
    swap(s[i+1],s[r]);
    return i+1;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
    }
    int q=partition(0,n-1);
    for(int i=0;i<n;i++){
        if(i){
            printf(" ");
        }
        if(i==q){
            printf("[");
        }
        printf("%d",s[i]);
        if(i==q){
            printf("]");
        }
    }
    printf("\n");
    return 0;
}
/*
12
13 19 9 5 12 8 7 4 21 2 6 11
*/



Measured memory_bytes: 3548
a = []

for i in range(3):
    a.append(list(map(int, input().split())))

n = int(input())

for i in range(n):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if (a[j][k] == b):
                a[j][k] = 0
                break

#print(a)

ans = min(sum(a[0]), sum(a[1]), sum(a[2]),(a[0][0] + a[1][1] + a[2][2]), (a[0][2] + a[1][1] + a[2][0]),(a[0][0] + a[1][0] + a[2][0]),(a[0][1] + a[1][1] + a[2][1]),(a[0][2] + a[1][2] + a[2][2]))

print(["No","Yes"][ans == 0])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define eps 1e-9
#define maxp 100000000000000000000
#define mod 1000000007
#define pi 3.141592653589793238
#define sin(s) scanf("%lld",&s);
#define sout(s) printf("%lld\n",s);
#define in(s) cin>>s
#define in2(a,b) cin>>a>>b
#define in3(a,b,c) cin>>a>>b>>c
#define vll vector<ll>
#define out(s) cout<<s
#define outs(s,a) cout<<s<<a
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define gear_change ios_base::sync_with_stdio(false),cin.tie(0)
#define nfl(i,n) for(i=0;i<n;i++)
#define sfl(i,s,e) for(i=s;i<e;i++)
#define ufl(i,n) for(i=n-1;i>=0;i--)
void solve(){
	ll n,i;
	in(n);
	unordered_map<string,ll>mp;
	ll mx=1;
	nfl(i,n){
		string str;
		in(str);
		mp[str]++;
		mx=max(mx,mp[str]);
	}
	vector<string>vec;
	for(auto it:mp){
		if(it.S==mx){
			vec.pb(it.F);
		}
	}
	sort(vec.begin(), vec.end());
	for(auto it:vec){
		cout<<it<<"\n";
	}
}	
int main(){
	clock_t t1=clock();
	gear_change;
	ll test=1;
	// in(test);
	while(test--){
		solve();
	}
	clock_t t2=clock();
	cerr<<"Time elapsed:- "<<(double)(t2-t1)/CLOCKS_PER_SEC<<'\n';
}	


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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int INF = 1e9+5;

int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    	cout.precision(10);
    	cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif
        
	int n;
	cin>>n;
	vi arr(n);
	forn(i,n) cin>>arr[i];

	vi dp(n,INF);
	dp[0]=0;
	forn(i,n){	
	 	fore(j,i+1,i+2){
	 	 	if(j<n)
	 	 		dp[j] = min(dp[i]+abs(arr[j]-arr[i]),dp[j]);
	 	}

	}
	cout<<dp.back()<<endl;

        #ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif

	return 0;
}	



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

#define ALL(a) (a).begin(), (a).end()
#define ll long long

using namespace std;

const ll MOD = (ll)1e9+7;

//string str;
char str[1000001];
//vector<ll> dp;
ll dp[20];

ll power(int num){
	ll ret = 1;
	for(int i = 0; i < 20; i++){
		if((num & (1 << i))){
			ret = (ret * dp[i])%MOD;
		}
	}
	//cerr << num << " " << "ret" << ret << endl;
	return ret;
}

pair<ll, int> expression(int &i);
pair<ll, int> term(int &i);
pair<ll, int> factor(int &i);
pair<ll, int> variable(int &i);

signed main(){
	dp[0] = 2;
	for(int i = 1; i < 20; i++){
		dp[i] = (dp[i-1]*dp[i-1])%MOD;
	}
	cin >> str;
	int i = 0;
	auto ans = expression(i);
	//cerr << ans.second << endl;
	cout << ans.first << endl;

	return 0;
}

pair<ll, int> expression(int &i){
	auto ret = term(i);
	if(str[i] == '|'){
		i++;
		auto right = expression(i);
		ll val = (power(ret.second)*right.first)%MOD;
		val = (val + power(right.second)*ret.first)%MOD;
		val = (val - (ret.first*right.first)%MOD + MOD)%MOD;
		ret = make_pair(val, ret.second+right.second);
	}
	//cerr << str.substr(0,i+1) << endl;
	//cerr << ret.first << " " << ret.second << endl;
	return ret;
}

pair<ll, int> term(int &i){
	auto ret = factor(i);
	if(str[i] == '&'){
		i++;
		auto right = term(i);
		ret = make_pair((ret.first*right.first)%MOD, ret.second+right.second);
	}
	return ret;
}

pair<ll, int> factor(int &i){
	switch(str[i]){
		case '~':{
			auto ret = factor(++i);
			ret.first = (MOD + power(ret.second) - ret.first)%MOD;
			return ret;
		}
		case '(':{
			auto ret = expression(++i);
			assert(str[i] == ')');
			++i;
			return ret;
		}
		default:
			return variable(i);
	}
}

pair<ll, int> variable(int &i){
	assert(str[i] == 'x');
	i++;
	while(isdigit(str[i]))i++;
	return make_pair(1ll, 1);
}


Measured memory_bytes: 50928
#include<stdio.h>

int main(void)

{

    int W, H, x, y, r;

    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

    if(x-r >= 0 && x+r <= W && y-r >= 0 && y+r <= H)

    {

        printf("Yes\n");

    }

    else

    {

        printf("No\n");

    }

    return 0;

}

Measured memory_bytes: 584
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n;
char s[105];
char app[105];
int tot=0;
int main()
{
	cin>>n;
	cin>>s+1;
	int ans1=0;
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		memset(app,0,sizeof(app));
		tot=0;
		for(int j=1;j<=i;j++)
		{
			bool pt=1;
			for(int k=1;k<=tot;k++) 
				if(app[k]==s[j]) {pt=0;break;}
			if(pt) app[++tot]=s[j];
		}
		for(int j=i+1;j<=n;j++)
		{
			for(int k=1;k<=tot;k++)
				if(app[k]==s[j])
				{ans++;app[k]='0';}
				if(ans>ans1) ans1=ans;
		}
	}
	cout<<ans1;
	return 0;
}

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

r = 0
while 2 ** r <= L:
    r += 1

E = []
for i in range(1, r):
    E.append((i, i + 1, 0))
    E.append((i, i + 1, 2 ** (i - 1)))

# 2**(r-1) ～ L-1 のPATHがない。

n = 2 ** (r - 1)

###
while True:
    d = L - 1 - n + 1
    if d <= 0:
        break
    zi = 0
    while 2 ** (zi) <= d:
        zi += 1

    E.append((zi, r, n))
    n = n + 2 ** (zi - 1)

print("{} {}".format(r, len(E)))

for e in E:
    print("{} {} {}".format(e[0], e[1], e[2]))


Measured memory_bytes: 3064
s = int(input())
b = 10**9 - s % 10**9
a = (s + b) // 10**9
if s == 10**18:
    print(0, 0, 10**9, 0, 0, 10**9)
else:
    print(0, 0, 10**9, 1, b, a)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef long long ll;
const ll INF = 1LL<<58;
void chmin(long long &a, long long b) { if (a > b) a = b; }

int left(const vector<ll> &v, ll x){
    return upper_bound(v.begin(),v.end(),x)-v.begin()-1;
}
int right(const vector<ll> &v, ll x){
    return lower_bound(v.begin(),v.end(),x)-v.begin();
}

int main(){
    int a,b,q;cin >> a >> b >> q;
    vector<ll> s(a);
    rep(i,a)cin >> s[i];
    vector<ll> t(b);
    rep(i,b)cin >> t[i];
    vector<ll> x(q);
    rep(i,q)cin >> x[i];
    s.push_back(INF);s.push_back(-INF);
    t.push_back(INF);t.push_back(-INF);
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    
    for(auto e : x){
        ll res = INF;
        rep(i,2){
            ll first = (i ? s[left(s,e)] : s[right(s,e)]);
            rep(j,2){
                ll second = (j ? t[left(t,first)] : t[right(t,first)]);
                chmin(res,abs(e-first) + abs(first - second));
            }
        }
        rep(i,2){
            ll first = (i ? t[left(t,e)] : t[right(t,e)]);
            rep(j,2){
                ll second = (j ? s[left(s,first)] : s[right(s,first)]);
                chmin(res,abs(e-first) + abs(first - second));
            }
        }
        cout << res << endl;
    }
    return 0;
}

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

using ll = long long;
#define f(i,a,b) for (int i = a; i < b; i++)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif


	string s; cin >> s;
	int n = s.length();
	ll ans = 1LL*n*(n-1)/2LL+1;
	int cnt[26];
	f(i,0,26) cnt[i] = 0;
	f(i,0,n) ans -= cnt[s[i]-'a']++;
	cout << ans << endl;

#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	
	return 0;
}



Measured memory_bytes: 720
s = input()

head = int(s[:2])
back = int(s[2:])

if 0 < head < 13 and 0 < back < 13:
    print("AMBIGUOUS")
elif 0 < head < 13:
    print("MMYY")
elif 0 < back < 13:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	public static void main(String [] args) {
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
		int k = in.nextInt();
		ArrayList<Integer> ks = new ArrayList<>();
		for(int i=1;i<=Math.min(a, b);i++) {
			if(a%i==0&&b%i==0) {
				ks.add(i);
				
				}
			}
		System.out.println(ks.get(ks.size()-k));
		}
	
		
	}




Measured memory_bytes: 22612
n,m=map(int,input().split())
s=input()
pos=n
p=n
tmp=n
ans=[]
while pos>0:
    q=p
    while pos-q<m and q>0:
        q-=1
        #print(q)
        if s[q]=='0':
            tmp=q
    p=q
    #print()
    if tmp>=pos:
        print(-1)
        exit(0)
    ans.append(pos-tmp)
    pos=tmp
#print()
for i in range(1,1+len(ans)):
    print(ans[-i],end=' ')


Measured memory_bytes: 4848
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>

#define roop(i, n) for(int i=0;i<n;i++)

using namespace std;
using ll = long long int;
using ull = unsigned long long;

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int main() {
	string n;
	cin >> n;
	for (int i = 0; i < n.length(); i++) {
		if (n[i] == '7') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int main(int argc, const char * argv[]) {
    // source code
    int n;
    cin >> n;
    int d[n];
    rep(i, n) cin >> d[i];
    ll total = 0;
    rep(i, n) repd (j, i + 1, n) {
        total += d[i] * d[j];
    }
    cout << total;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX_N = 201010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll ans[110][110];
bool flag[2][110];

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	ll n, m;
	cin >> n >> m;
	map<ll, ll>mp;
	rep(i, m) {
		ll a, b;
		cin >> a >> b;
		mp[a]++;
		mp[b]++;
	}
	for (auto p : mp) {
		if (p.second % 2) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 8984
# n = gets.chomp.to_i
# if n < 2
#   puts 0
# else
#   arr = (0..9).to_a.permutation(n).to_a
#   arr.select!{|a| a.include?(0) && a.include?(9)}
#   p arr.size
# end .select!{|a| a.include?(0) && a.include?(9)}
# arr = (0..9).to_a.repeated_permutation(869121).to_a
# p arr.size
n = gets.chomp.to_i
MOD = 10**9+7
ans = ((10**n)-(9**n)-(9**n)+(8**n))%MOD
puts ans



Measured memory_bytes: 23492
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int main() {
	int H;
	cin >> H;
	if (!H) {
		return 0;
	}
	vector< vector<int> > b(H, vector<int>(6));
	for (int i = 0; i < H; i++) {
		cin >> b[i][0] >> b[i][1] >> b[i][2] >> b[i][3] >> b[i][4];
		b[i][5] = 0;
	}
	int ans = 0;
	int score = -1;
	while (score) {
		score = 0;
		for (int i = 0; i < H; i++) {
			int prev = b[i][0];
			int index = 0;
			int length = 1;
			for (int j = 1; j <= 5; j++) {
				if (b[i][j] == prev) {
					length++;
				} else {
					if (length >= 3) {
						score += prev * length;
						for (int k = index; k < index + length; k++) {
							b[i][k] = 0;
						}
					}
					prev = b[i][j];
					index = j;
					length = 1;
				}
			}
		}
		vector< vector<int> > t(H, vector<int>(6, 0));
		for (int j = 0; j < 5; j++) {
			for (int i = H, k = H - 1; i--;) {
				if (b[i][j]) {
					t[k][j] = b[i][j];
					k--;
				}
			}
		}
		ans += score;
		b = t;
	}
	cout << ans << endl;
	return main();
}

Measured memory_bytes: 1744
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

// 0. この define した INF が使えるのは int のとき
// 1. N <= 50 なので O(N^5) でも通る（通らないと思って無理に高速化をしようとして失敗した）

int main(){
	int n, k;
	cin >> n >> k;
	vector<pair<ll, ll>> v;
	vector<pair<ll, ll>> w;
	for( int i = 0; i < n; ++i ){
		ll x, y;
		cin >> x >> y;
		v.emplace_back(x, y);
		w.emplace_back(x, y);
	}
	ll ans = -1;
	// v から横向きの部分連続区間を，w から縦向きの部分連続区間をとる
	// 連続区間の列挙は O(N^2) でできるので O(N^4)
	sort( v.begin(), v.end() );
	sort( w.begin(), w.end(), []( auto &x, auto &y ){ return x.second < y.second; } );
	for( int rangex = 1; rangex < n; ++rangex ){
		for( int ix = 0; ix + rangex < n; ++ix ){
			// 横向きの部分連続区間の左端と右端
			ll a = v.at(ix).first;
			ll b = v.at(rangex+ix).first;
			for( int rangey = 1; rangey < n; ++rangey ){
				for( int iy = 0; iy + rangey < n; ++iy ){
					// 縦向きの部分連続区間の下端と上端
					ll c = w.at(iy).second;
					ll d = w.at(rangey+iy).second;
					// 縦の区間と横の区間が交わっていない場合は長方形でないので除外
					if(
						a <= w.at(iy).first && w.at(iy).first <= b
						&&
						a <= w.at(rangey+iy).first && w.at(rangey+iy).first <= b
						&&
						c <= v.at(ix).second && v.at(ix).second <= d
						&&
						c <= v.at(rangex+ix).second && v.at(rangex+ix).second <= d
					){
						// 長方形に含まれる点の数が k 個以上か確認する
						// N 個の点を線形探索するので O(N)
						int cnt = 0;
						for( int i = 0; i < n; ++i ){
							ll x = v.at(i).first;
							ll y = v.at(i).second;
							if( a <= x && x <= b && c <= y && y <= d ) ++cnt;
						}
						if( cnt >= k ){
							ans = ( ( ans == -1 ) ? (b-a) * (d-c) : min( ans, (b-a) * (d-c) ) );
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
int main(void){
    // Your code here!
    int a,b,c;
	cin>>a;
	cin>>b;
	cin>>c;
	if(a+b+1>=c){
	    cout<<c+b<<endl;
	}
	else{
	    cout<<a+b+1+b<<endl;
	}

}


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


int main(){
  int N;
  cin >> N;
  ll ans = 0;
  for (int a=1; a<=N-1; a++ ) {
    ans += (N-1) / a;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

typedef long long ll;

using namespace std;

int main(){
  const int w = getInt();
  const int h = getInt();
  const int n = getInt();

  vector<int> x(n);
  vector<int> y(n);

  REP(i,n){
    x[i] = getInt();
    y[i] = getInt();
  }

  vector<int> xx = x; sort(xx.begin(), xx.end());
  vector<int> yy = y; sort(yy.begin(), yy.end());

  vector<int> px;
  vector<int> py;

  const int d = 3;
  for(int i = 0; i < d + d + 1; i++){
    int pp = n / 2 - d + i;
    if(0 <= pp && pp < n){
      px.push_back(xx[pp]);
      py.push_back(yy[pp]);
    }
  }

  ll ans = 1ll << 60;
  int ax = 0;
  int ay = 0;
  FOR(ix, px) FOR(iy, py){
    int cx = *ix;
    int cy = *iy;

    ll tmp = 0;
    ll mx = 0;
    REP(i,n){
      ll tt = abs(x[i] - cx) + abs(y[i] - cy);
      mx = max(mx, tt);
      tmp += tt + tt;
    }
    tmp -= mx;
    if(tmp < ans){
      ans = tmp;
      ax = cx;
      ay = cy;
    }else if(tmp == ans){
      if((cx < ax) || (cx == ax && cy < ay)){
        ax = cx;
        ay = cy;
      }
    }
  }

  printf("%lld\n", ans);
  printf("%d %d\n", ax, ay);

  return 0;
}

Measured memory_bytes: 2344
/**
 * @Author:      H S-J
 * @DateTime:    2017-11-11 20:58:05
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;
#define MST(a, b) memset(a, b, sizeof(a));
#define CLR(a) MST(a, 0);
#define DBG(x) cout << '#' << " = " << (x) << endl;
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.begin())
#define lson(x) (x) << 1
#define rson(x) (x) << 1|1
#define pb push_back
#define rep(x, y, z) for (int x = y; x < z; ++x)
#define ech(x, y, z) for (auto x = z.begin(), y = z.end(); x != y; ++x)
#define lowbit(x) (x & (-x))
#define opr operator
#define _st first
#define _nd second
#define prior_q1(x) priority_queue<x>
#define prior_q2(x) priority_queue<x, vector<x>, greater<x> >
typedef long long LL;
typedef stringstream strstm;
struct FastIO {
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint() {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline LL xlongint() {
        LL s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s) {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c> 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x) {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s) {
        while (*s) wchar(*s++);
    }
    ~FastIO() {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
const int maxn = 2000+11;
int a[maxn];
int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(0);cin.tie(0);
	int n, z, w, ans;
	cin >> n >> z >> w;
    rep(i, 1, n+1) cin >> a[i];
    if(n == 1) ans = abs(a[1] - w);
    else {
        int t1 = abs(a[n] - w);
        int t2 = abs(a[n] - a[n-1]);
        ans = max(t1, t2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
	//ABC166 A
	string s;
	// S
	// A B
	//cin >> x >> y >> a >> b >> c;

	cin >> s;

	if (s == "ABC") {
		cout << "ARC";
	}
	else if (s == "ARC") {
		cout << "ABC";
	}


	return 0;
}

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

void main_()
{
    ll N;
    cin >> N;
    vector<ll> dp(N + 1, 1e9);

    dp[0] = 0;

    for (ll i = 0; i < N; ++i) {
        dp[i + 1] = min(dp[i + 1], dp[i] + 1);
        for (ll cache = 6; cache + i <= N; cache *= 6) {
            dp[i + cache] = min(dp[i + cache], dp[i] + 1);
        }
        for (ll cache = 9; cache + i <= N; cache *= 9) {
            dp[i + cache] = min(dp[i + cache], dp[i] + 1);
        }
    }

    cout << dp[N] << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(){
    long int a, b, k;
    scanf("%ld%ld%ld", &a, &b, &k);

    if( a-k < 0 ){
       if( a+b-k < 0 ){
          a=0;
          b=0;
       }else{
          b-=(k-a);
          a=0;
       }
    }else{
       a-=k;
    }
    printf("%ld %ld\n", a, b);
    return 0;
}


Measured memory_bytes: 1736
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


void no() {
	puts("NO");
	exit(0);
}

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

	ll N;
	cin >> N;
	vector<ll>A(N);
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}
	if (sum % (N*(N + 1LL) / 2LL) != 0)no();

	ll k = sum / (N*(N + 1LL) / 2LL);
	vector<ll>x(N);
	for (int i = 0; i < N; i++) {
		ll s = A[i] - A[(i - 1 + N) % N];
		if (k - s < 0 || (k - s) % N != 0)no();
		x[i] = (k - s) / N;
	}

	for (int i = 0; i < N; i++) {
		A[0] -= x[N - 1 - i] * ((i+1)%N + 1);
	}
	if(A[0] != 0)puts("NO");
	
	puts("YES");


	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
//Longest Common Prefix(s,s.substr(i)) O(|s|)
#include<vector>
vector<int>Zalgo(const string&s)
{
	vector<int>ret(s.size());
	ret[0]=s.size();
	int i=1,j=0;
	while(i<s.size())
	{
		while(i+j<s.size()&&s[j]==s[i+j])j++;
		ret[i]=j;
		if(j==0)
		{
			i++;
			continue;
		}
		int k=1;
		while(i+k<s.size()&&k+ret[k]<j)ret[i+k]=ret[k],k++;
		i+=k;j-=k;
	}
	return ret;
}
string s,t;
bool ok[5<<17];
int memo[5<<17];
int dfs(int u)
{
	if(memo[u]>=0)return memo[u];
	else if(memo[u]==-2)
	{
		return memo[u]=1e9;
	}
	if(ok[u])
	{
		memo[u]=-2;
		return memo[u]=dfs((u+t.size())%s.size())+1;
	}
	else return memo[u]=0;
}
main()
{
	cin>>s>>t;
	string ss=s;
	while(ss.size()<t.size())ss+=s;
	vector<int>AA=Zalgo(t+ss+ss);
	for(int i=0;i<s.size();i++)
	{
		ok[i]=AA[i+t.size()]>=t.size();
		memo[i]=-1;
	}
	int ans=0;
	for(int i=0;i<s.size();i++)ans=max(ans,dfs(i));
	cout<<(ans<1e9?ans:-1)<<endl;
}

Measured memory_bytes: 22336
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  ll k;
  cin >> k;
  
  vector<ll> v(50, 49 + k / 50);

  for(int i = 0; i < k % 50; i++) {
    for(int j = 0; j < 50; j++) {
      if(j == i) v[i] += 50;
      else v[j]--;
    }
  }

  cout << 50 << endl;
  for(int i = 0; i < 50; i++) cout << v[i] << " \n"[i == 50 - 1];
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <boost/math/common_factor_rt.hpp>

using namespace std;
typedef long long LL;

int main(){
  LL N,h,n,w;
  cin >> N;
  for(LL i=1;i<=3500;i++){
	for(LL j=i;j<=3500;j++){
	  LL a=i*j*N;
	  LL b=4*i*j-(i+j)*N;
	  if(b>0&&a%b==0){
		cout << i << " " << j << " " << a/b << endl;
		return 0;
	  }
	}
  }

  return 0;


}


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

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

    rep(i,s.length()) {
        if(s[i] == '1')s[i] = '9';
        else s[i] = '1';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

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

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    ll sum = 0;
    rep(i,0,n){
        ll a,k; cin >> a >> k;
        ll t = 0;
        while(1){
            ll p = a / k, q = a % k;
            if(q == 0 || p == 0)break;
            if(q >= p + 1){
                ll r = (q + p) / (p + 1);
                a -= r * (p + 1);
            }
            else a -= p + 1;
        }
        if(a % k == 0)t = a / k;
        sum ^= t;
    }

    cout << (sum == 0 ? "Aoki" : "Takahashi") << "\n";
}

Measured memory_bytes: 3520
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a =10000,b=5000,c=1000;
    int n,y;
    bool flag=false;
    cin>>n>>y;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j+i<=n;j++)
        {
            int rem=y/1000-(i*10+j*5);
            if(rem>=0 && rem+i+j ==n )
            {
                flag=true;
                cout<<i<<" "<<j<<" "<<rem<<endl;
                break; 
            }
        }
        if(flag)
        break;
    }
    if(!flag)
    cout<<"-1 -1 -1"<<endl;
     return 0;
}


Measured memory_bytes: 256
'''
w,v = [0] * n, [0] * n
for i in range(n):
    w[i] , v[i] = map(int,input().split())
'''

N, W = map(int, input().split())
w, v = [0] * (N + 1), [0] * (N + 1)
INF = 10 ** 20
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

dp = [[INF] * ((10 ** 5) + 2) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(0, 10 **5+1):
        dp[i][j] = dp[i - 1][j]
        if j - v[i] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])

ans = 0
for i in range(0, 10 ** 5+1):
    if dp[N][i] <= W:
        ans = i
#print(dp[N])
print(ans)


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

typedef long long int ll;
typedef vector<int> vi;            typedef vector<ll> vl;
typedef vector<vi> vvi;         typedef vector<vl> vvl;
typedef pair<int, int>     pii;    typedef pair<ll, ll> pll;
typedef vector<pii> vii;         typedef vector<pll> vll;
typedef map<int,int> mii;
typedef vector<char> vc;
typedef vector<bool> vb;
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define rforne(i,n) for(int i=n;i>=1;i--)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
const ll INFL = 1e18;
const int INFI = 1e9;
#ifdef KARAN
    #include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}
ll modpow(ll a, ll b, ll m = MOD){a %= m; ll res = 1; 
    while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}
void graph(vvi &adj, int m) {int x, y; forn(i, m){cin>>x>>y; adj[--x].pb(--y); adj[y].pb(x);}}

void solve(){
    int n; cin>>n;
    vl a(n+1), b(n+1), c(n+1);
    forne(i, n) cin>>a[i]>>b[i]>>c[i];
    vvl dp(n+1, vl(3, 0));
    forne(i, n)
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i], 
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i],
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
    cout<<max3(dp[n][0], dp[n][1], dp[n][2])<<endl;

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef KARAN
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int t=1;
    while(t--)
        solve();
}

Measured memory_bytes: 8064
#include <iostream>
#include <algorithm>
#include <string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
	int n; cin>>n;
	char a[5]={'.',',','!','?',' '};
	rep(h,n){
		string s; cin>>s;
		string ans="";
		int key=0,cnt=-1;
		int x=s.size();
		rep(i,x){
			if(s[i]=='0'){
				switch(key){
					case 0:
						break;
					case 1:
						ans+=a[0+cnt%5];
						break;
					case 2:
						ans+='a'+(cnt%3);
						break;
					case 3:
						ans+='d'+(cnt%3);
						break;
					case 4:
						ans+='g'+(cnt%3);
						break;
					case 5:
						ans+='j'+(cnt%3);
						break;
					case 6:
						ans+='m'+(cnt%3);
						break;
					case 7:
						ans+='p'+(cnt%4);
						break;
					case 8:
						ans+='t'+(cnt%3);
						break;
					case 9:
						ans+='w'+(cnt%4);
						break;
				}
				cnt=-1;
				key=0;
			}else{
				key=s[i]-'0'; cnt++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}



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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

llong pow_mod(llong m, llong n) {
  if (n == 1) return m;

  llong ret = pow_mod(m, n/2);
  ret = ret * ret % mod;
  if (n&1) ret = ret * m % mod;

  return ret;
}

map<llong, llong> PrimeFact(llong n){
  map<llong, llong> ret;
  while(n % 2 == 0){
    ret[2]++;
    n /= 2;
  }
  for(llong i = 3; i*i <= n; i += 2){
    while(n%i == 0){
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1)
  ret[n]++;

  return ret;
}

int main() {
  llong N;
  vector<llong> A;
  map<llong, llong> m;

  cin >> N;
  A.resize(N);
  llong l = 1;
  llong p = 1;
  for (auto &in: A) {
    cin >> in;
    auto p = PrimeFact(in);
    for (auto it: p) {
      m[it.first] = max(m[it.first], it.second);
    }
  }

  llong res = 1;
  for (auto &it: m) {
    for (int i = 0; i < it.second; ++i) {
      res = res * it.first % mod;
    }
  }

  llong ans = 0;
  for (auto &a: A) {
    ans = (ans + res * pow_mod(a, mod - 2) % mod) % mod;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 896
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>

using namespace std;
typedef long long ll;
#define INF 1999999999
#define MODA 1000000007 
#define rep(i,n) for (long long i = 0; i < (n); ++i)

template<typename T>
T powint (const T& x, const T& y) {
  T ret = 1;
  for(int i=0; i<y; ++i) ret *= x;
  return ret;
}

long long factorial(long long X) {
  long long ans = 1;
  for(int i=1; i<X+1 ; ++i) ans *= i;
  return ans;
}

std::map<long long, long long> prime_factor(long long n) {
  std::map<long long, long long> ret;
  for(long long i = 2; i * i <= n; ++i) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1; // if n is prime number.
  return ret;
}

int main() {
  ll N;
  cin >> N;
  vector<ll> x(N), y(N);
  rep(i,N) cin >> x[i] >> y[i];

  double dist = 0;
  ll num = 0;
  rep(i, N-1) {
    for(ll j=i; j<N; ++j) {
      dist += sqrt((x[i]-x[j]) * (x[i]-x[j]) + ((y[i]-y[j]) * (y[i]-y[j])));
    }
  }
  double ans = dist * (N-1) / (N*(N-1)/2);
  cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int main() {
  int N; cin >> N;
  int p[100001]; rep(i, N) cin >> p[i];
  int cnt = 0;
  rep(i, N) {
    if (p[i] == i + 1) {
      swap(p[i], p[i + 1]);
      cnt ++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a)&-(a))
#define clean(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int inf=0x3f3f3f3f;
const int maxn = 2e5+9;

inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}

int _;

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a*b);
    return 0;
}


Measured memory_bytes: 3784
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

from collections import defaultdict
from collections import deque

def main():
	n,q=map(int,input().split())
	d=defaultdict(list)
	
	for i in range(n-1):
		a,b=map(int,input().split())
		d[a].append(b)
		d[b].append(a)
	
	cnt=[0]*(n+1)
	
	for i in range(q):
		p,x=map(int,input().split())
		cnt[p]+=x
	
	data=[]
	
	
	q=deque([1])
	sumi=set()
	
	while q:
		now=q.popleft()
		sumi.add(now)
		kouho=d[now]
		for i in kouho:
			if i not in sumi:
				q.append(i)
				cnt[i]+=cnt[now]
	
	print(*cnt[1:])
	
	
	
	
	
	
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()


Measured memory_bytes: 118868
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i

count = 0
(A + 1).times do |a|
  (B + 1).times do |b|
    (C + 1).times do |c|
if X ==  500 * a + 100 * b + 50 * c then
  count +=1
end
    end
  end
end
p count


Measured memory_bytes: 1788
N, D, A = gets.split.map(&:to_i)
XHs = readlines.map{|l| l.split.map(&:to_i)}

ans, b, bs = 0, 0, []
XHs.sort_by(&:first).each do |x, h|
  while !bs.empty? && bs[0][0] < x
    b -= bs.shift[1]
  end
  h -= b
  next if h <= 0
  n = (h + A - 1)/A
  ans += n
  y = n*A
  bs << [x + 2*D, y]
  b += y
end
puts ans

Measured memory_bytes: 35704
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
    auto s = readln().split();
    assert(s.length == t.length);
    foreach(ref ti; t) {
        ti = s[0].to!(typeof(ti));
        s = s[1..$];
    }
}

const real eps = 1e-10;

void main(){
    long a, b, c;
    readlnTo(a, b, c);
    long[] x = [a, b, c];
    x.sort();
    writeln(x[0]*x[1]*((x[2]+1)/2 - x[2]/2));
}



Measured memory_bytes: 256
def main():
    N = int(input().strip())

    n_399 = 0
    n_799 = 0
    n_1199 = 0
    n_1599 = 0
    n_1999 = 0
    n_2399 = 0
    n_2799 = 0
    n_3199 = 0
    n_free = 0
    rates = list(map(int, input().strip().split()))
    for r in rates:
        if r <= 399:
            n_399 = 1
        elif r <= 799:
            n_799 = 1
        elif r <= 1199:
            n_1199 = 1
        elif r <= 1599:
            n_1599 = 1
        elif r <= 1999:
            n_1999 = 1
        elif r <= 2399:
            n_2399 = 1
        elif r <= 2799:
            n_2799 = 1
        elif r <= 3199:
            n_3199 = 1
        else:
            n_free += 1

    n_less_3200 = n_399 + n_799 + n_1199 + \
        n_1599 + n_1999 + n_2399 + n_2799 + n_3199
    n_rest = N - n_less_3200

    n_min = n_less_3200
    if n_less_3200 == 0 and n_free > 0:
        n_min = 1

    n_max = n_less_3200 + n_free
    if n_less_3200 + n_free >= N:
        n_max = N

    print(n_min, n_max)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>

using namespace std;
int main()
{
    int n;
    cin >> n;
    int b[n],a[n];
    for(int i=0; i<n-1; i++){
        cin >> b[i];
    }

    int sum = 0;
    for(int i=0; i<n; i++){
        if(i == 0){
            a[i] = b[i];
        }else if(i == n-1){
            a[i] = b[i-1];
        }else{
            a[i] = min(b[i-1],b[i]);
        }
        //cout << b[i-1] << "," << b[i] << " -> ";
        //cout << a[i] << endl;
    }
    for(int i=0; i<n; i++){
        sum += a[i];
    }
    cout << sum << endl; 
    return 0;
}

Measured memory_bytes: 256
s=list(input())
N=len(s)
K=int(input())
num=123

for i in range(N):
    diff=(num-ord(s[i]))%26
    if K==0:
        break
    if diff<=K:
        s[i]="a"
        K=K-diff
#print(s)
#print(K)
if K>0:
    K=K%26
    s[N-1]=chr(ord(s[N-1])+K)
#print(s)
print("".join(s))


Measured memory_bytes: 49520