akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <cfloat>
#include <map>
using namespace std;
int main(){
	
	int n;
	
	while(cin>>n,n!=0){
		long long a,b,c;
		int f=0;
		map<int,long long> s;
			vector<int> d;
		
		for(int i=0;i<n;i++){
		
			cin>>a>>b>>c;
			if(!s[a])d.push_back(a);
			s[a]+=b*c;
		}
		for(int i=0;i<d.size();i++){
			if(s[d[i]]>=1000000){
				cout<<d[i]<<endl;
				f=1;
			}
			
		}
		if(f!=1)
			cout<<"NA"<<endl;
	
	}
	
}

Measured memory_bytes: 1288
#include <stdio.h>

int A[1000000],n;

int binarySearch(int key) {
  int left = 0;
  int right = n;
  int mid;
  while (left < right) {
    mid = (left + right) / 2;
    if (key == A[mid]) return 1;
    if (key > A[mid]) left = mid + 1;
    else if (key < A[mid]) right = mid;
  }

  return 0;

}

int main() {
  int i,q,k,sum = 0;

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

  scanf("%d",&q);
  for(i = 0;i < q;i++) {
    scanf("%d",&k);
    if (binarySearch(k)) sum++;
  }
  printf("%d\n",sum);

  return 0;

}



Measured memory_bytes: 2092
n,t = map(int, input().split())
a = list(map(int, input().split()))
min_a = a[0]
min_b = 0
cnt = 0
for i in range(1, n):
    min_a = min(min_a, a[i-1])
    if min_b < a[i]-min_a:
        min_b = a[i]-min_a
        cnt = 1
    elif min_b == a[i]-min_a:
        cnt += 1
print(cnt)


Measured memory_bytes: 15020
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TOPSIC
{
    partial class Program
    {
        static void Main(string[] args)
        {
          string S = Console.ReadLine();

            string ans = "";

            for (int i = 0; i < S.Length; i++)
            {
                ans += "x";
            }

            Console.WriteLine(ans);


        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int d,w;
int e[10][10];

int out_min(int left,int right,int up,int down){
  int ret=INF;
  for(int i=left;i<=right;i++){
    ret=min(ret,e[up][i]);
    ret=min(ret,e[down][i]);
    // cout<<"debug: "<<ret<<endl;
  }
  for(int i=up;i<=down;i++){
    ret=min(ret,e[i][right]);
    ret=min(ret,e[i][left]);
    // cout<<"debug: "<<ret<<endl;
  }

  return ret;
}

int in_max(int left,int right,int up,int down){
  int ret=-INF;
  for(int i=up+1;i<=down-1;i++){
    for(int j=left+1;j<=right-1;j++){
      ret=max(ret,e[i][j]);
    }
  }

  return ret;
}

int calc_score(int left,int right,int up,int down,int depth){
  int ret=0;
  for(int i=up+1;i<=down-1;i++){
    for(int j=left+1;j<=right-1;j++){
      ret+=(depth-e[i][j]);
    }
  }
  
  return ret;
}

int main(){
  while(cin>>d>>w,d|w){
    for(int i=0;i<d;i++){
      for(int j=0;j<w;j++){
	cin>>e[i][j];
      }
    }
    int ans=0;

    /* i==up j==down*/
    for(int i=0;i<d-2;i++){
      for(int j=i+2;j<d;j++){
	/* k==right l==left*/
	for(int l=0;l<w-2;l++){
	  for(int k=l+2;k<w;k++){
	    int o_m=out_min(l,k,i,j);
	    int i_m=in_max(l,k,i,j);
	    if(i_m<o_m){
	      ans=max(ans,calc_score(l,k,i,j,o_m));
	    }
	  }
	}
      }
    }

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



Measured memory_bytes: 3004
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        Point start = new Point(0.0, 0.0);
        Point end = new Point(100.0, 0);

        start.print();
        koch(n, start, end);
        end.print();
    }

    private static void koch(int d, Point p1, Point p2) {
        if (d == 0) return;

        // s, u, tの座標を計算
        Point s = new Point(
                (2.0 * p1.x + 1.0 * p2.x) / 3,
                (2.0 * p1.y + 1.0 * p2.y) / 3);
        Point t = new Point(
                (1.0 * p1.x + 2.0 * p2.x) / 3,
                (1.0 * p1.y + 2.0 * p2.y) / 3);
        double th = Math.PI * 60.0 / 180.0;
        Point u = new Point(
                (t.x - s.x) * Math.cos(th) - (t.y - s.y) * Math.sin(th) + s.x,
                (t.x - s.x) * Math.sin(th) + (t.y - s.y) * Math.cos(th) + s.y);

        koch(d - 1, p1, s);
        s.print();
        koch(d - 1, s, u);
        u.print();
        koch(d - 1, u, t);
        t.print();
        koch(d - 1, t, p2);

    }

}

class Point {
    double x;
    double y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    void print() {
        System.out.printf("%.8f %.8f%n", this.x, this.y);
    }
}


Measured memory_bytes: 44036
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int main(){
	int N;
	cin>>N;
	long long L[100];
	L[0] = 2;
	L[1] = 1;
	rep(i,89) L[i+2] = L[i+1] + L[i];
	cout<<L[N]<<endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include <vector>
#define re(i,n) for(int i = 0; i < n; i++)

int main() {
	int n, a[101], cnt= 0;
	cin >> n;
	for (int i = 1; i < n + 1; i++) cin >> a[i];
	for (int i = 1; i <= n; i += 2) {
		if (a[i] % 2) cnt++;
	}
	cout << cnt << endl;


	return 0;
}

Measured memory_bytes: 3560
import numpy as np

def main():
    n, m, x = map(int, input().split())
    a = map(int, input().split())
    
    arr_np = np.array(list(a))

    print(min(np.sum(arr_np < x) ,np.sum(arr_np > x)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 12484
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>; 
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const long long mod = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))


struct mint {
	int x;
	mint(int x = 0) :x((x%mod + mod) % mod) {}
	mint& operator+=(const mint a){
		if ((x += a.x) >= mod)x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod)x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x*=a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(int t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};
mint dp[61][2][2][2];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int l, r; cin >> l >> r;
	dp[60][0][0][0] = 1;
	for (int i = 59; i >= 0; i--) {
		int lb = l >> i & 1;
		int rb = r >> i & 1;
		rep(j, 2)rep(k, 2)rep(s, 2) {
			mint pre = dp[i + 1][j][k][s];
			rep(x, 2)rep(y, 2) {
				if (x && !y)continue;
				int nj = j; int nk = k;int ns = s;
				if (!s&&x != y)continue;
				if (x&&y)ns = 1;
				if (!j && !x&&lb)continue;
				if (x && !lb)nj = 1;
				if (!k&&y && !rb)continue;
				if (!y&&rb)nk = 1;
				dp[i][nj][nk][ns] += pre;
			}
		}
	}
	mint ans;
	rep(j, 2)rep(k, 2)rep(s, 2)ans += dp[0][j][k][s];
	cout << ans.x << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {

   int n;
   int a = 0;
  
  vector<string> vec;
  
  vector<string> p = {"P","W","G","Y"};
  
//  p.resize(0);
  vec.resize(100);
 
  
   string l;
  
   cin >> n;
 


    while(cin>>l){
        
        vec[a]=l;
    
       
        a++;
       
    }

 
   // cout << n << endl;
  
   for(int i = 0;i<n;i++){
     
     for(int j = 0;j<p.size();j++){
       
       if(vec[i]==p[j]){
       
          p.erase(p.begin() + j);
         
          
       
       }
     }
     
     
     
     
     
   }
    
  if(p.size()==0){
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
 
  
  
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from collections import defaultdict

N, M = map(int, input().split())
A = [0] + list(map(int, input().split()))

dic = defaultdict(int)
dic[0] += 1
ans = 0
for i in range(N):
    A[i + 1] += A[i]
    A[i + 1] %= M
    ans += dic[A[i + 1]]
    dic[A[i + 1]] += 1

print (ans)




Measured memory_bytes: 14844
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

lli h, w;

int main(void){
    cin >> h >> w;
    vector<string> m(h);
    vector<vector<lli>> a(h, vector<lli>(w)), b(h, vector<lli>(w));
    rep(i, h) cin >> m[i];
    rep(i, h){
        rep(j, w){
            if(m[i][j] == '#') continue;
            lli c = 0;
            int k;
            for(k = j; k < w && m[i][k] != '#'; k++){
                c++;
            }
            for(; j < k; j++) a[i][j] = c;
        }
    }
    rep(j, w){
        rep(i, h){
            if(m[i][j] == '#') continue;
            lli c = 0;
            int k;
            for(k = i; k < h && m[k][j] != '#'; k++){
                c++;
            }
            for(; i < k; i++) b[i][j] = c;
        }
    }
    lli ans = 0;
    rep(i, h){
        rep(j, w){
            if(m[i][j] == '.') ans = max(ans, a[i][j]+b[i][j]-1);
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define ll long long
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const int maxN = 1e5+5;
const int mod = 1e9+7;

void solve(){
    int H,W;
    cin>>H>>W;
    vector<string> grid(H);
    for(int i=0;i<H;i++){
        cin>>grid[i];
    }

    int mat[H+1][W+1];
    mat[0][0] = 1;
    for(int i=1;i<H;i++){
        if(grid[i][0]!='#')
            mat[i][0] = mat[i-1][0];
        else
            mat[i][0] = 0;
    }
    for(int i=1;i<W;i++){
        if(grid[0][i]!='#')
            mat[0][i] = mat[0][i-1];
        else
            mat[0][i] = 0;
    }
    for(int i=1;i<H;i++){
        for(int j=1;j<W;j++){
            if(grid[i][j]=='#') mat[i][j] = 0;
            else mat[i][j] = (mat[i-1][j]+mat[i][j-1])%mod;
        }
    }
    cout<<mat[H-1][W-1]<<endl;
}

int main()
{
    FASTIO
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}




Measured memory_bytes: 8596
#include <bits/stdc++.h>
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 
using namespace std;

const int N = 1e6 +3; 

int n , k ;
int arr[N];
 
int32_t main(){IOS;
	int test = 1; //cin >> test;
	while(test--){
		cin >> n >> k ;
		for(int i=0;i<n;i++){
			cin >> arr[i];
		}
		sort(arr,arr+n);
		if(k>=n){
			cout << 0 << endl; 
			return 0;
		}
		k = n-k;
		cout << max(0ll,accumulate(arr,arr+k,0ll)) << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return a*(ll)b%mod;}
void inc(int&a,int b){(a+=b)%=mod;}
int pow(int a,int b){
	int s=1;
	while(b){
		if(b&1)s=mul(s,a);
		a=mul(a,a);
		b>>=1;
	}
	return s;
}
vector<int>g[60];
int fac[210],rfac[210],k;
int C(int n,int k){return mul(fac[n],mul(rfac[k],rfac[n-k]));}
int dfn[60],low[60],stk[60],tp,M,ans;
set<int>s;
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int polya(int n){
	int i,s=0;
	for(i=1;i<=n;i++)inc(s,pow(k,gcd(i,n)));
	return mul(s,pow(n,mod-2));
}
void dfs(int x){
	int t,n,m;
	dfn[x]=low[x]=++M;
	stk[++tp]=x;
	for(int y:g[x]){
		if(!dfn[y]){
			dfs(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				s.clear();
				do{
					t=stk[tp--];
					s.insert(t);
				}while(t!=y);
				s.insert(x);
				n=s.size();
				m=0;
				for(int x:s){
					for(int y:g[x]){
						if(s.count(y))m++;
					}
				}
				m>>=1;
				if(m<n)ans=mul(ans,k);
				if(n==m)ans=mul(ans,polya(m));
				if(n<m)ans=mul(ans,C(m+k-1,k-1));
			}
		}else
			low[x]=min(low[x],dfn[y]);
	}
}
int main(){
	int n,m,i,x,y;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	fac[0]=1;
	for(i=1;i<=m+k;i++)fac[i]=mul(fac[i-1],i);
	rfac[m+k]=pow(fac[m+k],mod-2);
	for(i=m+k;i>0;i--)rfac[i-1]=mul(rfac[i],i);
	ans=1;
	for(i=1;i<=n;i++){
		if(!dfn[i])dfs(i);
	}
	printf("%d",ans);
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		long max = 0;
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextLong();
			max = Math.max(max, a[i]);
		}
		long half = 0;
		for(int i = 0; i < n; i++) {
			if(Math.abs(max / 2 - half) > Math.abs(max / 2 - a[i])) {
				half = a[i];
			}
		}
		System.out.println(max + " " + half);
	}

}


Measured memory_bytes: 55796
//----AUTHOR:kkdrummer----/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef    long long   ll;
typedef    long double   ld;
//typedef    unordered_set<ll>   usll;
//typedef    unordered_multiset<ll>   umsll;
typedef    multiset<ll>   msll;
typedef    set<ll>   sll;
typedef    vector<ll>   vll;
typedef    pair<ll,ll>   pll;
typedef    vector<pll>   vpll;
typedef    priority_queue<ll>   pqll;
typedef    vector<int>   vi;
typedef    set<int>   si;
typedef    multiset<int>   msi;
//typedef    unordered_multiset<int>   umsi;
//typedef    unordered_set<int>   usi;
typedef     pair<int,int>   pi;
typedef    vector<pi>   vpi;
typedef    set<pi>   spi;
typedef    priority_queue<int>   pqi;
typedef    tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>   ind_set;
typedef    tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>   ind_setll;
#define    in   insert
#define    fi   first
#define    se   second
#define    pb   push_back
#define    mp   make_pair
#define    be   begin
#define    en   end
#define    itr   iterator
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define    mo   1000000007
#define    inf  9223372036854775807
#define    ninf   -inf
#define    ima   2147483647
#define    imi   -ima
#define    oncnt    __builtin_popcount
#define    zerobegin   __builtin_clz
#define    zeroend   __builtin_ctz
#define    parity   __builtin_parity
#define    all(x)   x.be(),x.en()
#define    eps   1e-9
#define    coutd   cout<<setprecision(10)<<fixed
#define    mems(dp,x)   memset(dp,x,sizeof(dp))
const    ld   PI=3.14159265359;
inline ll modpow(ll x,ll n){if(n==0)return 1;if(n==1)return(x%mo);ll u=(modpow(x,n/2));u=(u*u)%mo;if(n%2!=0)u=(u*x%mo)%mo;return u;}
inline ll modinv(ll x){return modpow(x,mo-2);}
inline ll mmul(ll a,ll b){    if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll madd(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a+b>=mo)return(a+b)%mo;return(a+b);}
inline ll msub(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;return(((a-b)%mo+mo)%mo);}
inline ll mdiv(ll a,ll bb){if(a>=mo)a=a%mo;ll b=modinv(bb);if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll gcd(ll a,ll b){return __gcd(a,b);}

int main()
{
io
int testcases=1;//cin>>testcases;
while(testcases--)
{

int n;
cin>>n;
set<string> ss;
while(n--)
{
	string s;
	cin>>s;
	ss.in(s);
}
cout<<ss.size();










}return 0;}

Measured memory_bytes: 19240
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#define rep(i, n) for(int i=0;i<=n;i++)
using namespace std;
int main(){
	int n, y;
	cin>>n>>y;
	rep(i, n){
		rep(j, n){
			if(i+j>n)
				break;
			if(10000*i+5000*j+1000*(n-i-j)==y){
				cout<<i<<" "<<j<<" "<<n-i-j<<endl;
				return 0;
			}
		}
	}
	cout<<"-1 -1 -1"<<endl;
	return 0;
}


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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/4;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        int[] h = in.ni(n);
        int[] c = new int[n];
        Arrays.fill(c, inf);
        c[0]= 0;
        for (int i = 0; i < n-1; i++) {
            c[i+1] = Math.min(c[i+1], c[i]+Math.abs(h[i+1]-h[i]));
            if(i+2<n) c[i+2] = Math.min(c[i+2], c[i]+Math.abs(h[i+2]-h[i]));
        }
        out.println(c[n-1]);
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

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

int main(){
	int a,b,k;
	cin >> a >> b >> k;
	int num=0;
	for(int i=a; i>=1; i--){
		if(a%i==0 && b%i==0){
			num++;
			if(num==k){
				cout << i << endl;
				return 0;
			}
		}
	}

	return 0;
}



Measured memory_bytes: 384
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n=parseInt(readline())
    t=parseMap(split(readline()))
    m=parseInt(readline())
    for i in 1:m
        p,x=parseMap(split(readline()))
        ans=0
        for i in 1:n
            if i==p
                ans+=x
            else
                ans+=t[i]
            end
        end
        println(ans)
    end
end
main()

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

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


Measured memory_bytes: 3092
#include <iostream>
#include <cstdio>

using namespace std;

const int N=3000+5;

int n,a[N];
int m,b[N];
int dp[N][N];
int ans[N],sz=0;

string s,t;

int main()
{
    cin>>s>>t;
    n=s.size();
    m=t.size();
    for(int i=1;i<=n;i++)
    {
        a[i]=(s[i-1]);
    }
    for(int i=1;i<=m;i++)
    {
        b[i]=(t[i-1]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    int x=n;
    int y=m;
    while(x && y)
    {
        if(a[x]==b[y])
        {
            ans[++sz]=a[x];
            x--;
            y--;
        }
        else
        {
            if(dp[x][y]==dp[x-1][y])
            {
                x--;
            }
            else
            {
                y--;
            }
        }
    }
    for(int i=sz;i>=1;i--)
    {
        cout<<char(ans[i]);
    }
    cout<<"\n";
    return 0;
}


Measured memory_bytes: 35584
#include<stdio.h>

int main(void)
{
int A,B,K;

scanf("%d%d",&A,&B);

if(A<0) A = A*(-1);
if(B<0) B = B*(-1);

K=(A+B)/2;

if((A+B)%2==0)

printf("%d",K);

else
printf("IMPOSSIBLE");

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
int main()
{
    string s;
    cin >> s;
    int q;
    cin >> q;
    int cnt = 0;
    rep(i, q){
        int t;
        cin >> t;
        if (t == 1){
            cnt += 1;
            cnt %=2;
        }else{
            int f;
            char c;
            cin >> f >> c;
            if ((cnt + f)%2 == 0){
                s += c;
            }else s = c + s;
        }

    }
    if (cnt%2 == 1) reverse(all(s));
    cout << s << endl;
}

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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

void hawawa()
{
	int w, h, n;
	cin >> w >> h >> n;
	Vec<Vec<int>> info(w, Vec<int>(h, 1));
	while (n--) {
		int x, y, a;
		cin >> x >> y >> a;
		switch (a)
		{
		case 1:
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < h; j++) {
					info[i][j] = 0;
				}
			}
			break;
		case 2:
			for (int i = x; i < w; i++) {
				for (int j = 0; j < h; j++) {
					info[i][j] = 0;
				}
			}
			break;
		case 3:
			for (int i = 0; i < w; i++) {
				for (int j = 0; j < y; j++) {
					info[i][j] = 0;
				}
			}
			break;
		case 4:
			for (int i = 0; i < w; i++) {
				for (int j = y; j < h; j++) {
					info[i][j] = 0;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < w; i++) {
		for (int j = 0; j < h; j++) {
			ans += info[i][j];
		}
	}
	cout << ans << "\n";
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, N) for (int i=0; i<(int)N; i++)
#define rep1(i, N) for (int i=1; i<(int)N; i++)

using namespace std;

string s;

int main() {
  int counter = 0;
  cin >> s;
  int n = s.size();
  int last = (n+1)/2;
  rep(i, last) {
    if (s.substr(i,1) != s.substr(n-i-1,1)) counter++;
  }
  cout << counter;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [0]*q
for i in range(q):
    bc[i] = list(map(int,input().split()))

r = [0]*(10**5+1)
for i in range(n):
    r[a[i]] += 1
s = sum(a)
for b,c in bc:
    r[c] += r[b]
    s += (c-b)*r[b]
    r[b] = 0
    print(s)


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

int main(){
    ll n;
    cin>>n;
    ll cnt=1e18;
    ll t=pow(n,0.5);
    for(ll i=1;i<=t;i++){
        if(n%i!=0)continue;
        ll j=n/i;
        cnt=min(cnt,i+j-2);
    }
    cout<<cnt<<endl;
    return 0;
}

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

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

int main(){
    int h, w;
    std::cin >> h >> w;
    std::vector<std::vector<char>> stage(h, std::vector<char>(w));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++) std::cin >> stage[i][j];
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(stage[i][j] != '#') continue;
            int k;
            for(k = 0; k < 4; k++){
                if(i + dx[k] >= 0 && i + dx[k] < h){
                    if(j + dy[k] >= 0 && j + dy[k] < w){
                        if(stage[i + dx[k]][j + dy[k]] == '#') break;
                    }
                }
            }
            if(k == 4){
                std::cout << "No" << std::endl;
                return 0;
            }
        }
    }
    std::cout << "Yes" << std::endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]

for i in range(Q):
	min_s = 0
	max_s = A
	ind_s = (min_s + max_s) // 2
	
	while min_s < max_s:
		ind_s = (min_s + max_s) // 2
		if s[ind_s] > x[i]:
			max_s = ind_s
		else:
			min_s = ind_s + 1
	
	ind_s = (min_s + max_s) // 2
	
	min_t = 0
	max_t = B
	ind_t = (min_t + max_t) // 2
	
	while min_t < max_t:
		ind_t = (min_t + max_t) // 2
		if t[ind_t] > x[i]:
			max_t = ind_t
		else:
			min_t = ind_t + 1
	
	ind_t = (min_t + max_t) // 2
		
	if ind_s == A or ind_t == B:
		ptn1 = 3 * 10 ** 10
	else:
		ptn1 = max((s[ind_s] - x[i]), (t[ind_t] - x[i]))
		
	if ind_s == 0 or ind_t == 0:
		ptn2 = 3 * 10 ** 10
	else:
		ptn2 = max((x[i] - s[ind_s - 1]), (x[i] - t[ind_t - 1]))
		
	if ind_s == A or ind_t == 0:
		ptn3 = 3 * 10 ** 10
	else:
		ptn3 = min(2 * (s[ind_s] - x[i]) + (x[i] - t[ind_t - 1]), (s[ind_s] - x[i]) + 2 * (x[i] - t[ind_t - 1]))
		
	if ind_s == 0 or ind_t == B:
		ptn4 = 3 * 10 ** 10
	else:
		ptn4 = min(2 * (x[i] - s[ind_s - 1]) + (t[ind_t] - x[i]), (x[i] - s[ind_s - 1]) + 2 * (t[ind_t] - x[i]))
		
	print(min(ptn1, ptn2, ptn3, ptn4))

Measured memory_bytes: 85596
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9)+7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	ll x; cin >> x; ll out = 0;
	out += (ll)2*(x / (ll)11); x %= 11;
	if (x > 0)out++;
	if (x > 6)out++;
	cout << out << endl;
	return 0;
}

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


long long n;

void dfs(string s, char mx){
    if(s.size() == n){
        printf("%s\n", s.c_str());
    }
    else{
        for(char c = 'a'; c <= mx; c++){
            dfs(s+c, ((c == mx) ? (char)(mx + 1): mx));
        }
    }
}

int main(){
    cin >> n;
    dfs("", 'a');
    return 0;
}

Measured memory_bytes: 3616
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N, K = sc.nextInt()
    val X = Array.fill(N)(sc.nextInt())

    // K個のろうそく の距離 + どちらかの端点への距離 が最小のもの
    def solve(N: Int, K: Int, X: Array[Int]): Int = {
      val upper = N - K
      def loop(i: Int, min: Int): Int =
        if (i <= upper) {
          val width = X(i + K - 1) - X(i)
          val toStart = X(i + K - 1).abs min X(i).abs
          loop(i + 1, min min (width + toStart))
        } else min
      loop(0, Int.MaxValue)
    }

    println(solve(N, K, X))
  }

}


Measured memory_bytes: 51948
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int d;
	int w = sc.nextInt();
	int n = sc.nextInt();
	int[] line;
	int[] a;
	line = new int[w];
	a = new int[2];
	for(int i=0;i<w;i++) line[i] = i+1;
	for(int i=0;i<n;i++){
	    String s = sc.next();
	    int l = s.length();
	    int k = 0, f=0, x=0;
	    for(int j=0;j<l;j++){
		char c = s.charAt(j);
		if('0' > c || c > '9'){
		    a[k] = Integer.parseInt(s.substring(x,j));
		     k++;
		     f=0;
		}else{
		    if(f==0){
			x=j;
			f=1;
		    } 
		}
	    }
	    a[1] = Integer.parseInt(s.substring(x,l));
	    d = line[a[0]-1];
	    line[a[0]-1] = line[a[1]-1];
	    line[a[1]-1] = d;
	}
	for(int i=0;i<w;i++) System.out.println(line[i]);
    }
}

Measured memory_bytes: 26104
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>

using namespace std;

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

using ll = long long;
using P = pair<int, int>;

const long long MOD = 1e9+7;

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; }

template<class T>
istream& operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

int main() {
    string s;
    cin >> s;
    vector<int> ds(s.size());
    rep(i, s.size()) ds.at(i) = s.at(i) - '0';
    int n = ds.size();
    
    // dp[i][j][k] i := 桁, j := 0: 一致 1:不一致, k := 3,5,7のフラグ
    ll dp[n + 1][2][1 << 3];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    int v[3] = {3, 5, 7};
    
    rep(i, n) {
        dp[i + 1][1][0] = 1;
        rep(k, 1 << 3) {
            rep(l, 3) {
                if (ds[i] < v[l]) {
                    dp[i + 1][1][k | (1 << l)] += dp[i][1][k];
                }
                else if (v[l] == ds[i]) {
                    dp[i + 1][1][k | (1 << l)] += dp[i][1][k];
                    dp[i + 1][0][k | (1 << l)] += dp[i][0][k];
                }
                else {
                    dp[i + 1][1][k | (1 << l)] += dp[i][0][k] + dp[i][1][k];
                }
            }
        }
    }
    
    cout << dp[n][0][(1 << 3) - 1] + dp[n][1][(1 << 3) - 1] << endl;
}

Measured memory_bytes: 256
from fractions import gcd

T = int(input())

for i in range(T):
  A, B, C, D = map(int, input().split())
  if A < B or D < B:
    print('No')
  else:
    a = A % B
    if a > C:
      print('No')
    else:
      if C >= B:
        print('Yes')
      else:
        g = gcd(B, D)
        if B - g + A%g > C:
          print('No')
        else:
          print('Yes')

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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

#define vi vector <lli>
#define loop(num) for (lli i = 0 ; i < num ; i ++ )
#define loopcin(num , ar ) for (lli i = 0 ; i < num ; i ++ ) {cin >> ar [i] ;}
#define loopcout(num , ar) for (lli i = 0 ; i < num ; i ++ ) {cout << ar [i] << ' '; }

#define forr(num1 , num2) for (lli i = num1 ; i < num2 ; i ++ )
#define forrcin(num1 , num2 , ar ) for (lli i = num1 ; i < num2 ; i ++ ) {cin >> ar [i] ;}
#define forrcout(num1 , num2 , ar) for (lli i = num1 ; i < num2 ; i ++ ) {cout << ar [i] << ' '; }

#define D2forrcin(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cin >> A[i][j] ;}}
#define D2forrcout(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cout << A[i][j] << ' ' ;}cout << endl ;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define F first
#define S second

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main ()
{
    fastio
    st s ;
  cin >> s ;
  loop(s.size())
    if (s[i] == ',')
      s[i] = ' ' ;
  cout << s ;
    return 0 ;
}

/*___________________________________________________________________functions___________________________________________________________________________*/



Measured memory_bytes: 256
#include <stdio.h>
#include <float.h>
 
int main(void)
{
    float x[4], y[4], AB, CD;
    int i, j, n;
     
    scanf("%d", &n);
    for (i = 0; i < n; i++){
        for (j = 0; j < 4; j++){
            scanf("%f %f", &x[j], &y[j]);
        }
         
        if (x[1] == x[0]){
            AB = DBL_MAX;
        }
        else {  
            AB = (y[1] - y[0]) / (x[1] - x[0]);
        }
         
        if (x[3] == x[2]){
            CD = DBL_MAX;
        }
        else {
            CD = (y[3] - y[2]) / (x[3] - x[2]);
        }
         
        if (AB == CD){
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
     
    return (0);
}


Measured memory_bytes: 2032
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n = int(input())
    a = input_list()
    if list(set(a)) == [1]:
        print('No')
        exit()

    divide_counters = []
    for v in a:
        dt = divide_two(v)
        if dt == 0:
            divide_counters.append(1)
        elif dt == 1:
            divide_counters.append(2)
        else:
            divide_counters.append(4)
    
    if set(divide_counters) == {1, 4}:
        if divide_counters.count(1) <= divide_counters.count(4) + 1:
            print('Yes')
            exit()
        else:
            print('No')
            exit()
    if divide_counters.count(1) <= divide_counters.count(4):
        print('Yes')
    else:
        print('No')
        
def divide_two(n):
    c = 0
    while True:
        if c >= 2:
            break
        if n % 2 != 0:
            break
        n //= 2
        c += 1
    return c

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


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

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

const int N = 100010;
vector<int> g[N], g2[N];

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

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;

        g[u].push_back(v);
    }

    int s, t;
    scanf("%d %d", &s, &t);
    s--;
    t--;

    queue<ii> q;
    bool seen[N] = {false};
    q.push(ii(s, 0));
    seen[s] = true;
    int ans = -1;
    while (q.size() > 0) {
        auto cur = q.front();
        q.pop();

        if (cur.first == t) {
            ans = cur.second;
            break;
        }

        for (auto v : g[cur.first]) {
            for (auto v1 : g[v]) {
                if (v1 == v) {
                    if (seen[v1])
                        continue;
                    seen[v1] = true;

                    if (v1 == t) {
                        ans = cur.second + 1;
                        goto done;
                    }

                    q.push(ii(v1, cur.second + 1));

                    continue;
                }

                for (auto v2 : g[v1]) {
                    if (seen[v2])
                        continue;
                    seen[v2] = true;

                    if (v2 == t) {
                        ans = cur.second + 1;
                        goto done;
                    }

                    q.push(ii(v2, cur.second + 1));
                }
            }
        }
    }

done:
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 9984
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct s {
	int t, f, c;
};

int main(void){
	int l; cin >> l;
	int n=0; vector
 v;
	while (l>=1<<n) n++;
	for(int i=0; i<n-1; i++) {
		v.push_back({i+1, i+2, 0});
		v.push_back({i+1, i+2, 1<<i});
		if (l!=(1<<i) && l & (1<<i)) v.push_back({i+1, n, l - (l&(1<<i))});
		l &= ~(1<<i);
	}
	int m = v.size();
	cout << n << " " << m << endl;
	for(int i=0; i<m; i++) {
		cout << v[i].t << " " << v[i].f << " " << v[i].c << endl;
	}
}

Measured memory_bytes: 256
//#define TIMER_
#include <bits/stdc++.h>
using namespace std;
#define rep(i,r) for(int i = 0; i < (r); i++)
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using ll = long long;
using ull = unsigned long long;
using vvi = vector<vector<int>>;
const int maxn = 1e5 + 10;
const int maxm = 2e5 + 10;

struct edge {
  int to, from;
  int best;
  edge(int t, int f) {to=t;from=f;}
};

int main() {
  fastio;
  int n, m;
  cin >> n >> m;
  vector<vector<edge>> g(n+1);
  int a, b;
  for (int i = 0; i < m; i ++ ) {
    cin >> a >> b;
    g[a].push_back({b,a});
    g[b].push_back({a,b});
  }

  vector<int> visit(n+1, 0);
  vector<int> res(n+1);
  queue<int> q;
  visit[1] = true;
  q.push(1);
  while(!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
      int top = q.front(); q.pop();
      for (auto e : g[top]) {
        if (!visit[e.to]) {
          visit[e.to] = true;
          res[e.to] = top;
          q.push(e.to);
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (visit[i] == false) {
      cout << "No" << endl; return 0;
    }
  }

  cout << "Yes\n";
  for (int i = 2; i <= n; i++) {
    cout << res[i] << '\n';
  }
  
  #ifdef TIMER_
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  #endif
}


Measured memory_bytes: 14248
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
#include <iomanip>
#define M_PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
int now = 0;

const int MAX = 510000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
struct edge {
	int t;
	edge(int _t) : t(_t) {}
};
bool use[100010];


vector<edge> te[100010];
vector<edge> fe[100010];
int t[64];
int d[100100];
ll rec(int num) {
	if (num == 0) return 0;
	return rec(num - 1) + num;
}
ll gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
void Solve() {

	int n, m;
	cin >> n;
	
	ll res = 0;
	for (size_t i = 0; i < n; i++)
	{
		ll a;
		cin >> a;
		if (i == 0) {
			res = a;
		}
		else {
			res = gcd(res, a);
		}
	}
	cout << res << endl;
}


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



Measured memory_bytes: 6016
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <math.h>
#include <memory.h>
#include <vector>
using namespace std;
const int MAXN=105;
int xyh[MAXN][5],n;
int main(){
	cin>>n;
	int i,j,k,x,f,s,t;
	for(i=1;i<=n;i++)
		cin>>xyh[i][1]>>xyh[i][2]>>xyh[i][3];
	s=1;
	while(xyh[s][3]==0)s++;
	for(i=0;i<=100;i++){
		for(j=0;j<=100;j++){
			x=xyh[s][3]+abs(xyh[s][1]-i)+abs(xyh[s][2]-j);
			f=1;
			for(k=1;k<=n;k++){
				t=max(0,x-abs(xyh[k][1]-i)-abs(xyh[k][2]-j));
				if(xyh[k][3]!=t){
					f=0;break;
				}
			}
			if(f==1){printf("%d %d %d",i,j,x);return 0;}
		}
	}
	return 0;
}


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


int num[26];
int n;
int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		string s;
		cin >> s;
		int cc[26];
		memset(cc, 0, sizeof(cc));
		for (int j = 0; j < s.size(); j++){
			cc[s[j] - 'a']++;
		}

		if (i == 0){
			for (int j = 0; j < 26; j++){
				num[j] = cc[j];
			}
		}
		else{
			for (int j = 0; j < 26; j++){
				num[j] = min(num[j], cc[j]);
			}
		}
	}
	for (int j = 0; j < 26; j++){
		while (num[j]--){
			char f= j + 'a';
			cout << f;
		}
	}
	puts("");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,a[N];
signed main()
{
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);
	int p=0;
	for (int i=1;i<=n;i++) if (a[i]<0) p=i;
	p=max(p,1);p=min(p,n-1);
	//让前p个被减掉
	int s=0;
	for (int i=1;i<=p;i++)  s-=a[i];
	for (int i=p+1;i<=n;i++) s+=a[i];
	cout<<s<<endl;
	for (int i=p+1;i<n;i++)
	{
		printf("%d %d\n",a[p],a[i]);
		a[p]-=a[i];
	}
	printf("%d %d\n",a[n],a[p]);a[n]-=a[p];
	for (int i=1;i<p;i++)
	{
		printf("%d %d\n",a[n],a[i]);
		a[n]-=a[i];
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

Measured memory_bytes: 4148
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
#define INF 999999999
typedef long long ll;
using namespace std;
int main() {
    int H, W;
    cin >> H >> W;
    string s[H];
    REP(i, H) cin >> s[i];
    REP(i, H) {
        REP(j, W) {
            int cnt = 0;
            if(s[i][j]=='.') {
                for(int k = i-1; k <= i+1; k++) {
                    for(int l = j-1; l <= j+1; l++) {
                        if(k < 0 || l < 0) continue;
                        if(k == H || l == W) continue;
                        if(s[k][l] == '#') cnt++;
                    }
                }
                s[i][j] = (cnt + '0');
                cnt = 0;
            }
        }
        cout << s[i] << endl;
    }
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <time.h>
//#include <math.h>
#include <cmath>
#include <fstream>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <stdlib.h>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <bitset>

#pragma comment(linker, "/STACK:36777216")
using namespace std;

#define flu fflush(stdout)
#define gg return 0
#define mp make_pair

typedef long double ptype;

long long mod = /*27449*//*998244353*/ 1e9 + 7 /*1e9 + 9*/;
int inf = 1e9;
double eps = 1e-7;
long double pi = acosl(-1);
ifstream in("input.txt");
ofstream out("output.txt");

void solve()
{
	long long x, k, d;
	cin >> x >> k >> d;
	if (x < 0)
	{
		long long dist = -x;
		long long v = dist / d;
		if (v < k)
		{
			x += v * d;
			k -= v;
			if (k & 1)
			{
				cout << x + d;
			}
			else
			{
				cout << abs(x);
			}
		}
		else
		{
			cout << abs(x + d * k);
		}
	}
	else if (x == 0)
	{
		if (k & 1)
		{
			cout << d;
		}
		else
		{
			cout << 0;
		}
	}
	else
	{
		long long dist = x;
		long long v = dist / d;
		if (v < k)
		{
			x -= v * d;
			k -= v;
			if (k & 1)
			{
				cout << abs(x - d);
			}
			else
			{
				cout << x;
			}
		}
		else
		{
			cout << abs(x - d * k);
		}
	}
}

int main()
{
	cout << setprecision(2) << fixed;
	cin.tie();
	cout.tie();
	//freopen("input.txt", "r", stdin);
	int t;
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
	gg;
}

Measured memory_bytes: 3644
#include <iostream>
#include <complex>

using namespace std;

typedef complex<double> P;

#define EPS (1e-10)
#define EQ(a, b) (abs((a) - (b)) < EPS)
#define EQV(a, b) ((EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()))

double cross(P a, P b) 
{
    return (a.real() * b.imag() - a.imag() * b.real());
}

bool is_parallel(P a1, P a2, P b1, P b2) 
{
    return EQ(cross(a1 - a2, b1 - b2), 0.0);
}


int main()
{
    int num;
    double  x1, y1, x2, y2, x3, y3, x4, y4;
    
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        
        if (is_parallel(P(x1, y1), P(x2, y2), P(x3, y3), P(x4, y4)))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> p(m);
  rep(i, m) cin >> p[i].second >> p[i].first;
  sort(p.begin(), p.end());
  int cur = p[0].first - 1;
  int ans = 1;
  rep(i, m) {
    if(p[i].second <= cur) {
      continue;
    } else {
      cur = p[i].first - 1;
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4052