akhauriyash/Code-Regression huggingface dataset:
#input
N, M = map(int, input().split())
s = [0] * M
c = [0] * M
for i in range(M):
    s[i], c[i] = map(int, input().split())

#output
from collections import Counter
dp = [-1] * N
for i in range(M):
    if dp[s[i]-1] == -1:
        dp[s[i]-1] = c[i]
    elif c[i] != dp[s[i]-1]:
        print(-1)
        exit()

if N == 1:
    if dp[0] == -1:
        print(0)
    else:
        print(dp[0])
else:
    if dp[0] == 0:
        print(-1)
    else:
        for i in range(N):
            if dp[i] == -1:
                if i == 0:
                    print(1, end = "")
                else:
                    print(0, end = "")
            else:
                print(dp[i], end = "")

Measured memory_bytes: 3316
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

	static int h;
	static int w;
	static int n;

	static String matrix[][];

	static int sx, sy;
	static int gx, gy;

	static int answer = 0;

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

	static final int WHITE = 0;
	static final int GRAY = 1;
	static final int BLACK = 2;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		h = Integer.parseInt(str[0]);
		w = Integer.parseInt(str[1]);
		n = Integer.parseInt(str[2]);

		matrix = new String[h][w];

		for (int i = 0; i < h; i++) {
			str = br.readLine().split("");
			for (int j = 0; j < w; j++) {
				if (str[j].equals("S")) {
					sx = j;
					sy = i;
				}
				matrix[i][j] = str[j];
			}
		}
		bfs(sx, sy, 1);
		System.out.println(answer);
	}

	static void bfs(int x, int y, int nn) {
		int dist[][] = new int[h][w];
		int color[][] = new int[h][w];
		int num = nn;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				dist[i][j] = Integer.MAX_VALUE;
				color[i][j] = WHITE;
			}
		}
		color[y][x] = GRAY;
		dist[y][x] = 0;

		int a, b;

		Queue<Integer> queueX = new ArrayDeque<>();
		Queue<Integer> queueY = new ArrayDeque<>();
		queueX.add(x);
		queueY.add(y);
		while (!queueX.isEmpty() && !queueY.isEmpty()) {
			a = queueX.poll();
			b = queueY.poll();

			for (int i = 0; i < 4; i++) {
				int nx = a + dx[i];
				int ny = b + dy[i];
				if (nx >= 0 && nx < w && ny >= 0 && ny < h) {
					if (matrix[ny][nx].equals("X")) {
						continue;
					}
					if (color[ny][nx] == WHITE) {
						dist[ny][nx] = dist[b][a] + 1;
						color[ny][nx] = GRAY;
						queueX.add(nx);
						queueY.add(ny);
					}
					if (matrix[ny][nx].equals(String.valueOf(num))) {
						if (num <= n) {
							answer += dist[ny][nx];
							bfs(nx, ny, num + 1);
							queueX.clear();
							queueY.clear();
							break;
						}
					}
				}
			}
			color[b][a] = BLACK;
		}
	}
}

class Edge implements Comparable<Edge> {
	int to;
	int cost;

	public Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}



Measured memory_bytes: 249988
import java.io.*;
import java.util.StringTokenizer;

public class Main {
  private static PrintWriter out;

  public static void main(String[] args) {
    Main main = new Main();
    Runtime.getRuntime().addShutdownHook(new Thread(() -> out.close()));
    try {
      main.run(args);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  private void run(String[] arguments) throws Exception {
    MyScanner sc = new MyScanner();
    out = new PrintWriter(new BufferedOutputStream(System.out));

    int x = sc.nextInt();
    int y = sc.nextInt();
    String ans = "No";

    for (int i = 0; i < 51; i++) {
      for (int j = 0; j < 26; j++) {
        int turuTotal = i *2;
        int kameTotal = j * 4;
        int total = turuTotal + kameTotal;
        if (total==y && (i+j)==x){
          ans = "Yes";
          break;
        }
      }
    }
    out.println(ans);
    out.close();
  }

  /*          
   * Form: http://codeforces.com/blog/entry/7018
   */
  private class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    MyScanner() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}


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

using namespace std;
int main(void){
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> copy = a;
    
    sort(copy.rbegin(), copy.rend());
    
    int firstMax = copy[0];
    int secondMax = copy[1];
    
    for (int i = 0; i < n; i++){
        if (a[i] != firstMax){
            cout << firstMax << endl;
        }
        else{
            cout << secondMax << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define ll long long
#define N 200005
using namespace std;
int n,x,y,mx;ll sum;
struct pi{
	ll a,b;
	pi(){};
	pi(ll _a,ll _b){
		a=_a;b=_b;
	}
}tmp[N];
int deep[N];
vector<pi>h[N];
struct pl{int l,r,lv,rv;}s[N];
void add(int a,int b,int c){
	if(s[a].l==0) s[a].l=b,s[a].lv=c;
	else s[a].r=b,s[a].rv=c;
}
bool cmp(const pi &A,const pi &B){return A.a<B.a||A.a==B.a&&A.b<B.b;} 
void dfs(int a,int fa,ll v,int w){
	if(s[a].l==0){h[a].push_back(pi(w,w));return;}
	else dfs(s[a].l,a,v,s[a].lv),dfs(s[a].r,a,v,s[a].rv);
	if(h[s[a].l].size()>h[s[a].r].size()) swap(s[a].l,s[a].r),swap(s[a].lv,s[a].rv);
	if(h[s[a].l].size()==0) return;
	int l=0,top=0;
	for(int i=0;i<h[s[a].l].size();i++){
		while(l<h[s[a].r].size()&&h[s[a].r][l].a+h[s[a].l][i].b<=v) l++;
		if(l!=0) top++,tmp[top]=pi(h[s[a].l][i].a+w,h[s[a].r][l-1].b+w);
	}
	int tip=top;
	for(int i=1;i<=tip;i++)
		if(tmp[i].a!=tmp[i].b) top++,tmp[top]=pi(tmp[i].b,tmp[i].a);
	sort(tmp+1,tmp+1+top,cmp);
	if(top!=0) h[a].push_back(tmp[1]);
	for(int i=2;i<=top;i++)
		if(tmp[i].b<h[a][h[a].size()-1].b) h[a].push_back(tmp[i]);
}
int main()
{
	//freopen("cc.in","r",stdin);
	//freopen("cc.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++) scanf("%d%d",&x,&y),add(x,i,y),deep[i]=deep[x]+1,mx=max(mx,deep[i]),sum=max(sum,(ll)y);
	ll l=0,r=min((ll)sum*2*mx,(ll)1e10);
	while(l+1<r){
		ll mid=(l+r)/2;
		for(int i=1;i<=n;i++) h[i].clear();
		dfs(1,0,mid,0);
		if(h[1].size()!=0) r=mid;else l=mid;
	}
	for(int i=1;i<=n;i++) h[i].clear();
	dfs(1,0,l,0);if(h[1].size()!=0) r--;else l++;
	printf("%lld\n",l);
	return 0;
}

Measured memory_bytes: 32680
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

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

	int a[6];
	for(int i = 1; i <= 5; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= 5; i++) {
		if(!a[i]) {
			cout << i;
		}
	}

	return 0;
}

Measured memory_bytes: 3612
import java.util.*;
 
class Main {
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int lMax = 0;
    int rMin = Integer.MAX_VALUE;
    for (int i = 0; i < m; i++) {
      int l = sc.nextInt();
      int r = sc.nextInt() + 1;
      lMax = Math.max(lMax, l);
      rMin = Math.min(rMin, r);
    }
    if (rMin - lMax < 0) {
      System.out.println(0);
      System.exit(0);
    }
    System.out.println(rMin - lMax);
  }
}

Measured memory_bytes: 61516
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
	int h, w;
	cin >> h >> w;
	int sy, sx, gy, gx;
	cin >> sy >> sx >> gy >> gx;
	sx--, sy--, gx--, gy--;
	VE<string> s(h);
	rep(i, h) {
		cin >> s[i];
	}
	VV dist(h, V(w, upper));
	priority_queue<pair<int, pair<int, int>>, VE<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push(make_pair(0, make_pair(sx, sy)));
	dist[sy][sx] = 0;
	while (!pq.empty()) {
		int d = pq.top().first;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();
		if (dist[y][x] < d) continue;
		rep(dir, 4) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
			if (s[ny][nx] == '#') continue;
			if (chmin(dist[ny][nx], d)) pq.push(make_pair(dist[ny][nx], make_pair(nx, ny)));
		}
		REP(i, -2, 3) REP(j, -2, 3) {
			int nx = x + i;
			int ny = y + j;
			if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
			if (s[ny][nx] == '#') continue;
			if (chmin(dist[ny][nx], d + 1)) pq.push(make_pair(dist[ny][nx], make_pair(nx, ny)));
		}
	}
	if (dist[gy][gx] == upper) cout << -1 << endl;
	else cout << dist[gy][gx] << endl;
	return 0;
}

Measured memory_bytes: 9456
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { //USE LONGS TO AVOID OVERFLOW THEN CAST
 
	public static void main(String[] args) { 
		FastScanner input = new FastScanner();
		PrintWriter w = new PrintWriter(System.out);
		int N = input.nextInt();
		TreeSet<Long> set = new TreeSet<Long>();
		long ans = 0;
		while (N-->0) {
			long x = input.nextLong();
			if (set.add(x)) ans++;
			else {
				set.remove(new Long(x));
				ans--;
			}
		} 
		w.println(ans);
		w.flush();
	}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 50716
#include<stdio.h>
void selectionSort(int*, int);
int main(){
    int S[100];
    int s, t, i, j;
    scanf("%d", &s);
    
    for(i=0 ; i<s ; i++){
        scanf("%d", &S[i]);
    }
    
    selectionSort(S, s);
    
    return 0;
}

void selectionSort(int* A,int b){
    int min;
    int cont = 0;
    int change;
    int i, j, flag;
    
    for(i=0 ; i<=b-1 ; i++){
        min = i;
        flag = 0;
        
        for(j=i ; j<=b-1 ; j++){
            if(A[j]<A[min]){
                min = j;
                flag = 1;
            }
        }
        
        if(flag==1){
            cont++;
        }
        
        change = A[i];
        A[i] = A[min];
        A[min] = change;
    }
    
    for(i=0 ; i<b ; i++){
        if(i==b-1){
            printf("%d\n", A[i]);
        }
        else{
            printf("%d ", A[i]);
        }
    }
    
    printf("%d\n", cont);
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int n;
  string s;
  cin >> n >> s;
  
  int east[n];
  rep(i,n){
    if(s[i] == 'E') east[i] = 1;
    else east[i] = 0;
  }
  
  for(int i=n-2;i>=0;i--) east[i] += east[i+1];
  //rep(i,n) cout << east[i] << " "; cout << endl;
  
  int cnt = 1001001, west = 0;
  rep(i,n){
    int temp = west;
    if(i != n-1)temp += east[i+1];
    if(s[i] == 'W') west++;
    cnt = min(cnt,temp);
  }
  
  cout << cnt << endl;
  
  return 0;
}
        

Measured memory_bytes: 1796
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
ll a,b,n;
ll h[100000];
ll h2[100000];


bool C(ll m) {
	REP(i,n) {
		h2[i] = h[i] - b * m;
	}

	ll c = 0;
	REP(i,n) {
		if(h2[i] >= 1)
			c += ((h2[i] + a - 1) / a);
	}
	return c <= m;
}

ll binsearch_i_min(){
	ll lb = 0,ub = max((10000000000 * n) / (a + n * b),10000000ll);//(lb,ub]が探索範囲

	while(ub - lb > 1){
		ll mid = (lb + ub) / 2;
		if(C(mid))ub = mid;
		else lb = mid;
	}

	return ub;
}

int main(){
	cin >> n >> a >> b;
	a -= b;
	REP(i,n) {
		cin >> h[i];
	}

	cout << binsearch_i_min() << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int linearSearch (int A[], int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) i++;
    return i != n;
}

int main () {
    int i;
    int n, q, key;
    int sum = 0;
    int A[10000 + 1];

    scanf("%d", &n);
    for ( i = 0; i < n; i++ ) scanf("%d", &A[i]);

    scanf("%d", &q);
    for ( i = 0; i < q; i++ ) {
        scanf("%d", &key);
        if ( linearSearch(A, n, key) ) sum++;
    } 
    
    printf("%d\n", sum);
    return 0;
}



Measured memory_bytes: 2108
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <istream>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
#define MOD 1000000007
#define ra 380000
using namespace std;
typedef long long ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	rep0(i, 2) {
		if (s[i] == '9')
			s[i] = '1';
		else if (s[i] == '1')
			s[i] = '9';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;

ll N;

int main(){
	cin >> N;
	ll res = 0;
	for(ll i = 1; i * i <= N; i++){
		ll prod = N - i;
		if(prod % i != 0) continue;
		if(prod / i > i) res += prod / i;
	}
	cout << res << endl;
	return 0;
}


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

typedef long long int ll;
ll MOD = 998244353;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

const long long MAX = 510000;  // 最大を決めておく
// fac…階乗、inv…逆数、finv…逆数の累積積
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理、先にやっておく
void nCr_init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// nCrを計算する (前処理は忘れないように)
long long nCr(int n, int r) {
  if (n < r) return 0;
  if (n < 0 || r < 0) return 0;
  return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

// ====================================================================

int main() {
  nCr_init();
  ll n, m, k;
  cin >> n >> m >> k;

  if (m == 1) {  // 1色で塗るしかない！
    cout << (n - 1 <= k) << endl;
    return 0;
  }

  vector<ll> rui(300000);
  rui[0] = 1ll;
  for (int i = 1; i < 300000; i++) {  // (m-1) の累乗テーブル
    rui[i] = rui[i - 1] * (m - 1) % MOD;
  }

  ll ans = 0;
  for (int i = 0; i <= k; i++) {  // 境目を消す回数
    ans += nCr(n - 1, i) * m % MOD * rui[n - i - 1] % MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 17516
#include<bits/stdc++.h>
using namespace std;
int n,k,a[200005];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i>k)
		{
			if(a[i]>a[i-k])cout<<"Yes\n";
			else cout<<"No\n";
		}
	}
	return 0;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  // ifstream in("NOMURA2020/1.txt");
  // cin.rdbuf(in.rdbuf());

  ll n;
  cin >> n;
  vector<ll> a(n+1);
  rep(i, n+1) cin >> a[i];

  vector<ll> node(n+1);

  node[0] = 1;
  if (a[0] > 1) {
    cout << -1 << endl;
    return 0;
  }


  reps1(i, n) {
    node[i] = node[i-1] * 2 - a[i];
    chmin(node[i], INF);
    if (node[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
  }

  bool flag = false;
  reps1(i, n) {
    if (node[i] != 0 && flag) {
      cout << -1 << endl;
      return 0;
    }
    if (node[i] == 0) flag = true;
  }


  flag = false;
  if (a[0] != 0) flag = true;
  reps1(i, n+1) {
    if (a[i] != 0 && flag) {
      cout << -1 << endl;
      return 0;
    }
  }
  // rep(i, n) {
  //   cout << i << " " << node[i] << endl;
  // }
  // cout << "a" << endl;
  // cout << node[n-1] << " " << a[n] << endl;
  node[n] = 0;
  if (a[n] > 2 * node[n-1]) {
    cout << -1 << endl;
    return 0;
  }
  //cout << "a" << endl;
  /*
  rep(i, n+1) {
  cout << node[i] << endl;
}
*/

for(ll i = n-1; i >= 0; i--) {
  if (node[i] > node[i+1] + a[i+1]) {
    node[i] = node[i+1] + a[i+1];
  }
  //cout << i << " " << node[i] << endl;
  /*
  if (node[i+1] > node[i] * 2) {
  cout << -1 << endl;
  return 0;
}
*/


}
// ll ans = 0;
// rep(i, n+1) cout << node[i] << " ";
// cout << endl;
/*
rep(i, n) {
  ans += node[i];
  cout << i << " " << ans << endl;
}
*/

cout << accumulate(node.begin(), node.end(), 0ll) + accumulate(a.begin(), a.end(), 0ll) << endl;

return 0;
}


Measured memory_bytes: 4844
N = int(input())
A = [[] for _ in range(N)]

for i in range(N):
    line = list(map(int, input().split()))
    A[i] = line

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:  # 最短でない
                print('-1')
                exit()

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][j] == A[i][k] + A[k][j]:  # 代替可能
                break
        else:
            ans += A[i][j]

print(ans)


Measured memory_bytes: 44124
use std::str::FromStr;

fn get_one<T : FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().parse().ok().unwrap();
}

fn get_vec<T : FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
}

fn main() {
    let n : i64 = get_one();
    let mut ans = 1;
    for i in 1..(n+1) {
        ans *= i;
        ans %= 10i64.pow(9) + 7;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	vector<queue<int>> v(n);
	int t;
	For(i,0,n-1) For(j,1,n-1){
		cin>>t;
		v[i].push(t-1);
	}
	int cnt=n*(n-1)/2;
	int ans=0;
	queue<int> can;
	For(i,0,n-1) can.push(i);
	while(cnt>0){
		ans++;
		bool f=false;
		set<int> st;
		while(!can.empty()){
			int i=can.front(); can.pop();
			if(sz(v[i])>0 && v[v[i].front()].front()==i && !st.count(i)){
				f=true;
				st.insert(i);
				st.insert(v[i].front());
				cnt--;
			}
		}
		if(!f){
			cout<<"-1\n";
			return 0;
		}
		for(auto &i:st){
			v[i].pop();
			can.push(i);
		}
	}
	cout<<ans<<"\n";
	return 0;
}





























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

using namespace std;

#define rep1(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, n, m) for (long long i = (long long)(n); i <= (long long)(m); i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
const long long mod = 1e9 + 7;

int main() {
    int n, x;
    cin >> n >> x;
    long long arr[n];
    rep1(i, n) cin >> arr[i];
    long long count = 0;
    rep1(i, n - 1) {
        long long sum = arr[i] + arr[i + 1];
        if (sum <= x) continue;
        if (sum - x <= arr[i + 1]) {
            count += sum - x;
            arr[i + 1] -= sum - x;
        } else {
            count += sum - x - arr[i + 1];
            count += arr[i + 1];
            arr[i] -= sum - x - arr[i + 1];
            arr[i + 1] -= arr[i + 1];
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

int n, k;
vector<llong> t;

int check(llong p)
{
	int id = 0;
	for (int i = 0; i < k; i++)
	{
		llong s = 0;
		for (; s + t.at(id) <= p;)
		{
			s += t.at(id);
			id++;
			if (id == n)
			{
				return n;
			}
		}
	}

	return id;
}

int solve()
{
	llong l = 0;
	llong r = 100000 * 10000;

	for (; r - l > 1;)
	{
		int mid = (l + r) / 2;
		if (check(mid) >= n)
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}

	return r;
}

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

	for (int i = 0; i < n; i++)
	{
		llong x;
		cin >> x;
		t.push_back(x);
	}

	cout << solve() << endl;
}


Measured memory_bytes: 3944
'use strict'

function main(input) {
  input = input
    .split('')
    .slice(0, -1)
    .sort()

  const ans =
    input[0] === input[1] && input[2] === input[3] && input[1] !== input[2]
      ? 'Yes'
      : 'No'
  //Yes // No
  console.log(ans)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))


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

int n,ans,a[N];

int main() {

  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
  }
  sort(a+1,a+1+n);
  int son=1;
  for(int i=1;i<=n;i++) {
    while(son+1<=n && a[son+1]-a[i]<=2) son++;
    ans=max(ans,son-i+1);
  }
  printf("%d",ans);

}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
 
long long gcd(long long a, long long b)
{
	long long temp;
	while (a % b != 0)
	{
		temp = b;
		b = a % b;
		a = temp;
	}
	return b;
}
 
int main()
{
	long long A, B, C, D;
	cin >> A >> B >> C >> D;
 
	long long  count = 0;
	count += (B / C) - ((A-1)  / C) ;
	count += (B / D) - ((A-1)  / D) ;
	long long g = max(C,D)  / gcd(max(C,D), min(C,D)) * min(C,D);
	count -= (B / g) - ((A-1)  / g) ;
 
	cout << (B - A + 1 - count) << endl;
	return 0;
}

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

using namespace std;

typedef long long int ll;
#define pb push_back
#define ALL(a) (a).begin() , a.end()

int mod = 1e9 + 7;
int add(int a, int b){
	if(a + b >= mod)return a+ b - mod;
	return a + b;
}
int mul(int a, int b){
	return 1LL * a * b  % mod;
}
int const N = 200 * 1010;

/********************i**********************************/
void solve(){
	int a, b;
	cin >> a >> b;
	if(a > b)swap(a, b);
	for(int x =0; x<b; x++)cout << a;
}

/******************************************************/
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int t;
	t = 1;
	// cin >> t;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CSqrtInequality solver = new CSqrtInequality();
        solver.solve(1, in, out);
        out.close();
    }

    static class CSqrtInequality {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long a = in.nextLong();
            long b = in.nextLong();
            long c = in.nextLong();
            if (c - a - b < 0 || (c - a - b) * (c - a - b) <= 4 * a * b) {
                out.println("No");
            } else {
                out.println("Yes");
            }
        }

    }
}



Measured memory_bytes: 22608
n,k=map(int,input().split())
P,X,Y=[],[],[]
for _ in range(n):
    x,y=map(int,input().split())
    P.append((x,y))
    X.append(x)
    Y.append(y)
ans=10**19
X.sort()
Y.sort()
for d in range(n-1):
    for u in range(d,n):
        for l in range(n-1):
            for r in range(l,n):
                D,U,L,R=X[d],X[u],Y[l],Y[r]
                cnt=0
                for i in P:
                    if D<=i[0]<=U and L<=i[1]<=R:
                        cnt+=1
                if cnt>=k:
                    ans=min(ans,(U-D)*(R-L))
print(ans)


Measured memory_bytes: 48092
n = int(input())
  
T_s = 0
H_s = 0
  
for i in range(n):
    animals = input().split()
    T_a = animals[0]
    H_a = animals[1]
    if T_a < H_a:
        H_s += 3
    elif T_a > H_a:
        T_s += 3
    else:
        T_s += 1
        H_s += 1
  
print(T_s, H_s)

Measured memory_bytes: 7648
//In the name of Allah
//Ya Ali!
#include <bits/stdc++.h>

using namespace std;
typedef long long ll ;

const ll maxn = 2001 ;
const ll INF = 1e18 ;

#define f first
#define s second

ll n , m  , a , b ;
ll ans[maxn][maxn];

int main()
{
std::ios::sync_with_stdio(0) ;
cin.tie(0) ;
cout.tie(0) ;
cin >> n >> m >> a >> b ;
for(int i = 0 ; i < b ; i ++){
    for(int j = 0 ; j < a ; j ++){
        ans[i][j] = 1 ;
    }
}
for(int i = b ; i < n ; i ++){
    for(int j = a ; j < m ; j ++){
        ans[i][j] = 1 ;
    }
}

for(int i  = 0 ; i < n  ; i ++){
    for(int j = 0 ; j < m ; j ++)cout << ans[i][j] ;
    cout << endl ;
}
 return 0;
}
/*
                  _     _   __
            /_\  (_    (_)  __)
           /   \  _) . (_) (__
*/


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

class Dice{
    public:
    int val[6];

    Dice(){}

    bool match(Dice other){
        rep(i,6) {
            if(other.val[i] != val[i]){
                return false;
            }
        }
        return true; 
    }

    void move(char c){
        if(c == 'N') {
            int tmp = val[0];
            val[0] = val[1];
            val[1] = val[5];
            val[5] = val[4];
            val[4] = tmp;
        }
        if(c == 'W') {
            int tmp = val[1];
            val[1] = val[3];
            val[3] = val[4];
            val[4] = val[2];
            val[2] = tmp;
        }
        if(c == 'E') {
            int tmp = val[1];
            val[1] = val[2];
            val[2] = val[4];
            val[4] = val[3];
            val[3] = tmp;
        }
        if(c == 'S') {   
            int tmp = val[0];
            val[0] = val[4];
            val[4] = val[5];
            val[5] = val[1];
            val[1] = tmp;
        }
    }
};

Dice d[100];
int main() {
    string str = "WWWWNWWWWWSWWWWSSWWWWNWWWWWSWWWW";
    int n;
    cin >> n;
    rep(i,n) rep(j,6) cin >> d[i].val[j];

    rep(i,n-1){
        Dice di = d[i];
        for(int j=i+1;j<n;++j){
            Dice dj = d[j];
            for(auto &s:str){
                dj.move(s);
                if(di.match(dj)){
                cout << "No" << endl;
                return 0;
            }
            }
 
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3200
#include <stdio.h>

#define MAX_HEAP_SIZE   500001

int HeapSize;
int Heap[MAX_HEAP_SIZE];

void initVer(void){
    int i;
    
    for( i = 0; i < MAX_HEAP_SIZE; i++ ){
        Heap[i] = 0;
    }
}

void inputVal(void){
    int i;
    
    scanf("%d",&HeapSize);
    for( i = 1; i <= HeapSize; i++ ){
        scanf("%d",&Heap[i]);
    }
}

void maxHeapify(int Node){
    int LeftNode;
    int RightNode;
    int LargetNode;
    int TmpHeapVal;
    
    LeftNode = 2 * Node;
    RightNode = LeftNode + 1;
    
    if( ( LeftNode <= HeapSize ) && ( Heap[LeftNode] > Heap[Node] ) ){
        LargetNode = LeftNode;
    }else{
        LargetNode = Node;
    }
    
    if( ( RightNode <= HeapSize ) && ( Heap[RightNode] > Heap[LargetNode] ) ){
        LargetNode = RightNode;
    }
    
    if( LargetNode != Node ){
        TmpHeapVal = Heap[Node];
        Heap[Node] = Heap[LargetNode];
        Heap[LargetNode] = TmpHeapVal;
        maxHeapify(LargetNode);
    }
}

void buildMaxHeap(void){
    int i;
    
    for( i = HeapSize / 2; i > 0; i-- ){
        maxHeapify(i);
    }
}

void outputVal(void){
    int i;
    
    for( i = 1; i <= HeapSize; i++ ){
        printf(" %d",Heap[i]);
    }
    printf("\n");
}

int main(void){
    initVer();
    inputVal();
    buildMaxHeap();
    outputVal();
}




Measured memory_bytes: 3732
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
////////////////////////////////////////////
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	int ans=0;
	REP(i,101){
		if(i>=a&&i<b&&i>=c&&i<d) ans++;
	}
	cout << ans << endl;


//////////////////////////////////////////////
}


Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[18]:


N = int(input())
A = list(map(int, input().split()))


# In[19]:


s = sum(A)
x = s - sum(A[1::2])*2
ans = [x]
for i in range(N-1):
    x = 2*A[i]-x
    ans += [x]
print(*ans)


# In[ ]:






Measured memory_bytes: 20524
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

/* typedef */
typedef long long ll;

/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */
int main(){

    int n, m, x;
    set<int> odd, even;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        odd.insert(x);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x;
        even.insert(x);
    }

    // ==========================================
    set<int> s;
    set_symmetric_difference(odd.begin(), odd.end(),
          even.begin(), even.end(),
          inserter(s, s.begin()));

    for (auto const &e: s) {
        cout << e << '\n';
    }
}



Measured memory_bytes: 40612
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
int main() {
	int p, q;
	while (cin >> p >> q, p) {
		int cnt[3] = {};
		string s; int a[10], b[10], c[10]; int sum[10];
		rep(i, p) {
			cin >> s;
			int len = s.length();
			int chk = 0; bool f = true;
			rep(j, len) {
				if (f) {
					if (s[j] != '.') {
						f = false;
					}
					else {
						chk++;
					}
				}
				if (s[j] == '(') {
					cnt[0]++;
				}
				else if (s[j] == '{') {
					cnt[1]++;
				}
				else if (s[j] == '[') {
					cnt[2]++;
				}
				else if (s[j] == ')') {
					cnt[0]--;
				}
				else if (s[j] == '}') {
					cnt[1]--;
				}
				else if(s[j] == ']') {
					cnt[2]--;
				}
			}
			a[i] = cnt[0]; b[i] = cnt[1]; c[i] = cnt[2];
			if (i > 0)sum[i - 1] = chk;
		}
		vector<vector<int>> v;
		Rep(i, 1, 21) {
			Rep(j, 1, 21) {
				Rep(k, 1, 21) {
					bool f = true;
					rep(l, p - 1) {
						if (i*a[l] + j * b[l] + k * c[l] != sum[l]) {
							f = false;
						}
					}
					if (f) {
						v.push_back({ i,j,k });
					}
				}
			}
		}
		int le = v.size();
		cnt[0] = cnt[1] = cnt[2] = 0;
		vector<int> out; out.push_back(0);
		rep(i, q) {
			cin >> s;
			int len = s.length();
			bool f = true;
			rep(j, len) {
				if (s[j] == '(') {
					cnt[0]++;
				}
				else if (s[j] == '{') {
					cnt[1]++;
				}
				else if (s[j] == '[') {
					cnt[2]++;
				}
				else if (s[j] == ')') {
					cnt[0]--;
				}
				else if (s[j] == '}') {
					cnt[1]--;
				}
				else if (s[j] == ']') {
					cnt[2]--;
				}
			}
			if (i < q-1) {
				set<int> count; int check;
				rep(k, le) {
					count.insert(v[k][0] * cnt[0] + v[k][1] * cnt[1] + v[k][2] * cnt[2]);
					check = v[k][0] * cnt[0] + v[k][1] * cnt[1] + v[k][2] * cnt[2];
				}
				if (count.size() != 1) {
					out.push_back(-1);
				}
				else {
					out.push_back(check);
				}
			}
		}
		rep(i, (int)out.size()) {
			cout << out[i];
			if (i < (int)out.size() - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3300
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

int main(int argc, char const *argv[]) {
  int n, k;
  cin >> n >> k;
  vector<int> vec(n);
  for (size_t i = 0; i < n; i++) cin >> vec[i];
  sort(vec.begin(), vec.end(), greater<int>());
  int ans = accumulate(vec.begin(), vec.begin()+k,0);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

int N;
int Y;

int main() {
    while (cin >> N >> Y) {
        Y /= 1000;
        int resa = -1, resb = -1, resc = -1;
        
        for (int a = 0; a <= N; ++a) {
            int remsum = Y - N;
            int remn = N-a;
            int tmp = remsum - remn * 4;
            
            if (tmp < 0) continue;
            if (tmp % 5 != 0) continue;
            
            int c = tmp / 5;
            int b = N-a-c;
            
            if (a >= 0 && b >= 0 && c >= 0)
                resa = a, resb = b, resc = c;
        }
        
        cout << resc << " " << resb << " " << resa << endl;
    }
}

















Measured memory_bytes: 256
// 23
#include <bits/stdc++.h>
using namespace std;
#define coutc "\033[48;5;196m\033[38;5;15m"
#define endc "\033[0m"
#define endl '\n'
#define M(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) M(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rep4(_, x, n, s) for (int _ = x; (s < 0) ? _ > n : _ < n; _ += s)
#define rep3(_, x, n) rep4(_, x, n, (x < n ? 1 : -1))
#define rep2(_, n) rep3(_, 0, n)
#define rep1(n) rep2(i, n)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
#define lli __int128_t
#define li long long int
#define ld long double
#ifdef DEBUG
// 3
ostream &operator<<(ostream &o, pair<auto, auto> p) {
  return o << "(" << p.fi << ", " << p.se << ")";
}
// 4
ostream &operator<<(ostream &o, vector<auto> v) {
  rep(i, len(v)) o << setw(7) << right << v[i];
  return o << endc << endl << coutc;
}
// 4
ostream &operator<<(ostream &o, map<auto, auto> m) {
  for (auto &kv : m) o << kv;
  return o;
}
// 7
void debug(const auto &e, const auto &... r) {
  cerr << coutc << e;
  ((cerr << " " << r), ..., (cerr << endc << endl));
}
#else
#define debug(...)
#endif
// 3
void _main(int tc) {
  int a, b;
  cin >> a >> b;
  if (b == 1) {
    cout << 0 << endl;
    return;
  }
  int ans = (b - 1) / (a - 1);
  if ((b - 1) % (a - 1)) {
    ans++;
  }
  cout << ans << endl;
}
// 7
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0), exit(0);
  int tc;
  cin >> tc;
  rep(i, tc) _main(i + 1);
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    int a,b;
    cin >> a >>b;
    string s;
    getchar();
    cin >> s;
    if(s.size()!=a+b+1){
        cout << "No" << endl;
    }else{
        for(int i = 0; i < a+b+1; i++){
            if(i == a){
                if(s[i]!='-'){
                    cout << "No" << endl;
                    return 0;
                }
            }else{
                if(s[i]<'0' || s[i] >'9'){
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
        printf("Yes\n");
    }

    return 0;
}


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

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

using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> Q;
typedef vector<int> V;

const int inf = 1e8;
const int bs = 300;

struct E{
	E(int t, int c): t(t), c(c){}
	int t, c;
};

int n, m, k, q;
vector<E> g[100000];
P z[100000];
int d[100000];
int sd[100000];
vector<Q> f;
vector<int> v[334];
int r[100000];
int up[100000];
int ur[100000];

void ut_init(){
	rep(i, n){
		up[i] = i;
		ur[i] = 0;
	}
}
int ut_find(int i){
	return up[i] == i ? i : up[i] = ut_find(up[i]);
}
bool ut_same(int i, int j){
	return ut_find(i) == ut_find(j);
}
void ut_unite(int i, int j){
	int p = ut_find(i);
	int q = ut_find(j);
	if(p == q){
		return;
	}
	if(ur[p] > ur[q]){
		up[q] = p;
	}
	else{
		up[p] = q;
		if(ur[p] == ur[q]){
			++ur[q];
		}
	}
}

void solve(){
	rep(i, n){
		rep(j, g[i].size()){
			E e = g[i][j];
			if(i < e.t){
				f.push_back(Q(
					min(d[i], d[e.t]),
					P(i, e.t)
				));
			}
		}
	}
	sort(f.begin(), f.end(), greater<Q>());

	int nb = (n + bs - 1) / bs;

	ut_init();

	V x;
	rep(i, q){
		x.push_back(i);
	}

	int nf = 0;
	rep(i, nb){
		int a = i * bs;
		int b = min((i + 1) * bs, n);
		while(nf < f.size() && f[nf].first >= sd[b - 1]){
			ut_unite(f[nf].second.first, f[nf].second.second);
			++nf;
		}

		V y;
		rep(j, x.size()){
			if(ut_same(z[x[j]].first, z[x[j]].second)){
				v[i].push_back(x[j]);
			}
			else{
				y.push_back(x[j]);
			}
		}
		x = y;
	}

	/*
	rep(i, f.size()){
		printf("f = %d, (%d, %d)\n", f[i].first, f[i].second.first, f[i].second.second);
	}
	*/

	ut_init();

	nf = 0;
	rep(i, nb){
		int a = i * bs;
		int b = min((i + 1) * bs, n);
		for(int j = a; j < b; ++j){
			while(nf < f.size() && f[nf].first >= sd[j]){
				ut_unite(f[nf].second.first, f[nf].second.second);
				++nf;
			}

			// printf("nf = %d, sd[j] = %d, j = %d\n", nf, sd[j], j);

			V y;
			rep(k, v[i].size()){
				if(ut_same(z[v[i][k]].first, z[v[i][k]].second)){
					r[v[i][k]] = sd[j];
				}
				else{
					y.push_back(v[i][k]);
				}
			}
			v[i] = y;
		}
	}
}

int main(){
	scanf("%d%d%d%d", &n, &m, &k, &q);
	rep(i, m){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[--a].push_back(E(--b, c));
		g[b].push_back(E(a, c));
	}

	fill_n(d, n, inf);

	priority_queue<P, vector<P>, greater<P> > pq;
	rep(i, k){
		int f;
		scanf("%d", &f);
		d[--f] = 0;
		pq.push(P(0, f));
	}
	while(!pq.empty()){
		P v = pq.top();
		pq.pop();
		if(v.first > d[v.second]){
			continue;
		}
		rep(i, g[v.second].size()){
			E e = g[v.second][i];
			if(d[e.t] > v.first + e.c){
				d[e.t] = v.first + e.c;
				pq.push(P(d[e.t], e.t));
			}
		}
	}

	rep(i, q){
		int s, t;
		scanf("%d%d", &s, &t);
		z[i] = P(s - 1, t - 1);
	}

	rep(i, n){
		sd[i] = d[i];
	}
	sort(sd, sd + n, greater<int>());

	solve();

	rep(i, q){
		printf("%d\n", r[i]);
	}
	return 0;
}

Measured memory_bytes: 17000
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
//const int MOD=998244353;
const int INF=1e9;
const long long LINF=1e18;
#define int long long
//template
template <typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
//main
signed main(){
  int N;cin>>N;
  std::vector<int> t(N+1),x(N+1),y(N+1);
  t[0]=x[0]=y[0]=0;
  for(int i=1;i<=N;i++)cin>>t[i]>>x[i]>>y[i];
  bool NG=false;
  for(int i=1;i<=N;i++){
    int TIME=t[i]-t[i-1];
    int DISTANT=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
    if(TIME<DISTANT)NG=true;
    if((TIME+DISTANT)%2==1)NG=true;
  }
  if(NG)cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
}


Measured memory_bytes: 2560
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#else
#include <bits/stdc++.h>
#endif // VS

#define long long long
using namespace std;

#pragma region CS_COMPATIBLE
#define var auto
#define Max std::max
#define Min std::min
#define Abs std::abs
//#define List std::vector;
//#define Add push_back
#pragma endregion

void read(uint32_t& x)
{
	x = 0;
	int k;
	while (true)
	{
		k = getchar_unlocked();
		if (k < '0' || k > '9')	break;
		x = x * 10 + k - '0';
	}
}

void sread(int32_t& x)
{
	bool flag;
	x = 0;
	int k = getchar_unlocked();
	if (flag = (k == '-')) k = getchar_unlocked();

	while (true)
	{
		if (k < '0' || k > '9')	break;
		x = x * 10 + k - '0';
		k = getchar_unlocked();
	}
	if (flag) x *= -1;
}

void sprint(int64_t x) {
	if (x == 0) {
		putchar_unlocked('0');
		return;
	}
	if (x < 0) {
		putchar_unlocked('-');
		x *= -1;
	}
	int s = 0;
	char f[15];
	while (x) {
		f[s++] = x % 10;
		x /= 10;
	}
	while (s--)
		putchar_unlocked(f[s] + '0');
	putchar_unlocked('\n');
}

int32_t a[200000];
int main() {
	uint32_t n;
	read(n);
	for (size_t i = 0; i < n; i++) sread(a[i]);
	int64_t res;
	if (n & 1) {
		//Odd
		var sum = 0L;
		for (int i = 0; i < n - 1; i += 2) sum += a[i];
		res = sum;
		int64_t tailDiff = 0, tailDiffMax = 0;
		for (int i = n - 3; i >= 0; i -= 2)
		{
			sum -= a[i]; sum += a[i + 1];
			tailDiff += a[i + 2]; tailDiff -= a[i + 1];
			tailDiffMax = max(tailDiffMax, tailDiff);
			res = max(res, sum + tailDiffMax);
		}
	}
	else {
		//Even
		int64_t sum = 0;
		for (size_t i = 0; i < n; i += 2) sum += a[i];
		res = sum;
		for (int i = n - 1; i >= 0; i -= 2)
		{
			sum += a[i]; sum -= a[i - 1];
			res = max(res, sum);
		}
	}
	sprint(res);
}


Measured memory_bytes: 4400