akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def main():
    h,w = map(int, input().split())
    C = [input() for _ in range(h)]
    for i in range(h):
        for j in range(2):
            print(C[i])


if __name__ == '__main__':
    main()


Measured memory_bytes: 66728
#include <bits/stdc++.h>
#define maxn 100010

using namespace std;

int n, m;
int maxd, cnt;
int A, B;
vector<int> G[maxn];
int st[maxn];

void dfs(int u)
{
	st[u] = 1;
	for (auto v : G[u])
	{
		if (st[v] == 2)
		{
			if (A) B = v;
			else A = v;
		}
		else if (!st[v]) dfs(v);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++ )
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i ++ )//ORZDDD
	{
		int ddd = G[i].size();
		if (ddd % 2) { puts("No"); return 0; }
		if (ddd > maxd) maxd = ddd, cnt = 1;
		else if (ddd == maxd) cnt ++ ;
	}
	
	if (maxd >= 6) puts("Yes");
	else if (maxd == 4)
	{
		if (cnt >= 3)
		{
			puts("Yes");
			return 0;
		}
		else if (cnt == 1)
		{
			puts("No");
			return 0;
		}
		else
		{
			for (int i = 1; i <= n; i ++ )	
				if (G[i].size() == 4) st[i] = 2;
			for (int i = 1; i <= n; i ++ )
				if (!st[i])
				{
					A = B = 0;
					dfs(i);
					if (A == B)
					{
						puts("Yes");
						return 0;
					}
				}
			
			puts("No");
		}
	}
	else puts("No");
	
	return 0;
}

Measured memory_bytes: 6912
N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    s=money//ls[i]
    money-=s*ls[i]
    stock+=s
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)

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

int main() {
  int a , b;
  cin >> a;
  cin >> b;
  if ( a % 2 == 0 || b % 2 == 0 ){
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


X, Y, A, B, C = zz()
p = zz()
q = zz()
r = zz()

p = sorted(p)
q = sorted(q)
r = sorted(r, reverse=True)
# 透明なしのとき
p = p[-X:]
q = q[-Y:]

heapq.heapify(p)
heapq.heapify(q)
min_p = heapq.heappop(p)
min_q = heapq.heappop(q)
for i in range(C):

    if (min_p <= min_q):
        if (min_p < r[i]):
            # pと入れ替える
            heapq.heappush(p, r[i])
            min_p = heapq.heappop(p)
        else:
            break
    else:
        if (min_q < r[i]):
            heapq.heappush(q, r[i])
            min_q = heapq.heappop(q)
        else:
            break


print(sum(p) + sum(q) + min_p + min_q)


Measured memory_bytes: 31360
#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast")
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
inline int read() {
    int 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;
}
#define f(i, l, r) for (int i = l; i <= r; ++i)
#define rf(i, r, l) for (int i = r; i >= l; --i)
#define all(x) (x).begin(), (x).end()
#define l l
#define r r
#define lch (o << 1)
#define rch (o << 1 | 1)
#define mid ((l + r) >> 1)
#define mem(x, y) memset(x, y, sizeof(x))
#define mod1(x) ((x >= mod) && (x -= mod))
#define mod2(x) ((x < 0) && (x += mod))

const int inf = 2e9 + 7;
//const ll INF = INT64_MAX;
double eps = 1e-6;
const int mod = 1e9+7;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
ll power(ll a, ll b) { ll res = 1; while (b) { if (b & 1)res = res * a % mod; a = a * a % mod; b >>= 1; }return res; }
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
void add(ll& a, ll b) { a += b; mod1(a); mod2(a); }
/*int len, C[N], clen;
int id(int v) { return lower_bound(C + 1, C + len, v) - C; }
void initC() { sort(C + 1, C + clen); len = unique(C + 1, C + 1 + clen) - C - 1; }*/

ll a[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    int start = clock();
#endif
    int n; cin >> n;
    f(i, 1, n)cin >> a[i];
    ll ans = 0;
    ll sum = a[n];
    rf(i, n - 1, 1) {
        ans += sum * a[i]; ans %= mod; sum += a[i]; sum %= mod;
    }
    cout << ans;

#ifdef local
    int end = clock();
    //cout << '\n' << end - start << "ms";
#endif* /
}

Measured memory_bytes: 5160
#include <iostream>
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
char a[10005];
int d,len;
ll dp[10005][105][3];

ll solve(int idx,int sum,int pre){

    if(idx == len){
        if(sum == 0) return dp[idx][sum][pre] = 1;
        return dp[idx][sum][pre] = 0;
    }
    if(dp[idx][sum][pre] != -1) return dp[idx][sum][pre];

    ll ret = 0;
    if(idx == 0 || pre == 1){
    for(int i = 0;i <= (a[idx]-'0'); i++){
        if(i == a[idx]-'0')
        ret += solve(idx+1,(sum + i)%d, 1);
        else
        ret += solve(idx+1,(sum+i)%d,0);
        if(ret >= mod) ret -= mod;
        }
    }
    else{
        for(int i=0;i < 10; i++){
        ret += solve(idx+1,(sum + i)%d, pre);
        if(ret >= mod) ret -= mod;
        }
    }
    return dp[idx][sum][pre] = ret;
}

int main()
{
    cin>>a>>d;
    len = strlen(a);
    memset(dp,-1,sizeof(dp));
    cout<<(((solve(0,0,0)-1) + mod)%mod)%mod;

    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

int main()
{
	double n,m,d;
	cin>>n>>m>>d;

	if(d!=0)cout<<setprecision(12)<<2*(n-d)/(n*n)*(m-1)<<endl;
	else cout<<setprecision(12)<<(n-d)/(n*n)*(m-1)<<endl;
	return 0;
}

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


#define ll          long long
#define uint        unsigned int 
#define ld          long double
#define SAM         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define mod         1000000007
#define mxn         200005
#define pb          push_back
#define pii         pair<int,int>
#define f           first
#define s           second
#define sz(x)       (int)x.size()
#define all(x)      x.begin(),x.end()

using namespace std;


int power(int a,int n)
{
    a %= mod;
    if(n == 1) return a;
    if(n == 0) return 1;
    if(n%2) return (a*(power((a*a)%mod,n/2)%mod))%mod;           //n is odd
    return power((a*a)%mod,n/2)%mod;                             //n is even
}



int main()
{
    SAM;
    int a;
    cin>>a;
    cout<<a+power(a,2)+power(a,3);
   
    
    return 0;
}




Measured memory_bytes: 3648
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"

using namespace std;

constexpr long long int MOD = 1000000007;
//const int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;

//const double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> H >> W;
	vector<string>s(H);
	for (auto &i : s)cin >> i;
	vector<vector<int>>v(H + 2, vector<int>(W + 2));
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (s[i - 1][j - 1] == '.')continue;
			v[i][j] = s[i - 1][j - 1] - '0';
		}
	}
	int dy[] = { -1,0,1,1 };
	int dx[] = { 1,1,0,-1 };
	s[0] = s.back() = string(W + 2, '.');
	vector<vector<vector<int>>>dp(H + 2, vector<vector<int>>(W + 2, vector<int>(16, MOD)));
	dp[1][1][2] = v[1][1] + v[2][1];
	dp[1][1][4] = v[1][1] + v[1][2];
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			for (int k = 0; k < 16; k++) {
				if (j < W) {
					int add = 0;
					if ((k >> 1) & 1)add = v[i][j + 1];
					if ((k >> 0) & 1) {
						int nx = 1;
						if ((k >> 2) & 1)nx |= 1 << 3;
						dp[i][j + 1][nx] = min(dp[i][j + 1][nx], dp[i][j][k] + add + v[i][j + 2] + v[i + 1][j + 1]);
						add += v[i - 1][j + 1];
					}
					{
						int nx = 1 << 1;
						nx |= 1 << 0;
						if ((k >> 2) & 1)nx |= 1 << 3;
						dp[i][j + 1][nx] = min(dp[i][j + 1][nx], dp[i][j][k] + add + v[i + 1][j + 1]);
					}
					{
						int nx = 1 << 2;
						nx |= 1 << 0;
						if ((k >> 2) & 1)nx |= 1 << 3;
						dp[i][j + 1][nx] = min(dp[i][j + 1][nx], dp[i][j][k] + add + v[i][j + 2]);
					}
				}
				if (i < H) {
					int add = 0;
					if ((k >> 2) & 1)add = v[i + 1][j];
					if ((k >> 3) & 1) {
						int nx = 1 << 3;
						if ((k >> 1) & 1)nx |= 1 << 0;
						dp[i + 1][j][nx] = min(dp[i + 1][j][nx], dp[i][j][k] + add + v[i + 2][j] + v[i + 1][j + 1]);
						add += v[i + 1][j - 1];
					}
					{
						int nx = 1 << 1;
						nx |= 1 << 3;
						if ((k >> 1) & 1)nx |= 1 << 0;
						dp[i + 1][j][nx] = min(dp[i + 1][j][nx], dp[i][j][k] + add + v[i + 2][j]);
					}
					{
						int nx = 1 << 2;
						nx |= 1 << 3;
						if ((k >> 1) & 1)nx |= 1 << 0;
						dp[i + 1][j][nx] = min(dp[i + 1][j][nx], dp[i][j][k] + add + v[i + 1][j + 1]);
					}
				}
			}
		}
	}
	cout << *min_element(dp[H][W].begin(), dp[H][W].end()) << endl;
}


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

#define MAX 2000000
#define INFTY 1000000

int n, a[MAX+1];

void maxHeapify(int i)
{
  int l, r, largest, tmp;
  l = 2*i;
  r = 2*i+1;

  if(l <= n && a[l] > a[i])
    largest = l;
  else
    largest = i;
  if(r <= n && a[r] >  a[largest])
    largest = r;

  if(largest != i) {
    tmp = a[i];
    a[i] = a[largest];
    a[largest] = tmp;
    maxHeapify(largest);
  }
}

int extract()
{
  int maxv;
  if(n < 1)
    return -INFTY;
  maxv = a[1];
  a[1] = a[n--];
  maxHeapify(1);
  return maxv;
}

void increaseKey(int i, int key)
{
  int tmp;

  if(key <a[i])
    return ;
  a[i] = key;
  while(i > 1 && a[i/2] < a[i]) {
    tmp = a[i];
    a[i] = a[i/2];
    a[i/2] = tmp;
    i /= 2;
  }
}

void insert(int key)
{
  n++;
  a[n] = -INFTY;
  increaseKey(n, key);
}

int main()
{
  int key;
  char command[10];

  while(1) {
    scanf("%s", command);
    if(strcmp(command, "end") == 0)
      break;
    if(strcmp(command, "insert") == 0) {
      scanf("%d", &key);
      insert(key);
    }
    else {
      printf("%d\n", extract());
    }
  }
  return 0;
}

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

int main() {
  
  int a[4] = {1, 0, 0, 0};
  int x, y;
  cin >> x;
  cin >> y;
  
  a[x] = 1;
  a[y] = 1;
  
  for(int i = 1; i <= 3; ++i)
    if(a[i] == 0)
      cout << i << endl;
  
  return 0;
}
  

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

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

    for(int i=0; i<s.size(); i++){
        s[i] += n;
        if((int)s[i] > 90) s[i] = (char)(64 + (int)s[i]-90);
    }

    cout<<s<<endl;

    return 0;
}

Measured memory_bytes: 256
/**
*    author:  souzai32
*    created: 05.08.2020 01:04:23
**/

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

int main() {

    int n;
    cin >> n;
    vector<int> l(n);
    rep(i,n) cin >> l.at(i);
    sort(l.begin(),l.end(),greater<>());
    int count=0;

    for(int i=0; i<n-2; i++){
        for(int j=i+1; j<n-1; j++){
            for(int k=j+1; k<n; k++){
                if(l.at(i)<l.at(j)+l.at(k)){
                    count++;
                    //cout << l.at(i) << ' ' << l.at(j) << ' ' << l.at(k) << endl;
                }
                else break;
            }
            if(l.at(i)>l.at(j)*2) break;
        }
    }

    cout << count << endl;

    return 0;
}

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

int main( ) {
	
	long long a,ans;
	cin>>a;
	string b;
	cin>>b;
	
    long long bb=(b[0]-'0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');
	
	ans = (a*bb)/100LL;
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		
		int n = N%10;
		
		if(n == 2 || n == 4 || n == 5 || n == 7 || n == 9) {
			
			System.out.println("hon");
			
		}else if(n == 0 || n == 1 || n == 6 || n == 8 ) {
			
			System.out.println("pon");
			
		}else {
			
			System.out.println("bon");
		}
		
		
	}
}


Measured memory_bytes: 35836
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

using ll =long long;

ll N, K;
ll A;
ll d;
ll b[10000];

int main()
{
    cin >> N >> K;
    ll ans = N;
    for(int i = 0;i < K;i++)
    {
        cin >> d;
        for(int j = 0;j < d;j++)
        {
            cin >> A;
            if(b[A] == 0)
            {
                b[A] = 1;
                ans--;
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
#include <variant>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
#define MAX_V 10000
int V;

using Weight = ll;
const Weight INF = 1e13;
// const Weight eps = 1e-8;

struct Edge{
  int src, dest;
  int cap, rev;
  Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

Weight h[MAX_V];                // potential
Weight dist[MAX_V];             // minimum distance
int prevv[MAX_V], preve[MAX_V]; // previous vertex and edge

void add_edge(Graph &g, int src, int dest, int cap, Weight weight) {
  g[src].push_back((Edge){src, dest, cap, (int)g[dest].size(), weight});
  g[dest].push_back((Edge){dest, src, 0, (int)g[src].size() - 1, -weight});
}

Weight min_cost_flow(Graph &g, int s, int t, int f) {
  Weight res = 0; V = g.size();
  memset(h, 0, sizeof(h));
  using P = pair<Weight, int>;
  while (f > 0) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V, INF);
    dist[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
      P p = que.top(); que.pop();
      int v = p.second; 
      if (dist[v] < p.first) continue;
      REP(i, g[v].size()) {
        Edge &e = g[v][i];
        if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest] /* + eps */) {
          dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest];
          prevv[e.dest] = v;
          preve[e.dest] = i;
          que.push(P(dist[e.dest], e.dest));
        }
      }
    }
    if (dist[t] == INF) return -1;
    REP(v, V) h[v] += dist[v];

    int d = f;
    for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
    f -= d;
    res += d * h[t];
    for (int v = t; v != s; v = prevv[v]) {
      Edge &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,k;
  cin>>n>>k;
  Graph g(n*n + 2*n + 2);
  int voffset = n*n;
  int hoffset = voffset + n;
  int s = hoffset + n;
  int t = s + 1;
  REP(i,n) {
    REP(j,n) {
      int a;
      cin>>a;
      add_edge(g, voffset + i, i*n + j, 1, -a);
      add_edge(g, i*n + j, hoffset + j, 1, 0);
    }
  }
  REP(i,n) {
    add_edge(g, s, voffset + i, k, 0);
    add_edge(g, hoffset + i, t, k, 0);
  }
  add_edge(g, s, t, 1e8, 0);
  ll ans = -min_cost_flow(g, s, t, 1e8);
  cout<< ans<<endl;
  REP(i,n) {
    REP(j,n) {
      int idx = i*n + j;
      bool ok = false;
      for (auto&& e : g[idx]) {
        if (e.dest < hoffset) continue;
        if (e.cap == 0) ok = true;
      }
      if (ok) cout<<'X';
      else cout<<'.';
    }
    cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 4196
class UnionFindBySize():
    def __init__(self, n):
        self.parents = list(range(n+1))
        self.size = [1] * (n+1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # 根が同一かどうかを判定する
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

n, m, k = map(int, input().split())
AB_dict = {x:[] for x in range(1, n+1)}
AB = []
CD_dict = {x:[] for x in range(1, n+1)}
CD = []
for _ in range(m):
    a, b = map(int, input().split())
    AB_dict[a].append(b)
    AB_dict[b].append(a)
    AB.append([a,b])
for _ in range(k):
    c, d = map(int, input().split())
    CD_dict[c].append(d)
    CD_dict[d].append(c)
    CD.append([c,d])

UF = UnionFindBySize(n)
for i in range(m):
    UF.union(AB[i][0], AB[i][1])

# print(UF.size)
Ans = []
for i in range(n):
    same_tree_block = 0
    size = UF.size[UF.find(i+1)]
    for x in CD_dict[i+1]:
        same_tree_block += UF.same_check(i+1, x)
    friends = len(AB_dict[i+1])
    # print('-'*30)
    # print('i+1 is ' + str(i+1))
    # print('cand is ' + str(size))
    # print('same_tree_block is ' + str(same_tree_block))
    # print('friends is ' + str(friends))
    ans = size - same_tree_block - friends -1
    Ans.append(str(ans))
print(' '.join(Ans))

Measured memory_bytes: 88796
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)
ll INF = 1LL << 50;
ll cnt = 0;
vll vB(51), vP(51);

void solve(long long N, long long X){
    if(X <= 1) return;
    ll B = vB[N-1], P = vP[N-1], L = B+P;
    X--;
    if(X < L)
        solve(N-1, X);
    else{
        X -= L;
        cnt += P;
        if(X >= 1) {
            cnt += 1;
            X --;
        }
        else return;

        if(X < L)
            solve(N-1, X);
        else{
            cnt += P;
            return;
        }
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long X;
    scanf("%lld",&X);
    vB[0]=0; vP[0]=1;
    rep(i, 50){
        vB[i+1] = vB[i]*2+2;
        vP[i+1] = vP[i]*2+1;
    }
    solve(N, X);
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
require 'prime'
MOD=10**9+7;  cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.chomp.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def ar2(s1,s2,de=nil) Array.new(s1){Array.new(s2,de)} end
def ar3(s1,s2,s3,de=nil) Array.new(s1){Array.new(s2){Array.new(s3,de)}} end

def desc(ar) ar.sort!{|x,y| y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end
def ceil(a,b) (a.to_f/b).ceil end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end
def rui(ar) s=[0]; ar.size.times{|i| s<<s[-1]+ar[i]}; s end
def rev_rui(ar) s=[0]; ar.size.times.reverse_each{|i| s<<s[-1]+ar[i]}; s end

def puts_yesno(b) puts(b ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def pu(h) begin; require './../nemi_lib/debug.rb'; puts_val(h); rescue LoadError; end; end
########### ( ˘ω˘ )ｽﾔｧ… ###########
s=gs.chars
puts_yesno s.uniq.size!=1


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

const int N = 1000;
vector<int> G[N];

bool found = false;
vector<int> buf,cycle;
int vis[N] = {};

void dfs(int x){
    vis[x] = 2;
    buf.pb(x);

    for(int nx:G[x])if(vis[nx]!=1){
        if(vis[nx]==2 && !found){
            int idx = 0;
            while(buf[idx]!=nx) ++idx;

            vector<int> t;
            int sz = buf.size();
            for(int i=idx; i<sz; ++i) cycle.pb(buf[i]);

            found = true;
        }

        if(!vis[nx]) dfs(nx);
    }

    vis[x] = 1;
    buf.pop_back();
}

int main(){
    int n,m;
    cin >>n >>m;
    vector<pi> e(m);
    rep(i,m){
        int a,b;
        cin >>a >>b;
        --a;
        --b;

        e[i] = {a,b};
        G[a].pb(b);
    }

    rep(i,n)if(!vis[i]){
        dfs(i);
        if(found) break;
    }
    if(!found){
        cout << -1 << "\n";
        return 0;
    }

    rep(loop,n){
        bool upd = false;

        int C = cycle.size();
        vector<int> idx(n,-1);
        rep(i,C) idx[cycle[i]] = i;

        for(const pi &p:e){
            int a = p.fi, b = p.se;
            if(idx[a]!=-1 && idx[b]!=-1 && (idx[a]+1)%C != idx[b]){
                vector<bool> next(C);
                if(idx[a] < idx[b]){
                    fill(all(next), true);
                    for(int i=idx[a]+1; i<idx[b]; ++i) next[i] = false;
                }
                else{
                    fill(all(next), false);
                    for(int i=idx[b]; i<=idx[a]; ++i) next[i] = true;
                }

                vector<int> t;
                rep(i,C)if(next[i]) t.pb(cycle[i]);

                cycle = t;
                upd = true;
                break;
            }
        }
        if(!upd) break;
    }

    cout << cycle.size() << "\n";
    for(int i:cycle) cout << i+1 << "\n";
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#include <bitset>
#include <complex>
#include <cassert>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define GI(i) (scanf("%d",&i))
#define GLL(i) (scanf("%lld",&i))
#define GD(i)  (scanf("%lf",&i))
#define PB          push_back
#define MP          make_pair
#define MT          make_tuple
#define GET0(x)     (get<0>(x))
#define GET1(x)     (get<1>(x))
#define GET2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       (1LL<<60)
#define LLMIN       -(1LL<<60)
#define IMAX        (1<<30)
#define IMIN        -(1<<30)
typedef long long LL;
using namespace std;

int main(void){
    int N;
    LL x;
    GI(N);GLL(x);
    vector<LL> a(N);
    REP(i,N)
        GLL(a[i]);
    sort(ALL(a));
    int ans=0;
    REP(i,N)
        if(x>=a[i]){
            x-=a[i];
            ans++;
        }
    if(ans==N && x!=0)
        ans--;
    printf("%d\n",ans);
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin() x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin() x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define d fi
#define t se

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, k; cin >> n >> k;
	vector<pll> dt(n);
	rep(i, n) cin >> dt[i].t >> dt[i].d;
	sort(rall(dt));
	//おいしい順にk個の集合を作る
	ll sum=0, kind=0;
	priority_queue<ll, vll, greater<ll>> q;
	vector<bool> u(n+1, false);
	rep(i, k){
		sum += dt[i].d;
		if (u[dt[i].t])
			q.push(dt[i].d);
		else
			u[dt[i].t] = true, kind++;
	}
	//入れ替えていく
	ll ans=sum+kind*kind;
	for(int i=k; i<n && !q.empty(); i++){
		if (u[dt[i].t]) continue;
		u[dt[i].t] = true, kind++;
		sum -= q.top(), q.pop();
		sum += dt[i].d;
		ans = max(ans, sum+kind*kind);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 2428
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	int a, b;
	cin >> a;
	cin >> b;
	if(a % b == 0){
		cout << 0;
	}else if(a < b){
		cout << 1;
	}else{
		cout << 1;
	}
}

Measured memory_bytes: 256
import bisect
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = [0]+list(map(int,input().split()))
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
  u,v = map(int,input().split())
  tree[u].append(v)
  tree[v].append(u)
#print(tree)
d = [float("inf")]*(n+1)
ans = [0]*(n+1)

def dfs(now, pre):
  i = bisect.bisect_left(d, a[now])
  tmp = d[i]
  d[i] = a[now]
  ans[now] = bisect.bisect_left(d, float("inf"))
  for nxt in tree[now]:
    if nxt == pre:
      continue
    dfs(nxt, now)
  d[i] = tmp
dfs(1,-1)

for i in ans[1:]:
  print(i)

Measured memory_bytes: 345896
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b;
    cin >> n >> a >> b;
    ll c = n/(a+b);
    if (n - c*(a+b) >= a) PRINT(a*(c+1));
    else PRINT(a*c+n-c*(a+b));
}


Measured memory_bytes: 256
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def per(a, b):
    t = (a, b)
    if t in memo:
        return memo[t]
    re = 1
    for i in range(b):
        re = re * (a - i) % md
    memo[t] = re
    return re

def dfs(i, oi):
    cnt_ko = len(to[i])
    if i == 1:
        re = k * per(k - 1, cnt_ko) % md
    elif cnt_ko == 1:
        return 1
    else:
        re = per(k - 2, cnt_ko - 1)
    for ki in to[i]:
        if ki == oi: continue
        re = re * dfs(ki, i) % md
    return re

md = 10 ** 9 + 7
memo = {}
n, k = map(int, input().split())
to = defaultdict(list)
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a] += [b]
    to[b] += [a]
print(dfs(1, 0))


Measured memory_bytes: 92988
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes                \
    cout << "Yes" << endl; \
    return 0;
#define No                \
    cout << "No" << endl; \
    return 0;
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;

template <typename T>
void print(const T &v);

int main()
{
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    rep(i, N) cin >> x[i] >> y[i];
    vector<int> n(N);
    rep(i, N) n[i] = i;
    double total = 0;
    int cnt = 0;
    do
    {
        for (int i = 0; i < N - 1; i++)
        {
            int xi = x[n[i]], xii = x[n[i + 1]], yi = y[n[i]], yii = y[n[i + 1]];
            double dist = sqrt((xi - xii) * (xi - xii) + (yi - yii) * (yi - yii));
            total += dist;
        }
        cnt++;
    } while (next_permutation(n.begin(), n.end()));
    cout << fixed << setprecision(10) << total / cnt << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
using System.Linq;
using System.Text;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Numerics;
using System.Runtime.CompilerServices;

namespace AtCoder
{
    class Program
    {

        const int BiggestMod = 1000000007;

        public static void Main()
        {

            Console.WriteLine(Console.ReadLine().Substring(0, 3));

        }

    }

}


Measured memory_bytes: 25888
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

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


int main(){
    int N;
    int M;
    ll x[101000];
    ll y[101000];
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        cin >> x[i];
    }

    sort(x, x+M);
    for(int i = M-1; i > 0; i--){
        y[i-1] = x[i] - x[i-1];
        // cout << y[i-1] << endl;
    }
    sort(y, y+M-1);

    ll res = 0;
    for(int i = 0; i < M - N; i++){
        res += y[i];
    }

    cout << res << endl;


    return 0;

}


Measured memory_bytes: 1792
from sys import stdin
input = stdin.readline

n = int(input())
A = list(map(int, input().split()))
dic = {}

for i in range(n):
    a = A[i]
    for j in [a-1, a, a+1]:
        if j not in dic:
            dic[j] = 1
        else:
            dic[j] += 1

cou = 0
for x in dic:
    re_cou = dic[x]
    cou = max(cou, re_cou)

print(cou)

Measured memory_bytes: 19556
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int n,k;

int main()
{
	cin>>n>>k; int p=pow(2,n)-1;
	if(k==0)
	{
		for(int i=0;i<=p;i++) printf("%d %d ",i,i);
		return 0;
	}
	if(k>p) return puts("-1"),0;
	int nw=0;
	for(int i=0;i<=p;i++) if(i!=k) nw^=i;
	if(nw!=k) puts("-1");
	else
	{
		for(int i=0;i<=p;i++) if(i!=k) printf("%d ",i); printf("%d ",k);
		for(int i=p;i>=0;i--) if(i!=k) printf("%d ",i); printf("%d ",k);
	}
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, t;
    cin >> x >> t;
    cout << max(x - t, 0) << "\n";

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

int N;
int ans;

int main(){
	cin >> N;
	for (int i = 1; i <= 9; i++){
		for (int j = 1; j <= 9; j++){
			if (i*j == N){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;

	return 0;
}

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

void main() {
    const tmp = readln.split.to!(int[]);
    const a = tmp[0], b = tmp[1];

    auto current = DateTime(2018, 1, 1);
    auto end = DateTime(2018, a, b);
    end += 1.days;

    int cnt;
    while (current != end) {
        if (current.month.to!int == current.day.to!int) cnt++;
        current += 1.days;
    }
    writeln(cnt);
}



Measured memory_bytes: 256
// Package main provides
//
// File:  d.go
// Author: ymiyamoto
//
// Created on Mon Dec 31 16:35:13 2018
//
package main

import "fmt"

var graph []string
var H, W int

type pos struct {
	x, y int
}

func (p pos) isInRange() bool {
	return 0 <= p.x && p.x < H && 0 <= p.y && p.y < W
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func dfs(a pos, dists [][]int) {
	for _, d := range []pos{{x: 1, y: 0}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 0, y: -1}} {
		p := pos{x: a.x + d.x, y: a.y + d.y}
		if p.isInRange() && graph[p.x][p.y] == '.' {
			dist := dists[a.x][a.y] + 1
			if dist < dists[p.x][p.y] {
				dists[p.x][p.y] = dist
				dfs(p, dists)
			}
		}
	}
}

func countWhites() int {
	ret := 0
	for i := range graph {
		for j := range graph[i] {
			if graph[i][j] == '.' {
				ret++
			}
		}
	}
	return ret
}

func main() {
	fmt.Scan(&H, &W)

	graph = make([]string, H)
	for i := range graph {
		fmt.Scan(&graph[i])
	}

	dists := make([][]int, H)
	for i := range dists {
		dists[i] = make([]int, W)
		for j := range dists[i] {
			dists[i][j] = 1 << 30
		}
	}
	dists[0][0] = 0

	dfs(pos{x: 0, y: 0}, dists)
	if dists[H-1][W-1] == 1<<30 {
		fmt.Println(-1)
		return
	}
	fmt.Println(countWhites() - dists[H-1][W-1] - 1)
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  	cin>>n;
  	int a[n],b[n],c[n],flag=0,ans=0;
  	for(int i=0;i<n;i++){
    	cin>>a[i]>>b[i]>>c[i];
    }
  	int dp[n][3];
  	dp[0][0]=a[0];
  	dp[0][1]=b[0];
  	dp[0][2]=c[0];
  	for(int i=1;i<n;i++){
    	dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
      	dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
      	dp[i][2]=c[i]+max(dp[i-1][1],dp[i-1][0]);
    }
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
}

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

using ll = int64_t;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

  int n;
  std::cin >> n;
  ll t, a;
  std::cin >> t >> a;

  rep(i, n - 1) {
    ll ti, ai;
    std::cin >> ti >> ai;
    ll div = max((t + ti - 1) / ti, (a + ai - 1) / ai);
    a = div * ai, t = div * ti;
  }
  std::cout << t + a << "\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N;
  cin>>N;
  vector<vector<int>> A(N,vector<int>(0));
  vector<pair<int,int>> B(N-1);
  for(int i=0;i<N-1;i++){
    int a,b;
    cin>>a>>b;
    A[a-1].push_back(b-1);
    A[b-1].push_back(a-1);
    B[i]=make_pair(a-1,b-1);
  }
  int K=0;
  for(int i=0;i<N;i++)
    K=max(K,(int)(A[i].size()));
  cout<<K<<endl;
  queue<int> C;
  C.push(0);
  vector<int> D(N,-1);
  D[0]=0;
  map<pair<int,int>,int> E;
  while(!C.empty()){
    int I=C.front(),k=1;
    C.pop();
    for(int i:A[I]){
      if(D[I]==k)
        k++;
      if(D[i]==-1){
        C.push(i);
        D[i]=k;
        E[make_pair(I,i)]=k;
        k++;
      }
    }
  }
  for(pair<int,int> p:B)
    cout<<max(E[p],E[make_pair(p.second,p.first)])<<endl;
}

Measured memory_bytes: 23888
from collections import defaultdict
n = int(input())
s = list(map(int, list(input())))

base = set()
seci = set()
sec = defaultdict(set)

for i in s:
    for j in seci:
        sec[j].add(i)
    for j in base:
        seci.add(j*10+i)
    base.add(i)

count = 0
for v in sec.values():
    count+=len(v)
print(count)

Measured memory_bytes: 44508
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define N 1000005
typedef long long ll;
const ll LLINF=1ll<<60;
//const int mx=1e5+7;
//int n;
//bool visited[mx];
//vector<int> a(mx),b(mx);
//vector<int> g(mx);
// int deg[mx];
//vector<int> adj[mx];
//int sz[mx], par[mx];
//vector<int> ans;
//---dfs--
//vector<ll> val(mx,0);
// int sz=0;
// void dfs(int s, int p){
// 	par[s]=p;
// 	sz[s]=1;
// 	int maxx=0;
// 	for(int x: adj[s]){
// 		if(x!=p){
// 			dfs(x,s);
// 			sz[s]+=sz[x];
// 			maxx=max(maxx,sz[x]);
// 		}
// 	}
// 	maxx=max(maxx,n-sz[s]);
// 	//cout<<"mx "<<s<<" "<<maxx<<"\n";
// 	if(maxx<mn) mn=maxx, c1=s, c2=0;
// 	else if(maxx==mn) c2=s;
// 	//cout<<"mn "<<mn<<"\n";
// }
//---dfs---

//---primes---
// const int N = 1e7 + 10;

// bool prime[N];
 
// int spf[N];
 
// void calc(){
// 	for(int i = 2; i<1e4; i++){
// 		if(prime[i])
// 			continue;
// 		spf[i] = i;
// 		for(int j = i * i; j < N; j += i){
// 			prime[j] = 1;
// 			spf[j] = i;
// 		}
// 	}
// 	for(int i = 2; i < N; i++)
// 		if(!spf[i])
// 			spf[i] = i;
// }

// vector<pair<int,int>> getp(int x){
// 	int curr=x;
// 	vector<pair<int,int>> ans;
// 	while(curr>1){
// 		int a=spf[curr];
// 		int count=0;
// 		while(curr%a==0){ curr/=a; count++;}
// 		ans.push_back(make_pair(a,count));
// 	}
// 	return ans;
// }

// bool ispr(int n) {
// 	if(n==1) return false;
//     for (int i=2;i*i<=n;++i){
//         if(n%i==0){
//             return false;
//         }
//     }
//     return true;
// }
//---primes---

//---segment_tree---
// int upd(int t,int val,int l,int r,int y, int z){
// 	if(y<l||y>r) return tr[val];
// 	if(l==r) return tr[val]=z;
// 	int s=(l+r)/2;
// 	upd(t^1,2*val+1,l,s,y,z);
// 	upd(t^1,2*val+2,s+1,r,y,z);
// 	if(t) tr[val]=tr[2*val+1]|tr[2*val+2];
// 	else tr[val]=tr[2*val+1]^tr[2*val+2];
// 	return tr[val];
// }
//int query(){}
//---segment_tree---

ll power(ll x,ll y){
    ll res=1;
    if(x==0) return 0;
    while(y>0){
        if(y&1) res = (res*x)%MOD ;  
        y=y>>1;
        x=(x*x)%MOD;   
    } 
    return res; 
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int T=1;
	//cin>>T;
	while(T--){
		ll n;
		cin>>n;
		ll a1,a2,a3;
		a1=power(10,n);
		a2=power(9,n);
		a2*=2;
		a2%=MOD;
		a3=power(8,n);
		ll ans=(a1-a2+a3)%MOD;
		ans=(ans+MOD)%MOD;
		cout<<ans<<"\n";
	}
}


Measured memory_bytes: 3656
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rnr(i,a,b) for(int i=int(a);i>=int(b);i--)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int N; cin >> N;
    ll A[N], T[N];
    vector<ll> h(N, -INF);
    rep(i, N) cin >> T[i];
    rep(i, N) cin >> A[i];
    h[0] = T[0];
    h[N - 1] = A[N - 1];
    bool ok = true;
    rng(i, 0, N - 1) {
        if(T[i] != T[i + 1]) {
            if(h[i + 1] != -INF && h[i + 1] > 0) {
                if(h[i + 1] != T[i + 1]) ok = false;
            }
            h[i + 1] = T[i + 1];
        }else {
            h[i + 1] = max(h[i + 1], -T[i + 1]);
            //h[i + 1]はT[i + 1]以下である
        }
    }
    rnr(i, N - 1, 1) {
        if(A[i] != A[i - 1]) {
            if(h[i - 1] != -INF && h[i - 1] < 0) {
                if(-h[i - 1] < A[i - 1]) ok = false;
            }
            if(h[i - 1] != -INF && h[i - 1] > 0)
                if(h[i - 1] != A[i - 1])
                    ok = false;
            h[i - 1] = A[i - 1];
        }else {
            h[i - 1] = max(h[i - 1], -A[i - 1]);
        }
    }
    if(T[N - 1] != A[0] || !ok) {
        cout << 0 << endl;
    }else {
        ll ans = 1;
        rep(i, N) {
            if(h[i] < 0) {
                ans = ans * -h[i] % MOD;
            }
        }
        cout << ans << endl;
    }
}


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

namespace AtCoder
{
    class Program
    {
        #region
        private static int ReadInt() => int.Parse(ReadLine());
        private static IEnumerable<int> ReadSplitInt() => Console.ReadLine().Split(' ').Select(i => int.Parse(i));
        private static IEnumerable<double> ReadSplitDouble() => Console.ReadLine().Split(' ').Select(i => double.Parse(i));

        private static bool IsEven(int n) => n % 2 == 0;
        #endregion

        public static void Main(string[] args)
        {
            var inputs = ReadSplitDouble().ToArray();
            WriteLine(inputs[0] / inputs[1]);
        }
    }
}

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

#if DEBUG && !ONLINE_JUDGE
    #include "header.h"
#else
    #define debug(args...)
#endif

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long lli;
typedef long double ld;

#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(auto i=(a);i<b;i++)

#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
void preprocess(void) {
    return;
}
lli ar[22][22], dp[22][(1<<21)];
int solve(int pos, int mask) {
    if(pos == 0) {
        if(mask == 0) return dp[pos][mask] = 1;
        else return 0;
    }
    if(dp[pos][mask] != -1) return dp[pos][mask];
    lli ans = 0;
    rep(i,0,21) {
        int x = (1<<i);
        if(ar[pos][i+1] && (mask & x)) {
            ans += solve(pos - 1, mask ^ x);
            ans %= MOD;
        }
    }
    return dp[pos][mask] = ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(20);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    preprocess();
    int n; cin>>n;
    rep(i,1,n+1) {
        rep(j,1,n+1) cin>>ar[i][j];
    }
    memset(dp,-1,sizeof dp);
    cout<<solve(n, (1<<n) - 1)<<endl;

}



Measured memory_bytes: 360704
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        //Solve();
        return;
    }

    public static string Solve()
    {
        int N = ReadInt();
        int ans = (N - 1) / 2;
        return ans.ToString();
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


Measured memory_bytes: 11092
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 1e5 + 7;

int a[N];
vector<int> g[N];

int used[N];
vector<int> seen;

void dfs(int cur, int p) {
	used[cur] = 1;
	seen.push_back(a[cur]);
	for (auto t : g[cur]) {
		if (t != p) {
			dfs(t, cur);
		}
	}
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int c = n - m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if (c == 1) {
		cout << 0 << endl;
		return 0;
	}
	multiset<int> s;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			seen.clear();
			dfs(i, -1);
			sort(seen.rbegin(), seen.rend());
			ans += seen.back();
			for (int j = 0; j + 1 < (int)seen.size(); j++) {
				s.insert(seen[j]);
			}
		}
	}
	for (int i = 0; i < c - 2; i++) {
		if (s.empty()) {
			cout << "Impossible\n";
			return 0;
		}
		ans += *s.begin();
		s.erase(s.begin());
	}
	cout << ans << '\n';
}


Measured memory_bytes: 15860
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define r_all(a) (a).rbegin(), (a).rend()

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);
const int MAX_LEN = 3010;

int main() {
  string s, t; cin >> s >> t;
  int ls = (int)s.length(), lt = (int)t.length();

  vvi dp(MAX_LEN+1, vi(MAX_LEN+1, 0));
  rep(i, ls) {
    rep(j, lt) {
      if (s[i] == t[j]) {
        dp[i+1][j+1] = dp[i][j] + 1;
      } else {
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
      }
    }
  }

  string ans = "";
  int p = ls, q = lt;
  while (p>0 && q>0) {
    if (dp[p][q] == dp[p-1][q]) {
      p--;
    } else if (dp[p][q] == dp[p][q-1]) {
      q--;
    } else {
      ans += s[p-1];
      p--; q--;
    }
  }
  reverse(all(ans));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 71296