akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,head[100005],cc,A,ans,mx[100005],dep[100005];
struct sd{int next,to;}seg[200005];
inline void addseg(int v,int r) {seg[++cc].next=head[v];head[v]=cc;seg[cc].to=r;}
inline void dfs(int v,int fa) {
	dep[v]=dep[fa]+1;mx[v]=dep[v];
	for(int i=head[v];i;i=seg[i].next) if(seg[i].to!=fa) dfs(seg[i].to,v);
	for(int i=head[v];i;i=seg[i].next) if(seg[i].to!=fa) mx[v]=max(mx[v],mx[seg[i].to]);
	if(mx[v]-dep[v]+1==m&&v!=1&&dep[v]!=2) {++ans;mx[v]=dep[v]-1;}
}
int main()
{
	scanf("%d%d",&n,&m);scanf("%d",&A);if(A!=1) ++ans;
	for(int i=2;i<=n;++i) {scanf("%d",&A);addseg(A,i);addseg(i,A);}
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

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

typedef long long lint;
typedef pair<int,int> pii;
#define fint register int
#define flint register lint
#define foreach(IT,START,END) for(fint IT=START;IT<=END;IT++)

inline int ty()
{
	fint a=0,b=1,c=getchar();
	while(!isdigit(c))b^=c=='-',c=getchar();
	while(isdigit(c))a=a*10+c-48,c=getchar();
	return b?a:-a;
}


const int _N = 307 , mo = 1000000007;

int n,f[_N][_N][_N]={0};
int m,liml[_N],limr[_N],limx[_N];
vector<pii> lim[_N];

int main()
{
	n=ty(),m=ty();
	foreach(i,1,m)
	{
		liml[i]=ty(),limr[i]=ty(),limx[i]=ty();
		lim[limr[i]].emplace_back(liml[i],limx[i]);
	}

	f[1][0][0]=1;

	foreach(i,1,n)
	{
		for(auto it:lim[i])
		{
			fint l=it.first,x=it.second;
			foreach(j,0,i-1)
			{
				foreach(k,0,max(j-1,0))
				{
					if(x==0)f[i][j][k]=0;
					if(x==1 && j>=l)f[i][j][k]=0;
					if(x==2 && (k>=l || j<l))f[i][j][k]=0;
					if(x==3 && k<l)f[i][j][k]=0;
				}
			}
		}
		foreach(j,0,i-1)
		{
			foreach(k,0,max(j-1,0))
			{
				if(!f[i][j][k])continue;
				f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mo;
				f[i+1][i][j]=(f[i+1][i][j]+f[i][j][k])%mo;
				f[i+1][i][k]=(f[i+1][i][k]+f[i][j][k])%mo;
			}
		}
	}
	flint ans=0;
	foreach(i,0,n-1)
	{
		foreach(j,0,max(i-1,0))
		{
			ans=(ans+f[n][i][j])%mo;
		}
	}
	printf("%lld\n",ans*3ll%mo);
	return 0;
}


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

int main (void){
    int r;
    cin >> r;
    if(2800 <= r){
        cout << "AGC" << endl;
    }else if(1200 <= r){
        cout << "ARC" << endl;
    }else{
        cout << "ABC" << endl;
    }

    return 0;
}


Measured memory_bytes: 3492
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int Q = Integer.parseInt(bf.readLine());
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        for(int q=0; q<Q; q++) {
          StringTokenizer st = new StringTokenizer(bf.readLine());
          int A = Integer.parseInt(st.nextToken());
          int B = Integer.parseInt(st.nextToken());
          long low = 0;
          long high = 1L*1000000000*1000000000;
          while(low < high) {
            long mid = (low + high + 1)/2;
            if(isPossible(mid, A, B)) {
              low = mid;
            }
            else high = mid-1;
          }
          out.println(low);
        }
        // StringTokenizer st = new StringTokenizer(bf.readLine());
        // int[] a = new int[n];
        // for(int i=0; i<n; i++) a[i] =  Integer.parseInt(st.nextToken());

        out.close(); System.exit(0);
    }
    public static boolean isPossible(long max, long A, long B) {
      long prod = 1L*A*B;
      if((max < A) && (max < B)) return true;
      long last_A = max;
      if(max >= A) last_A = max+1;
      long last_B = max;
      if(max >= B) last_B = max+1;
     long first_A = 1;
      if(A == 1) first_A = 2;
      long first_B = 1;
      if(B == 1) first_B = 2;
      if(1L*first_A*last_B >= prod) return false;
      if(1L*first_B*last_A >= prod) return false;

      if(A <= max) {
        long toMult = (max+1-A);
        if(B <= toMult) toMult++;
        if(1.0*(A+1)*toMult > prod+1.0) return false;
        long test = 1L*(A+1)*toMult;
        if(test >= prod) return false;

        toMult = (max+1-(A-1));
        if(B <= toMult) toMult++;
        if(1.0*(A-1)*toMult > prod+1.0) return false;
        test = 1L*(A-1)*toMult;
        if(test >= prod) return false;
      }

      if(B <= max) {
        long toMult = (max+1-B);
        if(A <= toMult) toMult++;
        if(1.0*(B+1)*toMult > prod+1) return false;
        long test = 1L*(B+1)*toMult;
        if(test >= prod) return false;

        toMult = (max+1-(B-1));
        if(A <= toMult) toMult++;
        if(1.0*(B-1)*toMult > prod+1) return false;
        test = 1L*(B-1)*toMult;
        if(test >= prod) return false;
      }

      for(int diff = -2; diff <= 2; diff++) {
        if((max + 1 - diff) % 2 == 1) continue;
        long index1 = (max + 1 + diff)/2;
        long index2 = (max + 1 - diff)/2;
        if(index1 >= A) index1++;
        if(index2 >= B) index2++;
        if(1.0*index1*index2 > prod + 1.0) return false;
        if(1L*index1*index2 >= prod) return false; 
      }




      return true;
      //
    }


}


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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, m, x, y, q, k;
string s, t, s0,s1,s2;



// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin>>s0>>s1>>s2;
	if(s0[s0.length()-1] == s1[0] && s1[s1.length()-1] == s2[0]) cout<<"YES\n";
	else cout<<"NO\n";
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 3648
n, m = map(int, input().split())
ab = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    ab[a - 1].append(b - 1)
    ab[b - 1].append(a - 1)
    
bin = [2 ** i for i in range(n + 1)]

def bfs(bit, pos, s):
    global ans
    if bit == bin[-1] - 1:
        ans += 1
        return
    for next_pos in ab[pos]:
        if (bit // bin[next_pos]) % 2 == 1:
            continue
        bfs(bit + bin[next_pos], next_pos, s + str(next_pos + 1))

ans = 0
bfs(1, 0, "1")
print(ans)

Measured memory_bytes: 3064
# -*-coding: utf-8 -*-
H, W = map(int, input().split())
a = []
for i in range(H): # 文字列は扱いにくいので'.' -> 0, '#' -> 1と置換
    a.append(list(input()))
    a[i] = [0 if x == '.' else 1 for x in a[i]]

# まずは行を取り除く
new_a = []
for i in range(H):
    if sum(a[i]) != 0:
        new_a.append(a[i])

# print(2, new_a)

# 転置
new_a_t = [list(x) for x in zip(*new_a)]
# print(3, new_a_t)
# 転置した行を取り除く(元の配列の列を取り除くのと同じ)
pre_ans = []
for i in range(W):
    if sum(new_a_t[i]) != 0:
        pre_ans.append(new_a_t[i])

# print(4, pre_ans)

# 転置
pre_ans = [list(x) for x in zip(*pre_ans)]

# print(5, pre_ans)

for i in range(len(pre_ans)):
    pre_ans[i] = ['#' if x == 1 else '.' for x in pre_ans[i]]
    # print(i, pre_ans[i])
    print("".join(pre_ans[i]))

Measured memory_bytes: 3316
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int dp[maxn][3],n,m,s,t,vis[maxn][3];
vector <int> mp[maxn];
struct node{int to,x;};
queue <node> q;

int main()
{
	n=read(); m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		mp[u].push_back(v);
	}
	s=read(); t=read();
	q.push({s,0}); vis[s][0]=1;
	while(!q.empty())
	{
		node u=q.front(); q.pop();
		for(int i=0;i<mp[u.to].size();i++)
		{
			int v=mp[u.to][i];
			if(vis[v][(u.x+1)%3]) continue;
			dp[v][(u.x+1)%3]=dp[u.to][u.x]+1;
			vis[v][(u.x+1)%3]=1; q.push({v,(u.x+1)%3});
		}
	}
	if(dp[t][0]) cout<<dp[t][0]/3; else puts("-1");
	return 0;
}

Measured memory_bytes: 32000
from math import log2, ceil

def solve(n, A):
    def count_div2(m):
        if m % 2 == 1:
            return 0
        l, r = 0, ceil(log2(m)) + 1
        while r - l > 1:
            p = (r + l) // 2
            if m % (2 ** p) == 0:
                l = p
            else:
                r = p
        return l
    return sum(count_div2(a) for a in A)

_n = int(input())
_A = map(int, input().split())
print(solve(_n, _A))


Measured memory_bytes: 3956
# 配るDP
N = int(input())
H = list(map(int,input().split()))

INF = float('inf')

dp = [INF]*(10**5+10)
dp[0] = 0

for i in range(N-1):
    dp[i+1] = min(dp[i+1], dp[i] + abs(H[i] - H[i+1]))
    if i < N-2:
        dp[i+2] = min(dp[i+2], dp[i] + abs(H[i] - H[i+2]))

print(dp[N-1])


Measured memory_bytes: 13980
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

//const ll INF = 1e15;
const ll MOD = 1e9 + 7;

// 組み合わせ（nCm）を計算
ll calcCombination(ll n, ll m){
	ll i;
	ll ans = 1;
	for (i = 0; i < m; i++){
		ans *= n - m + i + 1;
		ans /= i + 1;
	}
	return ans;
}

int main(){
	ll N, P;
	cin >> N >> P;
	ll ne = 0;
	ll no = 0;
	ll i, j;
	for (i = 0; i < N; i++){
		ll a;
		cin >> a;
		if (a % 2 == 0){
			ne++;
		}
		else{
			no++;
		}
	}
	ll ans = 0;
	for (i = 0; i <= no; i++){
		if (i % 2 == P){
			ans += calcCombination(no, i);
		}
	}
	ans *= pow(2, ne);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let n = read::<usize>();
  let mut a = vec![];
  let mut memo_l = vec![0; n];
  let mut memo_r = vec![0; n];
  let mut answers = vec![];

  for _ in 0..n {
    let v = read::<u32>();
    a.push(v);
  }

  let mut memo = a[a.len() - 1];
  for (i, v) in a.iter().rev().enumerate() {
    memo = gcd(memo, *v);
    memo_r[i] = memo;
  }

  let mut memo2 = a[0];
  for (i, v) in a.iter().enumerate() {
    memo2 = gcd(memo2, *v);
    memo_l[i] = memo2;
  }

  memo_r.reverse();
  memo_l.reverse();
  memo_r.remove(0);
  memo_l.remove(0);
  answers.push(memo_l[0]);
  answers.push(memo_r[0]);

  memo_r.remove(0);
  memo_l.remove(0);
  memo_r.reverse();
  memo_l.reverse();

  memo_r.reverse();

  for i in 0..memo_r.len() {
    answers.push(gcd(memo_r[i], memo_l[i]));
  }


  println!("{}", answers.iter().max().unwrap());

}

fn gcd(a: u32, b: u32) -> u32 {
  if b == 0 {
    a
  } else {
    gcd(b, a % b)
  }
}



Measured memory_bytes: 6396
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
  
  int n,a,b; cin >>n>>a>>b;

  cout << min(n*a, b) << endl;
  
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

ll v[55],C[55][55];

void init(){
	for(int i=0; i<55; i++){
		C[i][0] = 1;
		for(int j=1; j<=i; j++)
			C[i][j] = C[i-1][j-1]+C[i-1][j];
	}
}

int main(){
	init();
	int n,a,b;
	cin >> n >> a >> b;
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v,v+n);

	int f = 0;
	for(int i=1; i<n; i++){
		if(v[i] != v[i-1]) f=1;
	}
	if(!f){
		ll k=0;
		for(int i=a; i<=b; i++)
			k += C[n][i];
		printf("%.10lf\n",(double)v[0]);
		cout << k << endl;

		return 0;
	}

	int i;
	ll t=v[n-1-a+1],sum=0;
	int cnt = 0;
	for(i=n-1; i>n-1-a; i--){
		sum += v[i];
		if(v[i] == t) cnt++;
	}
	double ans = sum*1.0/a;
	int tmp=cnt;

	for(int j=i; j>=0; j--){
		if(v[j] == t) cnt++;
	}
	if(v[n-1] == t){
		ll k=0;
		for(int i=a; i<=b && i<=cnt; i++)
			k += C[cnt][i];
		printf("%.10lf\n",(double)t);
		cout << k << endl;
	}else{
		printf("%.10lf\n",ans);
		cout << C[cnt][tmp] << endl;
	}

    return 0;
}

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

int main() {
  string O,E; cin >> O >> E;
  rep(i,0,E.size()) {
    cout << O[i];
    cout << E[i];
  }
  if (O.size() != E.size()) cout << O[O.size()-1] << endl;
  cout << endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main (){
    int A,B,count=0;
    cin >> A >> B;
    vector<int> v(5);

    for(int i=A;i<=B;i++){
        int x = i;
        for(int j=0;j<5;j++){
            v.at(j) = x%10;
            x/=10;
        }
    if(v.at(0)==v.at(4) && v.at(1)== v.at(3)){
        count++;
    }
    }
cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// */
using namespace std;
#define int long
signed main(){
  string s;
  cin>>s;
  bool f=false;
  int l=s.size()/2;
  while(!f){
    f=true;
    --l;
    for(int i=0;f&&i<l;++i)if(s[i]!=s[i+l])f=false;
    if(f)break;
  }
  cout<<l*2;
}

Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
void solve(){
    int n, v,q;
    ll b,c,s=0;
    map<ll,ll> m;
    cin>>n;
    for(int i=0;i<n;++i){
      cin>>v;
      m[v]++;
      s+=v;
    }
    cin>>q;
    while(q--){
      cin>>b>>c;
      if(m.find(b)==m.end()){
        cout<<s<<"\n";
        continue;
      }
      s+=m[b]*(c-b);
      m[c]+=m[b];
      m.erase(b);
      cout<<s<<"\n";
    }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout << solve() << "\n";
  solve();
  return 0;
} 


Measured memory_bytes: 7612
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>

typedef long long ll;
const ll MOD = 998244353;

using namespace std;

int main(){
    int N,S;
    cin >> N >> S;
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    ll dp[3001][3001][3];

    dp[0][0][0] = 1;
    dp[0][0][1] = 1;
    dp[0][0][2] = 1;
    if(A[0] <= S){
        dp[0][A[0]][1] = 1;
        dp[0][A[0]][2] = 1;
    }

    for(int i = 1; i < N; i++){
        for(int j = 0; j < S+1; j++){
            if(j+A[i] <= S){
                dp[i][j+A[i]][1] = (dp[i][j+A[i]][1] + dp[i-1][j][0] + dp[i-1][j][1])%MOD;
                dp[i][j+A[i]][2] = (dp[i][j+A[i]][2] + dp[i-1][j][0] + dp[i-1][j][1])%MOD;
            }
            dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][0])%MOD;
            dp[i][j][1] = (dp[i][j][1] + dp[i-1][j][1] + dp[i-1][j][0])%MOD;
            dp[i][j][2] = (dp[i][j][2] + dp[i-1][j][2] + dp[i-1][j][1] + dp[i-1][j][0])%MOD;
        }
    }

    cout << dp[N-1][S][2]%MOD << endl;

    return 0;
}

Measured memory_bytes: 211200
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(i=a;i<n;i++)
#define test(a) cout << "*" << a << endl
int main (){
  int h,w;
  char a[100][100];
  int i,j;
  bool nonexistH[100] = {};
  bool nonexistW[100] = {};
  
  cin >> h >> w;
  
  rep(i,0,h){
    rep(j,0,w){
      cin >> a[i][j];
    }
  }  
  /*rep(i,0,h){
    rep(j,0,w){
      cout << a[i][j];
    }
    cout << endl;
  }*/
  
  rep(i,0,h){
    rep(j,0,w){
      if(a[i][j]=='#'){
        nonexistH[i] = true;
        break;
        
      }
    }
  }
  //test("*");
  //rep(i,0,h) test(nonexistH[i]);
  
  rep(j,0,w){
    rep(i,0,h){
      if(a[i][j]=='#'){
        nonexistW[j] = true;
        //test(j);
        break;
        
      }
    }
  }
  //test("*");
  //rep(j,0,w) test(nonexistW[j]);
  
  rep(i,0,h){
    if(nonexistH[i]==false)
      continue;
    else{
      rep(j,0,w){
        if(nonexistW[j]==false)
          continue;
        else{
          cout << a[i][j];  
        }
      }
    }
    cout << endl;
  }
          
 
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
bool solve(int x, int y, int z) {
	for (int i = x; i <= y; ++i) {
		if (i == z) return true;
	}
	return false;
}
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a > b) swap(a, b);
	if (solve(a, b, c)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
import sys

N = int(input())

if N==0:
    print(0)
    sys.exit()

ans = ""
b = -2
while N!=1:
    if N%b==0:
        ans += "0"
        N = N/b
    else:
        ans += "1"
        N = (N-1)/b
ans += "1"
print(ans[::-1])

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramF
    {
        static void Main()
        {
            int m = NextInt;
            long k = NextLong;
            int limit = 1;
            for (int i = 0; i < m; i++) limit *= 2;

            if (k == 0)
            {
                System.Console.WriteLine(string.Join(" ", Enumerable.Range(0, limit).Select(i => $"{i} {i}")));
            }
            else if (limit <= k || (m == 1 && k == 1))
            {
                System.Console.WriteLine(-1);
            }
            else
            {
                System.Console.WriteLine($"0 {k} 0 {string.Join(" ", Enumerable.Range(1, limit - 1).Where(i => i != k))} {k} {string.Join(" ", Enumerable.Range(1, limit - 1).Where(i => i != k).Reverse())}");
            }
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


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

int main(){
  int n; cin >> n;
  vector<ll> a(n);
  vector<ll> s(n+1);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) s[i+1] += s[i] + a[i];
  ll ans = 1001001001001001;
  for(int i = 1; i < n; i++){
    ll sunuke = s[i] - s[0];
    ll arai = s[n] - s[i];
    ans = min(abs(arai - sunuke), ans);
  }
  cout << ans << endl;
}

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);

    string a,b;
    cin>>a>>b;
    int n=a.size();
    int c=0;
    loop(i,0,n)
    {
        if(a[i]!=b[i])
            c++;
    }
    cout<<c;

    return 0;
}


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

int main() {
    int N;
    cin >> N;
    int A[N], B[N];
    for(int i = 0; i <= N; i++) {
        B[i] = 0;
    }
    for(int i = 2; i <= N; i++) {
        cin >> A[i];
        B[A[i]]++;
    }
    for(int i = 1; i <= N; i++) {
        cout << B[i] << endl;
    }
}


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

using namespace std;
using std::vector;

#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD int(1e9) + 7
#define PAI  3.1415926535
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define chmax(x, y) x = max(x,y)
#define chmin(x, y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i, n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b != 0) gcd(b, a%b);
  return b;
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a / gcd(a , b)) * b;
}

int main(){

  int cnt = 1;
  int s; cin >> s;
  set<int> st;
  st.insert(s);

  while(true){
    cnt ++;
    if(s % 2)
      s = 3 * s + 1;
    else
      s /= 2;
    auto it = st.find(s);
    if(it != st.end()){
      pr(cnt);
      return 0;
    }

    st.insert(s);
    
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int partition(int,int);

int A[100000];
int point;
int main(){

  int n;
  int i;
  scanf("%d",&n);

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

  point = partition(1,n);

  for(i = 1;i < n;i++){
    if(point==i){
      printf("[%d] ",A[i]);
    }
    else{
      printf("%d ",A[i]);
    }
  }
  printf("%d\n",A[i]);
  return 0;
}

int partition(int p,int r){

  int x,y;
  int i,j;

  x = A[r];
  i = p-1;

  for(j = p;j <= r-1;j++){
    if(A[j] <= x){
      i = i+1;
      y = A[i];
      A[i] = A[j];
      A[j] = y;
    }
  }
  y = A[i+1];
  A[i+1] = A[r];
  A[r] = y;
  return i+1;
}

Measured memory_bytes: 988
n = int(input())
arr = []
temp = n
for i in range(2,int(-(-n**0.5//1))+1):
    if temp%i ==0:
        cnt = 0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i,cnt])
            
if temp!=1:
    arr.append([temp,1])
if arr==[]:
    arr.append([n,1])

count = 0

for k in arr:
    if k[0] == 1:
        continue
    now = 1
    while k[1] >= now:
        k[1] -= now
        now += 1
        count += 1

print(count)

Measured memory_bytes: 9484
import java.math.BigDecimal;
import java.util.Scanner;
 
class Main {
 
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int y = scan.nextInt();
        double f = 1.0 * x / y;
        BigDecimal g = new BigDecimal(f);
        g = g.setScale(5,BigDecimal.ROUND_HALF_UP);
        System.out.printf(x/y + " " + x%y + " " + "%.5f",g);
    }
}

Measured memory_bytes: 26780
#include<iostream>
using namespace std;
int main (void)
{
  long long int i,j,n,ans;
  cin>>n;
  i=1;
  
  while(1)
  {
    j=n/i;
    if(i*j==n){ans=i+j-2;}
    if(i>j)break;
    i++;
  }
  cout<<ans;
}

Measured memory_bytes: 3648
#include <iostream>

using namespace std;

int main(void) {
    int A, B;
    cin >> A >> B;
    if(A >= 13) {
        cout << B << endl;
    } else if(A >= 6) {
        cout << B/2 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int main(){
  int a,b,i;
  char s[200000];
  cin>>s;

  for (i = 0;s[i] != 'A'; i++) {
  }
  a = i;

  /*aは時間的問題なし*/

  for (i = strlen(s)-1; s[i] != 'Z'; i--) {
  }
  b = i;

  cout<<b-a+1;

  return 0;
}


Measured memory_bytes: 384
//#include <atcoder/modint>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder;
typedef long long ll;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(x) ll(x.size()) 
using P = pair<int, int>;
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; }
const int INF = 2e9;
const ll LINF = (1LL<<60);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s; cin >> s;
  if(s.back()=='s') s += "es";
  else s += "s";

  cout << s << endl;
  return 0;
}


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

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" << " = " << a[i] << endl;
#define fastio ios_base::sync_with_stdio(false); \
			cin.tie(0);							 \
			cout.tie(0);
#define PI 3.141592654

using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 9;

ll powmod(ll base, ll exp, const ll MOD) { ll ans = 1; while (exp) { if (exp & 1)	ans = (ans * base) % MOD; base = (base * base) % MOD; exp >>= 1; }return ans; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll modInverse(ll n, const ll p) { return powmod(n, p - 2, p); }
void add(ll& x, ll v) { x = (x + v) % MOD; if (x < 0) x += MOD; }
//ll f[500005];
//ll kCn(ll k, ll n) { return (f[n] * modInverse((f[n - k] * f[k]) % MOD, MOD)) % MOD; }


void test_case() {

}



int main() {
	fastio;
	//#ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	//#endif // !ONLINE_JUDGE
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if (n & 1) {
		int l = a[n/2], r = b[n / 2];
		cout << r - l + 1;
	}
	else {
		int l = (a[n / 2] + a[n / 2 - 1]), r = (b[n / 2] + b[n / 2 - 1]);
		cout << r - l + 1;
	}
	return 0;
}


Measured memory_bytes: 4728
import static java.lang.System.*;

import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int money;
		while((money = scan.nextInt())!=0){
			money = 1000 -money;
			int coin = 0;
			if(money >= 500){
				coin++;
				money -=500;
			}
			if(money >=100){
				while(money >=100){
					coin++;
					money -=100;
				}
			}
			if(money >=50){
				coin++;
				money -=50;
			}
			if(money >=10){
				while(money >=10){
					coin++;
					money -=10;
				}
			}
			if(money >=5){
				coin++;
				money -=5;
			}
			if(money >=1){
				while(money >=1){
					coin++;
					money -=1;
				}
			}
			out.println(coin);
		}
	}
}

Measured memory_bytes: 17164
#include <bits/stdc++.h>
//#define int long long
#define double long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define pii pair<int,int>
#define ff first
#define ss second
#define frr(i,n) for(int i=0;i<n;i++)
#define td(v) v.begin(),v.end()
#define inf 1000000000 // 1e9
#define M   1000000007 // 1e9 + 7
using namespace std;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int exp(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}
double dp[315][315][315];
double N;
double solve(int i,int j,int k){
    if(dp[i][j][k] > -0.5){
        return dp[i][j][k];
    }
    if(i==0 && j==0 && k==0){
        return dp[i][j][k] = 0.0;
    }
    double den = i+j+k;
    dp[i][j][k] = N;
    if(i>0) dp[i][j][k] += solve(i-1,j,k)*i;
    if(j>0) dp[i][j][k] += solve(i+1,j-1,k)*j;
    if(k>0) dp[i][j][k] += solve(i,j+1,k-1)*k;
    dp[i][j][k]/= den;
    //cout << "dp[" << i << "][" << j << "][" << k << "] = " << fixed << setprecision(18) << dp[i][j][k] << endl;
    return dp[i][j][k];
}
int main(){
    fastio;
    int n;
    cin >> n;
    N = n;
    int q1 = 0,q2=0,q3=0;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        if(x==1) q1++;
        if(x==2) q2++;
        if(x==3) q3++;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                dp[i][j][k] = -1.0;
    cout << fixed << setprecision(18) << solve(q1,q2,q3) << endl;
}

Measured memory_bytes: 467200
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  if (s[0] == t[0]) ans++;
  if (s[1] == t[1]) ans++;
  if (s[2] == t[2]) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;
typedef pair<int,int> P;

bool check(ll a){
    int s = 0; while(pow(10,s) <= a) s++;
    vector<bool> check(3,false);
    rep(i,s){
        int num = a % 10;
        if(num == 3) check[0] = true;
        if(num == 5) check[1] = true;
        if(num == 7) check[2] = true;
        a /= 10;
    }
    if(check[0] == true && check[1] == true && check[2] == true) return true;
    return false;
}

ll dfs(ll a, ll n){
    ll ans = 0;
    if(a > n) return ans;
    if (check(a)) ans++;
    ans += dfs(10*a + 3, n);
    ans += dfs(10*a + 5, n);
    ans += dfs(10*a + 7, n);
    return ans;
}

int main(){
    ll n; cin >> n;
    cout << dfs(0, n) << endl;
}

Measured memory_bytes: 4092
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int main() {
    long long n, a, b, ans, div;
    cin >> n >> a >> b;
    ans = 0;
    long long group = a + b;
    div = n / group;
    n = n % group;
    ans += div * a;
    if (n >= a) {
        ans += a;
    }
    else ans += n;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

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

constexpr int MAXGAPS = 13;

long g_cnt = 0;

void shellSort(vector<int>& line, const int n);
void insertionSort(vector<int>& line, const int n, const int gap);

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

    vector<int> line(n);
    for (auto i = 0; i < n; i++) {
        // cin >> line.at(i);
        scanf("%d", &line.at(i));
    }

    shellSort(line, n);

    cout << g_cnt << endl;
    for (auto i = 0; i < n; i++) {
        cout << line.at(i) << endl;
    }

    return 0;
}

void shellSort(vector<int>& line, const int n)
{
    vector<int> gap(MAXGAPS);
    int m = 1;
    gap.at(0) = m;
    int gap_cnt = 1;
    for (auto i = 1; (m = 3 * m + 1) <= n; i++) {
        gap.at(i) = m;
        gap_cnt++;
    }

    cout << gap_cnt << endl;
    for (auto i = gap_cnt - 1; i >=  0; i--) {
        cout << gap.at(i);
        if (i != 0) {
            cout << " ";
        }
    }
    cout << endl;

    for (auto i = gap_cnt - 1; i >=  0; i--) {
        insertionSort(line, n, gap.at(i));
    }
}

void insertionSort(vector<int>& line, const int n, const int gap)
{
    for (auto i = gap; i < n; i++) {
        int key = line.at(i);

        auto j = i - gap;
        while (j >= 0 && line.at(j) > key) {
            line.at(j + gap) = line.at(j);
            g_cnt++;
            j -= gap;
        }

        line.at(j + gap) = key;
    }
}

Measured memory_bytes: 4888
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};

fn main() {
  let m = read::<i32>();
  let mut a = vec![0; m as usize];
  for i in 0..m {
    a[i as usize] = read::<i32>();
  }

  println!("{}", a.iter().max().unwrap() - a.iter().min().unwrap());
}



Measured memory_bytes: 4352
#include<stdio.h>
#define NUM 2000000
void insert(int);
int extract();
void maxHeapify(int);
void heapIncreaseKey(int,int);

int a[NUM],heapsize=0;

int main(){
  char c[10];
  int n,max;
  while(1){
    scanf("%s",c);
    if(c[0]=='i'){
      scanf("%d",&n);
      insert(n);
    }else{
      if(c[1]=='x'){
	max=extract();
	printf("%d\n",max);
      }else{
	break;
      }
    }
  }
  return 0;
}

void insert(int n){
  heapsize++;
  a[heapsize]=-1;
  heapIncreaseKey(heapsize,n);
}

int extract(){
  int max;
  if(heapsize<1){
    return -1;
  }
  max=a[1];
  a[1]=a[heapsize];
  heapsize--;
  maxHeapify(1);
  return max;
}

void maxHeapify(int i){
  int l,r,largest,a1;
  l=2*i;
  r=2*i+1;
  if(l<=heapsize&&a[l]>a[i]){
    largest=l;
  }else{
    largest=i;
  }
  if(r<=heapsize&&a[r]>a[largest]){
    largest=r;
  }
  if(largest!=i){
    a1=a[i];
    a[i]=a[largest];
    a[largest]=a1;
    maxHeapify(largest);
  }
}

void heapIncreaseKey(int i,int n){
  int a1;
  if(n<a[i]){
    return;
  }
  a[i]=n;
  while(i>1&&a[i/2]<a[i]){
    a1=a[i];
    a[i]=a[i/2];
    a[i/2]=a1;
    i=i/2;
  }
}



Measured memory_bytes: 5584
#include <iostream>
#include <map>
#include <algorithm>

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

using namespace std;

typedef long long ll;

int n;
ll s[100000];
ll nrml[100000];
bool p[100000];
vector<int> pt;
vector<int> pm;
vector<ll> ps;
map<ll, int> cnrm;

void prm(){
	fill_n(p + 2, 100000 - 2, true);
	rep(i, 100000){
		if(p[i]){
			for(int j = 2 * i; j < 100000; j += i){
				p[j] = false;
			}

			if(i < 3000){
				pt.push_back(i);
			}
			pm.push_back(i);
			ps.push_back(ll(i) * i);
		}
	}
}

ll nrm(ll x){
	for(int v: pt){
		ll v3 = ll(v) * v * v;
		while(x % v3 == 0){
			x /= v3;
		}
	}
	return x;
}

ll pr(ll x){
	ll k = 1;
	for(int v: pt){
		if(x % (v * v) == 0){
			x /= (v * v);
			k *= v;
		}
		else if(x % v == 0){
			x /= v;
			k *= v * v;	
		}
	}
	if(binary_search(ps.begin(), ps.end(), x)){
		int idx = lower_bound(ps.begin(), ps.end(), x) - ps.begin();
		return pm[idx] * k;
	}
	return x * x * k;
}

int main(){
	cin >> n;
	rep(i, n){
		cin >> s[i];
	}

	prm();

	rep(i, n){
		nrml[i] = nrm(s[i]);
		++cnrm[nrml[i]];		
	}

	int ans = 0;
	rep(i, n){
		ll a = nrml[i];
		ll b = pr(a);

		if(a == 1 && cnrm[a]){
			++ans;
			cnrm[a] = 0;
		}
		else{
			ans += max(cnrm[a], cnrm[b]);
			cnrm[a] = cnrm[b] = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

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

vector<int> f(vector<int>& a) {
	int n = a.size();
	vector<int> res(n);
	rep(i, n) res[i] = a[i] ^ a[(i + 1) % n];
	return res;
}

// KMP
template<typename T>
struct MP {
	int n;
	T t;
	vector<int> a;
	MP() {}
	MP(const T& t) : t(t) {
		n = t.size();
		a = vector<int>(n + 1);
		a[0] = -1;
		int j = -1;
		for (int i = 0; i < n; ++i) {
			while (j != -1 && t[j] != t[i]) j = a[j];
			j++;
			a[i + 1] = j;
		}
	}
	int operator[](int i) { return a[i]; }
	vector<int> findAll(const T& s) {
		vector<int> res;
		int j = 0;
		for (int i = 0; i < s.size(); ++i) {
			while (j != -1 && t[j] != s[i]) j = a[j];
			j++;
			if (j == n) {
				res.push_back(i - j + 1);
				j = a[j];
			}
		}
		return res;
	}
};


int main() {
	int n;
	cin >> n; 
	vector<int> a(n), b(n);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	vector<int> xa = f(a);
	vector<int> xb = f(b); 
	MP<vector<int>> mp(xa);
	xb.insert(xb.end(), xb.begin(), xb.end());
	vector<int> res = mp.findAll(xb);
	vector<int> ks; 
	for (int p : res) ks.push_back(n - p);
	sort(ks.begin(), ks.end());  
	for (int k : ks) {
		if (k >= n) continue;
		int x = a[k] ^ b[0];
		printf("%d %d\n", k, x);
	}
	return 0;
}

Measured memory_bytes: 11728
#include <algorithm>
#include <vector>
#include <cmath>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#include <iostream>
#include <set>

using namespace std;

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


int main() {

    int N;
    long X;
    cin >> N >> X;
    vector<long> xs;

    for (int i = 0; i < N; i++) {
        long x;
        cin >> x;
        x -= X;
        x = abs(x);
        xs.push_back(x);
    }

    long currentGCD = xs[0];

    for (int i = 1; i < N; i++) {
        currentGCD = gcd(currentGCD, xs[i]);
    }

    cout << currentGCD << "\n";


    return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
const int mx = 100005;
int k;
long long a[mx], maxn = 2, minn = 2;

int main(){
    scanf("%d", &k);
    for(int i = k-1; i >= 0; i--) scanf("%lld", a+i);
    for(int i = 0; i < k; i++){
        minn = (minn - 1) / a[i] * a[i] + a[i];
        maxn = maxn / a[i] * a[i] + a[i] - 1;
        if(minn > maxn) return puts("-1")*0;
    }
    printf("%lld %lld\n", minn, maxn);
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

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

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int n, h, w;

  cin >> n >> h >> w;

  cout << (ll)(n-h+1) * (n+1-w) << endl;

  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }

const int max_V=208;
const ll INF=1000000000000000000;

ll d[max_V][max_V];
int N,M,R;

void warshall_floyd(){
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}
int main(){
    cin>>N>>M>>R;
    V<int> r(R);
    rep(i,R){
        cin>>r[i];
        r[i]--;
    }
    sort(all(r));
    rep(i,N){
        rep(j,N) d[i][j]=INF;
    }
    rep(i,M){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        a--;b--;
        d[a][b]=c;
        d[b][a]=c;
    }
    warshall_floyd();
    ll ans=1000000000000000000;
    do{
        ll cnt=0;
        for(int i=0;i<R-1;i++) cnt+=d[r[i]][r[i+1]];
        chmin(ans,cnt);
    }while(next_permutation(all(r)));
    cout<<ans<<endl;
}

Measured memory_bytes: 512
H,W=map(int, input().split())
S=[input() for i in range(H)]
l=[[0]*W for i in range(H)]
r=[[0]*W for i in range(H)]
t=[[0]*W for i in range(H)]
b=[[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            l[h][w]=l[h][w-1]+1
            t[h][w]=t[h-1][w]+1
        if S[h][W-w-1]=='.':
            r[h][W-w-1]=r[h][-w]+1
        if S[H-h-1][w]=='.':
            b[H-h-1][w]=b[-h][w]+1
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,l[h][w]+r[h][w]+t[h][w]+b[h][w]-3)
print(ans)

Measured memory_bytes: 180228
using System;

public class hello
{
    public static void Main()
    {
        int count = int.Parse(Console.ReadLine());
        int sum_h = 0;
        int sum_t = 0;

        int ct = 0;

        for (int i = 0; i < count; i++)
        {
            string[] str = Console.ReadLine().Split(' ');
            string hnk = str[0].ToLower();
            string tr = str[1].ToLower();

            if (hnk.CompareTo(tr) > 0) { sum_h += 3; }
            else if (hnk.CompareTo(tr) == 0)
            {
                sum_h++;
                sum_t++;
            }
            else
            {
                sum_t += 3;
            }
        }
        Console.WriteLine($"{sum_h} {sum_t}");
    }
}


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

signed main(){
  int N, X, Y;
  cin >> N >> X >> Y;X--;Y--;
  map<int, int> d;
  rep(i,N){
      rep(j,N){
          if(i==j)continue;
        d[min({abs(j - i),abs(X - i) + abs(j - Y) + 1, abs(Y - i) + abs(j - X) + 1})]++;
      }
    }
  for(int i = 1;i < N;i++){
      cout << d[i]/2 << endl;
  }
}



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

const int MAX_N = 1000001;

// is_p[i] := i が素数のとき true
bool is_p[MAX_N+1] = {false,false};

// エラトステネスのふるい
void sieve(){
	for(int i = 2 ; i <= MAX_N ; i++ )
		is_p[i] = true;
	for(int i = 2 ; i*i <= MAX_N ; i++ ){
		if( is_p[i] ){
			for(int j = i+i ; j <= MAX_N ; j += i ){
				is_p[j] = false;
			}
		}
	}
}


int main(){
	sieve();
	
	int m, a, b;
	while( cin >> m >> a >> b , m || a || b ){
		for(int p = m ; p >= 0 ; p-- ){
			bool f = false;
			for(int q = 2 ; q * q <= p ; q++ ){
				if( p % q != 0 ) continue;
				if( !is_p[q] || !is_p[p/q] ) continue;
				if( ((double)q/(p/q)) < (double)a/b ) continue;
				cout << q << " " << p/q << endl;
				f = true;
				break;
			}
			if( f ) break;
		}
	}
}

Measured memory_bytes: 2140
import sys
import math
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
flag = 0
for i in range(1,N+1):
    if math.floor(i*1.08) == N:
        print(i)
        flag = 1
        break

if flag == 0:
    print(":(")


Measured memory_bytes: 38512
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    if (a[i] < b[i]):
        ans += min(b[i], a[i] + a[i + 1])
        a[i + 1] = max(a[i + 1] + a[i] - b[i], 0)
    else:
        ans += b[i]

print(ans)


Measured memory_bytes: 19156
import math
n=int(input())
a=list(map(int,input().split()))
def s_bunkai(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
num1=a[0]
for i in range(1,n):
    num1=math.gcd(num1,a[i])
cnt=0
num3=set()
yn=0
for i in range(n):
    num2=s_bunkai(a[i])
    cnt+=len(num2)
    if a[i]==1:
        cnt-=1
    else:
        for j in range(len(num2)):
            num3.add(num2[j][0])
    if cnt!=len(num3):
        yn=1
        break
if yn==0:
    print("pairwise coprime")
elif num1==1:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 181880
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define fo(i,n) for(ll i=0;i<n;i++)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define loop(i,a,b)for(ll i=a;i<=b;i++)
#define loopr(i,a,b)for(ll i=b;i>=a;i--)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define vll vector<ll> 
#define vvl vector<vll>
#define vpll vector<pll>
#define pll pair<ll,ll>
#define F first
#define S second
#define MOD 1000000007
ll max(ll a,ll b){if (a>b) return a; else return b;}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll fexp(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%MOD; b/=2;a=a*a%MOD;}return ans;}
ll inverse(ll a, ll p){return fexp(a, p-2);}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll T=1;
	//cin >> T;
	ll t=0;
	while(t++<T){
		ll n;
		cin>>n;
		vll a(n);
		fo(i,n)cin>>a[i];
		ll mx=-1;
		ll ans=0;
		fo(i,n){
			mx=max(mx,a[i]);
			ans+=mx-a[i];
		}
		cout<<ans<<endl;
		
	}
return 0;
}


Measured memory_bytes: 4780