akhauriyash/Code-Regression huggingface dataset:
import math
a,b,h,m=map(int, input().split(" "))

kakua = 30 * h + 0.5 * m
kakub = 6 * m
soutai = min((abs(kakua - kakub), 360 - abs(kakua - kakub)))
#print(soutai)
print(abs(a ** 2 + b ** 2 - 2*a*b*(math.cos(math.pi/180*soutai)))**(1/2))


Measured memory_bytes: 9500
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
int main(void){
    int a,b;
    std::cin >> a >> b;
    if(a >= 10 || b >= 10){
        std::cout << -1 << std::endl;
    }
    else{
        std::cout << a * b << std::endl;
    }
}


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

const int inf = 1e9;

class Max_Flow{
public:
	struct edge{int to, cap, rev;};
	vector<vector<edge> > G;
	vector<bool> used;
	
	void init(int n){
		G.resize(n);
		used.resize(n);
	}
	void add_edge(int from, int to, int cap){
		G[from].push_back((edge){to, cap, (int)G[to].size()});
		G[to].push_back((edge){from, 0, (int)G[from].size()-1});
	}
	
	int dfs(int v, int t, int f){
		if(v == t)return f;
		used[v] = true;
		for(int i = 0;i < G[v].size();i++){
			edge &e = G[v][i];
			if(!used[e.to] && e.cap > 0){
				int d = dfs(e.to, t, min(f, e.cap));
				if(d > 0){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	
	int max_flow(int s, int t){
		int flow = 0;
		for(;;){
			fill(used.begin(), used.end(), 0);
			int f = dfs(s, t, inf);
			if(f == 0)return flow;
			flow += f;
		}
	}
};

char str[100][100];
typedef pair<int,int> P;
#define fi first
#define se second

int main(){
	int h, w, cnt = 1;
	P s, t;
	scanf("%d%d", &h, &w);
	for(int i = 0;i < h;i++){
		scanf("%s", str[i]);
		for(int j = 0;j < w;j++){
			if(str[i][j] == 'S')s = P(i, j);
			if(str[i][j] == 'T')t = P(i, j);
		}
	}
	
	if(s.fi == t.fi || s.se == t.se){
		printf("-1\n");
		return 0;
	}
	
	Max_Flow maxf;
	maxf.init(h+w+2);
	for(int j = 0;j < w;j++){
		for(int i = 0;i < h;i++){
			if(str[i][j] != 'o')continue;
			maxf.add_edge(i, h+j, 1);
			maxf.add_edge(h+j, i, 1);
		}
	}
	int sy = s.fi, sx = s.se, ty = t.fi, tx = t.se;
	maxf.add_edge(h+w, sy, inf);maxf.add_edge(h+w, sx+h, inf);
	maxf.add_edge(ty, h+w+1, inf);maxf.add_edge(tx+h, h+w+1, inf);
	int ans = maxf.max_flow(h+w, h+w+1);
	printf("%d\n", ans);
	return 0;
}


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

int main() {
  long long num;
  cin >> num;

  string pattern = "zabcdefghijklmnopqrstuvwxy";
  string name = "";
  
  while(num != 0) {
   int current = num % 26;
    name.insert(0, 1, pattern.at(current));  	
    if(current == 0 ) {
      num--;
    }
    num /= 26;     
  }
 
 cout << name << endl;
  
  return 0;
}

Measured memory_bytes: 3628
object Main extends App {

  case class State[A, S](run: S => (S, A)) {
    def flatMap[B](f: A => State[B, S]): State[B, S] = State((s: S) => {
      val (s1, a) = run(s)
      f(a).run(s1)
    })
//    def map[B](f: A => B) = State((s: S) => {
//      val (s1, a) = run(s)
//      (s1, f(a))
//    })
    def map[B](f: A => B): State[B, S] = {
      //      State((s: S) => (f(self.run(s)._1, f(self.run(s)._2)))
      flatMap(a => State.unit(f(a)))
    }
  }
  object State {
    def unit[A, S](a: A) = State((s: S) => (s, a))
  }

  implicit class StreamOps[A, S](s: Stream[State[A, S]]) {
    def sequence: State[Stream[A], S] =
      s.foldRight(State.unit[Stream[A], S](Stream.empty[A]))((h, acc) => h.flatMap(a => acc.map(st => a #:: st)))
  }

  case class Position(x: Double, y: Double, angle: Int) {
    def toInt = (x.toInt, y.toInt)
  }

  def exec(distance: Int, angle: Int): State[Unit, Position] = State((p: Position) => {
    (Position(
      p.x + distance * math.sin(math.Pi / 180 * p.angle),
      p.y + distance * math.cos(math.Pi / 180 * p.angle),
      angle + p.angle), Unit)
  })

  val ans = Stream.continually(readLine)
  .takeWhile(_ != "0,0")
  .map(_.split(",").map(_.toInt))
  .map { case Array(d, a) => exec(d, a) }
    .sequence
    .run(Position(0, 0, 0))
    ._1
    .toInt
  println(ans._1)
  println(ans._2)
}



Measured memory_bytes: 44436
#include <iostream>
using namespace std;
 
int main(){
    int n, m;
    cin >> n >> m;
    int a[100][100] = {};
    int b[100] = {};

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

    for(int j=0;j<m;j++){
        cin >> b[j];
    }

    int tmp;
    for(int j=0;j<n;j++){
        tmp = 0;
        for(int i=0;i<m;i++){
            tmp += a[j][i] * b[i];
        }
        cout << tmp << endl;
    }

}


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


int main() {
  int N;
  cin >> N;
  int min_v = 0;
  bool flag = true;

  rep(i, N) {
    int h;
    cin >> h;
    if (h == min_v) {
      continue;
    } else if (h > min_v) {
      min_v = h - 1;
    } else {
      flag = false;
      break;
    }
  }
  cout << (flag ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import deque
K = int(input())
d = deque([1,2,3,4,5,6,7,8,9])
count = 0
while True:
    tag = d.popleft()
    tmp1 = tag % 10
    tmp2 = tmp1 + tag * 10
    if tmp1 == 9:
        d.append(tmp2 - 1)
        d.append(tmp2)
    elif tmp1 == 0:
        d.append(tmp2)
        d.append(tmp2 + 1)
    else:
        d.append(tmp2 - 1)
        d.append(tmp2)
        d.append(tmp2 + 1)
    count += 1
    if count == K:
        print(tag)
        break



Measured memory_bytes: 74968
N = int(input())
S = [None for _ in range(N)]
for i in range(N):
    s = list(input())
    s.sort()
    S[i] = ''.join(s)
S.sort()


def combination(n, k):
    num = 1
    den = 1
    for i in range(k):
        num *= n-i
        den *= i+1
    return num//den


ct = 1
ans = 0
tmp = S[0]
for i in range(1, N):
    if S[i] == tmp:
        ct += 1
    else:
        if ct >= 2:
            ans += combination(ct, 2)
        ct = 1
        tmp = S[i]
if ct >= 2:
    ans += combination(ct, 2)

print(ans)


Measured memory_bytes: 83968
import java.util.Scanner;

public class Main {
    public static void main(String[] a){
        Scanner scanner=new Scanner(System.in);
        //int t=scanner.nextInt();
        String string=scanner.next();
        int aa=0,b=0;
        for(int j=0;j<string.length();j++){
            if(string.charAt(j)=='A'){
                aa++;
            }
            else{
                b++;
            }
        }
        if(aa==0 || b==0){
            System.out.println("No");
        }
        else{
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 23764
import Control.Monad
import Data.Set
main=do
 n<-readLn
 a<-replicateM n getLine
 print(f n a empty)
  where f 0 _ s = size s
        f n a s = f(n-1)(tail a)(if(member(head a)s)then(delete(head a)s)else(insert(head a)s))

Measured memory_bytes: 79228
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long n=sc.nextInt();
        long f=n/3;
        long sum=0;
        sum+=((f)*(6+(f-1)*3))/2;
        long b=n/5;
        sum+=((b)*(10+(b-1)*5))/2;
        long total=(n*(n+1))/2;
        long fb=n/15;
        sum-=((fb)*(30+(fb-1)*15))/2;
        System.out.println(total-sum);
    }
}


Measured memory_bytes: 35844
#!/usr/bin/env python3

import sys, math
sys.setrecursionlimit(300000)


def solve(H: int, A: int):
    ret = math.ceil(H / A)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    solve(H, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <stack>
#include <cctype>

using namespace std;

int main()
{
  string str;

  while(!cin.eof()){
    getline(cin, str);
    if(str == ".") break;
    bool f = true;
    stack<char> stk;
    for(int i = 0; i < str.size(); i++){
      if(str[i] == '(' || str[i] == '[') stk.push(str[i]);
      else if(str[i] == ']'){
	if(stk.empty()){
	  f = false;
	  break;
	} else if(stk.top() == '[') stk.pop();
	else break;
      } else if(str[i] == ')'){
	if(stk.empty()){
	  f = false;
	  break;
	} else if(stk.top() == '(') stk.pop();
	else break;
      }
    }

    cout << ((stk.empty() && f)? "yes" : "no") << endl;
  }

  return 0;
}

Measured memory_bytes: 904
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int a[100010]; 
int main()
{
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    int ct=0;
    for (;n>0;)
    {
        ct++;
        if (ct==1) n-=k;
        else n-=k-1;
    }
    cout<<ct<<endl;
    return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().strip().split())
hs = list(map(int, input().strip().split()))

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

print(dp[n - 1])


Measured memory_bytes: 84076
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>

#include <algorithm>

using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
const ll INF = 1ll << 60;

ll MOD = 1e9 + 7;

int main()
{

    int n;
    cin >> n;
    //n <100000

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        string t = to_string(i);
        if (t.length() % 2 == 1)
            ans++;
    }

    cout << ans << endl;

    return 0;
}

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

#ifdef LOCAL
#include "../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(ll i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(ll i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;

const ll inf = 1ll<<62;
const ll mod = 1e9+7;

#define int ll

main()
{
  while(1){
    int n,m; cin >> n >> m;
    if(n == 0) break;
    vi sn(n),sm(m);
    int sumn = 0, summ = 0;
    rep(i,n){
      cin >> sn[i];
      sumn += sn[i];
    }
    rep(i,m){
      cin >> sm[i];
      summ += sm[i];
    }
    bool f = false;
    rep(i,n){
      rep(j,m){
	if(sumn - sn[i] + sm[j] == summ - sm[j] + sn[i]){
	  cout << sn[i] << " " << sm[j] << endl;
	  f = true;
	}
	if(f) break;
      }
      if(f) break;
    }
    if(f == false) cout << -1 << endl;
  }
}


Measured memory_bytes: 2972
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End


/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template


signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Cini(N);
    double ans = 0;
    rep(i,N){
        double x;
        string u;
        cin >> x >> u;
        if(u=="JPY") ans += x*1;
        else
            ans += x * 380000.0;
    }
    cout << ans << nn;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void)
{
    int D, N;
    int i,j,t;

    scanf("%d%d",&D,&N);

    i=0;
    t=0;
    while (1) {
        t= t + pow(100,D);
        i++;
        if(i==100) t=t+ pow(100,D);
//        printf("%d %d\n",t,i);
        if(i>=N) break;
    }
    printf("%d",t);
    return 0;
}

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

int main(){
	int H, W;
	while(1){
		cin>>H>>W;
		if(H==0 && W==0) break;

		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(i==0 || i==H-1 || j==0 || j==W-1) cout<<"#";
				else cout<<".";
			}
			cout<<endl;
		}
		cout<<endl;
	}

	return 0;
}

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

using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second
//#define int long long
template<class T, class U>bool chmax(T &a, const U &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T, class U>bool chmin(T &a, const U &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>void println(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void){
    int h,w;
    cin>>h>>w;
    vector<vector<char>> a(h,vector<char>(w));
    queue<pint> q;
    vvint d(h,vint(w,INT_MAX));
    rep(i,h){
        rep(j,w){
            cin>>a[i][j];
            if(a[i][j]=='#'){
                q.push(pint(i,j));
                d[i][j]=0;
            }
        }
    }

    int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    

    while(!q.empty()){
        pint p=q.front();
        q.pop();
        rep(i,4){
            int x=p.first+dir[i][0];
            int y=p.second+dir[i][1];
            if(x<0||y<0||x>=h||y>=w)continue;
            if(a[x][y]=='#')continue;
            a[x][y]='#';
            d[x][y]=d[p.first][p.second]+1;
            q.push(pint(x,y));
        }
    }
    int ans=0;
    rep(i,h)rep(j,w)chmax(ans,d[i][j]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 13328
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

vector<bool> available;
vvi dp;

bool f(ll x, ll y)
{
    if (dp[x][y] >= 0)
    {
        return dp[x][y];
    }
    if (x == y)
    {
        return true;
    }
    if (x < y)
    {
        return false;
    }
    REP1(i, x)
    {
        if (available[i] and f(x % i, y))
        {
            dp[x][y] = 1;
            return true;
        }
    }
    dp[x][y] = 0;
    return false;
}

int main()
{
    IN(ll, N);
    AIN(ll, a, N);
    AIN(ll, b, N);
    ll M = *max_element(ALL(a));
    ll M2 = *max_element(ALL(b));
    available.assign(M + 2, false);
    ll r = M + 1;
    ll ans = 0;
    auto ok = [&]() {
        dp.assign(M + 1, vi(M2 + 1, -1));
        bool ok = true;
        REP(i, N)
        {
            ok &= f(a[i], b[i]);
        }
        return ok;
    };
    while (r > 0 and not ok())
    {
        ll i;
        for (i = 1; i <= r; ++i)
        {
            available[i] = true;
            if (ok())
            {
                ans += 1LL << i;
                break;
            }
        }
        if (i > r)
        {
            OUT(-1);
            return 0;
        }
        r = i - 1;
        REP1(j, r)
        {
            available[j] = false;
        }
    }
    OUT(ans);
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
/*typedef struct p{
	string name;
	int num;
}p;*/ 
int main()
{
	int n,x1=0,x2=0,x3=0,x4=0;
	cin>>n;
	while(n--)
	{
		string s;
		cin>>s;
		if(s=="AC")
		x1++;
		if(s=="WA")
		x2++;
		if(s=="TLE")
		x3++;
		if(s=="RE")
		x4++;
	}
	printf("AC x %d\n",x1);
	printf("WA x %d\n",x2);
	printf("TLE x %d\n",x3);
	printf("RE x %d\n",x4);
}

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

using flow_type = int;

struct dinic {
    struct edge {
        int src, dst;
        flow_type cap, flow;
        edge *next, *rev;
        flow_type residue() const {
            return cap - flow;
        }
        void *operator new (std::size_t) {
            constexpr std::size_t MAX_E = 100010;
            static edge pool[MAX_E];
            static std::size_t p = 0;
            return pool + p++;
        }
    };
    int n, source, sink;
    edge **g;
    int *level, *queue;
    edge **prog;

    dinic(int n_ = 0) :
        n(n_), g(new edge*[n]()), level(new int[n]), queue(new int[n]), prog(new edge*[n]) { }

    flow_type maximum_flow(int source_, int sink_) {
        source = source_;
        sink = sink_;
        flow_type res = 0;
        while (levelize()) {
            std::copy(g, g + n, prog);
            res += augment(source, std::numeric_limits<flow_type>::max());
        }
        return res;
    }

    edge *add_edge1(int u, int v, flow_type c, flow_type f) {
        return g[u] = new edge { u, v, c, f, g[u], nullptr };
    }

    std::pair<edge*, edge*> add_edge(int u, int v, flow_type c) {
        if (u == v || c == 0) return { nullptr, nullptr };
        auto uv = add_edge1(u, v, c, 0);
        auto vu = add_edge1(v, u, c, c);
        uv->rev = vu;
        vu->rev = uv;
        return {uv, vu};
    }

    bool levelize() {
        int fst = 0, lst = 0;
        queue[lst++] = source;
        std::fill(level, level + n, -1);
        level[source] = 0;
        while (fst != lst) {
            int v = queue[fst++];
            if (v == sink) break;
            for (auto e = g[v]; e != nullptr; e = e->next) {
                if (level[e->dst] == -1 && e->residue() != 0) {
                    level[e->dst] = level[v] + 1;
                    queue[lst++] = e->dst;
                }
            }
        }
        return level[sink] != -1;
    }

    flow_type augment(int v, flow_type lim) {
        flow_type res = 0;
        if (v == sink) return lim;
        for (auto &e = prog[v]; e != nullptr; e = e->next) {
            if (lim == 0) break;
            if (level[v] < level[e->dst] && e->residue() != 0) {
                flow_type aug = augment(e->dst, std::min(lim, e->residue()));
                if (aug == 0) continue;
                e->flow += aug;
                e->rev->flow -= aug;
                res += aug;
                lim -= aug;
            }
        }
        return res;
    }
};

using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    dinic g(N);
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
        g.add_edge(a, b, c);
    }
    cout << g.maximum_flow(0, N - 1) << endl;
}

Measured memory_bytes: 3168
#include <iostream>
#include<vector>  
#include<algorithm>  
#include<string>
using namespace std;
int main()
{
	string a, b; 
	cin >> a >> b; 
	string ans = ""; 
	int n = max(a.size(), b.size()); 
	for (int i = 0; i < a.size(); i++)
	{
		cout << a.at(i); 
		if (i<b.size())
		{
			cout << b.at(i);
		} 

	} 
	cout << endl;
}



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

int main() {
  int N;
  cin >> N;
  long long ans = 1, Ln = 1, Lnp = 2;
  if (N == 1) cout << ans;
  else {
    rep(i, N - 1) {
      ans = Ln + Lnp;
      Lnp = Ln;
      Ln = ans;
    }
    cout << ans;
  }
}


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

signed main(){
  int N;
  cin>>N;
  std::vector<int> A(N),B(N);
  for(int i=0;i<N;i++)cin>>A[i]>>B[i];
  std::vector<int> D(N);
  for(int i=0;i<N;i++){
    if(A[i]<=B[i])D[i]=B[i]-A[i];
    else D[i]=B[i]-A[i]%B[i];
    if(B[i]==1)D[i]=0;
    if(A[i]==0)D[i]=0;
  }
  int ans=0;
  for(int i=0;i<N;i++){
    D[N-1-i]-=ans;
    if(D[N-1-i]>=0)ans+=D[N-1-i];
    else if((-D[N-1-i])%B[N-1-i])ans+=B[N-1-i]-(-D[N-1-i])%B[N-1-i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
using namespace std;

int main(){
  map<string,set<int> > Index;
  string s;
    int val;
  while(cin  >> s >> val){
    Index[s].insert(val);
  }

  map<string,set<int> >::iterator it = Index.begin();
  while(it != Index.end()){
    cout << it->first << endl;  
    set<int>::iterator it2 = (it->second).begin();
    while(it2 != (it->second).end()){
      cout << *it2;
      it2++;
      if(it2 != (it->second).end())cout << " ";
    } 
   cout << endl;
   it++;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define pb push_back
#define size(v)  (int) v.size()
#define fast ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
ll power_mod(ll a,ll x){if(x==0) return 1;ll y=power_mod(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
ll inv(ll a){return power_mod(a,mod-2);}    
ll power(ll a, ll x){ if(x==0) return 1; ll y= power(a,x/2); ll ans=(y*y); if(x%2) ans*=a; return ans;}

# define N 1e18

int main() {
  vector<ll> p,pre;
  p.pb(0);
  pre.pb(0);
  ll prev = 0;
  ll c = 26;
  while (1){
  	p.pb(c);
  	pre.pb(c+prev);
  	prev = c + prev;
  	c = c*26;
  	if( c > N) break;
  } 
  ll n;
  cin >> n;
  ll k = size(p);
  ll len = 0;
  for(len = 1; len < k; len++) {
  	//cout<<pre[len] << endl;
  	if(pre[len] >= n){
  		break;
  	}
  }
  p[0] = 1;
  string res;
  for(ll i = len; i >= 1; i--){
  	ll now = p[i-1];
  	ll sum = pre[i-1];
  	//cout << now <<" "<<sum <<" " <<n << endl;
  	   	char ans = 'a';
  	for(char x = 'a' ; x <= 'z'; x++) {
  		sum += now;
  		//cout << sum << " " <<x<<endl;
  		if(sum >= n){
  			ans = x;
  			sum = sum - now;
  			n = n - sum;
  			if( i > 2)
  			n = n + pre[i-2];
  		//	cout << n << endl;
  			break;
  		}
  		
  	}
  
  	res.pb(ans);
  }

  cout << res << endl;

}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int mod = 1e+9 + 7;
const ll INF = 1e+13;

// i文字目まで見たとき、状態がjである場合の数(%mod)
// j=0 : どこにも印をつけていない状態
// j=1 : A一つだけに印をつけている状態
// j=2 : AとB一つずつに印をつけている状態
// j=3 : A,B,Cに印をつけた状態
ll dp[100005][4];

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

    string s; 
    cin >> s;
    int n = (int)s.length();

    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        if(s[i] == '?'){    // i文字目が確定していない場合
            // 前の状態を遷移させておく(i文字目は無視する場合)
            dp[i+1][0] = 3 * dp[i][0];
            dp[i+1][1] = 3 * dp[i][1];
            dp[i+1][2] = 3 * dp[i][2];
            dp[i+1][3] = 3 * dp[i][3];

            // 各文字を入れたときの追加処理
            dp[i+1][1] += dp[i][0];     // i文字目のAに印をつける場合
            dp[i+1][2] += dp[i][1];     // i文字目のBに印をつける場合
            dp[i+1][3] += dp[i][2];     // i文字目のCに印をつける場合
        }
        else{   // i文字目が確定している場合
            // 前の状態を遷移させておく(i文字目を無視する場合)
            dp[i+1][0] = dp[i][0];
            dp[i+1][1] = dp[i][1];
            dp[i+1][2] = dp[i][2];
            dp[i+1][3] = dp[i][3];

            // 各文字に対する追加処理
            if(s[i] == 'A'){
                dp[i+1][1] += dp[i][0];     // i文字目のAに印をつける場合
            }
            else if(s[i] == 'B'){
                dp[i+1][2] += dp[i][1];     // i文字目のBに印をつける場合
            }
            else if(s[i] == 'C'){
                dp[i+1][3] += dp[i][2];     // i文字目のCに印をつける場合
            }
        }
        if(dp[i+1][0] >= mod)   dp[i+1][0] %= mod;
        if(dp[i+1][1] >= mod)   dp[i+1][1] %= mod;
        if(dp[i+1][2] >= mod)   dp[i+1][2] %= mod;
        if(dp[i+1][3] >= mod)   dp[i+1][3] %= mod;
    }

    cout << dp[n][3] << endl;
}

Measured memory_bytes: 3664
n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
p = [list(map(int, input().split())) for _ in range(n)]
ans = -float('inf')

for bit in range(1, 1 << 10):
    tmp = 0
    for i in range(n):
        cnt = 0
        for j in range(10):
            if bit & 1 << j and f[i][j]:
                cnt += 1
        tmp += p[i][cnt]
    ans = max(ans, tmp)

print(ans)
    

Measured memory_bytes: 3064
N, Y = map(int, input().split(' '))

for x in range(N+1):
    for y in range(N-x+1):
        z = N-x-y
        if 10000*x + 5000*y + 1000*z == Y:
            print(x, y, z)
            exit()
print(-1, -1, -1)

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

using namespace std;

int main(void) {
	int n, a, b;
	cin >> n >> a >> b;
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int sum = 0;
		int tmp = i;
		for(int j = 10000; j >= 1; j = j / 10) {
			sum += tmp / j;
			tmp = tmp - (tmp / j) * j;
		}
		if(a <= sum && sum <= b) {
			ans += i;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<string> w(n);
    rep(i,n) cin>>w[i];
    rep(i,n-1) if(w[i].at(w[i].size()-1)!=w[i+1].at(0)){
        cout<<"No"<<endl;
        return 0;
    }
    rep(i,n){
        for(int j=i+1;j<n;j++) if(w[i]==w[j]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
implicit none
  
  integer::N
  integer,dimension(200)::a
  integer::s,t,i,j
  integer,parameter::nmax=1000

  read(*,*)n
  read(*,*)a(1:n)
!  write(*,*)a

  s=0
  t=0
  do i=1,nmax
     t=0
     do j=1,n
        if(mod(a(j),2)==0)t=t+1
     end do

     if(t==n)then
        s=s+1
        a(1:n)=a(1:n)/2
     else
        exit
     end if

  end do

  write(*,*)s

end program

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define F(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define F1(a,n) for(int i=1;i<=n;i++){cin>>a[i];}
#define P(a,n) for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define P1(a,n) for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;
#define NF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}
#define NF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}
#define PNF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define PNF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define AS 200010
#define Size 100001
ll *weight, *price;
ll dp[101][Size];
ll n, capacity;
ll knapsack2(ll max_profit) {
	ll inf = 1e11;
	for (ll N = 0; N <= n; N++) {
		for (ll profit = 0; profit <= max_profit; profit++) {
			if (N == 0 and profit == 0) {
				dp[N][profit] = 0;
			}
			else if (N == 0) {
				dp[N][profit] = inf;
			}
			else if (price[N - 1] <= profit) {
				dp[N][profit] = min(weight[N - 1] + dp[N - 1][profit - price[N - 1]], dp[N - 1][profit]);
			}
			else {
				dp[N][profit] = dp[N - 1][profit];
			}
		}
	}
	ll ans = 0;
	for (ll profit = 0; profit <= max_profit; profit++) {
		if (dp[n][profit] <= capacity)
			ans = profit;
	}
	return ans;
}

int main() {
	cin >> n >> capacity;
	weight = new ll[n];
	price = new ll[n];
	ll max_profit = 0;
	for (int i = 0; i < n; i++) {
		cin >> weight[i] >> price[i];
		max_profit += price[i];
	}

	cout << knapsack2(max_profit) << endl;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> A(N),B(N);
  for(int i=1;i<N;i++){
    cin >> A.at(i);
    B.at(A.at(i)-1)++;
  }
  for(int i=0;i<N;i++){
    cout << B.at(i) << endl;
  }
}

Measured memory_bytes: 4788
# https://atcoder.jp/contests/abc145/tasks/abc145_d


X, Y = map(int, input().split())

if (2*Y- X) % 3 or (2*X- Y) % 3:
    print(0)
    exit()

x = (2*Y - X) // 3
y = (2*X - Y) // 3

if x < 0 or y < 0:
    print(0)
    exit()

n = x + y
r = x


mod = 10**9 + 7
f = 1
for i in range(1, n + 1):
    f = f*i % mod
fac = f
f = pow(f, mod-2, mod)
facinv = [f]
for i in range(n, 0, -1):
    f = f*i % mod
    facinv.append(f)
facinv.append(1)

print(fac * facinv[r] * facinv[n - r] % mod)

Measured memory_bytes: 65628
#include<stdio.h>
int main(void)
{
    int S;
    int h, m, s;

    scanf("%d", &S);
    h = S / 3600;
    m = (S % 3600) / 60;
    s = (S % 3600) % 60;

    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 2088
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

# A
"""
a, b = map(int, input().split())
sum = a-1
if b >= a:
    sum += 1
print(sum)
"""
# B
"""
a,b,c = map(int, input().split())
k = int(input())
sum = a+b+c+max(a,b,c)*(2**k-1)
print(sum)
"""
# C
"""
def check(y,x):
    if y-1 < 0:
        if x-1 < 0:
            move_x = [1,0]
            move_y = [0,1]
        if x+1 >= w:
            move_x = [-1,0]
            move_y = [0,1]
        else:
            move_x = [1,-1,0]
            move_y = [0,0,1]
    if y+1 >= h:
        if x-1 < 0:
            move_x = [1,0]
            move_y = [0,-1]
        if x+1 >= w:
            move_x = [-1,0]
            move_y = [0,-1]
        else:
            move_x = [1,-1,0]
            move_y = [0,0,-1]
    else:
        if x-1 < 0:
            move_x = [1,0,0]
            move_y = [0,1,-1]
        if x+1 >= w:
            move_x = [-1,0,0]
            move_y = [0,1,-1]
        else:
            move_x = [1,-1,0,0]
            move_y = [0,0,1,-1]
    for i in range(len(move_x)):
        if stage[y+move_y[i]][x+move_x[i]] == "#":
            return True
    return False
h,w = map(int, input().split())
stage = [input() for i in range(h)]
for i in range(h):
    for j in range(w):
        if stage[i][j] == "#":
            if not check(i,j):
                print("No")
                quit()
print("Yes")
"""
# D
n = I()
f = [i for i in range(55555)]
z = 2
ans = []
while 1:
    if z%5 == 1:ans.append(z)
    for i in range(2,55555//z+1):
        if z*i < 55555:
            f[z*i] = 0
    for j in range(z+1,55555):
        if f[j]:
            z = j
            break
    if j == 55554:break
print(*ans[:n])


Measured memory_bytes: 42096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int n;
	cin>>n;
	vector<ll> v(n);
	for (int i = 0; i<n; i++){
		cin>>v[i];
	}
	sort(v.begin(), v.end());
	ll prev = -1;
	for (ll i : v){
		if (i==prev){
			cout<<"NO"<<endl;
			return 0;
		}
		prev=i;
	}
	cout<<"YES"<<endl;
	return 0;
}

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

int main() {
	
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n);
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	string ans = "IMPOSSIBLE";
	for(auto t1: a[0]){
		if(t1 == n-1) ans = "POSSIBLE";
		for(auto t2: a[t1]){
			if(t2 == n-1) ans = "POSSIBLE";
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12016
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair <lli,lli> pr;



int frogjump(vector <lli> &stone, int N,vector <lli> &jumps){
    //base condition
    if(N == 1){
        return jumps[N-1] = 0;
    }

    //choice diagram
    else if(N == 2){
        return jumps[N-1] = abs(stone[N-1]-stone[N-2]);
    }

    if(jumps[N-1] != -1){
        return jumps[N-1];
    }

    else{
        return jumps[N-1] = min(abs(stone[N-1]-stone[N-2]) + frogjump(stone,N-1,jumps),abs(stone[N-1]-stone[N-3]) + frogjump(stone,N-2,jumps));
    }
    
}

int main(){
    lli N;
    cin >> N;

    vector <lli> stone(N);
    vector <lli> jumps(N,-1);

    for(int i=0;i<N;i++){
        cin >> stone[i];
    }

    reverse(stone.begin(),stone.end());

    cout << frogjump(stone,N,jumps) << endl;;
}

Measured memory_bytes: 7896
#include<bits/stdc++.h>
using namespace std;
long long n,a,b,x,s,ans;
int main(){
	cin>>n>>a>>b>>s;
	for(int i=2;i<=n;i++)
	{
		cin>>x;
		ans+=min((x-s)*a,b);
		s=x;
	}
	cout<<ans;
	return 0;
}

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

using namespace std;

#define Fo(i, l, r) for (int i = l; i <= r; ++ i)
#define Fod(i, r, l) for (int i = r; i >= l; -- i)

typedef long long LL;

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
}

LL Getint()
{
	using namespace io;
	char ch;
	bool f = false;
	while (Getchar(ch) && (ch < '0' || ch > '9'))
		f |= ch == '-';
	LL s = ch - '0';
	while (Getchar(ch) && ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0';
	return f ? -s : s;
}

const int maxn = 1e5 + 10;

int p[maxn];
LL x[maxn], a[maxn];

void Power(int n, int *p, LL k)
{
	static int res[maxn];
	Fo(i, 1, n) res[i] = i;
	for (; k; k >>= 1)
	{
		if (k & 1) Fo(i, 1, n) res[i] = p[res[i]];
		Fo(i, 1, n) a[i] = p[p[i]];
		Fo(i, 1, n) p[i] = a[i];
	}
	Fo(i, 1, n) p[i] = res[i];
}

int main()
{
	int n = Getint();
	Fo(i, 1, n)
	{
		x[i] = Getint();
		p[i] = i;
	}
	Fod(i, n, 1) x[i] -= x[i - 1];
	int m = Getint();
	LL k = Getint();
	Fo(i, 1, m)
	{
		int pos = Getint();
		swap(p[pos], p[pos + 1]);
	}
	Power(n, p, k);
	Fo(i, 1, n) a[i] = x[p[i]];
	Fo(i, 1, n) a[i] += a[i - 1];
	Fo(i, 1, n) printf("%lld\n", a[i]);
	return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h> 
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;
using Pii = std::pair<int, int>;
 
int main(int argc, char *argv[])
{
    /*
    int N;
    std::cin >> N;

    int ans = 0;
    for (int i = 111; i < 1000; i += 111) {
        if (N <= i) {
            ans = i;
            break;
        }
    }    

    std::cout << ans << std::endl;
    */

    std::string N;
    std::cin >> N;

    std::string ans = "000";
    for (int i = 1; i < 10; i++) {
        std::string tmp = std::to_string(i*100+i*10+i);
        if (N <= tmp) {
            ans = tmp;
            break;
        }
    }

    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 256
w,h,x,y,r=gets.chop.split.map(&:to_i)

x=x-r
y=y-r
w=w-r-r
h=h-r-r

if x>=0 && x<=w && y>=0 && y<=h
    print "Yes\n"
else
    print "No\n"
end


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

int main() {

   string N ;
   cin >> N;
  if (N[0] == N[1] && N[1] == N[2]) cout << "Yes" << endl;
  else if (N[1] == N[2] && N[2] == N[3]) cout << "Yes" << endl;
  else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int N;
  scanf("%d", &N);
  printf("%d\n", N*(N+1)/2);
  return 0;
}

// Reading Material
// https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Measured memory_bytes: 1712
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val s = sc.nextLine()
    val k = sc.nextInt()
    val n = s.length
    val dp0 = Array(n + 1) { Array(k + 2) { 0 } }   //n以下であることが未確定
    val dp1 = Array(n + 1) { Array(k + 2) { 0 } }   //n以下であることが確定
    dp0[0][0] = 1
    for (i in 0 until n) {
        for (j in 0..k) {
            val lim = s[i] - '0'
            if (lim > 0) {
                dp1[i + 1][j] += dp0[i][j] + dp1[i][j]      //0を追加
                dp0[i + 1][j + 1] += dp0[i][j]              //i桁目を追加
            } else {
                dp0[i + 1][j] += dp0[i][j]
                dp1[i + 1][j] += dp1[i][j]
            }
            for (d in 1 until lim) {
                dp1[i + 1][j + 1] += dp0[i][j]      //i桁目より小さい数を追加
            }
            for (d in 1..9) {
                dp1[i + 1][j + 1] += dp1[i][j]      //任意の数字を追加
            }
        }
    }
    println(dp0[n][k] + dp1[n][k])
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 31272
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;

int w, h, n;
int area[15];
vector<pii> size[15];
pii flag[15];
int field[10][10];
int tmp[10][10];
int ans[10][10];
bool found;

void dfs(int y, int x, int d, int a[])
{
	if(d == n){
		if(!found){
			rep(i, h) rep(j, w)
				ans[i][j] = tmp[i][j];
			found = true;
		}
		else{
			ans[0][0] = -1;
		}
		return;
	}
	
	while(tmp[y][x]){
		++x;
		if(x == w){
			x = 0;
			++y;
		}
	}
	reps(k, d, n){
		swap(a[d], a[k]);
		int minh = flag[a[d]].first - y + 1;
		int minw = flag[a[d]].second - x + 1;
		if(0<=minh && 0<=minw){
			int maxh = h-y;
			int maxw = w-x;
			rep(l, size[a[d]].size()){
				int th = size[a[d]][l].first;
				int tw = size[a[d]][l].second;
				if(th<minh || maxh<th || tw<minw || maxw<tw)
					continue;
				rep(i, th) rep(j, tw){
					if(tmp[y+i][x+j] != 0 || (field[y+i][x+j] != 0 && field[y+i][x+j] != a[d]+1))
						goto end;
				}
				rep(i, th) rep(j, tw){
					tmp[y+i][x+j] = a[d] + 1;
				}
				dfs(y, x, d+1, a);
				rep(i, th) rep(j, tw){
					tmp[y+i][x+j] = 0;
				}
end:;
			}
		}
		swap(a[d], a[k]);
	}
}

int main()
{
	while(scanf("%d%d%d", &w, &h, &n), n){
		ans[0][0] = -1;
		rep(i, h) 
			fill(tmp[i], tmp[i]+w, 0);
		found = false;

		rep(i, n){
			int b, k;
			scanf("%d%d", &b, &k);
			--b;
			area[b] = k;
			size[b].clear();
			reps(y, 1, h+1){
				if(k%y == 0){
					int x = k / y;
					if(x <= w)
						size[b].push_back(pii(y, x));
				}
			}
		}
		rep(i, h) rep(j, w){
			scanf("%d", &field[i][j]);
			if(field[i][j] != 0)
				flag[field[i][j]-1] = pii(i, j);
		}
		int a[15];
		rep(i, n)
			a[i] = i;
		dfs(0, 0, 0, a);

		if(ans[0][0] == -1)
			puts("NA");
		else{
			rep(i, h) rep(j, w)
				printf("%d%c", ans[i][j], j==w-1?'\n':' ');
		}
	}
	return 0;
}

Measured memory_bytes: 1048
n, m = map(int, input().split())
x = [-1] * n
for _ in range(m):
    s, c = map(int, input().split())
    s -= 1
    if x[s] != -1 and x[s] != c:
        print(-1)
        quit()
    x[s] = c
if n > 1 and x[0] == 0:
    print(-1)
    quit()

if x[0] == -1:
    x[0] = 1 if n > 1 else 0
for i in range(1, n):
    if x[i] == -1:
        x[i] = 0
print(''.join(map(str, x)))

Measured memory_bytes: 62000
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    size_t N;
    scanf("%zu", &N);

    for (size_t i=0; i<N; ++i) {
        vector<int> a(3);
        for (size_t i=0; i<3; ++i)
            scanf("%d", &a[i]);

        sort(a.begin(), a.end());
        printf("%s\n", (a[0]*a[0]+a[1]*a[1]==a[2]*a[2])? "YES":"NO");
    }

    return 0;
}

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

int main(void){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(fabs(a-b) <= d && fabs(b-c) <= d)cout <<"Yes"<< endl;
    else if(fabs(a-c) <= d)cout << "Yes" << endl;
    else cout <<"No"<< endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 205
#define MAX_P 1005
struct edge{ int to,cost,v; };
 
int N,M,P;
 
double dp[MAX_P][MAX_N];
vector<edge> G[MAX_N];
 
int main(){
 
  cin>>N>>M>>P;
  for(int i=0;i<M;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--,b--;
    G[a].push_back((edge){b,c,d});
    G[b].push_back((edge){a,c,d});
  }
  for(int i=0;i<MAX_P;i++)
    for(int j=0;j<MAX_N;j++)
      dp[i][j]=-1e9;
 
  dp[0][0]=0;
  for(int i=0;i<P;i++){
    for(int j=0;j<N;j++){
      if(dp[i][j]==-1e9)continue;
      for(int k=0;k<(int)G[j].size();k++){
        edge e=G[j][k];
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(double)e.v/(double)e.cost);
        if(i+e.cost<=P)
          dp[i+e.cost][e.to]=max(dp[i+e.cost][e.to],dp[i][j]+e.v);
      }
    }
  }
 
  printf("%.10f\n",dp[P][0]);
  return 0;
}

Measured memory_bytes: 3512
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(llint i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<int>>
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！


//2のn乗を求めるよ！！！
int ni(int n) {
	if (n == 0)return 1;
	int x = ni(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;
}

//フィボナッチ数列のx番目を求めるよ！
llint f(int x, vector<llint> &s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	return  s[x] = f(x - 1, s) + f(x - 2, s);
	
}

//aとｂの最大公約数を求めるよ！
llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}



// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//m進数のn桁を全列挙やで
void dfs(int m, int n) {
	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			cout << now << endl;
		}
		else {
			for (int i = m - 1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}
void press(vector<int>& v) { v.erase(unique((v).begin(), (v).end()), v.end()); }

llint min(llint a, llint b) {
	if (a < b)return a;
	return b;
}
llint max(llint a, llint b) {
	if (a < b)swap(a, b);
	return a;
}
llint p(int n) {
	if(n==1)return 1;
	return n * p(n - 1);
}

int main() {
	int n;
	cin >> n;
	vector<pair<llint, llint>> s(n);
	rep(i, 0, n) {
		int a, b;
		cin >> a >> b;
		s[i] = make_pair(a + b, a - b);
	}
	int ans = 0;
	llint x = -1000000002;
	sort(s);
	rep(i, 0, n) {
		if (s[i].second >= x) {
			ans++;
			x = s[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792