akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class Class1
{
	static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        string[] input = Console.ReadLine().Split(' ');
        long[] a = new long[N];
        for(int i = 0;i < N;i++)
        {
            a[i] = int.Parse(input[i]);
        }

        long[] b = new long[N];
        long absmin = 1000000;
        long absminAdd = 0;
        for(int i = 0;i < N;i++)
        {
            b[i] = Math.Abs(a[i]);
            if (b[i] < absmin)
            {
                absmin = b[i];
                absminAdd = i;
            }
        }

        long result = b.Sum() - b[absminAdd];

        //-count
        int upc = 0;
        int downc = 0;
        for(int i = 0;i < absminAdd;i++)
        {
            if (a[i] < 0) upc++;
        }

        for(int i = N - 1;i > absminAdd;i--)
        {
            if (a[i] < 0) downc++;
        }

        if (upc % 2 == 0 && downc % 2 == 0) result += a[absminAdd];
        else if (upc % 2 == 1 && downc % 2 == 1) result += a[absminAdd];
        else result += -1 * a[absminAdd];

        Console.WriteLine(result);
    }
}


Measured memory_bytes: 30684
from sys import stdin
n, k = map(int, input().split())
nums = [list(map(int, stdin.readline().split())) for _ in range(n)]
nums.sort(key=lambda x:x[0])
i = 0
while True:
    k -= nums[i][1]
    if k <= 0:
        print(nums[i][0])
        break
    i += 1

Measured memory_bytes: 29056
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	ll x,t;cin>>x>>t;
	cout << max(0ll,x-t) << endl;
	
	return 0;
}

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

using namespace std;
using ll = long long int;

#define REP(i,n) for(ll (i) = 0 ; (i) < (n) ; ++(i))


const int N = 1000;

ll tile[2][N];
ll n;

int bfs(int i , int j)
{
    if(i == 0){
        int k = bfs(i+1,j);
        if(j != n){
            k = max(bfs(i,j+1),k);
        }
        return k + tile[i][j];
    }else{
        if(j != n){
            return tile[i][j] + bfs(i,j+1);
        }
        else{
            return tile[i][j];
        }
    }
}

int main()
{
    cin >> n;
    REP(i,2){
        REP(j,n){
            cin >> tile[i][j];
        }
    }
    cout << bfs(0,0) << endl;
}

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

int main() {
  int rep,j;
  char ch[3];
  cin>>ch;
  for(rep=0,j=1;rep<3;rep++)
  {
    if(ch[rep]=='a')
    j*=1;
    else if(ch[rep]=='b')
    j*=2;
    else if(ch[rep]=='c')
    j*=3;
  }
  if(j==6)
  cout<<"Yes";
  else
  cout<<"No";
}

Measured memory_bytes: 256
num = int(input())
x = list(map(int, input().split()))
n = 0
for i in range(num):
    min_j = i
    for j in range(i, num):
        if x[min_j] > x[j]:
            min_j = j
    if min_j != i:
        x[i], x[min_j] = x[min_j], x[i]
        n += 1
print(' '.join([str(s) for s in x]))
print(n)


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

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

    ll ans = 0;
    ll cou = 1;
    while(1){
        ans += cou;
        if(ans >= n){
            break;
        }
        cou++;
    }

    cout << cou << endl;
}

Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=300000;

int n;
int a[MAXN];

pair<int,int> b[MAXN]; int nb;

bool solve() {
	sort(a,a+n);
	for(int l=0,r=l;l<n;l=r) {
		int v=a[l];
		while(r<n&&a[r]==v) ++r;
		int cnt=r-l;
		b[nb++]=MP(v,cnt);
	}
	sort(b,b+nb);
	assert(nb>=1);
	if(nb==1&&b[0].first==0) return true;
	if(nb==2&&b[0].first==0&&b[1].second==b[0].second*2) return true;
	if(nb==3&&(b[0].first^b[1].first)==b[2].first&&b[1].second==b[0].second&&b[2].second==b[0].second) return true;
	return false;

}

void run() {
	scanf("%d",&n);
	REP(i,n) scanf("%d",&a[i]);
	printf("%s\n",solve()?"Yes":"No");
}

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


Measured memory_bytes: 1152
C = [list(map(int, input().split())) for i in range(3)]
a =[]
b = []
for i in range(3):
    a.append(C[1][i] - C[0][i])
for j in range(3):
    b.append(C[2][j] - C[0][j])
if (a[0] == a[1] and a[1] == a[2]) and (b[0] == b[1] and b[1] == b[2]):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
/*****And nothing else matters!******/

#include<bits/stdc++.h>
using namespace std;

#define pi 3.1415926535
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define llu unsigned long long
#define setbits(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define tc int test_case; cin >> test_case; while(test_case--)
#define f(i,a,n) for(int i = a ; i < n ; i++)
#define rf(i,n,a) for(int i = n-1 ; i >= a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define get(a,n) f(i,0,n) cin >> a[i];
#define show(a,n) f(i,0,n) cout << a[i] << " "; cout << endl;
#define sp(x) fixed << setprecision(10) << x
#define fast ios:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trace(x) cerr << '>' << #x << ':' << (x) << "\n"
#define trace2(x,y) cerr<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n"
#define trace3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define trace4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"

typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

const int inf = 1e9;
const ll inf64 = 1e18;
const int mod = inf + 7;
const int N = 1e6 + 10;

int main()
{
    fast;
    ll n;
    cin >> n;
    ll a = 1, b = 1, c = 1;
    f(i,0,n)
    {
        a = a * 10 % mod;
        b = b * 9 % mod;
        c = c * 8 % mod;
    }

    cout << (a - 2*b + c + 10ll * mod) % mod;
}


Measured memory_bytes: 3588
function Main(input) {
  "use strict"
  const str = input.split("\n").shift()
  const len = str.length
  function judgePalindrome(str){
    const n = str.length
    let preStr, postStr
    if(n === 1) return true
    else if(n % 2 === 1){
      preStr = str.slice(0, (n - 1) / 2)
      postStr = str.slice((n + 1) / 2, n)
    }else{
      preStr = str.slice(0, n / 2)
      postStr = str.slice(n / 2)
    }
    
    return (preStr === postStr.split("").reverse().join("")) ? preStr : false
  }
  
  const preStr = judgePalindrome(str)
  if(!preStr) console.log("No")
  else{
    if(judgePalindrome(preStr)) console.log("Yes")
    else console.log("No")
  }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

struct mp{
	int to,dis;
	mp(int x,int y):to(x),dis(y){}
};

void trip(int nw,int f,int64_t dist,vector<vector<mp>>&v,vector<int64_t>&d){
	d.at(nw)=dist;
	for(auto&i:v.at(nw)){
		if(i.to!=f)trip(i.to,nw,dist+i.dis,v,d);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<vector<mp>>v(n+1);
	for(int i=1;i<n;++i){
		int a,b,c; cin>>a>>b>>c;
		mp x(a,c),y(b,c);
		v.at(a).emplace_back(y);
		v.at(b).emplace_back(x);
	}
	int q,k; cin>>q>>k;
	vector<int64_t>d(n+1);
	trip(k,-1,0,v,d);
	for(int i=0;i<q;++i){
		int x,y; cin>>x>>y;
		cout<<d.at(x)+d.at(y)<<"\n"s;
	}
}

Measured memory_bytes: 17168
N,A,B = list(map(int,input().split()))

item=[]
for i in range(N):
    a,b,c = list(map(int,input().split()))
    item.append([a,b,c])

D = [[[10**27 for i in range(401)] for j in range(401)] for k in range(N+1)]
D[0][0][0] = 0
for i in range(N):
    for j in range(401):
        for k in range(401):
            if D[i][j][k]<10**26:
                D[i+1][j][k]=min(D[i+1][j][k],D[i][j][k])
                D[i+1][j+item[i][0]][k+item[i][1]] = min(D[i+1][j+item[i][0]][k+item[i][1]],D[i][j][k]+item[i][2])

i=1
min_cost=10**27
while A*i<=400 and B*i<=400:
    min_cost = min(D[N][A*i][B*i],min_cost)
    i+=1
if min_cost==10**27:
	print(-1)
else:
	print(min_cost)

Measured memory_bytes: 61168
/**
 * @author torith
 * @date 2018-11-06
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K; cin >> N >> K;
    char D[9];
    for (int i = 0; i < K; ++i) {
        cin >> D[i];
    }

    int ans = N;
    while(1) {
        if (N <= ans) {
            bool frg = true;
            string str_ans = to_string(ans);
            for (int i = 0; i < str_ans.size(); ++i) {
                for (int j = 0; j < K; ++j) {
                    if (D[j] == str_ans[i]) {
                        frg = false;
                    }
                }
                if(!frg) break;
            }
            if(frg) break;
        }
        ans++;
    }

    cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

const int N = 1000;
vector<int> prime(N, 1);

void Eratosthenes(){
    for(int i = 2; i < sqrt(N); i++){
        if(prime[i] == 1){
            for(int j = 0; i * (j + 2) < N; j++){
                prime[i * (j + 2)] = 0;
            }
        }
    }
}

int main(){
    vector<int> num;
    vector<int> ans(N + 1, 0);
    int n,tmp;
    long long int sum = 1;

    Eratosthenes();

    for(int i = 0; i < N; i++){
        if(prime[i] == 1 && i != 0 && i != 1){
           num.push_back(i);
        }
    }

    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < num.size(); j++){
            if(i % num[j] == 0){
                tmp = i;
                while(1){
                    if(tmp < num[j] || tmp % num[j] != 0){
                        break;
                    }
                    tmp /= num[j];
                    ans[num[j]]++;
                }
            }
        }
    }
    /*
    int ans = 1;
    for (int i = 0; i < n; i++) {
        ans = ans * a[i] % (1000000007);
    }*/

    for(int i = 0; i < ans.size(); i++){
        if(ans[i] > 0){
            sum = sum * (ans[i] + 1) % (1000000007);
            
        }
    }

    cout << sum << endl;

    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(){
  vector<string> v;
  string s,t;
  cin>>s>>t;
  rep(i,s.size()-t.size()+1){
    string tmp=s.substr(i,t.size());
    bool flag=true;
    rep(j,t.size()) if(!(t[j]==tmp[j] || tmp[j]=='?')) flag=false;
    if(flag){
      string ans=s.substr(0,i)+t+s.substr(i+t.size());
      rep(j,ans.size()) if(ans[j]=='?') ans[j]='a';
      v.push_back(ans);
    }
  }
  if(v.size()!=0){
    sort(v.begin(),v.end());
    cout<<v[0]<<endl;
  }else{
    cout<<"UNRESTORABLE"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::string str;

using namespace std;

inline int nxt(){int x;cin>>x;return x;}

inline str nxt_str(){str x;cin>>x;return x;}

inline ll nxt_ll(){ll x;cin>>x;return x;}

/*
a,b-fixed
a<b+c => a-b<c
b<c+a => b-a<c
c<a+b => c<a+b

max(a-b,b-a)<c<a+b

*/

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n=nxt();
    vi l(n);
    rep(i,0,n-1)l[i]=nxt();
    vi cnt(2000);
    rep(i,0,n-1)cnt[l[i]]++;
    rep(i,1,1999)cnt[i]+=cnt[i-1];
    ll ans=0;
    rep(i,0,n-1){
        rep(j,i+1,n-1){
            int a=l[i],b=l[j];
            int le=max(a-b,b-a);
            int re=a+b;
            ans+=max(cnt[re-1]-cnt[le],0);
            if(le<a&&a<re) ans--;
            if(le<b&&b<re) ans--;
        }
    }
    cout<<ans/3;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	int n, k;
	cin >> n >> k;
	
	lli ans = k;
		
	rep(i, n-1) ans *= (k-1);	
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>

using namespace std;
typedef long long ll;
ll N;

int main(){
    
    ll A, B, C;
    cin >> A >> B >> C;
    ll X, Y;
    cin >> X >> Y;
    ll x = X;
    ll y = Y;

    if(X < Y){
        swap(X, Y);
        swap(x, y);
        swap(A, B);
    }

    ll ans = 0;
    for(ll i = 0; i < max(X, Y); i++){
        if(y == 0){
            break;
        }
        if(A + B > 2 * C && x > 0 && y > 0){
            ans += 2 * C;
        }else{
            ans += A + B;
        }

        x--;
        y--;
    }

    for(ll i = 0; i < x; i++){
        if(A > 2 * C){
            ans += 2 * C;
        }else{
            ans += A;
        }
    }

    cout << ans << endl;

} 

Measured memory_bytes: 256
n,k = gets.chomp.split(' ').map(&:to_i)
p = gets.chomp.split(' ').map(&:to_i)

ruiseki_array = [0]
n.times do |i|
  ruiseki_array[i+1] = ruiseki_array[i] + ((p[i] + 1) /2.000000)
end
max = -1
(ruiseki_array.size-k).times do |i|
  if ((ruiseki_array[i+k] - ruiseki_array[i]) > max)
    max = ruiseki_array[i+k] - ruiseki_array[i]
  end
end
puts max

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


int main() {
    ll L,R;
    cin>>L>>R;
    ll mn =2018;
    if((R-L+1)>=2019){
        cout<<0<<endl;
        return 0;
    }
    else {
        for(ll i=L;i<R;i++){
        for(ll j=L+1;j<=R;j++){
            mn=min(mn,(i*j)%2019);
        }
        }
}
cout<<mn<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int i = 1;
		for (; i <= 9; i++) {
			if (n <= i * 111) {
				break;
			}
		}
		System.out.println(i * 111);
		sc.close();
	}
}


Measured memory_bytes: 21844
#include <stdio.h>
#define DATA_NUM (200)

int calc_digit(int);

int main(void)
{
  int a, b;

  while(scanf("%d %d\n",&a,&b)!=EOF)
  {
    printf("%d\n",calc_digit(a+b));
  }

  return 0;		
}
	
int calc_digit(int x)
{
  int i;

  for(i=1; ; i++)
  {
    x = x/10;
	if(x==0) break;
  }  	  
  return i;
}

Measured memory_bytes: 604
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Numerics;
using System.Collections.Generic;
using System.Linq;
using System;

namespace bla2
{
    class Program
    {
        static void Main()
        {
            string[] s = Console.ReadLine().Split();
            int n = int.Parse(s[0]);
            int m = int.Parse(s[1]);
            List<Tuple<long, long, long>> a = new List<Tuple<long, long, long>>();
            for (int i = 0; i < n; i++)
            {
                s = Console.ReadLine().Split();
                a.Add(new Tuple<long, long, long>(long.Parse(s[0]), long.Parse(s[1]), long.Parse(s[2])));
            }
            long max = int.MinValue;
            max = Math.Max(max, fmax(a, 1, 1, 1, m));
            max = Math.Max(max, fmax(a, -1, 1, 1, m));
            max = Math.Max(max, fmax(a, 1, -1, 1, m));
            max = Math.Max(max, fmax(a, 1, 1, -1, m));
            max = Math.Max(max, fmax(a, -1, -1, 1, m));
            max = Math.Max(max, fmax(a, 1, -1, -1, m));
            max = Math.Max(max, fmax(a, -1, 1, -1, m));
            max = Math.Max(max, fmax(a, -1, -1, -1, m));
            Console.WriteLine(max);
        }

        static long fmax(List<Tuple<long, long, long>> c, int maxa, int maxb, int maxc, int count)
        {
            List<long> sums = new List<long>();
            for (int i = 0; i < c.Count; i++)
            {
                sums.Add(c[i].Item1 * maxa + c[i].Item2 * maxb + c[i].Item3 * maxc);
            }
            sums.Sort();
            sums.Reverse();
            long r = 0;
            for (int i = 0; i < count; i++)
            {
                r += sums[i];
            }
            return r;
        }
    }
}


Measured memory_bytes: 13280
#include <bits/stdc++.h>
using namespace std;
long long n,m,p,i,a;
int main()
{
  //  freopen("a.in","r",stdin);
  //  freopen("a.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    n-=m;
    p=1;
    for(i=1; i<=m; ++i)
        p*=2;
    a=(1900*m+100*n)*p;
    printf("%lld\n",a);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N, M, K;
string S, T;
vector<int> A;
int dp[111111] = {};
//=============================
void input()
{
    cin>>N;
}
//=============================
void func() {}
//=============================
void solve()
{
    rep(i,N+2)dp[i]=INF;
    dp[0] = 0;
    A.push_back(1);
    for (int i=6;i<=N; i*=6){
        A.push_back(i);
    }
    for (int i=9; i<=N; i*=9){
        A.push_back(i);
    }

    rep(i,A.size()){
        rep(j,N+1){
            if (j+A[i] > N) break;
            dp[j+A[i]] = min(dp[j+A[i]], dp[j]+1);
        }
    }
    cout<<dp[N]<<endl;

}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

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

int main(){

    lint n,x,y;
    cin >> n >> x >> y;

    vector<lint> k(n);

    rep(i,n)k[i] = 0;

    for(lint i = 1; i <= n; ++i){
        for(lint j = i+1; j <= n; ++j){
            lint dis = j-i;
            if(i <= x){
                if(y <= j){
                    dis -= y-x-1;
                }
                else {
                    dis = min(dis, x-i+y-j+1);
                }
            }else{
                if(y >= j){
                    dis = min(dis, i-x+y-j+1);
                }else{
                    dis = min(dis, i-x+j-y+1);
                }
            }
            ++k[dis];
        }
    }

    for(lint i = 1; i < n; ++i){
        cout << k[i] << endl;
    }

}

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

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> a(H);
	for (int i = 0; i < H; ++i) {
		cin >> a[i];
	}
	vector<bool> row(H, false);
	vector<bool> col(W, false);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (a[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}
	for (int i = 0; i < H; i++) {
		if (row[i]) {
			for (int j = 0; j < W; j++) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x,ans;
  cin>>x;
  if(x<600){
    ans=8;
  }else if(x<800){
    ans=7;
  }else if(x<1000){
    ans=6;
  }else if(x<1200){
    ans=5;
  }else if(x<1400){
    ans=4;
  }else if(x<1600){
    ans=3;
  }else if(x<1800){
    ans=2;
  }else{
    ans=1;
  }
  cout<<ans<<endl;
}

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

char grid[55][55];

int main(){
  int h,w;
  cin>>h>>w;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      cin>>grid[i][j];
    }
  }
  bool ans=1;
  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      if(grid[i][j]=='#'){
        if(grid[i+1][j]!='#'&&grid[i-1][j]!='#'&&grid[i][j+1]!='#'&&grid[i][j-1]!='#')ans=0;
      }
    }
  }
  if(ans)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}




Measured memory_bytes: 3620
# D
import numpy as np

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(a_list[:(connec - 2)]))


Measured memory_bytes: 47408
#include <stdio.h>
int main(void){
    int a,b,ans;
    char op;
    scanf("%d %c %d",&a,&op,&b);
    if(op=='+'){
        ans=a+b;
    }
    else {
        ans=a-b;
    };
    printf("%d",ans);
    return 0;
};


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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  int maxH = 0;
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] >= maxH) {
      res += 1;
      maxH = a[i];
    }
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void spread(int y, int x, vector<vector<bool> >& resField, vector<pair<int, int> > enposes);

int main() {
  int w, h;
  while(cin >> w >> h, w || h) {
    vector<vector<bool> > wfield(h, vector<bool>(w, false));
    vector<vector<bool> > bfield(h, vector<bool>(w, false));
    vector<vector<char> > qfield(h, vector<char>(w));
    vector<pair<int, int> > wposes;
    vector<pair<int, int> > bposes;
    for(int y = 0; y < h; ++y) for(int x = 0; x < w; ++x) {
      char c;
      cin >> c;
      qfield[y][x] = c;
      if(c == 'W') wposes.push_back(make_pair(y, x));
      if(c == 'B') bposes.push_back(make_pair(y, x));
    }
    for(auto&& wpos : wposes) spread(wpos.first, wpos.second, wfield, bposes);
    for(auto&& bpos : bposes) spread(bpos.first, bpos.second, bfield, wposes);
    // for(auto&& cols : wfield) {
    //   for(auto&& bs : cols) cout << bs;
    //   cout << endl;
    // }
    // cout << endl;
    // for(auto&& cols : bfield) {
    //   for(auto&& bs : cols) cout << bs;
    //   cout << endl;
    // }
    int answ, ansb;
    answ = ansb = 0;
    for(int y = 0; y < h; ++y) for(int x = 0; x < w; ++x) {
      if(wfield[y][x] xor bfield[y][x] && qfield[y][x] == '.') {
        answ += wfield[y][x];
        ansb += bfield[y][x];
      }
    }
    cout << ansb << ' ' << answ << endl;
  }
  return 0;
}

void spread(int y, int x, vector<vector<bool> >& resField, vector<pair<int, int> > enposes) {
  int dy[] = {-1, 0, 1, 0};
  int dx[] = {0, -1, 0, 1};
  int h = resField.size();
  int w = resField[0].size();
  if(y >= 0 && y < h && x >= 0 && x < w && !resField[y][x] && count(begin(enposes), end(enposes), make_pair(y, x)) == 0) {
    resField[y][x] = true;
    for(int i = 0; i < 4; ++i) spread(y + dy[i], x + dx[i], resField, enposes);
  }
}

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

int main() {
   int n,m,x,ans=1e8,tmp=0;
   cin >> n >> m >> x;
   vector<int> c(n);
   vector<int> cnt(m,0);
   vector<vector<int>> a(n,vector<int>(m));
   rep(i,n){
       cin >> c[i];
       rep(j,m){
           cin >> a[i][j];
       }
    }
    bool flag=true;
    for (int bit = 0; bit < (1<<n); ++bit) {
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) {
                rep(j,m){
                    cnt[j] += a[i][j];
                }
                tmp += c[i];
            }
        }
        rep(i,m){
            if(cnt[i]<x) flag = false;
        }
        if(flag) ans = min(ans,tmp);
        tmp = 0;
        flag = true;
        rep(i,m){
            cnt[i] = 0;
        }
    }
    if(ans!=1e8) cout << ans << endl;
    else cout << -1 << endl;
}

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

int main(){
  int n,q; 
  string s;
  cin>>n>>q>>s;
  vector<int> t(n,0);
  for(int i=0;i<n-1;i++){
    int a=0;
    if(s.substr(i,2)=="AC") a++;
    t[i+1] = t[i]+a;
  }
  for(int i=0;i<q;i++){
    int l,r; cin>>l>>r;
    cout<<t[r-1]-t[l-1]<<endl;
  }
}

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



int main(){
    int E,y,z;
    while (cin >> E && E!=0) {
        int minimum=1000000;
        for (z=0; z*z*z<=E; z++) {
            for (y=0; y*y<=E-z*z*z; y++) {
                minimum=min(minimum,E+y+z-(y*y+z*z*z));
            }
        }
        cout << minimum << endl;
    }
}



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

const int N=100100;
int n,m,a[N],b[N],q;
char S[N],T[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>S>>T>>q;n=strlen(S);m=strlen(T);
	for(int i=1;i<=n;++i)a[i]=a[i-1]+(S[i-1]=='A'?1:-1);
	for(int i=1;i<=m;++i)b[i]=b[i-1]+(T[i-1]=='A'?1:-1);
	for(;q --> 0;){
		int x,y,z,w;cin>>x>>y>>z>>w;
		int res=(a[y]-a[x-1])-(b[w]-b[z-1]);
		cout<<(res%3?"NO\n":"YES\n");
	}
	return 0;
}


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

const int inf = 1000000000000000LL;

signed main() {
	int n, t;
	cin >> n >> t;
	int ans = inf;
	rep(i, n) {
		int c, s;
		cin >> c >> s;
		if(s <= t) {
			ans = min(ans, c);
		}
	}
	if(ans == inf) {
		cout << "TLE" << endl;
	}
	else {
		cout << ans << endl;
	}
}

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    for(int i=1; i<100000; i++) {
        if(i*8/100 == a && i/10 == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
using namespace std;
using ll = long long;
int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
	ll n, m, h, w;
	ll x;
	//cin >> x;
	string s;
	cin >> a;
	if (a==1)
	{
		cout << "Hello World" << endl;

	}
	else
	{
		cin >> a;
		cin >> b;
		cout << a+b << endl;

	}

	//printf("? %lld\n", q); fflush(stdout);
	//cout << sum << endl;
	//cout <<  endl;
	return 0;
}

//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}




//
//ll insuusyurui[1000] = {};
//ll insuukazu[1000] = {};
//ll memo[4000] = {};
//ll memo2[4000] = {};
//cin >> n;
//cin >> m;
//a = 2;
//// √n ≧ a ( n ≧ a * a ) の間ループ処理
//while (n >= a * a) {
//	// a で割り切れたら、a は素因数
//	// そして、割られる数を a で割る
//	// a で割り切れなかったら、 a を 1 増加させる
//	if (n % a == 0) {
//		printf("%lld * ", a);
//		insuukazu[c]++;
//		n /= a;
//	}
//	else {
//		a++;
//		//if (insuukazu[c] != 0)
//		{
//			c++;
//			//cout << c << endl;
//
//		}
//	}
//}
//printf("%lld\n", n);
//for (int i = 0; i < c; i++)
//{
//	//cout << insuukazu[i] << endl;
//}
//
//cout << "Yes" << endl;

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
main()
{
	long h,w;cin>>h>>w;
	long ans=1e9;
	long a,b,c;
	if(h%3==0||w%3==0)
	{
		cout<<0<<endl;
		return 0;
	}
	ans=min(h,w);
	for(int i=1;i<h;i++)
	{
		a=i*w;
		b=(h-i)*(w/2);
		c=(h-i)*((w+1)/2);
		ans=min(ans,max(max(a,b),c)-min(min(a,b),c));
	}
	for(int i=1;i<w;i++)
	{
		a=i*h;
		b=(w-i)*(h/2);
		c=(w-i)*((h+1)/2);
		ans=min(ans,max(max(a,b),c)-min(min(a,b),c));
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <stdio.h>
#include <bitset>
#include <complex>
#include <iomanip>
#include <math.h>
using namespace std;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    return x*y/(T)GCD(x,y);
}
int main(){
    int n; cin >> n;
    int now[100010];
    fill(now,now+100010,-1);
    int res = 0;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        int ok = res;
        int ng = -1;
        while(abs(ok-ng) > 1){
            int mid = (ok+ng)/2;
            if (now[mid] < a){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        if (ok == res){
            ++res;
        }
        now[ok] = a;
    }
    cout << res << endl;
}





Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<string>
#include<map>
#include<queue>

using namespace std;

int main(void){

    string n; cin >> n;

    int sum = 0;

    for(int i = 0;n[i] != '\0';i++){
        sum += n[i]-'0';
    }

    cout << (atoi(n.c_str()) % sum == 0 ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    h = [int(input()) for _ in range(n)]
    h.sort()
    res = 10**20
    for i in range(k-1, n):
        res = min(res, h[i]-h[i-k+1])
    print(res)

if __name__ == '__main__':
    main()

Measured memory_bytes: 43868
N=int(input())
A=list(map(int,input().split()))

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Measured memory_bytes: 32204
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
ilelec = lambda: map(int1,input().split())
alelec = lambda: list(map(int1, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
#MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

S = input()
T = input()
n = len(T)
mini = n
for i in range(len(S)-len(T)+1):
    x = S[i:i+n]
    c = 0
    for j in range(n):
        if x[j] != T[j]:
            c+=1
    mini = min(mini,c)
print(mini)
        

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

int main() {
  char c;
  cin >> c;

  if (c=='A') {
    cout << 'T';
  } else if (c=='T') {
    cout << 'A';
  } else if (c=='G') {
    cout << 'C';
  } else {
    cout << 'G';
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n, k;

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

    llong ans = k;
    for (int i = 0; i < n - 1; i++) {
        ans *= k - 1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define MAX_N 20001

using namespace std;

int main(){
  int a[MAX_N],b[MAX_N];
  char op[MAX_N];
  int i = 0;
  while(1){
    cin >> a[i] >> op[i] >> b[i];
    if(op[i] == '?') break;
    i++;
  }
  for(int j=0;j < i;j++){
    switch(op[j]){
      case '+':
      cout << a[j] + b[j] << endl;
      break;
      case '-':
      cout << a[j] - b[j] << endl;
      break;
      case '*':
      cout << a[j] * b[j] << endl;
      break;
      case '/':
      cout << a[j] / b[j] << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 3124
//What day is today?
#include<bits/stdc++.h>
using namespace std;

int md[12]={31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main(){
  int m, d;
  while(cin >> m >> d){
    int sumd=0;
    if(m==0)break;
    for(int i=0; i<m-1; i++){
      sumd+=md[i];
    }
    sumd+=d;
    switch(sumd%7){
    case 1 : cout << "Thursday" << endl; break;
    case 2 : cout << "Friday" << endl; break;
    case 3 : cout << "Saturday" << endl; break;
    case 4 : cout << "Sunday" << endl; break;
    case 5 : cout << "Monday" << endl; break;
    case 6 : cout << "Tuesday" << endl; break;
    case 0 : cout << "Wednesday" << endl; break;
    }
  }
  return 0;
}

Measured memory_bytes: 1152
//8:45
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};

void ff(int (*p)[8],int c,int y,int x){
  if(c==p[y][x])return;
  int b=p[y][x];
  p[y][x]=c;
  for(int i=0;i<4;i++){
    if(0<=y+dy[i]&&y+dy[i]<8&&0<=x+dx[i]&&x+dx[i]<8&&b==p[y+dy[i]][x+dx[i]]){
      ff(p,c,y+dy[i],x+dx[i]);
    }
  }
}

int fc(int (*p)[8],int c,int y,int x){
  int sum=0;
  if(p[y][x]==c){
    p[y][x]=0;
    sum++;
    for(int i=0;i<4;i++){
      if(0<=y+dy[i]&&y+dy[i]<8&&0<=x+dx[i]&&x+dx[i]<8){
	sum+=fc(p,c,y+dy[i],x+dx[i]);
      }
    }
  }
  return sum;
}

int cc(int (*p)[8],int c,int r){
  if(r>1){
    int mc=0;
    for(int i=1;i<=6;i++){
      int tp[8][8];
      memcpy(tp,p,sizeof(tp));
      ff(tp,i,0,0);
      mc=max(mc,cc(tp,c,r-1));
    }
    return mc;
  }else{
    int tp[8][8];
    memcpy(tp,p,sizeof(tp));
    ff(tp,c,0,0);
    return fc(tp,c,0,0);
  }
}


int main(){
  for(int h,w,c;cin>>h>>w>>c,h|w|c;){
    int panel[8][8]={};
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin>>panel[i][j];
      }
    }
    cout<<cc(panel,c,5)<<endl;
  }
  return 0;
}

Measured memory_bytes: 868
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int a;
	int b,c,x,y=0,n;
	cin>>n>>b>>c;
	for(x=1;x<=n;x++)
	{
		cin>>a;
		if(a<b||a>=c)
		{
			y++;
		}
	}
	cout<<y<<endl;
}

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

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

namespace
{
	ll ModPow(ll x, ll n, ll mod)
	{
		ll res = 1;
		while (n > 0)
		{
			if (n & 1)
				res = res * x %mod;
			x = x * x % mod;
			n >>= 1;
		}
		return res;
	}
}
void Nikkei2B()
{
	ll MOD = 998244353;
	int N;
	cin >> N;
	vector<int> dist(N);
	for (int i = 0; i < N; ++i)
	{
		int D;
		cin >> D;
		if (i == 0 && D != 0)
		{
			cout << 0 << endl;
			return;
		}
		if (i > 0 && D == 0)
		{
			cout << 0 << endl;
			return;
		}
		++dist[D];
	}
	for (int i = 1; i < N; ++i)
	{
		if (dist[i - 1] == 0 && dist[i] > 0)
		{
			cout << 0 << endl;
			return;
		}
	}
	ll ans = 1;
	for (int i = 1; i < N; ++i)
	{
		if (dist[i] == 0)
		{
			cout << ans << endl;
			return;
		}
		ans *= ModPow(dist[i - 1] , dist[i], MOD);
		ans %= MOD;
	}
	cout << ans << endl;

}

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


Measured memory_bytes: 640
loop do
    x = gets.to_i
    break if x == 0
    ans = ''
    sign = 1
    until x == 0
        if sign > 0
            ans = (x % 10).to_s + ans
            x /= 10
        else
            if x % 10 == 0
                ans = ?0 + ans
            else
                ans = (10 - x % 10).to_s + ans
                x += 10
            end
            x /= 10
        end
        sign *= -1
    end
    puts ans
end



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


int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(M);
  vector<int> b(M);
  for(int i = 0; i < M; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<int> num(N);
  for(int i = 0; i < M; ++i) {
    num[a[i] - 1]++;
    num[b[i] - 1]++;
  }
  for(int i = 0; i < N; ++i) {
      cout << num[i] << endl;
  }
 }

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define pii pair <int, int>
#define XX first
#define YY second

// constants:
const int mn = 200005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 0;
const bool is_interactive = 0;

// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"

// data preprocessing: (e.g.: divisor generating, prime sieve)
void preprocess()
{
  
}

// global variables:
int n;
int POW(int u, int v) {
  if (v == 0) return 1;
  int mid = POW(u, v/2);
  mid = (mid*mid)%mod;
  if (v&1) return (mid*u)%mod;
  else return mid;
}
// main solution goes here:
void execute(int test_number)
{
  cin>>n;
//   cout << POW(10, n) <<"\n";
  cout<<(POW(10, n) - POW(9, n) - POW(9, n) + POW(8, n) + 2*mod)%mod;
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_



















signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;

    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: https://www.codeforces.com/profile/low_
// ...or linkedIn: https://www.linkedin.com/in/daniel-to-83045a19a/
// I use VS Code. Here's a JSON format for my template: https://pastebin.com/xH2yRdwx


Measured memory_bytes: 3588
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int a,b,c,n;
	while(cin>>a>>b>>c>>n,a){
		int p[301]={0};
		vector<vector<int> > q;
		rep(i,n){
			vector<int> t(4);
			cin>>t[0]>>t[1]>>t[2]>>t[3];
			if(t[3])p[t[0]]=p[t[1]]=p[t[2]]=1;
			else q.push_back(t);
		}
		rep(i,q.size()){
			int c=0; rep(j,3)c+=p[q[i][j]]==1;
			if(c==2)rep(j,3)if(p[q[i][j]]==0)p[q[i][j]]=2;
		}
		rep(i,a+b+c)cout<<2-p[i+1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,k,a[100005],i,ans=1e18;
	scanf("%lld%lld",&n,&k);
	for(i=0;i<n;i++) scanf("%lld",&a[i]);
	for(i=0;i<=n-k;i++)
	{
		if(a[i]<=0&&a[i+k-1]<=0) ans=min(ans,abs(a[i]));
		else if(a[i]>=0&&a[i+k-1]>=0) ans=min(ans,a[i+k-1]);
		else ans=min(min(ans,2*abs(a[i])+abs(a[i+k-1])),abs(a[i])+2*abs(a[i+k-1]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <string>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const ll mod=1000000007ll;

const ll hmax=100000;
const ll wmax=100000;



int main(){
    string s;
    cin>>s;
    ll l,r;
    l=-1;
    r=-1;
    for(ll i=0;i<s.length()-1;i++){
        if(i==s.length()-2){
            if(s[i]==s[i+1]){
                l=i+1;
                r=i+2;
                break;
            }
        }
        else{
            if(s[i]==s[i+1]){
                l=i+1;
                r=i+2;
                break;
            }
            if(s[i]==s[i+2]){
                l=i+1;
                r=i+3;
                break;
            }
        }
    }
    cout<<l<<" "<<r<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, A, B;
  cin >> n >> A >> B;
  
  bool c=0;
  for(int i=A; i<=B; i++){
  if(i%n == 0){
  c=1;
  break;
  }
  }
  if(c){
    cout << "OK" << endl;
  }
  else cout << "NG" << endl;
}


Measured memory_bytes: 3580
using System;

class ABC073A
{
	static public void Main(string[] args)
	{
		string N = Console.ReadLine();
		if(N[0] == '9' || N[1] == '9')
		{
			Console.WriteLine("Yes");
		}
		else
		{
			Console.WriteLine("No");
		}
	}
}


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

V = [[] for i in range(N)]

tmp = []

for i in range(M):
    a, b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
    tmp.append([a, b])
    

def DFS(now_V, now_Log, ans):
    
    if sum(now_Log)==N:
        return 1
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
    
    return ans

count = 0
          
for i in range(M):
    
    Log = [0]*N
    Log[0] = 1
    
    V[tmp[i][0]-1].remove(tmp[i][1]-1)
    V[tmp[i][1]-1].remove(tmp[i][0]-1)
    if DFS(0, Log, 0)<1:
        count = count+1
    V[tmp[i][0]-1].append(tmp[i][1]-1)
    V[tmp[i][1]-1].append(tmp[i][0]-1)
    
print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>

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

using namespace std;

typedef pair<int,int> pii;
typedef long long int lli;

int main () {
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    vector<int> a(N);
    vector<int> b(N);
    vector<int> c(N);
    REP (i, 0, N) cin >> a[i] >> b[i] >> c[i];
    vector<map<pii,int>> m(N + 1);
    m[0][make_pair(0, 0)] = 0;
    REP (i, 0, N) {
        for (auto it = m[i].begin(); it != m[i].end(); it++) {
            pii p = it -> first;
            int cost = it -> second;
            pii next = make_pair(p.first + a[i], p.second + b[i]);
            if (m[i + 1].count(next)) {
                m[i + 1][next] = min(m[i + 1][next], cost + c[i]);
            } else {
                m[i + 1][next] = cost + c[i];
            }
            if (m[i + 1].count(p)) {
                m[i + 1][p] = min(m[i + 1][p], cost);
            } else {
                m[i + 1][p] = cost;
            }
        }
    }
    int ans = 1 << 30;
    for (auto it = m[N].begin(); it != m[N].end(); it++) {
        pii p = it -> first;
        int cost = it -> second;
        if (cost == 0) continue;
        if ((lli)p.first * Mb == (lli)p.second * Ma) {
            ans = min(ans, cost);
        }
    }
    if (ans == (1 << 30)) ans = -1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 19200
#include<bits/stdc++.h>
#include<string.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define see(x) cout<<#x<<" : "<<(x)<<endl;
#define ya cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define ff first
#define sc second
typedef long long ll;
using namespace std;
string s[10];
ll row[10],col[10];
int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(NULL),cout.tie(NULL);
    //freopen("test.txt","r",stdin);
    ll h,w,k,i,j,n,sum=0,ans=0,l,m,cnt=0;
    cin>>h>>w>>k;
    for(i=0;i<h;i++)
    {
        cin>>s[i];
    }
    for(i=0;i<(1<<h);i++)
    {
        for(j=0;j<(1<<w);j++)
        {
            cnt=0;
            for(l=0;l<h;l++)
            {
                for(m=0;m<w;m++)
                {
                    if(( (1<<l) & i ) && ((1<<m) & j) && (s[l][m]=='#'))
                    cnt++;
                }
            }
            if(cnt==k)ans++;
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>

int a,b,c,d,e,f,g,h,i;
int flag;

int main(void){
	scanf("%d %d %d", &a,&b,&c);
	scanf("%d %d %d", &d,&e,&f);
	scanf("%d %d %d", &g,&h,&i);

        //printf("%d %d %d %d %d %d %d %d %d\n", a,b,c,d,e,f,g,h,i);
	if(b-a==e-d && e-d==h-g && c-b==f-e && f-e==i-h && a-d==b-e && b-e==c-f && d-g==e-h && e-h==f-i)	printf("Yes");
	else printf("No");

	return 0;
}


Measured memory_bytes: 128