akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        string A, B, C;
        cin >> A >> B >> C;
        ll acur, bcur, ccur;
        acur = bcur = ccur = 0;

        char now = 'a';
        char ans;
        while (true) {
                if (now == 'a') {
                        now = A[acur];
                        if (acur == len(A)) {
                                ans = 'A';
                                break;
                        }
                        ++acur;
                } else if (now == 'b') {
                        now = B[bcur];
                        if (bcur == len(B)) {
                                ans = 'B';
                                break;
                        }
                        ++bcur;
                } else {
                        now = C[ccur];
                        if (ccur == len(C)) {
                                ans = 'C';
                                break;
                        }
                        ++ccur;
                }
        }
        cout << ans << endl;
}

Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
 
using namespace std;

int main(){
    int N,X;
    cin >> N >> X;

    int sum = 1;
    int D = 0;

    for(int i = 0; i < N; i++){
        int l;
        cin >> l;

        D += l;

        if(D <= X){
            sum++;
        }
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            
            {
                var b = 0;
                while (true)
                {


                    var ab = Console.ReadLine().Split().Select(long.Parse).ToArray();
                    var a = ab[0];

                    if (a == 0)
                        break;
                    b++;
                    Console.WriteLine("Case {0}: {1}", b, ab[0]);



                }
            }
    }
    }
}

Measured memory_bytes: 9664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void wri(ll a){write(a); putchar(' ');}
inline void writeln(ll a){write(a); puts("");}
const int N=300,mod=998244353;
int get(int n){
	int ans=1;
	for(int i=1;i<=n;i++)ans=ans*2%mod;
	return ans;
}
bitset<N> s[N];
signed main(){
	int n=read(),m=read();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)s[i][j]=read();
	}
	int rk=0;
	for(int i=0,j=0;i<m;i++){
		for(int k=j;k<n;k++)if(s[k][i]){swap(s[k],s[j]); break;}
		if(!s[j][i])continue; else rk++;
		for(int k=j+1;k<n;k++)if(s[k][i])s[k]^=s[j];
		j++;
	}
	int ans=get(n)-get(n-rk)+mod;
	cout<<(ll)ans*get(m-1)%mod<<endl;
}


Measured memory_bytes: 256
n, d = map(int, input().split())
lst = []
cnt = 0
for i in range(n):
    a = list(map(int, input().split()))
    lst.append(a)
for i in range(n-1):
    for j in range(i+1, n):
        x = 0
        for k in range(d):
            x += (lst[i][k]-lst[j][k]) ** 2
        dist = x ** 0.5
        if dist%1 == 0:
            if dist != 0:
                cnt += 1
print(cnt)

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

const int MAX = 510000;
const int mod = 924844033;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

ll cnt[4001];
ll dp[2001][2001][2];
ll sum[4001][2001];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    COMinit();
    ll n,k;
    cin>>n>>k;
    for(int i=0;i<=k;i++){
        cnt[2*i] = (n-i-1)/k;
        cnt[2*i+1] = (n-i-1)/k;
        //cerr << cnt[2*i] << endl;
    }
    ll ans = fac[n];
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            if(j+1 <= n) dp[i+1][j+1][1] += dp[i][j][0];
            dp[i+1][j][0] = dp[i][j][0] + dp[i][j][1];
            dp[i+1][j][0] %= mod;
            dp[i+1][j][1] %= mod;
            //cerr << i+1 << " " << j << " " << dp[i+1][j][1] + dp[i+1][j][0] << endl;
        }
    }
    sum[0][0]=1;
    for(int i=0;i<2*k;i++){
        for(int j=n;j>=0;j--){
            for(int k=cnt[i];k>=0;k--){
                if(j-k >=0) sum[i+1][j] += sum[i][j-k] * (dp[cnt[i]][k][0]+dp[cnt[i]][k][1]);
                sum[i+1][j] %= mod;
                //cerr << i+1 << " " << j << " " << sum[i+1][j] << endl;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i%2) ans += (sum[2*k][i+1]*fac[n-i-1])%mod;
        else ans += mod - (sum[2*k][i+1]*fac[n-i-1])%mod;
        ans %= mod;
        //cerr << i << " " << ans << " " << sum[2*k][i+1] << endl;
    }
    cout << ans << endl;
}


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

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  
  int len = s.size();
  for(int i = 0; i < len; i++){
    int x = s[i] - 'A';
    x = (x+n)%26;
    s[i] = x + 'A';
  }
  

  cout << s << endl;
}

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

#define fast() {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
using ll = long long;
const int mod = 1e9 + 7;

int main()
{
	fast();
	int n, x, y;
	cin >> n >> x >> y;
	x--, y--;
	vector<int> ans(n + 1, 0);
	vector<vector<int>>a(n + 1, vector<int>(n + 1, 1));
	for(int i = 0; i < n; ++i){
		for(int j  = i + 1; j < n; ++j){
			if(x >= i && j >= y){
				ans[j - i - (y - x) + 1]++;
			}
			else{
				int dis = abs(i - x) + 1 + abs(j - y);
				ans[min(dis, j - i)] ++;
			}
		}
	}
	for(int i =  1; i <= n - 1; ++i){
		cout << ans[i] <<" ";
	}
}			

Measured memory_bytes: 16000
import java.io.*;
import java.util.*;
class   Main       {
	public static void main(String[] args) 
	{
		InputReader in = new InputReader(System.in);
		PrintWriter w = new PrintWriter(System.out);
		Scanner sc = new Scanner(System.in);
		int n = in.nextInt();
		int m=in.nextInt();
		w.println((n-1)*(m-1));
		w.close();
		sc.close();
	}
	static class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		public InputReader(InputStream st) {
			this.stream = st;
		}
		public int read() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		
		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		public String readString() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		
		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
		
	}
	
}

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

using namespace std;

const int64_t M = 998244353;
const int MAX_N = 300000;
int64_t com[MAX_N+1];

int64_t mod_pow(int64_t a, int64_t b)
{
  if (b == 0) return 1;
  int64_t ret = mod_pow(a, b/2);
  ret = ret * ret % M;
  if (b % 2 == 1) ret = a * ret % M;
  return ret;
}

int main()
{
  int64_t n, a, b, k;

  cin >> n >> a >> b >> k;

  int64_t c = com[0] = 1;
  for (int64_t i = 1; i <= n; i++) {
    com[i] = c = (c * (n-i+1) % M) * mod_pow(i, M-2) % M;
  }

  int64_t count = 0;
  for (int64_t i = 0; i <= n && i*a <= k; i++) {
    int64_t r = (k - i*a) % b;
    int64_t j = (k - i*a) / b;
    if (r == 0 && j <= n) {
      count = (count + com[i] * com[j] % M) % M;
    }
  }
  cout << count << endl;

  return 0;
}


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

int main() {
  int h, w, i, j, k, x = 0, y = 0;
  cin >> h >> w;
  
  vector<vector<char>> a(h, vector<char>(w)), b(h, vector<char>(w)), c(h, vector<char>(w));
  for(i = 0; i < h; i++){
    for(j = 0; j < w; j++){
      cin >> a.at(i).at(j);
    }
  }
  
  for(i = 0; i < h; i++){
    for(j = 0; j < w; j++){
      if(a.at(i).at(j) == '#'){
        for(k = 0; k < w; k++){
          b.at(x).at(k) = a.at(i).at(k);
        }
        x++;
        break;
      }
    }
  }
  
  for(i = 0; i < w; i++){
    for(j = 0; j < x; j++){
      if(b.at(j).at(i) == '#'){
        for(k = 0; k < x; k++){
          c.at(k).at(y) = b.at(k).at(i);
        }
        y++;
        break;
      }
    }
  }
  
  for(i = 0; i < x; i++){
    for(j = 0; j < y; j++){
      cout << c.at(i).at(j);
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		sc.close();
		int fiveHundred = 0, five = 0, one = 0;
		while (x!=0) {
			if (x%500 == 0) {
				x-=500; fiveHundred++;
			} else if (x%5 == 0) {
				x-=5; five++;
			} else {
				x-=1; one++;
			}
		}

		System.out.println(1000 * fiveHundred + 5 * five);
	}
}


Measured memory_bytes: 35648
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

const int MAX = 100010;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int MOD = 1000000007;

int n[MAX];

void solve(void){
    int N;
    cin >> N;
    rep(N, i) scanf("%d ", &n[i]);

    ll ans = 1LL;
    int i = 0;
    while (i < N) {
        ll dif = n[i+1] - n[i];
        while (dif == 0) {
            i++;
            dif = n[i+1] - n[i];
        }
        while (dif * (n[i+1] - n[i]) >= 0 && i < N) {
            i++;
            if (i == N-1) {
                cout << ans << endl;
                return;
            }
        }
        i++;
        if (i < N) ans++;
    }
    cout << ans << endl;
}

int main(void){
  solve();
  return 0;
}


Measured memory_bytes: 640
/*
  Topic12 ProblemB 単一始点最短経路
  与えられた重み付き有向グラフG=(V,E)について、単一始点最短経路のコストを求める
  プログラムを作成してください。
  Gの頂点0を始点とし,0から各頂点vについて、
  最短経路上の辺の重みの総和 d[v] を出力してください。
*/
#include<stdio.h>

#define MAX 100
#define INFTY 100008
#define WHITE 0
#define GRAY 1
#define BLACK 2

void dijkstra(void);

int n, M[MAX][MAX];

int main()
{
  int i, j, k, c, u, v;

  scanf("%d", &n);
  //Initialize
  for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
        {
          M[i][j] = INFTY;
        }
    }

  for(i=0;i<n;i++)
    {
      scanf("%d%d", &u, &k);
      for(j=0;j<k;j++)
        {
          scanf("%d%d", &v, &c);
          M[u][v] = c;
        }
    }

    dijkstra();

  return 0;
}

void dijkstra(void)
{
  int i, j, minv, u, v;
  int d[MAX], color[MAX];

  for(i=0;i<n;i++)
    {
      color[i] = WHITE;
      d[i] = INFTY;
    }

  color[0] = GRAY;
  d[0] = 0;
  while(1)
    {
      minv = INFTY;
      u = -1;
      for(i=0;i<n;i++)
        {
          if(minv > d[i] && color[i] != BLACK)
            {
              u = i; minv = d[i];
            }
        }
      if(u == -1)break;
      color[u] = BLACK;
      for(v=0;v<n;v++)
        {
          if(color[v] != BLACK && M[u][v] != INFTY)
            {
              if(d[v] > d[u] + M[u][v])
                {
                  d[v] = d[u] + M[u][v];
                  color[v] = GRAY;
                }
            }
        }
    }
    for(i=0;i<n;i++)
      {
        printf("%d %d\n", i, d[i]);
      }
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n, ans = 0;
    string s;
    cin >> n >> s;
    char pre = '@';
    for(char c: s) {
        if (c != pre)
            ans += 1;
        pre = c;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

vec kmp_table(string &Pattern) {
    ll i = 2, j = 0;
    vec T(Pattern.size(), -1);
    T[1] = 0;

    while (i < Pattern.size()) {
        if (Pattern[i-1] == Pattern[j]) {
            T[i] = j+1;
            i++;
            j++;
        } else if (j > 0) {
            j = T[j];
        } else {
            T[i] = 0;
            i++;
        }
    }

    return T;
}

vec kmp_search (string &Text, string &Pattern, vec &kmptable) {
    vec ret;
    ll m = 0, i = 0;
    while (m+i < Text.size()) {
        if (Pattern[i] == Text[m+i]) {
            i++;
            if (i == Pattern.size()) {
                if (m%32 == 0) ret.push_back(m/32);
                i--;
                m = m+i-kmptable[i];
                i = kmptable[i];
            }
        } else {
            m = m+i-kmptable[i];
            if (i > 0) i = kmptable[i];
        }
    } 
    return ret;
}

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

    ll N;
    cin >> N;
    vec A(N), B(N);
    Rep (i, N) cin >> A[i];
    Rep (i, N) cin >> B[i];

    vec da(N), db(N);
    stringstream ssa, ssb;
    Rep (i, N) {
        da[i] = A[i] ^ A[(i+1)%N];
        db[i] = B[i] ^ B[(i+1)%N];
        ssa << bitset<32>(da[i]);
        ssb << bitset<32>(db[i]);
    }

    string sa = ssa.str();
    string sb = ssb.str();

    // cout << sa << "\n";
    // cout << sb << "\n";

    sa += sa;
    sa.pop_back();
    vec t = kmp_table(sb);
    t = kmp_search(sa, sb, t);
    Rep (i, t.size()) {
        cout << t[i] << " " << (A[0] ^ B[(N-t[i])%N]) << "\n";
    }

}

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b && b == c && a == c){
        cout << "No" << endl;
        return 0;
    }
    if(a == b || b == c || a == c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

public class Hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = int.Parse(line[0]);
            var m = int.Parse(line[1]);
            if (n == 0 && m == 0) break;
            var a = new int[n, n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) a[i, j] = -1;
            for (int i = 0; i < m; i++)
            {
                string[] line2 = Console.ReadLine().Trim().Split(' ');
                var w1 = int.Parse(line2[0]);
                var w2 = int.Parse(line2[1]);
                var w3 = int.Parse(line2[2]);
                a[w1, w2] = w3; a[w2, w1] = w3;
            }
            Console.WriteLine(getStlist(a));
        }
    }
    public static int getStlist(int[,] a)
    {
        var s = new List<int>();
        var n = a.GetLength(0);
        var a1 = 0;
        var totalmincost = 0;
        while (true)
        {
            s.Add(a1);
            if (s.Count() == n) return totalmincost;
            var nexta1 = -1; var mincost = 999999;
            foreach (var x in s)
                for (int i = 0; i < n; i++)
                    if (!s.Contains(i) && a[x, i] != -1 && a[x, i] < mincost) { nexta1 = i; mincost = a[x, i]; }
                    else a1 = nexta1;
            totalmincost += mincost;
        }
    }
}

Measured memory_bytes: 9980
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
#include <algorithm>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int ms = 100100;

std::vector<int> edges[ms];
std::vector<std::pair<int, int>> dp[ms];

void pre(int on, int par) {
	for(int i = 0; i < (int) edges[on].size(); i++) {
		if(edges[on][i] == par) {
			std::swap(edges[on][i], edges[on].back());
			edges[on].pop_back();
			i--;
			continue;
		}
		pre(edges[on][i], on);
	}
	dp[on].resize(edges[on].size());
}

int L;
int solve(const std::vector<std::pair<int, int>> &a, int skip) {
	int ans = 0;
	for(int l = 0, r = (int) a.size() - 1; l < r; l++) {
		if(l == skip) continue;
		if(r == skip) {
			r--;l--;
			continue;
		}
		int s1 = L - a[l].first;
		int s2 = L - a[r].first;
		if(s1 + s2 <= L) {
			r--;
			ans++;
		}
	}
	return ans;
}
std::pair<int, int> dfs(int on) {
	// returns (number of paths, rest of path going up)
	int sum = 0;
	for(int i = 0; i < (int) edges[on].size(); i++) {
		dp[on][i] = dfs(edges[on][i]);
		if(dp[on][i].second == 0) {
			dp[on][i].first++;
			dp[on][i].second = L - 1;
		} else {
			dp[on][i].second--;
		}
		sum += dp[on][i].first;
	}
	// always when possible, pair shit up
	for(auto &p : dp[on]) std::swap(p.first, p.second);
	std::sort(dp[on].begin(), dp[on].end());
	int can = solve(dp[on], 1298739);
	if(2 * can == (int) dp[on].size()) {
		return std::pair<int, int>(sum - can, 0);
	}
	int l = 0, r = (int) dp[on].size() - 1;
	while(l != r) {
		int mid = (l + r + 1) / 2;
		if(solve(dp[on], mid) == can) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	assert(solve(dp[on], l) == can);
	return std::pair<int, int>(sum - can, dp[on][l].first);
}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n;
	std::cin >> n;
	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		u--;v--;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	pre(0, 0);
	int l = 1, r = n;
	L = n;
	int best = dfs(0).first;
	while(l != r) {
		L = (l + r) / 2;
		if(dfs(0).first == best) {
			r = L;
		} else {
			l = L + 1;
		}
	}
	std::cout << best << ' ' << l << '\n';
}

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

using namespace std;

#define sqr(x) ((x) * (x))
#define pb push_back
#define mp make_pair
#define ins insert
#define er erase
#define bg begin()
#define ed end()
#define X first
#define Y second
#define fin(name) freopen(name, "r", stdin)
#define fout(name) freopen(name, "w", stdout)
#define files(name) fin(name".in"); fout(name".out")
#define enter cout << "\n"
#define space cout << " "
#define endl "\n"
#define fi(st,n) for (int i = (st); i <= (n); i++)
#define fj(st,n) for (int j = (st); j <= (n); j++)
#define fk(st,n) for (int k = (st); k <= (n); k++)
#define fq(st,n) for (int q = (st); q <= (n); q++)
#define fw(st,n) for (int w = (st); w <= (n); w++)
#define ff(i, st, n) for (int (i) = (st); (i) <= (n); (i)++)
#define ei(st,n) for (int i = (st); i >= (n); i--)
#define ej(st,n) for (int j = (st); j >= (n); j--)
#define ek(st,n) for (int k = (st); k >= (n); k--)
#define ri(st,n) for (int i = (st); i < (n); i++)
#define rj(st,n) for (int j = (st); j < (n); j++)
#define rk(st,n) for (int k = (st); k < (n); k++)
#define rq(st,n) for (int q = (st); q < (n); q++)
#define rf(i, st, n) for (int (i) = (st); (i) < (n); (i)++)
#define clean(a) memset((a),0,sizeof (a))
#define sync ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define y1 dsklmlvmd

typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int inf = (int)1e9;
const dbl eps = (dbl) 1e-8;
const int mod = (int) 1000000007;
const int maxn = (int) 1e5 + 5;
//const dbl M_PI = (dbl)2 * (dbl)acos(0);

//cout<<fixed<<setprecision(10);
//srand(time(0))

string st;
int t[11];

int main()
{
//	fin("t.in");
	sync;
	cin >> st;
	clean(t);
	ri(0, st.size())
	{
		if (st[i] == 'N')
			t[1] = 1;
		if (st[i] == 'E')
			t[2] = 1;
		if (st[i] == 'S')
			t[3] = 1;
		if (st[i] == 'W')
			t[4] = 1;
	}
	if (t[1] == t[3] && t[2] == t[4])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;		
 	return 0;
}


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


int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> A(H, vector<char>(W));
  for(int ii=0; ii<H; ii++){
    for(int jj=0; jj<W; jj++){
      cin >> A[ii][jj];
    }
  }
  
  vector<bool> output_row(H, false);
  vector<bool> output_col(W, false);
  for(int ii=0; ii<H; ii++){
    for(int jj=0; jj<W; jj++){
      if(A[ii][jj] == '#'){
        output_row[ii] = true;
        output_col[jj] = true;
      }
    }
  }
  for(int ii=0; ii<H; ii++){
    if(output_row[ii]==false) continue;
    for(int jj=0; jj<W; jj++){
      if(output_col[jj]==false) continue;
      cout << A[ii][jj];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define INFTY 1000000001

void merge(int *,int,int,int);

void mergesort(int *,int,int);

long long Count;

int main()
{
  int n,i;

  scanf("%d",&n);

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

  mergesort(A,0,n);

  printf("%lld\n",Count);
  
}

void mergesort(int *A,int L,int R)
{
  int M;
  
  if(L+1<R)
    {
      M=(L+R)/2;
      mergesort(A,L,M);
      mergesort(A,M,R);
      merge(A,L,M,R);
    }
}

void merge(int *A,int L,int M,int R)
{
  int n1,n2,i,j,k;
  static int a=0;
  n1=M-L;
  n2=R-M;

  int l[n1+1],r[n2+1];

  for(i=0;i<n1;i++) l[i]=A[L+i];
  for(i=0;i<n2;i++) r[i]=A[M+i];

  l[n1]=INFTY;
  r[n2]=INFTY;

  i=0;
  j=0;

  for(k=L;k<R;k++)
    {
      if(l[i]<=r[j])
	{
	  A[k]=l[i];
	  i=i+1;
	}
      else
	{
	  A[k]=r[j];
	  j=j+1;
	  Count+=n1-i;
	}
    }
}



Measured memory_bytes: 3416
#include "bits/stdc++.h"

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector< int> in(n + 1);

    int res = 1, p = 0;
    for (int i = 1; i <= n; ++i) {
       int a;
       scanf("%d", &a);
        p += a;
        if (p <= x) res ++;
        else break;
    }

    printf("%d\n", res);
}

Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int a,b,c,d,x;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	x=min(b,d)-max(a,c);
	if(x<0)	x=0;
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
def input_n
  gets.to_i               # 単一整数
end

def input_s
  gets.chomp              # 文字列。chompを付けないと改行文字がついてくる
end

def input_a
  gets.split.map(&:to_i)  # スペースで区切られた複数の整数
end

def input_o(num)
  num.times.map { gets.to_i }  # 縦に並んだ複数の整数。たまにある
end

def output_f(num)
  puts sprintf("%.12f", num)
end

n, k = input_a
a = input_a
b = Array.new(n, -1)
index = 0
cnt = 0
while cnt < k
  if b[index] != -1
    nokori = k - cnt
    amari = nokori % (cnt - b[index])
    amari.times do |i|
      index = a[index] - 1
    end
    puts index + 1
    exit
  end
  b[index] = cnt
  index = a[index] - 1
  cnt += 1
end
puts index + 1


Measured memory_bytes: 28988
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

const int N = 2e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 3e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 2e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);

template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
bool a[N],b[N];
main() {
    file("balance");
    ios;
    cin>>n;
    fo(i,1,n,1) cin>>a[i];
    foo(i,n,1,1) {
        int sum=0;
        fo(j,i,n,i) sum+=b[j],sum%=2;
        if (sum==a[i]) continue;
        b[i]^=1;
    }
    vector <int> ans;
    fo(i,1,n,1) {
        int sum=0;
        fo(j,i,n,i) {
            sum+=b[j];
            sum%=2;
        }
        if (a[i]!=sum) return !(cout<<-1);
    }
    fo(i,1,n,1) if (b[i]) ans.eb(i);
    cout<<ans.size()<<"\n";
    for (int it : ans) cout<<it<<" ";
    return 0;
}
/**

*/


Measured memory_bytes: 2040
import java.util.Arrays;

class Main {

    private static final int CONST= 1000000007;
    public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] S = new int[n];
        for(int i=0; i<n; i++)  S[i] = Integer.parseInt(sc.next());

        int q = Integer.parseInt(sc.next());
        int[] T = new int[q];
        for(int i=0; i<q; i++)  T[i] = Integer.parseInt(sc.next());

        int count = 0;
        for(int element : T){
            if(Arrays.binarySearch(S, element) >= 0)    count++;
        }
        System.out.println(count);
        sc.close();
    }
}


Measured memory_bytes: 70972
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;

int main()
{
	char buf[4];
	cin >> buf;
	for (size_t i = 0; i < 3; i++)
	{
		buf[i] = buf[i] == '1' ? '9' : '1';
	}
	cout << buf << endl;
	return 0;
}

Measured memory_bytes: 256
def gcd(a,b):    #求最大公约数
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
mod=1000000007
s=[int(j) for j in input().split()]
ans=1
for i in s:
    ans*=i//gcd(ans,i)
print(sum(ans//i for i in s)%mod)


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

#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN = 2e5+5;
const int MOD= 998244353;
int n,b[MAXN];
struct node{
    int x,y;
}a[MAXN];
bool cmp(node a,node b){
    return a.x<b.x;
}
ll dp[MAXN];
struct Node{
    int l,r,maxx;
}t[MAXN<<2];
void build(int rt,int l,int r){
    t[rt].l=l,t[rt].r=r;
    t[rt].maxx=-2e9-1;
    if(l==r)return;
    int mid=(t[rt].l+t[rt].r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
void update(int rt,int p,int val){
    if(t[rt].l==t[rt].r){
        t[rt].maxx=max(t[rt].maxx,val);
        return;
    }
    int mid=(t[rt].l+t[rt].r)>>1;
    if(p<=mid)update(rt<<1,p,val);
    else update(rt<<1|1,p,val);
    t[rt].maxx=max(t[rt<<1].maxx,t[rt<<1|1].maxx);
}
int query(int rt,int l,int r){
    if(t[rt].l>=l&&t[rt].r<=r)return t[rt].maxx;
    int ans=-2e9-1;
    int mid=(t[rt].l+t[rt].r)>>1;
    if(l<=mid)ans=max(ans,query(rt<<1,l,r));
    if(r>mid)ans=max(ans,query(rt<<1|1,l,r));
    return ans;
}
int main()
{
    scanf("%d",&n);
    build(1,1,n);
    rep(i,1,n){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].y+=a[i].x-1;
    }
    sort(a+1,a+n+1,cmp);
    rep(i,1,n)b[i]=a[i].x;
    dp[n+1]=1;
    per(i,n,1){
        int p=upper_bound(b+1,b+n+1,a[i].y)-b;
        p--;
        int temp=max(query(1,i,p),a[i].y);
        update(1,i,temp);
        p=upper_bound(b+1,b+n+1,temp)-b;
        dp[i]=(dp[i+1]+dp[p])%MOD;
    }
    printf("%lld\n",dp[1]);
}


Measured memory_bytes: 13568
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    // input
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    // input end
    if (a + b == c + d) { std::cout << "Balanced" << std::endl; }
    else if (a + b > c + d)
    {
        std::cout << "Left" << std::endl;
    }
    else
    {
        std::cout << "Right" << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/

#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define fo(x,y) for(int x = 1 ; x <= y ; ++x)
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;

typedef long long ll;
typedef unsigned int uint;
const int nmax = 200005;
const ll linf = LLONG_MAX;
const int mod = 1e9+7;
const int inf = INT_MAX;

ll h, n, value[nmax], cost[nmax];
ll dp[nmax];

int main(){
    cin >> h >> n;
    fo(i,n){
        cin >> value[i] >> cost[i];
    }
    fo(i,h){
        dp[i] = linf;
        fo(j,n){
            if(i - value[j] <= 0)dp[i] = min(dp[i],cost[j]);
            else{
                dp[i] = min(dp[i],dp[i-value[j]] + cost[j]);
            }
        }
    }
    cout << dp[h] << '\n';
}


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

using namespace std;
int n,m;

   int s =0;

int a[100110];
int main()
{
    cin>> n>> m;
for(int i =0;i<m;i++){
    cin>>a[i];
   }
   for(int i =0;i<m;i++){
 s+=a[i];
   }
if(s>n){
    cout<<-1<<endl;
}
else{
    cout<< n-s<<endl;
}


    return 0;
}


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

int main()
{
    ll a, b, c, d;
    cin>>a>>b>>c>>d;

    ll lc = (c*d)/__gcd(c,d);

    ll tot = b - a + 1;

    ll low_l = ceil((long double)a/lc);
    ll high_l = floor((long double)b/lc);

    //cout<<low_l<<" "<<high_l<<endl;

    ll low_c = ceil((long double)a/c);
    ll high_c = floor((long double)b/c);
    //cout<<low_c<<" "<<high_c<<endl;
    ll re = high_c - low_c + 1;
    ll low_d = ceil((long double)a/d);
    ll high_d = floor((long double)b/d);
    //cout<<low_d<<" "<<high_d<<endl;
    re += high_d - low_d + 1;
    //cout<<re<<endl;
    re -= (high_l - low_l + 1);

    cout<<tot - re ;
    return 0;
}
//532105071133627368


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a,b,c;
    int n=0;
    scanf("%d %d %d",&a,&b,&c);
    for (int i=a;i<=b;i++){
        if (c%i==0){
            n++;
        }
    }
    printf("%d\n",n);
    return 0;
}
  


Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
const int NIL = -1;
const int maxn = 1010;
const int disx[4] = {-1, 1, 0, 0};
const int disy[4] = {0, 0 ,1 ,-1};
int H, W, ch, cw, dh, dw;
char maz[maxn][maxn];
int b[maxn][maxn], blk;
void dfs(int x,int y, int bb){
    b[x][y] = bb;
    for (int i=0;i<4;i++){
        int p = x + disx[i];
        int q = y + disy[i];
        if (p < 0 || q < 0 || p >= H || q >= W) continue;
        if (maz[p][q] == '#') continue;
        if (b[p][q] != -1) continue;
        dfs(p, q, bb);
    }
}
bool vis[maxn*maxn];
int dist[maxn*maxn];
vector<int>node[maxn*maxn];
void Spfa(int X){
//    cout<<"X = "<<X<<endl;
    queue<int> que;
    for(int i = 1; i <= blk; i++) {dist[i] = NIL;vis[i] = false;}
    dist[X] = 0;
    que.push(X);
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        vis[now] = false;
        for (int i=0,sz = node[now].size();i<sz;i++){
            int to = node[now][i];
            if(dist[to] == NIL || dist[to] > dist[now] + 1) {
                dist[to] = dist[now] + 1;
                if(!vis[to]) {
                    vis[to] = true;
                    que.push(to);
                }
            }
        }
    }
//    for (int i=1;i<=blk;i++) cout<<dist[i]<<" ";cout<<endl;
}
void add(int u, int v){
    for (int i=0,sz = node[u].size();i<sz;i++){
        int to = node[u][i];
        if (to == v) return;
    }
    node[u].push_back(v);
}
void addedge(int x,int y, int bb){
    for (int i=-2;i<=2;i++)
        for (int j=-2;j<=2;j++){
            int p = x + i, q = y + j;
            if (p < 0 || q < 0 || p >= H || q >= W) continue;
            if (maz[p][q] == '#') continue;
            if (b[p][q] != bb) add(bb, b[p][q]);
    }

}
int work(){
//    for (int i=0;i<H;i++){
//        for (int j=0;j<W;j++) printf("%c",maz[i][j]);
//        cout<<endl;
//    }
//    cout<<"ok"<<endl;
    memset(b, -1, sizeof(b));
    blk = 0;
    for (int i=0;i<H;i++)
        for (int j=0;j<W;j++) if (maz[i][j] == '.' && b[i][j] == -1) dfs(i,j, ++blk);

//    for (int i=0;i<H;i++){
//        for (int j=0;j<W;j++) printf("%d ",b[i][j]);
//        cout<<endl;
//    }
    for (int i=0;i<H;i++)
        for (int j=0;j<W;j++) if (maz[i][j] == '.'){
            addedge(i,j, b[i][j]);
    }
//    for (int i=1;i<=blk;i++){
//        cout<<i<<" --- ";
//        for (int j=0,sz = node[i].size();j<sz;j++) cout<<node[i][j]<<" ";
//        cout<<endl;
//    }
    Spfa(b[ch-1][cw-1]);
//    cout<<"to = "<<b[dh-1][dw-1]<<endl;
    return dist[b[dh-1][dw-1]];
}
int main(){
    scanf("%d%d%d%d%d%d",&H,&W, &ch, &cw, &dh, &dw);
    for (int i=0;i<H; i++) scanf("%s", maz[i]);
    printf("%d\n",work());
    return 0;
}


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

LR = [[0 for _ in range(N+2-i)] for i in range(N+2)]
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

  
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
A = []
for i in range(Q):
  p, q = map(int, input().split())
  A.append(LR[p][q-p+1])

print("\n".join(map(str,A)))


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

typedef long long ll;

int S;
ll ans = 0;
ll mod = 1000000007;
ll F[100010];

int f(int i)
{
    int res = 0;
    while(i)i /= 10,res++;
    return res;
}

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod,b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

int main()
{
    scanf("%d",&S);

    int l = 1,r = 1,sum = 0,ll = 10,rr = 10,nl = 1,nr = 1;
    while(1)
    {
        while(r != 100000000 && sum < S)
        {
            sum += nr;
            r++;
            if(r == rr)
            {
                rr *= 10;
                nr++;
            }
        }
        while(sum > S)
        {
            sum -= nl;
            l++;
            if(l == ll)
            {
                ll *= 10;
                nl++;
            }
        }
        if(r == 100000000)break;
        if(sum == S && nl != nr - (r == rr / 10))ans++;
        sum -= nl;
        l++;
        if(l == ll)
        {
            ll *= 10;
            nl++;
        }
    }

    for(int i = 1; i <= (int)sqrt((double)S); i++)
    {
        if(S % i == 0)
        {
            if(i * i == S)
            {
                if(i >= 9 || pow_mod(10,i - 1) * 9 + 1 >= i)
                {
                    ans += (mod + pow_mod(10,i - 1) * 9 - i + 1) % mod;
                }
            }
            else
            {
                if(i >= 9 || pow_mod(10,i - 1) * 9 + 1 >= S / i)
                {
                    ans += (mod + pow_mod(10,i - 1) * 9 - S / i + 1) % mod;
                }
                if(S / i >= 9 || pow_mod(10,S / i - 1) * 9 + 1 >= i)
                {
                    ans += (mod + pow_mod(10,S / i - 1) * 9 - i + 1) % mod;
                }
            }
        }
    }

    ans += S / 8 - (S % 8 == 0);
    ans %= mod;

    for(int i = 1; i <= (int)sqrt((double)(S)); i++)
    {
        if(S % i == 0 && i < S / 8)
        {
            if(i * i == S)ans--;
            else
            {
                ans--;
                if(S / i < S / 8)ans--;
            }
            ans %= mod;
        }
    }


    printf("%lld\n",ans);
    return 0;
}




Measured memory_bytes: 384
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

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

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

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int64 ans = 0;
    for (int j = 1; j <= n; ++j) {
        int k = n / j;
        ans += (int64) j * (k + 1) * k / 2;
    }
    print(ans);

    return 0;
}

/*
     _
  __| |  ___ _ __  _ __
 / _` | / __| '_ \| '_ \
| (_| || (__| |_) | |_) |
 \__,_(_)___| .__/| .__/
            |_|   |_|
*/


Measured memory_bytes: 3632
N=int(input())
H=list(map(int,input().split()))
A=[0]*N
j=0
for i in range(0,N-1):
    if H[i]>=H[i+1]:
        A[j]=A[j]+1
    else :
        j=j+1
ANS=max(A)
print(ANS)




Measured memory_bytes: 14252
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello
{
    public static void Main()
    {
        //入力を保持する
        var AB = Console.ReadLine().Split().ToArray();
        var A = long.Parse(AB[0]);
        var B = long.Parse(AB[1].Replace(".",""));
        Console.WriteLine(A * B/100);
    }
}


Measured memory_bytes: 27984
N = int(input())
X = [0] * N
for i in range(N):
    x, l = map(int, input().split())
    X[i] = x, l, x - l, x + l

X.sort(key=lambda x: x[3])  # 端点順
right = X[0][3]
count = 1
for i in range(1, N):
    if right <= X[i][2]:
        count += 1
        right = X[i][3]

print(count)

Measured memory_bytes: 26152
import math


def combination(i: int, j: int) -> int:
    return math.factorial(i) // math.factorial(i - j) // math.factorial(j)


if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    modulo = 10 ** 9 + 7
    ans = 0
    if k <= n:
        for i in range(k):
            if 0 == i % 2:
                ans += (k - i) ** n * combination(k, i)
            else:
                ans -= (k - i) ** n * combination(k, i)
        ans = ans % modulo

    print(ans)



Measured memory_bytes: 5668
#!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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    while True:
        n = II()
        if not n:
            break
        a = IR(n)
        a.sort()
        print(sum(a[1:-1])//(n-2))
            
    return

#B
def B():
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while True:
        w, h = LI()
        if w == h == 0:
            break
        field = SR(2 * h - 1)
        check = [[True] * (2 * w - 1) for i in range(2 * h - 1)]
        next = deque()
        next.append((0, 0))
        ans = 1
        flg = True
        
        while next and flg:
            now = next
            next = deque()
            while now:
                x, y = now.pop()
                for mx, my in move:
                    mmx, mmy = x + mx, y + my
                    
                    if 0 <= mmx < 2 * w - 1 and 0 <= mmy < 2 * h - 1:
                        if field[mmy][mmx] == '0' and check[mmy+my][mmx+mx]:
                            next.append((mmx + mx, mmy + my))
                            check[mmy + my][mmx + mx] = False
                            if mmx+mx == 2 * w - 2 and mmy+my == 2 * h - 2:
                                print(ans+1)
                                flg = False
                                next = deque()
                                now = deque()
                                break
            ans += 1
        if flg:
            print(0)
            
    
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()



Measured memory_bytes: 8380
#include<bits/stdc++.h>
const int mo=1e9+7,N=75;
int n,K,i,j,k,s1,s2,C[N*2][N*2],st[N],w,b,x,y,ans=1,a[N];
char c[N];
void dfs(int d,int s,int ss,bool fl){
	if(fl){
		for(i=1,j=k=w,b=0;i<=K;++i){
			if(c[i]=='r'){if(j)--j;else if(b)--b;}
			if(c[i]=='b'){if(k>j && st[k])b+=st[k--]-1;else if(b)--b;}
		}
		if(!j && !st[k] && !b){
			s1=s-1,s2=ss+1,x=C[n-s1+s2-1][s2-1];y=0;
			for(i=0;i<d;++i)y+=a[i],x=1ll*C[y][a[i]]*x%mo;
			ans=(ans+x)%mo;
		}
	}
	if(s+(d<2?1:d*2-1)>n)return;
	int ow=w;
	for(int i=0,j;s+i*(d<2?1:d*2-1)+i-1<=n;st[++w]=d,++i)
		a[d]=i,dfs(d+1,s+i*(d<2?1:d*2-1)+i,ss+i*(d*2+1)+i,i);
	w=ow;
}
int main(){
	for(i=**C=1;i<N*2;++i)for(j=*C[i]=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	scanf("%d%d%s",&n,&K,c+1);
	dfs(0,0,0,0);
	printf("%d\n",ans%mo);
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	const char *SEP = " ";
	int n;
	char input_str[256];
	char *num_str;

	fgets(input_str, sizeof(input_str), stdin);
	num_str = strtok(input_str, SEP);
	n = atoi(num_str);

	if ( 30 <= n ) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 1552