akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)

F = [-1 for _ in range(N)]


def dfs(s):
    if F[s] != -1:
        return F[s]
    ret = 0
    for g in G[s]:
        ret = max(ret, dfs(g)+1)
    F[s] = ret
    return ret


res = 0
for i in range(N):
    res = max(dfs(i), res)

print(res)


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

struct Edge {
	int u, v, c;
	bool operator < (const Edge& o) const { return c < o.c; }
};

class UnionFind {
public:
	vector< int > data;
	
	UnionFind(int n) : data(n, -1) {}
	
	void unionSet(int a, int b) {
		a = root(a); b = root(b);
		
		if (a != b) {
			if (data[a] < data[b]) swap(a, b);
			data[a] += data[b]; data[b] = a;
		}
	}
	
	bool sameSet(int a, int b) { return root(a) == root(b); }
	
	int root(int x) { return data[x] < 0 ? x : root(data[x]); }
};

int n, m;
vector< Edge > edges;

void solve() {
	sort(edges.begin(), edges.end());
	
	UnionFind uf(n);
	
	vector< int > cv;
	
	for_(i,0,m) {
		Edge e = edges[i];
		
		if (!uf.sameSet(e.u, e.v)) {
			uf.unionSet(e.u, e.v);
			cv.push_back(e.c);
		}
	}
	
	cout << cv[(n - 1) / 2] << endl;
}

int main() {
	while (cin >> n >> m, n) {
		edges.clear();
		
		for_(i,0,m) {
			int u, v, c;
			cin >> u >> v >> c;
			edges.push_back(Edge{--u, --v, c});
		}
		
		solve();
	}
}

Measured memory_bytes: 1440
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_int(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁目を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁を生成し queue に投げる
    for next_i in next_int(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0])  # K 回目に取り出す最小値


Measured memory_bytes: 12228
def jumpCost(array):
    size = len(array)

    memo = [99999999999] * (size)

    memo[0] = 0

    for i in range(size):
        j = i+1

        while j < i + 2 + 1 and j < size:
            memo[j] = min(memo[j], memo[i] + abs(array[i] - array[j]))

            j += 1

    return memo[size - 1]


if __name__ == '__main__':
    n = int(input())

    a = list(map(int, input().rstrip().split()))
    print(jumpCost(a))

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++){
        int t;
        cin >> t;
        v.push_back(t);
    }
    sort(v.begin(),v.end());
    if (n % 2 == 1) cout << 0;
    else cout << v[n / 2] - v[n / 2 - 1];
    return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

double solve(int& n, int& w, vector<int>& v) {
    vector<int> g(100, 0);
    int right = 0;
    for(int i = 0; i < n; ++i) {
        right = max(right, v[i] / w);
        ++g[v[i] / w];
    }

    int height = 0;
    for(int i = 0; i <= right; ++i) {
        height = max(height, g[i]);
    }

    double ret = 0.01;
    for(int i = 0; i <= right; ++i) {
        ret += (double)g[i] / height * (right - i) / right;
    }

    return ret;
}

int main() {
    int n, w;
    vector<int> v;
    while(true) {
        cin >> n >> w;
        if(n == 0 && w == 0) break;
        v.resize(n);
        for(int i = 0; i < n; ++i) {
            cin >> v[i];
        }
        cout << setprecision(10) << solve(n, w, v) << endl;
    }
    return 0;
}

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

int main() {
    int n = 0, m = 0;
    int h[100000], a[100000], b[100000];
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }

    set<int> s;
    for (int i = 0; i < m; i++) {
        if (h[a[i] - 1] < h[b[i] - 1]) s.insert(a[i]);
        else if (h[a[i] - 1] > h[b[i] - 1]) s.insert(b[i]);
        else {
            s.insert(a[i]);
            s.insert(b[i]);
        }
    }

    cout << n - s.size() << endl;
}

Measured memory_bytes: 7460
#import math
#def main(S, b):
if __name__ == '__main__':
    #a, b, c, d = map(int, input().split())

    k = int(input())
    a, b = map(int, input().split())

    # a = list(map(int, input().split()))

    # s = sum(a)

    flug = 1
    for i in range(1000):
        if (k * i >= a and k * i <= b):
            flug = 0
            break
    #print(n * 2 * pi)

    if (flug == 1):
        print("NG")
    else:
        print("OK")


Measured memory_bytes: 9176
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

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

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<typeof((c).front())>())
#define SZ(x) ((int)(x).size())
#define MEMSET(c, v) memset((c), v, sizeof(c))

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// constant
// const ll MOD = 1e9 + 7;
// const int INF = 1e9;
// const ll INF = 1e15;
// const int dx[4] = {0, -1, 1, 0};
// const int dy[4] = {-1, 0, 0, 1};
// const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


// --------------------------------------------------------


int main()
{
    int N, K, x, sum = 0;
    cin >> N >> K;
    REP(i, N)
    {
        cin >> x;
        sum += min(abs(x), abs(K - x)) * 2;
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;
using ll = long long;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    int N; cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++)cin>>A[i];

    int d = __gcd(A[0], A[1]);
    for(int i = 0; i < N; i++)
    {
        d = __gcd(d, A[i]);
    }
    
    cout<<d<<endl;

    return 0;
}

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

using namespace std;

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

#define INF 1000000000
#define MOD 1000000007
#define EPS 1e-9
#define DEBUG(x) cout<< '>' << #x << ':' << x << "\n";
#define all(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define UNIQUE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define tr(container, it) \
	for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) 

// #define sz(a) int((a).size())
// #define pb push_back
// #define fill(a,v) memset(a,v,sizeof a)


#define trace(x) cout << '>' << #x << ':' << x << endl;
#define trace2(x,y) cout<< '>' << #x << ':' << x << " | " << #y << ':' << y << endl;

#define trace3(x,y,z) cout<< '>' << #x << ':' << x \
		<< " | " << #y << ':' << y <<" | " << #z << ':' << z << endl;

#define trace4(x,y,z,w) cout<< '>' << #x << ':' << x \
	<< " | " << #y << ':' << y <<" | " << #z << ':' << z << " | " << #w << ':' << w << endl;


inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

const double pi = acos(-1);

/////////////////////////////////////////////////////////////////////

// bool sortbysec(const pair<int,int> &a,
//               const pair<int,int> &b)
// {
//     return !(a.first < b.first);
// }

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } // __gcd(0,0) gives exception


const int MAX_N = 210;

int arr[10];

int AdjMat[210][210];

int main(){
	int N,M,R,a,b,c;
	ll ans=INF;
	scanf("%d %d %d",&N,&M,&R);
	for(int i=0;i<R;i++){
		scanf("%d",arr+i);
	}
	//memset(AdjMat,INT_MAX,sizeof AdjMat);
	//EBUG(AdjMat[1][2]);
	int V=N+1;
	for (int i = 1; i < V; i++)
			for (int j = 1; j < V; j++)
				AdjMat[i][j]=INF;
	//DEBUG(AdjMat[1][2]);
	//DEBUG(INF+INF);
	//DEBUG((int)(INF+INF));
	for(int i=0;i<M;i++){
		scanf("%d %d %d",&a,&b,&c);
		AdjMat[a][b]=c;
		AdjMat[b][a]=c;
	}
	for (int k = 1; k < V; k++) // remember that loop order is k->i->j
		for (int i = 1; i < V; i++)
			for (int j = 1; j < V; j++)
				AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j]);

	sort(arr,arr+R);
	do{
		ll temp=0;
		for(int i=0;i<R-1;i++){
			temp+=AdjMat[arr[i]][arr[i+1]];
			//trace2(i,temp);
		}
		ans=min(ans,temp);
	}
	while(next_permutation(arr,arr+R));
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> v(n),c(n),xy(n);
    for(int i=0;i<n;i++)cin>>v[i];
    for(int i=0;i<n;i++)cin>>c[i];
    for(int i=0;i<n;i++){
        xy[i]=v[i]-c[i];
    }
    sort(xy.begin(),xy.end(),greater<int>());
    int ans=0;
    for(int i=0;i<n;i++){
        if(xy[i]>0)ans+=xy[i];
    }
    cout<<ans<<endl;


}

   


Measured memory_bytes: 888
loop do
	a, op, b = gets.split
	a = a.to_i
	b = b.to_i
	if op == "?" then
		break
	end
	if op == "+" then
		puts a + b
	elsif op == "-" then
		puts a - b
	elsif op == "*" then
		puts a * b
	else
		puts a / b
	end
end



Measured memory_bytes: 6860
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define REP(i, n) for (LL i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define int long long
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
signed main() {

  int n;
  cin >>n;
  string a[n];
  cin >>  a[0];
  for (int i = 1; i < n;i++)
  {
    cin >> a[i];
    if(a[i][0]!=a[i-1][a[i-1].size()-1]){ 
      cout <<"No";
      return 0;
    }
    REP(j,i) if(a[j]==a[i]){
        cout <<"No";
      return 0;
      }
  }
  cout << "Yes";
  }

Measured memory_bytes: 3600
N = int(input())
A = [0]+list(map(int,input().split()))
A.sort()
B = [0]+list(map(int,input().split()))
B.sort()
C = [0]+list(map(int,input().split()))
C.sort()

bko = [0 for i in range(N+1)]
cnt = 1
for i in range(1,N+1):
  b = B[i]
  for j in range(cnt,N+1):
    if A[j] >= b:
      bko[i] = j-1
      cnt = j
      break
    if j == N:
      bko[i] = N
      cnt = N

#bkoを累積和にする
for i in range(N):     
  bko[i+1] += bko[i]

cko = [0 for i in range(N+1)]
cnt = 1
for i in range(1,N+1):
  c = C[i]
  for j in range(cnt,N+1):
    if B[j] >= c:
      cko[i] = bko[j-1]
      cnt = j
      break
    if j == N:
      cko[i] = bko[N]
      cnt = N
###
print(sum(cko))        

Measured memory_bytes: 23328
#include<stdio.h>
#include<stdlib.h>

#define N 500000

int parent(int);
int right(int);
int left(int);
void max_heapify(int);
void build_max_heap(void); 

int A[N], n;

int main(){
  int i, key;

  scanf("%d", &n);

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

  build_max_heap();
  
  for(i = 1; i <= n; i++){
    printf(" %d", A[i]);
  }

  printf("\n");

  return 0;
}

int parent(int i){
  return i / 2;
}

int right(int i){
  return (i * 2) + 1;
}

int left(int i){
  return i * 2;
}
    
void max_heapify(int i){
  int l, r, biggest, tmp;

  l = left(i);
  r = right(i);

  if(l <= n && A[l] > A[i])
    biggest = l;

  else
    biggest = i;

  if(r <= n && A[r] > A[biggest])
    biggest = r;

  if(biggest != i){
    tmp = A[i];

    A[i] = A[biggest];
    A[biggest] = tmp;

    max_heapify(biggest);
  }
}

void build_max_heap(){
  int i;

  for(i = n / 2; i > 0; i--)
    max_heapify(i);

  return;
}
    



Measured memory_bytes: 3660
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;

// Output
template<class T, class S> std::ostream& operator << (std::ostream& os, std::pair<T, S> p)
{
  return os << "(" << p.first << " " << p.second << ")";
}

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  //os << v[0]; for (ll i = 1; i < (ll)v.size(); i++){ os << " " << v[i]; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::map< T, S > m)
{
  ll i = 0; for (auto p : m){ os << " [" << i << "]" << p.first << "->" << p.second; i++;}
  return os;
}

template<class T> std::ostream& operator <<(std::ostream& os, std::vector< std::vector<T> > vv)
{
  for (auto& vec : vv){ os << vec; }
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll N;
  std::cin >> N;
  std::vector< ll > va(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> va[i];
  }

  std::sort(va.begin(), va.end(), std::less<>());

  ld ans = va[0];
  for (ll i = 1; i < N; ++i) {
    ans = (ans + va[i]) / 2.0;
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(100010);
	rep(i,n){
		int x;
		cin >> x;
		a.at(x)++;
	}
	int ans=0;
	for(int i=1;i<100000;++i){
		ans=max(ans,a[i-1]+a[i]+a[i+1]);
	}
	cout << ans << endl;
}

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

import math

def cal():
    # https://qiita.com/drken/items/97e37dd6143e33a64c8c
    ok = n
    ng = 0
    # 隣接するまで繰り返す
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if mid * 1.08 >= n:
            ok = mid
        else:
            ng = mid
    return ok


ans = cal()
if int(ans * 1.08) == n:
    print(ans)
else:
    print(':(')


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

#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const ll INF = LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MAXN = 21*21;
const double EPS= 1e-10;

int allmask;
//
//vector<int> g[MAXN];
//vector<int> match, vis;
//
//int Aug(int l) { // return 1 if an augmenting path is found
//    if (vis[l]) return 0; // return 0 otherwise
//    vis[l] = 1;
//    forn (j , g[l].size()) {
//        int r = g[l][j]; // edge weight not needed -> vector<vi> AdjList
//        if (match[r] == -1 || Aug(match[r])) {
//            match[r] = l; return 1; // found 1 matching
//        }
//    }
//    return 0; // no matching
//}

const int mod = 1e9 + 7;
int dp[int(1<<21)];
int main(){
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL); cout.tie(NULL);
//    cout<< setprecision(2)<< fixed;
    int n;
    cin>> n;
    vector<vector<int>> can(n, vector<int>(n));
    forn(i,n){
        forn(j,n){
            cin>> can[i][j];
        }
    }
    memset(dp, 0, sizeof dp);
    dp[0]=1;
    forn(mask, (1<<n)-1 ){
        int a = __builtin_popcount(mask);
        forn(b,n){
            if(can[a][b] && !(mask & (1<<b))){
                int m2 = mask ^ (1<<b);
                dp[m2]+=dp[mask];
                dp[m2]%=mod;
            }
        }
    }
    cout<< dp[(1<<n)-1]<<el;
}



Measured memory_bytes: 8448
#include<stdio.h>
int main(void) {
	int a, b;
	scanf("%d %d", &a, &b);
	//n*a + 1 - n = b
	//n(a-1) = b-1
	int n = 0;
	n = (b - 1) / (a - 1);
	if ((b - 1) % (a - 1) != 0) {
		n++;
	}
	printf("%d", n);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  vi a(3);
  rep(i,3){
    cin >> a[i];
  }
  sort(all(a));
  print(a[2] - a[0]);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,m,k;
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();for(m=1;m<<1<=n;m<<=1);
	if(m==n)return puts("No"),0;
	puts("Yes");
	cout<<m<<" 1\n1 "<<m+1<<"\n"<<m+1<<" "<<m+n<<"\n"<<n+1<<" "<<m+n<<"\n"<<n+1<<' '<<n+m+1<<"\n";
	for(int i=2;i<n;i+=2)if(i!=m)cout<<i<<" "<<i+1+n<<"\n"<<i+1<<" "<<i+n<<"\n1 "<<i<<"\n1 "<<i+1<<"\n";
	if(!(n&1))cout<<n<<" "<<m+1<<"\n"<<n-m<<" "<<n+n<<"\n";
	return 0;
}




Measured memory_bytes: 3572
DIV = 10**9 + 7

N = int(input())
T = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]


def get_range(a, b):
    if b > a:
        return b, b
    if b == a:
        return (1, b)


left = [(T[0], T[0])]
right = [(A[-1], A[-1])]
for i in range(N - 1):
    a, b = T[i], T[i + 1]
    left.append(get_range(a, b))
    a, b = A[N - i - 1], A[N - i - 2]
    right.append(get_range(a, b))
right = right[::-1]


ans = 1
for i in range(N):
    a1, b1 = left[i]
    a2, b2 = right[i]

    a = max(a1, a2)
    b = min(b1, b2)

    ans *= max((b - a + 1), 0)
    ans %= DIV


print(ans)

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

#define rep(i,n) for(ll i=0;i<n;i++)
#define REP(i,a,n) for(ll i=a;i<n;i++)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef pair<ll, ll> pll;

const int INF = 100000000;
const ll LINF = 1e18+5;

ll A[200000];
ll B[200000];

// 文章Sに対して，ワードWの開始位置のvectorを返す
vector<ll> KMP(vector<ll>& W, vector<ll>& S) {
    int N = W.size();
    vector<int> T(N+1);
    T[0] = -1;
    ll j = -1;
    rep(i,W.size()){
        while (j >= 0 && W[i] != W[j]) j = T[j];
        T[i+1] = ++j;
    }
    vector<ll> res;
    ll m = 0, i = 0;
    while (m+i < S.size()) {
        if (W[i] == S[m+i]) {
            if (++i == (ll)W.size()) {
                res.push_back((N-m)%N);
                m = m+i-T[i];
                i = T[i];
            }
        } else {
            m = m+i-T[i];
            if (i > 0) i = T[i];
        }
    }
    return res;
}

int main() {
    ll N;
    cin >> N;
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    vector<ll> C(N);
    vector<ll> D(2*N);
    rep(i,N) {
        C[i] = A[i] ^ A[(i+1)%N];
        D[i] = B[i] ^ B[(i+1)%N];
        D[i+N] = D[i];
    }
    D.pop_back();
    vector<ll> Ks = KMP(C, D);
    
    sort(Ks.begin(), Ks.end());
    for(auto k : Ks) {
        ll x = B[0] ^ A[k];
        cout << k << " " << x << endl;
    }
    return 0;
}

Measured memory_bytes: 12896
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;


int main(){
	string s;
	int cnt = 0;
	
	cin >> s;
	
	for(int i=0;i<s.size()/2;i++){
		if(s[i] != s[s.size()-i-1])cnt++;
	}
	
	cout << cnt << endl;
	
	
	return 0;
}

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

int main(){

    int a, b;
    scanf("%d%d", &a, &b);
    int cnt=0;
    for(int i=a; i<=b; ++i){
        int num=i, s=0;
        while(num){
            s*=10;
            s+=num%10;
            num/=10;
        }
        if(s==i)
            ++cnt;
    }
    printf("%d\n", cnt);








    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    private void run() throws IOException {
        boolean b = true;
        final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while (b) {
            b = runOnce(reader);
        }

        reader.close();
    }

    private boolean runOnce(final BufferedReader reader) throws IOException {
        final String[] params = reader.readLine().split(" ");
        final int count = Integer.parseInt(params[0]);
        final int max = Integer.parseInt(params[1]);
        if (count == 0 && max == 0) return false;
        final List<Integer> prices = Arrays.stream(reader.readLine().split(" "))
                .map(Integer::parseInt)
                .sorted()
                .collect(Collectors.toList());
        int nextLow = 0;
        int maxSum = 0;
        for (int i = prices.size() - 1; i >= 0; i--) {
            int j;
            for (j = nextLow; j < i; j++) {
                if (prices.get(i) + prices.get(j) > max) {
                    break;
                }
            }
            if (j == nextLow) continue;
            maxSum = Math.max(maxSum, prices.get(i) + prices.get(j - 1));
            nextLow = j;
        }

        System.out.println(maxSum == 0 ? "NONE" : maxSum);
        return true;
    }
}

Measured memory_bytes: 35072
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,n,s=0;
	cin>>n;
	for(i=1;i<=n;i++){
		if(i%3!=0&&i%5!=0){
			s+=i;
		}
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 3656
using System;

namespace code
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] read = Console.ReadLine().Split(' ');
            // n:参加者
            // k:ポイント数
            // q:問題数
            int n = int.Parse(read[0]);
            int k = int.Parse(read[1]);
            int q = int.Parse(read[2]);
            int[] sankasya = new int[n];

            for(int i = 0; i < q; i++)
            {
                int seikai = int.Parse(Console.ReadLine());
                sankasya[seikai - 1] = sankasya[seikai - 1] + 1;
            }
            for(int i = 0; i < n; i++)
            {
                if(k - q + sankasya[i] > 0)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
                
        }
    }
}


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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
int64_t dp[3001][3001][2];

int main(){
    int i, j, k;
    int N, M;
    cin >> N >> M;

    for(j=0; j<=N; j++) dp[0][j][(j==0)] = 1;
    for(i=0; i<M; i++){
        for(j=0; j<=N; j++){
            for(k=0; k<2; k++){
                if(j>0){
                    add(dp[i+1][j][k|(j==1)], dp[i][j][k]);
                    add(dp[i+1][j-1][k|(j==1)], dp[i][j][k]);
                }
                if(j<N){
                    add(dp[i+1][j+1][k], dp[i][j][k]);
                    add(dp[i+1][j][k], dp[i][j][k]);
                }
            }
        }
    }

    int64_t ans = 0;
    for(j=0; j<=N; j++) add(ans, dp[M][j][1]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 140928
#include<iostream>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    using namespace std;
    #define INF 10000000;
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
    #define vec(n) vector<int>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

  
  
    int main(){
      int n;
      cin >> n;
      auto a = vec(n);
      auto b = vec(n);
      rep(i,n)cin >> a[i];
      rep(i,n)cin >> b[i];

      auto Sa = vec(n);Sa[0] = a[0];
      auto Sb = vec(n);Sb[0] = b[0];
      rep(i,n-1)Sa[i+1] = Sa[i]+a[i+1];
      rep(i,n-1)Sb[i+1] = Sb[i]+b[i+1];

      int mx = 0;
      rep(i,n){
        
        int now = Sa[i]+Sb[n-1]-Sb[i-1];
        if(!i)now = Sa[i]+Sb[n-1];
        mx = max(mx,now);
      }
      cout << mx <<endl;
    }

    


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

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = new int[N];
        int ptr, res;
        ptr = res = 0;

        for(int i=0; i < N; i++){
            A[i] = int.Parse(Console.ReadLine());
        }

        Array.Sort(A);

        while(ptr < N){
            int cc = A[ptr], f = 0;
            while(ptr < N && A[ptr] == cc){
                f++;
                ptr++;
            }

            res += f % 2;
        }

        Console.WriteLine(res);
    }
}



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

void check(char ch)
{
	if (ch >= 'A' && ch <= 'Z')
		cout<<"A"<<endl;
	else if (ch >= 'a' && ch <= 'z')
	cout<<"a"<<endl;
}
int main()
{
	char ch;
    cin>>ch;
	check(ch);
	return 0;
}


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

int main() {
    int N,M;
    cin>>N>>M;
    if(N%2==1){
        for (int i = 1; i <= M; i++){
            cout<<i<<" "<<i+N-1-2*(i-1)<<endl;
        }
    }else{
        for (int i = 1; i <= M; i++){
            int b=N-1-2*(i-1);
            if(b<=N/2)b--;
            cout<<i<<" "<<i+b<<endl;
        }
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL n;
    cin >> n;
    vector<vector<LL>> a_bin(n+1,vector<LL>(20, 0));
    vector<LL> a(n);
    for(LL i=0; i<n; i++){
        cin >> a[i];
    }
    LL tmp;
    for(LL i=1; i<=n; i++){
        tmp=a[i-1];
        for(LL j=0; j<20; j++){
            a_bin[i][j]=tmp%2;
            a_bin[i][j]+=a_bin[i-1][j];
            tmp/=2;
        }
    }

    LL end_point=1;
    LL ans=0;
    for(LL i=0; i<=n; i++){
        while(true){
            bool is_ok=true;
            for(LL j=0; j<20; j++){
                if(a_bin[end_point][j]-a_bin[i][j]>1){
                    is_ok=false;
                }
            }
            if(is_ok==false){
                ans+=(end_point-1-i);
                break;
            }else if(end_point==n){
                ans+=end_point-i;
                break;
            }else{
                end_point++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 43860
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value != 0>::type
fill_v(U & u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value == 0>::type
fill_v(U & u, const V... v) { for (auto& e : u) fill_v<T>(e, v...); }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vvi X(N);
	vi s(130);
	REP(i, 130) {
		s[i] = (i + 1) * (i + 1);
	}
	REP(i, N) {
		REP(j, D) {
			int x;
			cin >> x;
			X[i].push_back(x);
		}
	}
	int ans = 0;
	REP(i, N) {
		REP(j, i) {
			if (i == j)continue;
			int sum = 0;
			REP(k, D) {
				sum += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
			}
			REP(k, 130) {
				if (sum == s[k]) {
					ans++;
					break;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
// Try AtCoder
//author: Leonardone @ NEETSDKASU

fn main() {
	let mut stdin = String::new();
    std::io::Read::read_to_string(
    	&mut std::io::stdin(),
        &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
    	($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let n =  get!();
	let mut ans = 0;
    let mut xs = vec![];
    xs.push((0,0));
    for i in 0..10 {
    	let mut tmp = vec![];
        for &(x, f) in xs.iter() {
        	if f == 7 && x <= n {
            	ans+=1;
            }
            tmp.push((x*10+3,f|1));
            tmp.push((x*10+5,f|2));
            tmp.push((x*10+7,f|4));
        }
        xs = tmp;
    }
    
    println!("{}", ans);
}

Measured memory_bytes: 6396
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

map<string, int> mp;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    mp[s] = 1;
    rep(i, n - 1) {
        string w;
        cin >> w;
        if (mp[w] != 0 || s.back() != w[0]) {
            cout << "No" << endl;
            return 0;
        }
        mp[w] = 1;
        s = w;
    }
    cout << "Yes" << endl;
    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define FOR(i,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)
 
#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
 
typedef long long ll;
typedef pair<int, int> PII;
 
const double EPS = 1e-10;
 
const int N = 200000;
int r[N];
int n;
 
int main() {
  int i, j;
  scanf("%d ", &n);
  for (i=0; i<n; i++) scanf("%d ", r+i);

/*
  //O(n^2):TLE
  int res = r[1] - r[0];
  for (i=0; i<n-1; i++)
  for (j=i+1; j<n; j++)
    res = (res < r[j] - r[i]) ? r[j] - r[i] : res; 
  printf("%d\n", res);
*/
   
/*
  //WA(mini???????¨??????´??°?????????maxj-mini????????????????????¨?????????)
  int maxj = r[1];
  int mini = r[0];
  for (j=1; j<n; j++) {
    if (maxj-mini < r[j]-mini) {
    maxj = r[j];
    if (j < n-1 && r[j] < mini) mini = r[j];
    }
  //    if (j < n-1 && r[j] < mini) mini = r[j];
  }
  printf("%d\n", maxj-mini);
*/
     
  //res???max-min???????????????(???????????????mini?????´??°??§???????????¨???????????????)
  int res = r[1] - r[0];
  int mini = r[0];
  for (j=1; j<n; j++) {
    if (res < r[j] - mini) res = r[j] - mini;
    if (r[j] < mini) mini = r[j];
  }

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

  return 0;
}

Measured memory_bytes: 1976
#include <stdio.h>
#include <iostream>
using namespace std;
static const int MAX = 36;

// static int cnt = 0;

struct Card {
    char suit;
    int value;
};

void trace(struct Card *a, int n) {
    for (int i = 0; i < n-1; i++) {
        cout << a[i].suit << a[i].value << " ";
    }
    cout << a[n-1].suit << a[n-1].value << endl;
}

void bubbleSort(struct Card *a, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = n-1; j > i; j--) {
            if (a[j].value < a[j-1].value) {
                struct Card tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
}

void selectionSort(struct Card *a, int n) { 
    for (int i = 0; i < n; i++) {
        int minj = i;
        for (int j = i; j < n; j++) {
            if (a[minj].value > a[j].value) {
                minj = j;
            }
        }
        if (i != minj) {
            struct Card tmp = a[i];
            a[i] = a[minj];
            a[minj] = tmp;
        }
    }
}

bool isStable(struct Card *stable, struct Card *hatena, int n) {
    for (int i = 0; i < n; i++) {
        if (stable[i].suit != hatena[i].suit || stable[i].value != hatena[i].value) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    struct Card a[MAX], b[MAX];

    cin >> n;
    
    for (int i = 0; i < n; i++) {
        char s;
        int v;
        cin >> s >> v;
        a[i].suit = b[i].suit = s;
        a[i].value = b[i].value = v;
    }
    // trace(a, n);
    bubbleSort(a, n);
    selectionSort(b, n);
    
    trace(a, n);
    cout << "Stable" << endl;
    trace(b, n);
    if (isStable(a, b, n)) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
    // cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3060
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

N, X = map(int, input().split())
A = list(map(lambda x: abs(int(x) - X), input().split()))
g = A[0]
for i in range(1, N):
  g = math.gcd(g, A[i])
print(g)


Measured memory_bytes: 21260
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long  b = sc.nextLong();
        long k = sc.nextLong();
        if(a >= k) {
            a -= k;
            k = 0;
        }else{
            k -= a;
            a = 0;
            if(b >= k) {
                b -= k;
                k = 0;
            }else {
                b = 0;
                k = 0;
            }
        }
        
        System.out.println(a+" "+b);
    }
}

Measured memory_bytes: 20948
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

vector<vector<int>> G;
vector<bool> checked;
queue<int> a, b; //a true b false
void dfs(int v, bool visin){

    for(int i: G[v]){
        if( checked[i] == true ) continue;
        checked[i] = true;
        if(visin){
            b.push(i);
            dfs(i, !visin);
        }
        else{
            a.push(i);
            dfs(i, !visin);
        }


    }

}


int main(){
    int N;
    cin >> N;
    G.resize(N); // 0-indexed
    checked.resize(N);
    for (int i = 0; i < N; i++) {
        checked[i] = false;
    }
    char tmpchar;
    int tmp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> tmpchar;
            tmp = tmpchar - '0';
            if(i >= j) continue;
            if(tmp == 0) continue;
            G[i].push_back(j);
            G[j].push_back(i);
        }
    }

    a.push(0);
    dfs(0, true);

    vector<int> biG(N);
    while(!a.empty()) {
        tmp = a.front();
        a.pop();
        biG[tmp] = 1;
    }
    while(!b.empty()) {
        tmp = b.front();
        b.pop();
        biG[tmp] = 2;
    }

    for (int i = 0; i < N; i++) {
        for (int v : G[i]){
            if(biG[i] + biG[v] != 3){
                printf("-1\n");
                return 0;
            }
        }
    }

    vector<vector<int>> dist(N, vector<int>(N, inINF));
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
        for(int v : G[i]){
            dist[i][v] = 1;
        }
    }

    int ans = 0;

    for(int k = 0; k < N; k++)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans = max(ans, dist[i][j]);
        }
    }

    printf("%d\n", ans+1);

    
    return 0;
}



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

int main(void){
    int i;
    int a[5];
    //WHxyr
    for (i=0;i<5;i++){
        cin >> a[i];
    }
    if(a[2] >= a[4] && a[2] <= a[0]-a[4] && a[3] >= a[4] && a[3] <= a[1]-a[4]){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3108
#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)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
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;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

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

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

int main() {
    ll X, Y;
    cin >> X >> Y;
    if(X == Y) {
        cout << -1 << endl;
        return 0;
    }
    if(lcm(X, Y) == X) {
        cout << -1 << endl;
        return 0;
    }
    ll Z = X;
    while(Z < 1000000000) {
        if(Z % Y != 0) {
            cout << Z << endl;
            return 0;
        }
        Z += X;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

ll sum[202020];
int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	rep(i, 0, n)cin >> a[i];
	rep(i, 0, n)sum[i + 1] += sum[i]+a[i];


	ll ans = inf;
	for (int c = 1; c <= n-3; c++) {
		ll sum1 = sum[c + 1];
		ll sum2 = sum[n] - sum1;
		ll p, q, r, s;
		//left
		if (a[0] > sum1-a[0]) {
			p = a[0];
			q = sum1 - a[0];
		}
		else {
			int ok = 0;
			int ng = c;
			while (ng - ok > 1) {
				int mid = (ok + ng) / 2;
				if (sum[mid + 1] <= sum1 - sum[mid + 1])ok = mid;
				else ng = mid;
			}
			ll diff1 = abs(sum[ok+1] - (sum1-sum[ok+1]));
			ll diff2 = abs(sum[ok+2] - (sum1-sum[ok + 2]));
			if (diff1 <=  diff2) {
				p = sum[ok + 1];
				q = sum1 - sum[ok + 1];
			}
			else {
				p = sum[ok + 2];
				q = sum1 - sum[ok + 2];
			}
		}
		//right
		if (a[c+1] > sum2 - a[c+1]) {
			r = a[c+1];
			s = sum2 - a[c+1];
		}
		else {
			int ok = c+1;
			int ng = n-1;
			while (ng - ok > 1) {
				int mid = (ok + ng) / 2;
				if (sum[mid+1]-sum[c+1] <= sum2 - sum[mid + 1]+sum[c+1])ok = mid;
				else ng = mid;
			}
			ll diff1 = abs(sum[ok + 1]-sum[c+1] - (sum2 - sum[ok + 1]+sum[c+1]));
			ll diff2 = abs(sum[ok + 2]-sum[c+1] - (sum2 - sum[ok + 2]+sum[c+1]));
			if (diff1 <= diff2) {
				r = sum[ok + 1]-sum[c+1];
				s = sum2 - r;
			}
			else {
				r = sum[ok + 2]-sum[c+1];
				s = sum2 - r;
			}
		}
		vector<ll>v;
		v.pb(p);
		v.pb(q);
		v.pb(r);
		v.pb(s);
		sort(all(v));
		ans = min(ans, v[3] - v[0]);
	}
	puts(ans);

	
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#define FOR(i, m, n) for (int i = m; i <= n; ++i)
using namespace std;

int main() {
    int n; cin >> n;
    int a[3][101] = {};
    FOR(i,1,2) {
        FOR(j,1,n) {
            cin >> a[i][j];
            a[i][j] += max(a[i-1][j], a[i][j-1]);
        }
    }
    cout << a[2][n] << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

count = 0

flag = 1
while flag:
    flag = 0
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
            count += 1
            flag = 1

print(count)

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

int main()
{
	for(int i = 1; i < 10; i++)
	{
		for(int j = 1; j < 10; j++)
		{
			cout << i << 'x' << j << '=' << i*j << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
// clang-format off

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

// clang-format on

int main() {
  string s[200], ans;
  int N, L;
  cin >> N >> L;
  rep(i, N) { cin >> s[i]; }
  sort(s, s + N);
  rep(i, N) { ans += s[i]; }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

ll h,w;

ll get_ans(ll a1, ll b1, ll c1){
  vector<ll> v{a1, b1, c1};
  sort(v.begin(), v.end());
  return v[2] - v[0];
}

int main(){
  cin >> h >> w;
  ll a, b, c;
  ll ans = LINF;
  rrep(i, w){
    a = h * i;
    b = (h / 2) * (w - i);
    c = (h - (h / 2)) * (w - i);
    ans = min(ans, get_ans(a, b, c));
  }

  rrep(i, h){
    a = w * i;
    b = (w / 2) * (h - i);
    c = (w - (w / 2)) * (h - i);
    ans = min(ans, get_ans(a, b, c));
  }

  rrep(i, w){
    a = h * i;
    b = h * ((w - i) / 2);
    c = h * (w - i - ((w - i) / 2));
    ans = min(ans, get_ans(a, b, c));
  }

  rrep(i, h){
    a = w * i;
    b = w * ((h - i) / 2);
    c = w * (h - i - ((h - i) / 2));
    ans = min(ans, get_ans(a, b, c));
  }

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


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

bool can(int N, int K, vector<int> &A, int v){
	int i;
	vector<int> b(N);
	for(i = 0; i < N; i++){
		b[i] = A[i] % v;
	}
	sort(b.begin(), b.end());
	vector<int> c(N + 2, 0), d(N + 2, 0);
	for(i = 1; i <= N; i++){
		c[i] = c[i - 1] + b[i - 1];
	}
	for(i = N; i > 0; i--){
		d[i] = d[i + 1] + v - b[i - 1];
	}
	for(i = 1; i <= N + 1; i++){
		if(max(c[i - 1], d[i]) <= K){
			return true;
		}
	}
	return false;
}

signed main(){
	int N, K, i;
	scanf("%lld%lld", &N, &K);
	vector<int> A(N);
	int S = 0;
	for(i = 0; i < N; i++){
		scanf("%lld", &A[i]);
		S += A[i];
	}
	int ans = 0;
	for(i = 1; i * i <= S; i++){
		if(S % i != 0){
			continue;
		}
		if(can(N, K, A, i)){
			ans = max(ans, i);
		}
		if(can(N, K, A, S / i)){
			ans = max(ans, S / i);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

vector<ll> pow2(61);
void pre() {
    pow2[0] = 1;
    for (int i = 1; i < pow2.size(); i++) {
        pow2[i] = pow2[i-1]*2;
    }
}

int main() {
    pre();
    ll x, y; cin >> x >> y;
    ll MAX = 0;
    for (int i = 0; i < pow2.size(); i++) {
        if (y >= pow2[i]*x) MAX = i+1;
        else break;
    }
    cout << MAX << endl;
}

Measured memory_bytes: 256