akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int m, k;
    cin >> m >> k;
    int num = 1;
    rep(i, m) num *= 2;
    if (k >= num)
    {
        cout << -1 << endl;
        return 0;
    }
    if (k == 0)
    {
        rep(i, num) cout << i << " " << i << " ";
        cout << endl;
        return 0;
    }
    if (m == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << k << " ";
    rep(i, num) if (i != k) cout << i << " ";
    cout << k << " ";
    repr(i, num - 1) if (i != k) cout << i << " ";
    cout << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int n;

i64 fact[101010];
i64 MOD = 1e9 + 7;

int main()
{
    fact[0] = 1;
    rep(i,1,101000)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    cin >> n;
    cout <<fact[n] << endl;
}

Measured memory_bytes: 1024
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define REP2(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = (l), i##_len = (int)(r); i < i##_len; ++i)
#define GET_MACRO_REP(_1, _2, _3, NAME, ...) NAME
#define REP(...) GET_MACRO_REP(__VA_ARGS__, REP3, REP2) (__VA_ARGS__)
#define RREP2(i, n) for (int i = (n - 1); i >= 0; --i)
#define RREP3(i, l, r) for (int i = (r - 1), i##_len = (l); i >= i##_len; --i)
#define GET_MACRO_RREP(_1, _2, _3, NAME, ...) NAME
#define RREP(...) GET_MACRO_REP(__VA_ARGS__, RREP3, RREP2) (__VA_ARGS__)
#define IN(type, n) type n; cin >> n
#define INALL(type, v) REP(i, v.size()) { IN(type, _tmp); v.at(i) = _tmp; }
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#ifdef _DEBUG
#define DEBUG(x) cout << #x << ": " << x << endl
#else
#define DEBUG(x)
#endif

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; }
#pragma endregion

int main() {
  IN(int, x);
  if (x == 0) x = 1;
  else x = 0;
  cout << x << endl;

  return 0;
}


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

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

bool isprime(ll X) {
    for (ll i = 2; i * i <= X; ++i) {
        if (X % i == 0) return false;
    }
    return true;
}

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

    while (!isprime(X)) {
        X++;
    }

    cout << X << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli > plli;
typedef vector<lli> vlli;
typedef vector<plli > vplli;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define lcm(a, b) ((a * b) / gcd(a, b))
#define sqr(x) (x)*(x)
#define all(a) a.begin(),a.end()
#define UN(v) sort(all(v)), v.resize(unique(all(v))-v.begin())

#define endl '\n'

const long long INF = 100000000000000000;
const long long MOD = 1000000007;
const long long MAXN = 100005;
const double PI = acos(-1);

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

lli gcd(lli a , lli b) {
    if(b == 0) return a;
    a %= b;
    return gcd(b,a);
}

void solve() {
    lli n;
    cin >> n;
    lli lo = 0, hi = n;

    lli ans = -1;
    while (lo <= hi) {
        lli mid = (lo + hi) / 2;
        lli x = mid * 1.08;
        if (x < n) {
            lo = mid + 1;
        } else if (x > n) {
            hi = mid - 1;
        } else {
            ans = mid;
            break;
        }
    }

    if (ans == -1) cout << ":(" << endl;
    else cout << ans << endl;
}

int main()
{
    IOS;
    //comment it out
    //freopen("input.txt", "r", stdin);
    lli t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n;
    cin >> n;
    ll a[n];
    rep(i, 0, n) cin >> a[i];
    ll ans = 0;
    rep(i, 0, 61) {
        ll sum1 = 0;
        rep(j, 0, n) {
            if (a[j] & (1LL << (ll)i)) sum1++;
        }
        ans += (((1LL << (ll)i) % MOD) * ((sum1 * (n - sum1)) % MOD)) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
def f(n):
	i=e=[1,0,0,1];z=[1,1,1,0]
	while n:e=[e,g(e,z)][n%2];z=g(z,z);n//=2
	return e[1]
M=998244353;g=lambda a,b:[(a[0]*b[0]+a[1]*b[2])%M,(a[0]*b[1]+a[1]*b[3])%M,(a[2]*b[0]+a[3]*b[2])%M,(a[2]*b[1]+a[3]*b[3])%M];n,m=map(int,input().split());I=[1,1];r=f(m+2*n-2);c=1
for i in range(2,n):I+=[(M-M//i)*I[M%i]%M]
for i in range(n-1):r=(r+c*(M-f(2*n-2-2*i)))%M;c=c*(m+i)*I[i+1]%M
print(r)

Measured memory_bytes: 52976
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int four = 0;
		int two = 0;
		int others = 0;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if (a % 4 == 0) {
				four++;
			} else if (a % 2 == 0) {
				two++;
			} else {
				others++;
			}
		}
		if ((two >= 2 && four >= others) ||
			(two == 0 && four >= others - 1) ||
			(four >= others + two - 1)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 49756
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <bitset>
#include <cmath>
#include <utility>
#define Maxn 100005
#define Maxm 1000005
#define lowbit(x) x&(-x)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PI acos(-1.0)
#define LL long long 
#define Inf (1LL<<62)
#define inf 0x3f3f3f3f
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
using namespace std;
const int mod=1e9+7;
int main()
{
	//input;output;
	int arr[Maxn],n;
	LL a,b;
	while(~scanf("%d",&n))
	{
		a=-1;b=-1;
		for(int i=0;i<n;i++)
			scanf("%d",arr+i);
		sort(arr,arr+n);
		for(int i=n-1;i>=0;i--)
		{
			if(arr[i]==arr[i-1])
			{
				if(a==-1)
				{
					a=arr[i];
					i--;
					continue;
				}
				if(a!=-1&&b==-1)
				{
					b=arr[i];
					break;
				}
			}
		}
		if(a!=-1&&b!=-1)
			cout<<a*b<<endl;
		else
			cout<<0<<endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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


#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/

// vector
template <typename T>
istream & operator>>(istream & is, vector<T> & vec) {
	for (T& x : vec) is >> x;
	return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
	os << "(" << pair_var.first << ", " << pair_var.second << ")";
	return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
	os << "{";
	for (int i = 0; i < vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
	}
	os << "}";
	return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
	os << "{";
	repi(itr, map_var) {
		os << *itr;
		itr++;
		if (itr != map_var.end()) os << ", ";
		itr--;
	}
	os << "}";
	return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
	os << "{";
	repi(itr, set_var) {
		os << *itr;
		itr++;
		if (itr != set_var.end()) os << ", ";
		itr--;
	}
	os << "}";
	return os;
}

#define DUMPOUT cerr

void dump_func() {
	DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
	DUMPOUT << head;
	if (sizeof...(Tail) > 0) {
		DUMPOUT << ", ";
	}
	dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif



signed main() {
	string S;
	cin >> S;
	int ans = 0;
	if (S == "SUN") ans = 7;
	if (S == "MON") ans = 6;
	if (S == "TUE") ans = 5;
	if (S == "WED") ans = 4;
	if (S == "THU") ans = 3;
	if (S == "FRI") ans = 2;
	if (S == "SAT") ans = 1;
	cout << ans << endl;

	

}

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



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

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    int n;cin>>n;
    vector<int> a(9);

    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x>=3200){
            a[8]++;
        }else{
            a[x/400]++;
        }
        
    }

    int c=0;

    for(int i=0;i<8;i++){
        if(a[i]){
            c++;
        }
    }

    if(c==0){
        cout<<"1 "<<a[8];
    }else{
        cout<<c<<" "<<c+a[8];
    }
    
}


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

#define fi first
#define se second

using namespace std;

typedef pair<int, int> ii;

int n, k, h[100005], dp[100005];

int recur(int d)
{
	if(d == n)
		return 0;
	else
	{
		int a = INT_MAX;
		for(int i = 1; i <= k; ++i)
			if(d + i <= n)
				a = min(abs(h[d + i] - h[d]) + recur(d + i), a);
		return a;
	}
}
int main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> h[i];
	memset(dp, 63, sizeof dp);
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	for(int i = 3; i <= n; ++i)
	{
		for(int j = 1; j <= k; ++j)
		{
			if(i - j >= 1)
				dp[i] = min(abs(h[i] - h[i - j]) + dp[i - j], dp[i]);
		}
	}
	cout << dp[n];
	return 0;
}

Measured memory_bytes: 1024
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let n = read::<usize>();
    let a = read_vec::<usize>();
    let diff = a.iter().max().unwrap() - a.iter().min().unwrap();
    if diff >= 2 {
        println!("No");
        return;
    }
    if diff == 0 {
        if a[0] == n - 1 {
            println!("Yes");
            return;
        } else if n / a[0] >= 2 {
            println!("Yes");
            return;
        }
        println!("No");
        return;
    }
    let mut solo_count = 0;
    let min_num = *a.iter().min().unwrap();
    for &num in a.iter() {
        if num == min_num {
            solo_count += 1;
        }
    }
    let multi_count = a.iter().max().unwrap() - solo_count;
    if multi_count >= 1 && (n - solo_count) / multi_count >= 2 {
        println!("Yes");
        return;
    } else {
        println!("No");
        return;
    }
}


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

int main(){
  long long N, K;
  cin >> N >> K;
  long long ans=0;
  if(N-K==1) ans=1;
  else if(K==0) ans=N*N;
  else{
    for(int i=K+1; i<=N; i++){
      ans+=(N/i)*(i-K);
      if(N-N/i*i>=K) ans+=N-N/i*i-K+1;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
list = []
c = 1
for i in range(2, 1001):
	list.append(c)
	c += i
a, b = map(int,raw_input().split())
c = b - a
for i in range(1, 999):
	if list[i]-list[i-1] == c:
		ans = list[i] - b
print ans

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

struct edge { int to, cost; };

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

class UnionFind{
private:
	vector<int> par; //�e
	vector<int> sz; //�f�[�^�̐�

public:
	UnionFind(int n){ 
		par = vector<int>(n);
		sz = vector<int>(n);
		for(int i = 0; i < n; i++){
			par[i] = i;
			sz[i] = 1;
		}
	}
	//�؂̍������߂�
	int find(int x){
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	//x��y�̑�����W���𕹍�
	void unite(int x,int y){
		x = find(x); //x,y�͊e�f�[�^�̍��m�[�h�𓾂�
		y = find(y);
		if(x == y) return;
		if (sz[x] < sz[y]) swap(x,y);
		par[y] = x; //x��y�̐e�ƂȂ�悤�ɘA������
		sz[x] += sz[y];
	}
	//x��y�������W���ɑ����邩�ۂ�
	bool same(int x, int y){
		return find(x) == find(y);
	}
	//x��������W���̃f�[�^��
	int size(int x){
		return sz[find(x)];
	}
};

int main()
{
	int n,k,l;
	cin >> n >> k >> l;
	UnionFind uni1(n+10),uni2(n+10);
	for(int i = 0; i < k; i++){
		int p,q;
		cin >> p >> q;
		uni1.unite(p,q);
	}
	for(int i = 0; i < l; i++){
		int r,s;
		cin >> r >> s;
		uni2.unite(r,s);
	}
	map<P,int> mp;
	for(int i = 1; i <= n; i++){
		mp[make_pair(uni1.find(i),uni2.find(i))]++;
	}
	for(int i = 1; i <= n; i++){
		cout << mp[make_pair(uni1.find(i),uni2.find(i))] << ' ';
	}
	cout << endl;
	return 0;	
}

Measured memory_bytes: 15104
#include <iostream>

using namespace std;

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

    int A[N];
    int GPA[4001]{};

    int a, c;
    char b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        a = a * 1000 + c;
        A[i] = a;
        GPA[a]++;
    }

    for (int i = 1; i <= 4000; i++) {
        GPA[i] += GPA[i - 1];
    }

    int p;
    for (int i = 0; i < N; i++) {
        if (A[i] == 0) {
            p = GPA[A[i]] - 1;
        } else {
            p = GPA[A[i] - 1] * 3;
            p += GPA[A[i]] - GPA[A[i] - 1] - 1;
        }
        cout << p << endl;
    }
}


Measured memory_bytes: 3436
#include<stdio.h>
int main() {
	long long N, K, a, b, ans;
	scanf("%lld%lld", &N, &K);
	a = N / K;
	ans = a * a * a;
	if (K % 2 == 0)
	{
		b = N / (K / 2) - a;
		ans += b*b*b;
	}
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 128
// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 1e18;
const ll MAX = 200008;
//
//

struct mi {
    ll v; explicit operator ll() const { return v; }
    mi() { v = 0; }
    mi(ll _v) { 
        v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
        if (v < 0) v += MOD;
    }
    friend bool operator==(const mi& a, const mi& b) { 
        return a.v == b.v; }
    friend bool operator!=(const mi& a, const mi& b) { 
        return !(a == b); }
    friend bool operator<(const mi& a, const mi& b) { 
        return a.v < b.v; }
   
    mi& operator+=(const mi& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    mi& operator-=(const mi& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    mi& operator*=(const mi& m) { 
        v = v*m.v%MOD; return *this; }
    mi& operator/=(const mi& m) { return (*this) *= inv(m); }
    friend mi pow(mi a, ll p) {
        mi ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mi inv(const mi& a) { assert(a.v != 0); 
        return pow(a,MOD-2); }
        
    mi operator-() const { return mi(-v); }
    mi& operator++() { return *this += 1; }
    mi& operator--() { return *this -= 1; }
    mi operator++(int) { mi temp; temp.v = v++; return temp; }
    mi operator--(int) { mi temp; temp.v = v--; return temp; }
    friend mi operator+(mi a, const mi& b) { return a += b; }
    friend mi operator-(mi a, const mi& b) { return a -= b; }
    friend mi operator*(mi a, const mi& b) { return a *= b; }
    friend mi operator/(mi a, const mi& b) { return a /= b; }
    friend ostream& operator<<(ostream& os, const mi& m) {
        os << m.v; return os;
    }
    friend istream& operator>>(istream& is, mi& m) {
        ll x; is >> x;
        m.v = x;
        return is;
    }
};

typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;
mi facs[MAX];
mi facInvs[MAX];
 
mi choose(mi _a, mi _b) {
    ll a = (ll) _a, b = (ll) _b;
    if (b > a) return 0;
    if (a < 0) return 0;
    if (b < 0) return 0;
    mi cur = facs[a];
    cur = cur * facInvs[b];
    cur = cur * facInvs[a-b];
    return cur;
}
 
void initFacs() {
    facs[0] = 1;
    facInvs[0] = 1;
    for(int i = 1; i < MAX; i++) {
        facs[i] = (facs[i-1] * i);
        facInvs[i] = inv(facs[i]);
    }
}

void solve(){
    ll n, m, k;
    cin>>n>>m>>k;
    initFacs();
    mi ans = 0;
    mi mm = m;
    for(int i = 0; i <= k; i++){
        ans += m*choose(n-1, i)*pow(1, k)*pow(mm-1, n-1-i);
    }
    cout<<ans;
}
int main(){ 
        hs;
        ll t;
        t=1;
        // cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}

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

template <typename T>
struct SegmentTree {
  using F = function<T(T, T)>;
  long n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree() {};
  SegmentTree(F f, T ti) : f(f), ti(ti) {}
  void init(long n_) {
    n = 1;
    while (n < n_) n <<= 1;
    dat.assign(n << 1, ti);
  }
  void build(const vector<T> &v) {
    long n_ = v.size();
    init(n_);
    for (long i = 0; i < n_; i++) dat[n + i] = v[i];
    for (long i = n - 1; i; i--) dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  void set_val(long k, T x) {
    dat[k += n] = x;
    while (k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
  }
  T query(long a, long b) {
    T vl = ti, vr = ti;
    for (long l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
  template<typename C>
  long find(long a, long b, C &check, long k, long l, long r) {
    if (!check(dat[k]) || r <= a || b <= l) return -1;
    if (k >= n) return k - n;
    long m = (l + r) >> 1;
    long vl = find(a, b, check, (k << 1) | 0, l, m);
    if (~vl) return vl;
    return find(a, b, check, (k << 1) | 1, m, r);
  }
  template<typename C>
  long find(long a, long b, C &check) {
    return find(a, b, check, 1, 0, n);
  }
};

int main() {
  long N;
  cin >> N;
  vector<long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);

  auto f = [&](long x, long y) {
    return __gcd(x, y);
  };
  SegmentTree<long> ST(f, 0);
  ST.build(A);

  long ans = 0;
  for (int i = 0; i < N; i++) {
    int L = ST.query(0, i);
    int R = ST.query(i + 1, N);
    ans = max(ans, f(L, R));
  }

  cout << ans << "\n";
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{   
    int a,b,c; cin>>a>>b>>c;
    cout<<min(c,a+b+1)+b<<endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline auto vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

int main()
{
    ll n=in(),k=-1;vector<ll>a(n),b(n),c(10001,0);
    for(ll i=0;i<n;++i){
        ++c[a[i]=in()];
        k=max(k,a[i]);
    }
    for(ll i=0;i<k;++i)c[i+1]+=c[i];
    for(ll i=n-1;i>=0;--i)b[--c[a[i]]]=a[i];
    for(ll i=0;i<n;++i){
        if(i!=0)cout<<' ';
        cout<<b[i];
    }
    cout<<endl;
}


Measured memory_bytes: 34168
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1LL << 60
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const long long MOD=1000000007;

// vector<p> cut(M); vector<vector<ll> > v(4);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
// for(int i=0; i<N;i++){
// }
// sort(cut.begin(),cut.end()), sort(v.rbegin(), v.rend()); //sort
// char '' str ""
int main(void)
{
    int N; cin>>N; ll ans; std::vector<ll> v(N+1); v[0]=2; v[1]=1;
    for(int i=2;i<=N;i++){
      v[i] = v[i-1] + v[i-2];
    }
    cout<<v[N]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define dbg(x) cerr<<#x": "<<(x)<<endl
#define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<endl
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<endl;}
#define all(v) v.begin(), v.end()
#define fi first
#define se second

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

template <typename T>
ostream& operator <<(ostream &out, const vector<T>& v) {
	for(const auto &item : v) out << item << ' ';
	return out;
}

const int N = 1010;
const int dl[] = { -1, 0, 1, 0 };
const int dc[] = { 0, 1, 0, -1 };

char s[N];
int d[N][N];

int main()
{
	ios_base::sync_with_stdio(false);
	
	memset(d, -1, sizeof d);

	int m, n;
	queue<pii> q;

	cin >> m >> n;
	for(int i = 0; i < m; ++i) {
		cin >> s;
		for(int j = 0; j < n; ++j)
			if(s[j] == '#') q.push({i, j}), d[i][j] = 0;
	}

	int ans = 0;
	while(!q.empty()) {
		int x = q.front().fi;
		int y = q.front().se;
		q.pop();

		for(int i = 0; i < 4; ++i) {
			int a = x + dl[i];
			int b = y + dc[i];
			if(0 <= a && a < m && 0 <= b && b < n && d[a][b] == -1) {
				d[a][b] = 1 + d[x][y];
				q.push({a, b});
				ans = max(ans, d[a][b]);
			}
		}
	}

	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 12432
import sys
import fractions

a,b,c,d = input().split()
a,b,c,d = int(a), int(b), int(c), int(d)

lcm = c * d // fractions.gcd(c, d)

count = b - a + 1 -1* (b // c) + (a-1) // c  -1*( b // d )+ (a-1) // d  + b // lcm -1*( (a-1) // lcm)

if count < 0 :
    count = 0

print(count)



Measured memory_bytes: 5044
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		Map<String, Integer> map = new HashMap<>();

		for (int i = 0; i < n; i++) {
			String str = sc.next();
			int now = map.getOrDefault(str, 0);
			map.put(str, now + 1);
		}

		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			String str = sc.next();
			int now = map.getOrDefault(str, 0);
			map.put(str, now - 1);
		}

		int ans = map.values().stream().mapToInt(Integer::valueOf).max().getAsInt();

		ans = ans < 0 ? 0 : ans;


		System.out.println(ans);
		sc.close();
	}

}

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

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

    int N, k;
    std::cin >> N >> k;

    std::vector<int> h(N);
    std::vector<int> dp(N, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < N; ++i)
        cin >> h[i];

    for (int i = 0; i < N; ++i)
    {
        for (int j = 1; j <= k and i - j >= 0; ++j)
        {
            dp[i] = min(dp[i], abs(h[i] - h[i - j]) + dp[i - j]);
        }
    }

    cout << dp[N - 1] << '\n';

    return 0;
}


Measured memory_bytes: 1024
n = int(input())
a = [int(i) for i in input().split()]
x,m,num = 10**9,0,0
for i in a:
    if i<0: m+=1
    x = min(abs(i),x)
    num+=abs(i)
if x and m%2: print(num-2*x)
else: print(num)

Measured memory_bytes: 14412
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int N, A, B;
    cin >> N >> A >> B;

    int vac = abs(B - A) - 1;

    if(vac % 2 == 0) cout << "Borys" << endl;
    else cout << "Alice" << endl;

    return 0;
}

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

int main() {
  int n, cnt = 0;
  cin >> n;
  vector<int> a(n), b(n);
  
  for (int i = 0; i < n; i++){
    cin >> a.at(i) >> b.at(i);
    if (a.at(i) == b.at(i))
      cnt++;
    else
      cnt = 0;
    if (cnt >= 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" <<endl;
  return 0;
}

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

using namespace std;
using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

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

int main(){
    int h,w;
    cin>>h>>w;

    vector<vector<char>>hw(h+2,vector<char>(w+2,'.'));

    rep2(i,1,h){
        rep2(j,1,w)cin>>hw[i][j];
    }

    rep2(i,1,h){
        rep2(j,1,w){
            if(hw[i][j]=='#'){
                if(hw[i-1][j]!='#'&&hw[i+1][j]!='#'&&
                        hw[i][j-1]!='#'&&hw[i][j+1]!='#'){
                    cout<<"No"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"Yes"<<endl;
}


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

int main() {
  int N;
  cin >> N;
  int p[N];
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }
  int ans=0;
  for (int i = 1; i < N-1; i++) {
    if ((p[i] < p[i-1] && p[i] > p[i+1]) ||
        (p[i] > p[i-1] && p[i] < p[i+1])) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int a,b;
    while(1){
        cin>>a>>b;
        if(a==0&b==0)break;
        for(int i=0;i<a;i++){
            for(int o=0;o<b;o++){
              if((o+i)%2==0){
                cout<<"#";
                                continue;
              }
                cout<<".";
            }
            cout<<endl;
        }
      cout<<endl;
    }
}


Measured memory_bytes: 3096
#coding:utf-8
N = int(input())

xu = []
for i in range(0, N):
    data = list(map(str, input().split()))
    xu.append(data)

for i in range(0, N):
    if(xu[i][1] == 'JPY'):
        xu[i][0] = int(xu[i][0])
    else:
        xu[i][0] = float(xu[i][0])*380000.0

money = []
for i in range(0, N):
    money.append(xu[i][0])

print(sum(money))


Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
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;
}

int main(){
    ll a;
    string b;
    cin >> a >> b;
    ll k;
    k = 100*(b[0]-'0')+10*(b[2]-'0')+(b[3]-'0');
    ll p = a*k;
    p/=100;
    cout << p << endl;   
    return 0;
}

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

typedef long long ll;
int main()
{
    int i,j,n;cin>>n;
    ll a[n];
    ll sum[n];sum[0]=0;
    //std::memset(sum1,0,n);cout<<sum1[4]<<endl;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ll minn=1e16;
    for(i=1;i<=n-1;i++)
    {
       minn=min(abs(sum[i]-(sum[n]-sum[i])),minn);
    }
    cout<<minn;
}


Measured memory_bytes: 3328
'use strict'
function Main(input) {
    input = input.split("\n")
    const heights = input[1].split(' ').map(i => {
      return parseInt(i, 10)
    })
 
    const result = heights.filter((val, index, array) => {
      let max = Math.max(...array.slice(0, index+1))
      return max <= val
    }).length

    console.log(result)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"))

Measured memory_bytes: 11468
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

vector<pair<ll, pair<ll, ll>>> g[55];
ll dp[55][2505]; //time to get to i and have j coins

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	ll n, m, s;
	cin >> n >> m >> s;
	ll mxn = 2500;
	rep(i, m){
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b;
		u--, v--;
		g[u].pb(mp(v, mp(a, b)));
		g[v].pb(mp(u, mp(a, b)));
	}
	s = min(s, (ll)mxn);
	vector<ll> c(n), d(n);
	rep(i, n) cin >> c[i] >> d[i];
	rep(i, 55) rep(j, 2505) dp[i][j] = 1e18;
	dp[0][s] = 0LL;
	set<pair<ll, pair<ll, ll>>> q;
	q.insert(mp(dp[0][s], mp(0LL, s)));
	while(!q.empty()){
		pair<ll, ll> cur = q.begin() -> se;
		q.erase(q.begin());
		for(pair<ll, pair<ll, ll>> v : g[cur.fi]){
			ll amt = cur.se;
			ll cur1 = dp[cur.fi][cur.se];
			while(amt <= mxn){
				//do the update
				if(amt >= v.se.fi && (cur1 + v.se.se) < dp[v.fi][amt - v.se.fi]){
					q.erase(mp(dp[v.fi][amt - v.se.fi], mp(v.fi, amt - v.se.fi)));
					dp[v.fi][amt - v.se.fi] = cur1 + v.se.se;
					q.insert(mp(dp[v.fi][amt - v.se.fi], mp(v.fi, amt - v.se.fi)));
				}
				amt += max(1LL, min(c[cur.fi], mxn - amt));
				cur1 += d[cur.fi];
			}	
		}
	}
	repn(i, 1, n){
		ll ans = 1e18;
		rep(j, 2505) ans = min(ans, dp[i][j]);
		cout << ans << endl;
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 12212
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5+4;
vector <int> adj[MAX];
vector <int> parent[MAX];
int f[MAX];
int dp(int x)
{
	int best = -1;
	if(parent[x].size() == 0) return 0;
	if(f[x] != -1) return f[x];
	for(int i=0;i<parent[x].size();i++)
	{
		best = max(best,dp(parent[x][i]) + 1);
	}
	
	f[x] = best;
	return f[x];
}
int main()
{
	memset(f,-1,sizeof(f));
	int n,m,a,b;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		adj[a].push_back(b);
		parent[b].push_back(a);
	}
	
	int maxi = -1;
	for(int i=1;i<=n;i++)
	{
		maxi = max(maxi,dp(i));
	}
	
	cout<<maxi;
}

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

signed main() {
    int N;
    cin >> N;
    map<string, int> m;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        m[s]++;
    }

    int ans = 0;
    for (auto e : m) {
        int t = e.second;
        ans += t * (t - 1) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  ll N;
  cin>>N;
  ll C[N];
  ll S[N];
  ll F[N];
  FOR(i,0,N-2){
    cin>>C[i]>>S[i]>>F[i];

  }
  FOR(i,0,N-2){
    ll ans=0;
    FOR(j,i,N-2){
      ll tmp;
      if(ans%F[j]==0){
        tmp=0;
      }else{
        tmp=F[j]-ans%F[j];
      }
      ans=max(S[j],ans+tmp);
      ans=ans+C[j];
    }
  cout<<ans<<endl;
  }

  cout<<"0"<<endl;

  return 0;


 
}
 


Measured memory_bytes: 256
n = input()
cnt = 0
S = input()
m = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1
    m = min(m, cnt)

left = -min(0, m)
right = abs(cnt - m)
print("(" * left + S + ")" * right)


Measured memory_bytes: 9104
n,m = map(int,input().split())
A = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
cur = 0
if n != 1:
    t = A[0]
    while t%2 == 0:
        cur += 1
        t = t//2
        flag = True
    for i in range(1,n):
        temp = 0
        s = A[i]
        while s%2 == 0:
            temp += 1
            s = s//2
        if temp != cur:
            flag = False
            break
    if flag:
        g = A[0]*A[1]//(4*gcd(A[0]//2, A[1]//2))
        for i in range(2, n):
            u = g
            v = A[i]//2
            p = u*v//gcd(u,v)
            g = p
        if g <= m:
            print(int((m/g-1)/2)+1)
        else:
            print(0)
    else:
        print(0)
else:
    if A[0] <= 2*m:
        print(int(((2*m/A[0])-1)/2)+1)
    else:
        print(0)


Measured memory_bytes: 15060
import numpy

N, M= map(int, input().split())
l = []
for _ in range(M):
  L, R = map(int, input().split())
  l.append([L, R])
a = numpy.array(l)

if (numpy.amin(a, axis=0)[1] - numpy.amax(a, axis=0)[0] + 1) < 0:
    print(0)
else:
    print(numpy.amin(a, axis=0)[1] - numpy.amax(a, axis=0)[0] + 1)




Measured memory_bytes: 30068
N, K = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
ans = float('inf')
for x1 in x:
    for x2 in x:
        if x1 > x2:
            continue
        for y1 in y:
            for y2 in y:
                if y1 > y2:
                    continue
                area = (x2 - x1) * (y2 - y1)
                if area >= ans:
                    continue
                cnt = 0
                for i in range(N):
                    if x1 <= x[i] <= x2 and y1 <= y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = area
print(ans)


Measured memory_bytes: 50780
import java.io.*;
import java.util.*;
 
public class Main{
	
	public void solve(){
		while(true){
			int A = nextInt();
			int L = nextInt();
			if(L == 0) return;
			
			int[] a0 = new int[L];
			int a = A;
			int[] memo = new int[21];
			memo[0] = a;
			LOOP:
			for(int cnt = 1; cnt <= 20; cnt++){
				for(int i = 0; i < L; i++){
					a0[i] = a % 10;
					a = a / 10;
				}
				Arrays.sort(a0);
				int amax = 0;
				int amin = 0;
				for(int i = 0; i < L; i++){
					amin = amin * 10 + a0[i];
					amax = amax * 10 + a0[L - 1 - i];
				}
				a = amax - amin;
				for(int i = 0; i < cnt; i++){
					if(memo[i] == a){
						out.println(i + " " + memo[i] + " " + (cnt - i));
						break LOOP;
					}
				}
				memo[cnt] = a;
			}
		}
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

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

using namespace std;

typedef long double ld;
typedef long long ll;

const int N = 505;
const int M = N * N;

int n, m;
int cnt[N];
int x[N];

void read() {
  cin >> n;
  m = n * n;

  for (int i = 0; i < n; ++i) {
    cin >> x[i];
    --x[i];
  }
}

void no() {
  cout << "No\n";
  exit(0);
}

void kill() {
  vector<int> ans;

  for (int j = 0; j < m; ++j) {
    int y = -1;
    for (int i = 0; i < n; ++i) {
      if (j == x[i]) {
        y = i;
        if (cnt[i] != i)
          no();
        break;
      }

      if (j > x[i]) {
        if (y == -1 && cnt[i] < n)
          y = i;
        continue;
      }

      if ((y == -1 || x[y] < j || x[i] < x[y]) && cnt[i] < i) {
        y = i;
      }
    }

    if (y == -1)
      no();

    cnt[y]++;
    ans.push_back(y);
  }

  cout << "Yes\n";
  for (int x : ans)
    cout << x + 1 << " ";
  cout << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("d.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();
}



Measured memory_bytes: 2420
//

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	long long h,w; cin>>h>>w;
	long long ans = 0;
	if(h == 1 || w == 1){
		cout<<1<<endl;
		return 0;
	}
	ans += h*(w/2);
	if(w % 2 == 1){
		ans+=h/2;
		if(h%2 == 1) ans++;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

// O(|s|)
bool OK(string s)
{
	char f = s.front();
	for (char ch : s)
	{
		if (ch != f) return false;
	}
	return true;
}

// O(|s|^2)
int Comp(string s, char ch)
{
	int ret = 0;
	for (;;)
	{
		if (OK(s)) break; // O(|s|)
		string next = "";
		for (int i = 0; i < s.length() - 1; ++i)
		{
			if (s[i] == ch || s[i + 1] == ch)
			{
				next += ch;
			}
			else
			{
				next += s[i];
			}
		}
		++ret;
		s = next;
	}
	return ret;
}

int main()
{
	string s; cin >> s;
	int ans = 10000;
	// あり得る全ての文字についてシミュレーション
	// O(26 * |s|^2)
	for (char ch = 'a'; ch <= 'z'; ++ch)
	{
		ans = min(ans, Comp(s, ch));
	}
	cout << ans << endl;
}


Measured memory_bytes: 3556
open Batteries
let inf = 1010101010
let n, k = Scanf.scanf "%d %d" (fun x y -> x, y)
let dislikes = List.init k (fun _ -> Scanf.scanf " %c" (fun x -> x))

let ans =
  List.init 100001 (fun p ->
    if p < n then inf
    else
      let res =
        p |> string_of_int |> String.to_list
        |> List.exists (fun d -> List.mem d dislikes)
      in
      if res then inf else p
  ) |> List.fold_left min inf;;

Printf.printf "%d\n" ans


Measured memory_bytes: 6656
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

int n,d;
signed main() {
  IO;
  cin >> n >> d;
  d = d * d;
  int ans = 0;
  rep(i, 1, n) {
    int x, y;
    cin >> x >> y;
    int tmp = x * x + y * y;
    if (tmp <= d) ans++;
  }
  cout << ans << '\n';
  return 0;
}

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

int main()
{
    long long n,i,j;
    cin>>n;
    long long ans=0;
    for(i=1;i<n;i++)
    {
        j=n/i;
        if(n%i==0)
        {
            j--;
        }
        ans+=j;
    }
    cout<<ans;
}

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

int main(){
	int n;
	cin >> n;
	int p[n];
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}
	int ans =0;
	for(int i = 1; i <= n; i++){
		int t=0;
		for(int j = 0; j < n; j++){
			if(p[j] >= i)t++;
		}
		t = min(i,t);
		ans = max(ans, t);
	}
	cout << ans <<endl;
	
	return 0;
}



Measured memory_bytes: 3080
n, m = [int(i) for i in input().split(" ")]
l = 1
r = n

for i in range(m):
    li, ri = [int(i) for i in input().split(" ")]
    if l < li:
        l = li
    if ri < r:
        r = ri

if r - l + 1 < 0:
    print(0)
else:
    print(r - l + 1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

vector<int64_t> Divisor(int64_t n) {
    vector<int64_t> ret;
    for(int64_t i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}


int main() {
	int64_t n; cin >> n;
	// for(int64_t i = 2; i <= n; ++i) {
	// 	int64_t tmp = n;
	// 	while(tmp > 1) {
	// 		if(tmp % i == 0) tmp /= i;
	// 		else tmp -= i;
	// 	}
	// 	if(tmp == 1) {
	// 		cout << i << '\n';
	// 	}
	// }
	vector<int64_t> v = Divisor(n);
	for(int64_t i : Divisor(n - 1)) {
		v.push_back(i);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int64_t ans = 0;
	for(int64_t i : v) {
		if(i == 1) continue;
		// cerr << i << '\n';
		int64_t tmp = n;
		while(tmp % i == 0) {
			tmp /= i;
		}
		if(tmp % i == 1) {
			++ans;
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define REP(i,n) for (int i=0;i<(n);++i)
using namespace std;

int main(){
    char s[3];
    REP(i, 3) cin >> s[i];
    sort(s, s+3);
    if(s[0] == 'a' && s[1] == 'b'&& s[2] == 'c') cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
mod=10**9+7;dif = [];cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
for i in range(100000):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % mod)
print(ans % mod)

Measured memory_bytes: 464816
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n, p; cin >> n >> p;
  vector<int> v(n);
  bool flag = true;
  for(int i = 0; i < n; ++i){
    cin >> v[i];
    if(v[i] % 2) flag = false;
  }
  if(flag){
    if(p == 0){
      long long ans = pow(2, n);
      cout << ans << endl;
    }
    else cout << 0 << endl;
  }
  else{
    long long ans = pow(2, n - 1);
    cout << ans << endl;  
  }
}

Measured memory_bytes: 256