akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
vector<int> g[MAXN];
int s[MAXN];
int vis[MAXN];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin >> n >> m;
  for(int i = 0 ; i < m ; i++)
   {
       int u,v;
       cin >> u >> v;
       g[u].push_back(v);
       g[v].push_back(u);
   }
   queue<int> q;
  q.push(1);
  vis[1] = 1;
  while(!q.empty())
  {
      int u = q.front();
      q.pop();
      for(auto &k : g[u])
           {
               if(!vis[k])
               {
                   s[k] = u;
                   vis[k] = 1;
                   q.push(k);
               }
           }
  }
  

          
    cout << "Yes\n";
    for(int i = 2 ; i <= n ; i++)
         cout << s[i] << '\n';
  
  
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

vector<int> G[2000];
vector<P> edge;
int d[2000], vs[15][2000], dis[2000][2000];
int n, k;
void dfs(int v, int p, int dep){
	d[v] = dep;
	vs[0][v] = p;
	rep(i,G[v].size())if(G[v][i] != p){
		dfs(G[v][i], v, dep+1);
	}
}

void make_table(){
	rrep(i,14)rep(j,n){
		if(vs[i-1][j] == -1)vs[i][j] = -1;
		else vs[i][j] = vs[i-1][vs[i-1][j]];
	}
}

int lca(int u, int v){
	if(d[u] > d[v])swap(u, v);
	int dd = d[v]-d[u];
	//printf("%lld ", dd);
	rep(i,15)if(dd & (1<<i))v = vs[i][v];
	if(v == u)return v;
	drep(i,14,0){
		if(vs[i][u] == -1)continue;
		if(vs[i][u] != vs[i][v]){u = vs[i][u];v = vs[i][v];}
	}
	return vs[0][v];
}

signed main(){
	scanf("%lld%lld", &n, &k);
	rep(i,n-1){
		int x, y;
		scanf("%lld%lld", &x, &y);x--;y--;
		G[x].pb(y);G[y].pb(x);
		edge.pb(P(x, y));
	}
	dfs(0, -1, 0);
	make_table();
	rep(i,n)rep(j,n){
		int p = lca(i, j);
		dis[i][j] = d[i]+d[j]-2*d[p];
	}
	
	int ans = INF;
	if(k%2 == 1){
		rep(i,edge.size()){
			int u = edge[i].fi, v = edge[i].se, res = 0;
			rep(j,n){
				res += min(dis[u][j], dis[v][j]) > k/2;
			}
			chmin(ans, res);
		}
	}else{
		rep(i,n){
			int res = 0;
			rep(j,n)if(dis[i][j] > k/2)res++;
			chmin(ans, res);
		}
	}
	
	printf("%lld\n", ans);
	/*rep(i,n){
		rep(j,n)printf("%lld ", dis[i][j]);
		printf("\n");
	}*/
	//rep(i,n)printf("%lld ", vs[0][i]);
	return 0;
}







Measured memory_bytes: 32000
import java.io.*;
import java.util.*;

public class Main {

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null; }
        String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try { tokenizer = new StringTokenizer(reader.readLine()); } 
                catch (IOException e) { throw new RuntimeException(e);} }
            return tokenizer.nextToken(); }
        public int nextInt() { return Integer.parseInt(next()); }
        public long nextLong() { return Long.parseLong(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
    }

    static InputReader r = new InputReader(System.in);
    static PrintWriter pw = new PrintWriter(System.out);

    public static void main(String[] args) {
        
        long a = r.nextLong();
        long b = r.nextLong();

        pw.println(factors(gcd(a, b)));

        pw.close();
    }

    static long factors(long n){
        HashSet<Long> factors = new HashSet<Long>();
        factors.add(1L);
        if(n % 2 == 0){
            factors.add(2L);
            while(n % 2 == 0){
                n /= 2;
            }
        }
        for(int i = 3; i <= Math.sqrt(n); i += 2){
            if(n % i == 0){
                factors.add((long)i);
                while(n % i == 0){
                    n /= i;
                }
            }
        }
        if(!factors.contains(n)){
            factors.add(n);
        }
        return factors.size();
    }

    static long gcd(long a, long b){
        if(b == 0){
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

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

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

using namespace std;

void solve()
{
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cout << ((i <= b) ^ (j <= a));
        }
        cout << '\n';
    }
}

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


Measured memory_bytes: 1280
n = int(input())

def F(A, B):
    if len(str(A)) > len(str(B)):
        return len(str(A))
    else:
        return len(str(B))
ans = float('inf')

for a in range(1,int(n**.5)+1):
    if n%a==0:
        b = n // a
        tmp = F(a, b)
        if ans > tmp:
            ans = tmp
print(ans)

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

int main(){
  int x, m1=0, m2=0, m3=0;

  for (int i=0; i<10; i++){
    cin >> x;
    if (x>m1){
      m3=m2; m2=m1; m1=x;
    } else if (x>m2){
      m3=m2; m2=x;
    } else if (x>m3){
      m3=x;
    }
  }

  cout << m1 << endl << m2 << endl << m3 << endl;

  return 0;
}

Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
const int maxn=1e5+2;
int x[maxn],m,n,qwq;
 bool cmp(int ma,int w){
	return fabs(ma-qwq)<fabs(w-qwq);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+n);
	m=x[n];
	qwq=m/2;

	if(m%2!=0)qwq++;

	sort(x+1,x+n,cmp);
	
	printf("%d %d\n",m,x[1]);
}
 


Measured memory_bytes: 640
import math
ary1 = [int(input()) for x in range(5)]
x1 = sum(10*math.ceil(x/10) for x in ary1)
x2 = max([10-(y % 10) if y % 10 !=0 else 0 for y in ary1 ])
ans = x1 - x2
print(ans)


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

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);



int N, M;
int m[15];
int p[15];
vector<vector<int>> g(15); // switch: bulb

int main() {
    int k, s;

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> s;
            g[s-1].pb(i);
        }
    }

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

    int count = 0;
    for (int i = 0; i < 1 << N; i++) {
        Fill(m,0);
        for (int j = 0; j < N; j++) {
            if (i & 1 << j) {
                for (int b : g[j]) {
                    m[b]++;
                }
            }
        }

        count++;
        for (int j = 0; j < M; j++) {
            if (m[j] % 2 != p[j]) {
                count--;
                break;
            }
        }
    }

    cout << count << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
S = input()
ans = ''

for m in S:
    ans += chr((ord(m) - 65 + N) % 26 + 65)

print(ans)


Measured memory_bytes: 9132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
操作の逆順を考える
Codeforcesではscanfを使う
 */
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
    vector <ll> bk;

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL), bk(sz_) {
        for (ll i = 0; i < sz_; ++i){
          par[i] = i; // 初期では親は自分自身
          bk[i] = 0;
        }
    }
    void init(ll sz_) {
        siz.assign(sz_, 1LL);  // assign: 再代入
        par.resize(sz_);  // resize: 再確保
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        bk[x]+=bk[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }

    void bkp(ll x){
        bk[root(x)]++;
    }

    ll bkn(ll x){
        return bk[root(x)];
    }
};
int main() {
    int h,w;
    cin >> h >> w;
    char c[h][w];
  	UnionFind tree(h*w);
    rep(i,h){
        rep(j,w){
          cin >> c[i][j];
          if(c[i][j]=='#')tree.bkp(i*w+j);
        }
    }
    rep(i,h){
        rep(j,w){
            rep(k,4){
                if(0<=i+dx[k] && i+dx[k]<h && 0<=j+dy[k] && j+dy[k]<w){
                    if(c[i][j]!=c[i+dx[k]][j+dy[k]])tree.merge(i*w+j,(i+dx[k])*w+j+dy[k]);
                }
            }
        }
    }
    bool visited[h*w]={};
    ll sum=0;
    rep(i,h){
        rep(j,w){
          	if(!visited[tree.root(i*w+j)]){
              	visited[tree.root(i*w+j)]=true;
                ll bl=tree.bkn(i*w+j);
               	ll sai=tree.size(i*w+j);
               	sum+=bl*(sai-bl);
            }
        }
    }
    cout << sum;

}

/*



 */



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll N;
    cin >> N;
    deque<ll> color;
    rep(i, 0, N){
        ll a; cin >> a;
        auto itr = lower_bound(color.begin(), color.end(), a);
        if(color.begin() == itr){
            color.push_front(a);
        }else{
            *(itr-1) = a;
        }
    }
    cout << color.size() << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  vector<int> H(N);
  rep(i, N) {
    cin >> H[i];
  }

  vector<bool> good(N, true);
  int a, b;
  rep(i, M) {
    cin >> a >> b;
    a--;
    b--;
    if (H[a] > H[b]) good[b] = false;
    else if (H[a] < H[b]) good[a] = false;
    else {
      good[a] = false;
      good[b] = false;
    }
  }

  int count = 0;
  rep(i, N) {
    if (good[i]) count++;
  }

  cout << count << endl;

  return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(){
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	cout << max(A*B, C*D) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  while(true){
    c -= b;
    if (c < 1){
      cout << "Yes" << endl;
      break;
    }
    a -= d;
    if (a < 1){
      cout << "No" << endl;
      break;
    }
  }
}

Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    from collections import defaultdict
    def check(k):
        D=defaultdict(lambda :-1)
        for i in range(n-k+1):
            hash=rh[i:i+k]
            if(D[hash]!=-1):
                if(i-D[hash]>=k): return True
            else:
                D[hash]=i
        return False

    for k in range(n):
        if(not check(k)):
            print(max(0,k-1))
            return
resolve()

Measured memory_bytes: 68700
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
 
using namespace std;



int MOD=1000000007;
int main(void){
	string s,t,u;
	cin >> s >> t;
	int a,b;
	cin >> a >> b >> u;
	if(u==s) a-=1;
	if(u==t) b-=1;
	cout << a << " " << b << endl;

}


Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    val Array(a, b) = sc.nextLine.split(" ").map(_.toInt)
    if (a % 3 == 0 | b % 3 == 0 | (a + b) % 3 == 0) println("Possible")
    else println("Impossible")
  }
}


Measured memory_bytes: 25916
#include<stdio.h>
#include<stdlib.h>
#pragma warning (disable:4996)

int main() {
	int N= 0;
	int f = 9;
	bool correct = 0;
	scanf("%d", &N);
	if (N <= 100 && N >= 1) {
		while (f > 0) {
			if (N % f == 0) {
				if (N / f <= 9) {
					correct=1;
					break;
				}
				else f -= 1;
			}
			else f -= 1;
		}
	}
	if (correct == 0) printf("No");
	else if (correct == 1) printf("Yes");
	
	return 0;
}

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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);++i)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);--i)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld=long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
	ll to, rev;
    long double cap;
	Edge(ll _to, long double _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, long double cap, bool revFlag, long double revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

void solve(){
	ll h,w,k;
	cin>>h>>w>>k;
	ll sx,sy,gx,gy;
	cin>>sy>>sx>>gy>>gx;
	sx--;sy--;gx--;gy--;
	vec<vvec<pair<int,int>>> dp(h,vvec<pair<int,int>>(w,vec<pair<int,int>>(4,{-1,-1})));

	vec<string> s(h);
	REP(i,h) cin>>s[i];

	priority_queue<tuple<int,int,int,int,int>,vec<tuple<int,int,int,int,int>>,greater<tuple<int,int,int,int,int>>> que;//cost,d,v,i,j
	que.push(make_tuple(0,0,-1,sy,sx));

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

	while(que.size()){
		auto [cost,d,v,i,j]=que.top();que.pop();
		//cout<<i<<" "<<j<<" "<<v<<en;
		if(v!=-1 and dp[i][j][v].first!=-1 and cost>dp[i][j][v].first) continue;
		REP(m,4){
			int ni=i+dy[m];
			int nj=j+dx[m];
			//cout<<ni<<" "<<nj<<" "<<m<<en;
			if(ni<0 or ni>=h or nj<0 or nj>=w) continue;
			if(s[ni][nj] == '@')continue;
			if(v==m and k>d){
				if(dp[ni][nj][m].first != -1 and dp[ni][nj][m] <= make_pair(cost,d+1)) continue;
				dp[ni][nj][m] = make_pair(cost,d+1);
				que.push(make_tuple(cost,d+1,m,ni,nj));
			}else{
				//cout<<ni<<" "<<nj<<en;
				if(dp[ni][nj][m].first != -1 and dp[ni][nj][m] <= make_pair(cost+1,1)) continue;
				dp[ni][nj][m] = make_pair(cost+1,1);
				que.push(make_tuple(cost+1,1,m,ni,nj));
			}
		}
	}


	int ans=INT_MAX;
	REP(i,4){
		//cout<<gy<<" "<<gx<<" "<<i<<en;
		if(dp[gy][gx][i].first!=-1) chmin(ans,dp[gy][gx][i].first);
	}

	cout<<(ans==INT_MAX?-1:ans)<<en;

}

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

	solve();
	//ll t;cin>>t;REP(i,t) solve();

    return 0;
}


Measured memory_bytes: 143920
#include<stdio.h>
int main(){
	int n;
	double gai;
	scanf("%d",&n);
	if(n==1){
		printf("1.0000000000");
		return 0;
	}
	if(n%2==1){
		gai=(double)(n/2+1)/n;
	}
	else{
		gai=1/2.0;
	}
	printf("%.10lf\n",gai);
return 0;
}

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int k;
  cin >> k;
  for(int i=0;i<k;++i){
    if(c<=b || c<=a) c=c*2;
    else if(c>a && c>b && b<=a)b=b*2;
    else c=c*2;
  }
  if(b>a && c>b) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

int main()
{
    int a,b,i,j;
    scanf("%d%d",&a,&b);
    int  sz[a+2][b+2];
    char qwe[a+2][b+2];
    for(i=0;i<b+2;i++)
    {
        sz[0][i]=0;
        sz[a+1][i]=0;
    }
    for(i=0;i<a+2;i++)
    {
        sz[i][0]=0;
        sz[i][a+1]=0;
    }
    getchar();
    for(i=1;i<a+1;i++)
    {
        for(j=1;j<b+1;j++)
        {
            scanf("%c",&qwe[i][j]);
            if(qwe[i][j]=='#')
                sz[i][j]=1;
            else
                sz[i][j]=0;
        }
        getchar();
    }
    int cnt=1;
    for(i=1;i<a+1;i++)
    {
        for(j=1;j<b+1;j++)
        {
            if(sz[i][j]==1)
            {
                if(sz[i-1][j]==0&&sz[i+1][j]==0&&sz[i][j-1]==0&&sz[i][j+1]==0)
                   {
                       printf("No\n");
                       cnt=0;
                      break;
                   }

            }
        }
        if(cnt==0)
            break;
    }
    if(cnt)
        printf("Yes\n");
    return 0;
}


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

#define int long long
#define counter(m)     for(int i=0;i<m;i++)
#define gcd            __gcd
#define endl           "\n"
#define pb             emplace_back
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x, y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;

int32_t main() {
    nitin;
    string s;
    cin>>s;
    vector<int>v(26,0);
    for(auto c:s)
        v[c-'a']++;
    int cnt=0;
    for(auto c:v)
        if(c!=0)
            cnt++;
        if(cnt==1)
        {
            cout<<0<<endl;
            return 0;
        }
    int n=s.length();
    int ans=n-1;
    for(int i=n-1;i>=1;i--)
    {
        char op1=s[i];
        char op2=s[i-1];
        //op1
        vector<int>a;
        a.push_back(-1);
        for(int j=0;j<=i;j++)
        {
            if(s[j]==op1)
                a.push_back(j);
        }
        vector<int>b;
        b.push_back(-1);
        for(int j=0;j<i;j++)
        {
            if(s[j]==op2)
            {
                b.push_back(j);
            }
        }
        int temp=INT_MIN;
        for(int j=1;j<a.size();j++)
        {
            temp=max(temp,a[j]-a[j-1]-1);
        }
        int ntemp=INT_MIN;
        for(int j=1;j<b.size();j++)
        {
            ntemp=max(ntemp,b[j]-b[j-1]-1);
        }
        ans=min(ans,max(min(ntemp,temp),n-i));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>

int main()
{
    int n, i, j, sum=0;
    scanf("%d",&n);
    int a[n];
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            sum += a[i]*a[j];
        }
    }
    printf("%d\n", sum);
    return 0;
}


Measured memory_bytes: 128
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;


int gcd(int p, int q)
{
    return q==0?p:gcd(q,p%q);
}
int main() {
   int n,m;
   scanf("%d%d",&n,&m);
   printf("%d\n",n*n-m);
    return 0;
}



Measured memory_bytes: 256
n = int(input())
ans = ''
for i in range(1, 99):
  if n <= 26 ** i:
    n  -= 1
    for j in range(i):
      ans += chr(ord('a') + n % 26)
      n //= 26
    break
  else:
    n -= 26 ** i
print(ans[::-1])

Measured memory_bytes: 9184
def main():
    sx, sy, tx, ty = map(int, input().split())
    print(
        ''.join(
            [
                'U' * (ty - sy),
                'R' * (tx - sx),
                'D' * (ty - sy),
                'L' * (tx - sx + 1),
                'U' * (ty - sy + 1),
                'R' * (tx - sx + 1),
                'D',
                'R',
                'D' * (ty - sy + 1),
                'L' * (tx - sx + 1),
                'U'
            ]
        )
    )


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long int ll;

//define
#define INF 1e9 
#define NUM 1000000007
#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string s;
	cin >> s;
	rep(i, s.size()) {
		if (i == 4) {
			cout << " ";
		}
		cout << s[i];
	}
	cout << "\n";
	

	return 0;
	
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100001], b[100001], cnt[100001];
int main() {
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
		cnt[a[i]]++;
		cnt[b[i] + 1]--;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		cnt[i] += cnt[i - 1];
		if(cnt[i] == m){
			ans++;
		}
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 1408
import math


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


q = int(input())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_cnt = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 1])

Measured memory_bytes: 18148
N = int(input())
p = [[] for _ in range(N)]
for i in range(N):
    p[i] = int(input())
    
max=0
sum=0
for i in range(N):
    sum += p[i]
    if p[i]>max:
        max = p[i]

print(int(sum-max/2))

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char *argv[])
{
  int H, i;
  int *node;
  int parent, left, right;
 
  scanf("%d", &H);
  node = (int *)malloc(sizeof(int) * (H + 1));
  for (i = 1; i <= H; i++) scanf("%d", &node[i]);
 
  for (i = 1; i <= H; i++) {
    printf("node %d: key = %d, ", i, node[i]);
    parent = (int)floor(i/2.0);
    left = 2 * i;
    right = 2 * i + 1;
    if (1 <= parent && parent <= H) printf("parent key = %d, ", node[parent]);
    if (1 <= left && left <= H) printf("left key = %d, ", node[left]);
    if (1 <= right && right <= H) printf("right key = %d, ", node[right]);
    printf("\n");
  }
 
  return 0;
}



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

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);	
    char s; cin >> s;
    if(isupper(s)) {
        cout << 'A';
        return 0;
    }
    cout << 'a';
    return 0;
} 
 


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

using Vertex = int;
using Weight = long long;

struct Edge{
    Vertex from, to;
};

struct VW{
    Vertex v;
    Weight w;
};

struct Tree{
    int nV;
    Vertex root;
    vector<Edge> edges;
    vector<vector<Vertex>> adj;
    vector<Vertex> parent;
    vector<int> subtree_size;
    void add_edge(Vertex a, Vertex b){
        edges.push_back(Edge{a, b});
    }
    void build(Vertex _root = 0){
        root = _root;
        nV = 0;
        for (auto edge : edges) nV = max(nV, max(edge.from, edge.to));
        adj.resize(++nV);
        parent.assign(nV, 0);
        subtree_size.assign(nV, 0);
        for (auto edge : edges){
            adj[edge.from].push_back(edge.to);
            adj[edge.to].push_back(edge.from);
        }
        dfs(root);
    }
    int dfs(Vertex v){
        subtree_size[v] = 1;
        for (auto u : adj[v]) {
            if (subtree_size[u] == 0) {
                subtree_size[v] += dfs(u);
                parent[u] = v;
            }
        }
        return subtree_size[v];
    }
};

class Centroid{
    const Tree &t;
public:
    Centroid(const Tree &_t): t(_t){}
    vector<Vertex> find(){
        vector<Vertex> centroids;
        for (Vertex v = 0; v != t.nV; ++v) {
            bool is_centroid = true;
            for (auto u : t.adj[v]){
                if ((u == t.parent[v] ? t.nV - t.subtree_size[v] : t.subtree_size[u]) > t.nV/2) is_centroid = false;
            }
            if (is_centroid) centroids.push_back(v);
        }
        return centroids;
    }
};

long long calc_upper_bound(const Tree &t, const vector<vector<VW>> &costs){
    long long ret = 0;
    auto nV = t.nV;
    for (Vertex u = 0; u != nV; ++u){
        for (const auto &vw : costs[u]){
            if (vw.v == t.parent[u]){
                ret += vw.w * min(t.subtree_size[u], nV - t.subtree_size[u]);
            }else{
                ret += vw.w * min(t.subtree_size[vw.v], nV - t.subtree_size[vw.v]);
            }
        }
    }
    return ret;
}


int main(){
    int N;
    cin >> N;
    vector<vector<VW>> costs(N, vector<VW>());
    Tree tree;
    for (int m = 1; m != N; ++m){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        costs[--a].push_back(VW{--b, c});
        costs[b].push_back(VW{a, c});
        tree.add_edge(a, b);
    }
    tree.build();
    auto upper_bound = calc_upper_bound(tree, costs);
    Centroid cntr(tree);
    auto cntrs = cntr.find();
    if (cntrs.size() == 1){
        long long min_cost = 1e9;
        for (const auto &vw : costs[cntrs[0]]){
            min_cost = min(min_cost, vw.w);
        }
        cout << upper_bound - min_cost << endl;
    }else{
        for (const auto & vw : costs[cntrs[0]]){
            if (vw.v == cntrs[1]){
                cout << upper_bound - vw.w << endl;
                break;
            }
        }
    }
    return 0;
}

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

int main() {
    int S;
    cin >> S;
    int h = S / 3600;
    int m = (S - h * 3600) / 60;
    int s = (S - h * 3600) - m * 60;
    cout << h << ':' << m << ':' << s << endl;
    return 0;
}

Measured memory_bytes: 3088
using System;
using System.Collections.Generic;

public class AtCoderB
{
    static void Main()
    {
        int n;
        int x;
        {
            var line = Console.ReadLine();
            var words = line.Split(' ');
            n = int.Parse(words[0]);
            x = int.Parse(words[1]);
        }

        int answer = 0;
        int oldD = 0;
        {
            var line = Console.ReadLine();
            var words = line.Split(' ');
            if (oldD <= x)
            {
                answer++;
            }
            for (int i = 0; i < n; i++)
            {   
                oldD = oldD + int.Parse(words[i]);
                if (oldD <= x)
                {
                    answer++;
                }
            }
        }

        Console.WriteLine(answer);
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <fstream>
#include <set>
#include <stack>
#include <queue>
#include <list>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
int64 q, n;

void solve(){

    return;
}


int main(){
    string s;
    string t;
    cin >> s >> t;
    int64 rs = 0;
    for (int i = 0; i < s.size(); i++){
        if (s[i] != t[i]){
            rs++;
        }
    }
    ctn(rs);
    return 0;
}



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

using namespace std;

#define FOR(i, s, n) for (size_t i = (s); i < (size_t)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

int main()
{
  int n;
  cin >> n;
  auto a = vector<int>(n);
  for (auto &x : a)
  {
    cin >> x;
  }
  auto sum = 0;
  REP(i, a.size())
  {
    if (i % 2 == 0 && a[i] % 2 == 1)
    {
      sum++;
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3592
X, N = map(int, input().split())
P = [int(x) for x in input().split()]

a = X
j = 0
for i in range(200):
    if P.count(a) == 0:
        print(a)
        break
    else:
        j += 1
        a = a - j
        if P.count(a) == 0:
            print(a)
            break
        else:
            j += 1
            a = a + j
            if P.count(a) == 0:
                print(a)
                break

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

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


int main() {
    double pi = 3.141592653589793;
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double Ax = a * std::cos(2*pi*(60*h+m)/720);
    double Ay = a * std::sin(2*pi*(60*h+m)/720);
    double Bx = b * std::cos(2*pi*m/60);
    double By = b * std::sin(2*pi*m/60);

    double ans = sqrt(std::pow(Ax-Bx, 2) + std::pow(Ay-By, 2));
    printf("%.10f\n", ans);
    return 0;
}

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

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	if (n == 1) {
		printf("Hello World\n");
	} else {
		int a, b; cin >> a >> b;
		cout << a + b << endl;
	}
	return 0;
}


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

int main()
{
vector<string> v(3);
cin >> v[0] >> v[1] >> v[2] ;
sort(v.begin(),v.end());
do{
bool a[v[0].size()+1000]={};
bool b[v[0].size()+1000]={};
bool c[v[1].size()+1000]={};
rep(i,v[0].size())rep(j,v[1].size())if(i+j<v[0].size()&&v[0][i+j]!='?'&&v[1][j]!='?'&&v[0][i+j]!=v[1][j]){a[i]=1;break;}
rep(i,v[0].size())rep(j,v[2].size())if(i+j<v[0].size()&&v[0][i+j]!='?'&&v[2][j]!='?'&&v[0][i+j]!=v[2][j]){b[i]=1;break;}
rep(i,v[1].size())rep(j,v[2].size())if(i+j<v[1].size()&&v[1][i+j]!='?'&&v[2][j]!='?'&&v[1][i+j]!=v[2][j]){c[i]=1;break;}
rep(i,v[0].size()+1000)rep(j,v[1].size()+1000){
  if(!a[i]&&(i+j>v[0].size()||!b[i+j])&&!c[j])ans=min(ans,max({(ll)v[0].size(),(ll)v[1].size()+i,(ll)v[2].size()+i+j}));
}
}while(next_permutation(v.begin(),v.end()));
cout << ans << endl;
return 0;
}


Measured memory_bytes: 384
n, m, x = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(n)]

# rについて表裏のすべての組み合わせを調べる。
ans = 10 ** 19
for b in range(2 ** n):
  aa = [0] * m
  amn = 0
  for i in range(n):
    if (b >> i) & 1:
      amn += CA[i][0]
      for k in range(m):
        aa[k] += CA[i][k + 1]
  if all(a >= x for a in aa):
    ans = min(ans, amn)  

if ans == (10 ** 19):
  print(-1)
else:
  print(ans)


Measured memory_bytes: 9216
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()

int main() {
	int n;
	for (int i = 1; cin >> n && n != 0; ++i)
		cout << "Case " << i << ": " << n << endl;

	return 0;
}


Measured memory_bytes: 3072
function main()
  
  N = parse(Int,readline())
  
  dict = Dict('M' => 0, 'A' => 0, 'R' => 0, 'C' => 0, 'H' => 0)
  
  for i in 1:N
    S = readline()
    if haskey(dict,S[1])
      dict[S[1]] += 1
    end
  end
  
  values = [dict['M'], dict['A'], dict['R'], dict['C'], dict['H']]
  
  ans = 0
  
  for i in 1:5, j in i+1:5, k in j+1:5
    ans += values[i]*values[j]*values[k]
  end
  
  println(ans)
  
end

main()

Measured memory_bytes: 125700
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<string> ss(n);
  FOR(s,ss) {
    cin >> s;
  }
  int begin_b = 0;
  int end_a = 0;
  int both = 0;
  FOR(s,ss) {
    if (s[0] == 'B') {
      if (s.back() == 'A') {
        both++;
      } else {
        begin_b++;
      }
    } else if (s.back() == 'A') {
      end_a++;
    }
  }
  int ans = 0;
  if (both > 0) {
    ans += both - 1;
    if (end_a > 0) {
      ans += 1;
      end_a--;
    }
    if (begin_b > 0) {
      ans += 1;
      begin_b--;
    }
  }
  ans += min(begin_b, end_a);
  FOR(s,ss) {
    REP(i,0,s.size()-1) {
      if (s[i] == 'A' && s[i+1] == 'B') {
        ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 768
import os
import sys

import numpy as np
from heapq import heappop, heappush, heapify


def solve(inp):
    def fenwick_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(arr, n, log_n, x):
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    def bit_length(x):
        res = 0
        while x:
            res += 1
            x >>= 1
        return res

    h = inp[0]
    w = inp[1]
    aaa = inp[2::2]
    bbb = inp[3::2]

    w1 = w + 1
    log_w = bit_length(w1)
    arr = np.zeros(w1 + 1, dtype=np.int64)
    for j in range(1, w1):
        arr[j] = j & -j
    fenwick_add(arr, w1, w1, 10 ** 18)
    horizontal = np.zeros(w + 1, dtype=np.int64)
    horizontal_rev = np.arange(w + 1, dtype=np.int64)
    q = [(0, j) for j in range(1, w + 1)]
    heapify(q)

    ans = np.full(h, -1, dtype=np.int64)

    for row in range(h):
        a = aaa[row]
        b = bbb[row]
        k = 1 if a == 1 else fenwick_sum(arr, a - 1) + 1
        c = fenwick_lower_bound(arr, w1, log_w, k)
        stack = []
        while c <= b + 1:
            stack.append(c)
            if c == w1:
                break
            k += 1
            c = fenwick_lower_bound(arr, w1, log_w, k)
        # print(a, b, k, c, horizontal, stack)

        if len(stack) == 0:
            ans[row] = row + q[0][0] + 1
            continue

        if stack[-1] == w1:
            found_nearest = True
            stack.pop()
        else:
            found_nearest = False
        stack.reverse()

        for c in stack:
            if found_nearest:
                fenwick_add(arr, w1, c, -1)
                horizontal[horizontal_rev[c]] = -1
            elif c == b + 1:
                found_nearest = True
            else:
                orig = horizontal_rev[c]
                horizontal[orig] = b + 1 - orig
                horizontal_rev[b + 1] = orig
                fenwick_add(arr, w1, c, -1)
                fenwick_add(arr, w1, b + 1, 1)
                heappush(q, (horizontal[orig], orig))
                found_nearest = True

        while q and q[0][0] != horizontal[q[0][1]]:
            heappop(q)

        if len(q) == 0:
            break

        ans[row] = row + q[0][0] + 1

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))


Measured memory_bytes: 52152
#include<stdio.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

i64 gcd (i64 a, i64 b) {
  i64 r = a % b;
  while (r > 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

i64 calc (i64 a, i64 c, i64 d) {
  return a / c + a / d - a / (c * d / gcd (c, d));
}

void run (void) {
  i64 a, b, c, d;
  scanf ("%" SCNi64 "%" SCNi64 "%" SCNi64 "%" SCNi64, &a, &b, &c, &d);
  i64 ans = (b - a + 1) - (calc (b, c, d) - calc (a - 1, c, d));
  printf ("%" PRIi64 "\n", ans);
}

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


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int MOD = 1e9 + 7;

constexpr int MAX = 200020;
long fac[MAX], inv[MAX], finv[MAX];
void CombInit(){
  fac[0] = inv[0] = finv[0] = 1;
  fac[1] = inv[1] = finv[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 Comb(int n,int k){
  if(n < 0 || k < 0 || n < k) return 0;
  return (fac[n] * finv[n-k] % MOD) * finv[k] % MOD;
}

long h, w, n, r, c, dp[100010][2];
pair<int, int> wall[100010];

int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  cin >> h >> w >> n;
  for(int i = 0; i < n; ++i) {
    cin >> r >> c;
    wall[i] = {r, c};
  }
  // combの計算用にスタートとゴーるを設置
  wall[n] = {1, 1};
  wall[n+1] = {h, w};
  CombInit();

  sort(wall, wall+n+2);

  // 包除原理を使う。訪れた回数の偶奇のみ取れればよい。
  dp[0][0] = 1;
  for(int i = 0; i < n+2; ++i) {
    for(int j = 0; j < i; ++j) {
      // iとjが描く四角
      // 訪れる順番はj -> iとなる。
      long way = Comb(wall[i].first-wall[j].first+wall[i].second-wall[j].second, wall[i].first-wall[j].first);
      (dp[i][0] += dp[j][1] * way) %= MOD;
      (dp[i][1] += dp[j][0] * way) %= MOD;
    }
  }
  cout << (dp[n+1][1] - dp[n+1][0] + MOD) % MOD;
  return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define int long long int
signed main() 
{
          int A,B,N;
          cin>>A>>B>>N;
          if(N>=B)
          {
                    int ans=(A*(B-1))/B;
                    cout<<ans<<"\n";
          }
          else
          {
                   int ans=((A*N)/B);
                    
                    cout<<ans<<"\n";      
          }

}


Measured memory_bytes: 3632
#include <stdio.h>

void Leap_Year(int start_year, int end_year)
{
    while ((start_year != 0) || (end_year != 0)) {
        if ((end_year - start_year >= 0) && (end_year - start_year < 4)) {
            if (((start_year % 4 == 0) && (start_year % 100 != 0)) || (start_year % 400 == 0)) {
                printf("%d\n", start_year);
            } else if (start_year % 4 < end_year % 4) {
                printf("NA\n");
            } else {
                if (start_year % 100 < end_year % 100) {
                    printf("%d\n", start_year + 4 - start_year % 4);
                } else if (start_year % 400 > start_year % 400) {
                    printf("%d\n", start_year + 4 - start_year % 4);
                } else {
                    printf("NA\n");
                }
            }
        } else {
            for (int i = start_year; i <= end_year; ++i) {
                if (i % 400 != 0) {
                    if ((i % 100 != 0) && (i % 4 == 0)) {
                        printf("%d\n", i);
                    }
                } else {
                    printf("%d\n", i);
                }
            }
        }
        scanf("%d %d", &start_year, &end_year);
        if ((start_year != 0) || (end_year != 0)) {
            printf("\n");
        }
    }
}

int main(void)
{
    
    int start_year, end_year;
    scanf("%d %d", &start_year, &end_year);
    Leap_Year(start_year, end_year);
    return 0;
}

Measured memory_bytes: 1044
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=n;i>0;i--)
    {
        int res=sqrt(i);
        if((res*res)==i)
        {
            printf("%d\n",i);
        break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String tmp = br.readLine();
		
		int n = Integer.parseInt(tmp);
		
		long lucas[] = new long[n + 1];
		lucas[0] = 2;
		lucas[1] = 1;
		
		for(int i = 2; i <= n; i++){
			lucas[i] = lucas[i-1] + lucas[i-2];
		}
		
		System.out.println(lucas[n]);
	}

}


Measured memory_bytes: 21204