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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define rep(i, x, y) for(decltype(y) i = (x) - ((x) > (y)); i != (y) - ((x) > (y)); i += 1 - 2 * ((x) > (y)))
#define trav(i,a) for(auto& (i) : (a))
#define all(a) (a).begin(),(a).end()
#define sz(a) int((a).size())
#define clr(a,x) memset((a),(x),sizeof(a)) // array (0,-1)
#define dbg(x) cerr << "STDERR => " << __LINE__ << ": " << #x << " = " << (x) << "  :(\n";
#define pb push_back
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void cpuTime() { cerr << "cpu time : " << double(clock())/CLOCKS_PER_SEC << "\n"; return; }
using ll = long long;
using ull = unsigned long long;
using F = float;
using D = double;
using vi = vector<int>;
using pii = pair<int,int>;


void solve(){

    int n;
    cin >> n;
    ll k;
    cin >> k;

    vi a(n, 0);
    int tmp;
    rep(i,0,n){
        cin >> tmp;
        a[i] = tmp-1;
    }

    vi isVisited(n, -1);
    int cnt = 0, s = 0;
    while(1){
        if(isVisited[s] != -1) break;
        isVisited[s]=cnt;
        ++cnt;
        s=a[s];
    }

    int cycle = cnt-isVisited[s];
    if(k > 10000000){
        k -= isVisited[s];
        k = (k+cycle)%cycle+isVisited[s];
    }

    s=0;
    while(k--){
        s=a[s];
    }

    cout << s+1 << "\n";

    return;
}

/*
 read the question carefully ( what're the exact constraints? )
 look out for SPECIAL CASES (n=1?) and OVERFLOW (ll vs int?) ARRAY OUT OF BOUNDS
 Check datatypes
*/
int main(){

    fast_io;
    int t=1;
    // cin >> t;

    while(t--){
        solve();
    }

    cpuTime();
return 0;
}


Measured memory_bytes: 4784
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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 MAX = 2000010;
ll 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;
    }
}

ll comb(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;
}

ll calc(int r, int c) {
    return comb(r+c+2, r+1) - 1;
}

int main() {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    r1--; c1--;

    COMinit();
    ll ans = 0;
    ans += calc(r2, c2);
    ans -= calc(r1, c2);
    ans -= calc(r2, c1);
    ans += calc(r1, c1);
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}


Measured memory_bytes: 47104
#include <stdio.h>

int group(int x) {
	switch (x){
		case 1: case 3: case 5: case 7: case 8: case 10: case 12:
			return 1;
		case 4: case 6: case 9: case 11:
			return 2;
		case 2:
			return 3;
		default:
			return 0;
	}
}

int main(void) {
	int x, y;
	if (scanf("%d%d", &x, &y) != 2) return 1;
	puts(group(x) == group(y) ? "Yes" : "No");
	return 0;
}


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

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
*/

using namespace std;

#if DEBUG && !ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(...)
#endif

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

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define ff first
#define ss second
#define trav(a, x) for(auto& a : x) 
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
const ll INF = 1e18;
const int mod = 1e9 + 7;
ll gcd(ll a,ll b){if (a==0) return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return a*(b/gcd(a,b));}
ll Abs(ll a){if(a>0)return a;return -a;}
ll Ceil(ll a,ll b){if(a%b==0)return a/b;else return a/b+1;}
double Abs(double a){if(a>0)return a;return -a;}

//*X.find_by_order(2) element at index=2
//X.order_of_key(1) how many elements strictly less than 1

//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_NOde_update> 

inline int pow_(ll x, ll y,ll p){
  int r = 1; while(y){if(y & 1) r = r * x % p; y >>= 1; x = x * x % p;} return r;
}
inline int inv_(int x){return pow_(x, mod - 2, mod);}
inline int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}
inline int mul(int a, int b){return a * 1LL * b % mod;}
inline int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}

int main()
{
    #ifdef LOCAL_TEST
    freopen("in.txt","r",stdin);
    //freopen("out.txt", "w", stdout);
    #else
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    #endif
    ll k,x;
    cin>>k>>x;
    vector<ll> v;
    for(int i=x;i<=x+k-1;i++){
        v.pb(i);
    } 

    for(int i=x-1;i>=x-k+1;i--){
        v.pb(i);
    }
    sort(all(v));
    for(int i=0;i<v.size();i++)cout << v[i] << " ";
    cout << "\n";
    return 0;   
}

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

int main() {
	int n;
	int flag;
	int count=0;
	cin>>n;
	int a[n];
	for(int j=0;j<n;j++){
		cin>>a[j];
	}
	
	flag=1;
	while(flag){
		flag=0;
		for(int i=n-1;i>0;i--){
			if(a[i]<a[i-1]){
				swap(a[i],a[i-1]);
				flag=1;
				count++;
			}
		}	
	}
	
	cout<<a[0];
	for(int k=1;k<n;k++){
		cout<<' '<<a[k];
	}
	cout<<'\n'<<count<<endl;
	
	return 0;
}

Measured memory_bytes: 1164
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 2e5 + 5;
const int mod = 998244353;
const int inf = 1e9 + 9;

struct fork{
    int le, ri, v;
};

int c, ver[N];
pi p[N];
fork t[40*N];

bool cmp(pi &a, pi &b){
    return a.se < b.se;
}

void build(int nd, int s, int e){
    t[nd].v = 0;
    if(s == e)
        return;
    int md = (s + e) >> 1;
    t[nd].le = ++c;
    t[nd].ri = ++c;
    build(t[nd].le, s, md);
    build(t[nd].ri, md + 1, e);
}

void upd(int cur, int pre, int s, int e, int id){
    if(s == e){
        t[cur].v++;
        return;
    }    
    int md = (s + e) >> 1;
    if(id <= md){
        t[cur].le = ++c;
        t[cur].ri = t[pre].ri;
        upd(t[cur].le, t[pre].le, s, md, id);
    }
    else{
        t[cur].le = t[pre].le;
        t[cur].ri = ++c;
        upd(t[cur].ri, t[pre].ri, md + 1, e, id);
    }
    t[cur].v = t[t[cur].le].v + t[t[cur].ri].v;
}

int query(int cur, int pre, int s, int e, int l, int r){
    if(s > r || e < l)
        return 0;
    if(s >= l && e <= r)
        return t[cur].v - t[pre].v;
    int md = (s + e) >> 1;
    return query(t[cur].le, t[pre].le, s, md, l, r)
            + query(t[cur].ri, t[pre].ri, md + 1, e, l, r);
}

ll power(int a, int b){
    ll ans = 1;
    while(b){
        if(b&1)
            ans = (1LL*ans*a) % mod;
        a = (1LL*a*a) % mod;
        b >>= 1;
    }
    return ans;
}
 
signed main() {
    IOS;
    #ifdef LOCAL
        freopen("input.txt","r", stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n;  cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i].fi >> p[i].se;
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++)
        p[i].fi = i;
    sort(p + 1, p + n + 1, cmp);
    for(int i = 1; i <= n; i++)
        p[i].se = i;
    sort(p + 1, p + n + 1);
    ver[0] = ++c;
    build(ver[0], 1, n);
    for(int i = 1; i <= n; i++){
        ver[i] = ++c;
        upd(ver[i], ver[i-1], 1, n, p[i].se);
    }
    ll ans = n;
    for(int i = 1; i <= n; i++){
        ll lb = query(ver[i], ver[0], 1, n, 1, p[i].se-1);
        ll lt = query(ver[i], ver[0], 1, n, p[i].se+1, n);
        ll rt = query(ver[n], ver[i], 1, n, p[i].se, n);
        ll rb = query(ver[n], ver[i], 1, n, 1, p[i].se);
        lb = power(2, lb) - 1;
        lt = power(2, lt) - 1;
        rt = power(2, rt) - 1;
        rb = power(2, rb) - 1;
        ans = (ans + lb + lt + rt + rb) % mod;
        ll y = (lb*rt) % mod;
        ll z = (lt*rb) % mod;
        ll x = (y*z) % mod;
        ans = (ans + 2*x + 2*y + 2*z) % mod;
        ans = (ans + lt*rt + lb*rb) % mod;
        ans = (ans + lb*lt + rb*rt) % mod;
        ans = (ans + 2*y*(rb + lt) + 2*z*(rt + lb)) % mod;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 53376
#![allow(unused)]

//input
use proconio::input;
use proconio::marker::{Bytes, Chars};
//use std::io::Read;

//collections
//use std::collections::BTreeMap;
//use std::collections::BTreeSet;
//use std::collections::HashMap;
//use std::collections::HashSet;
//use std::collections::VecDeque;
//use std::collections::BinaryHeap;

//use std::cmp::*;

fn main() {
    input! {
        n: usize,
        m: usize,
        x: i64,
        ca:[(i64,[i64;m]);n],
    }

    let mut bits = vec![vec![]; 1 << n];
    for i in 0..1 << n {
        for j in 0..n {
            if (1 << j) & i != 0 {
                bits[i].push(j);
            }
        }
    }
    //println!("{:?}", bits);

    let mut ans = -1i64;

    'outer: for i in 0..1 << n {
        let mut t = 0i64;
        let mut rikai = vec![0i64; m];
        for j in 0..bits[i].len() {
            t += ca[bits[i][j]].0;
            for k in 0..m {
                rikai[k] += ca[bits[i][j]].1[k];
            }
        }
        for j in 0..m {
            if rikai[j] < x {
                continue 'outer;
            }
        }
        if ans == -1 || t < ans {
            ans = t;
        }
    }

    println!("{}", ans);
}


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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	lnt N, A[200000]; cin >> N;
	map<lnt, lnt> B;
	REP(i, N){
		cin >> A[i];
		B[i+1-A[i]]++;
	}
	lnt ans = 0;
	REP(i, N){
		ans += B[i+1+A[i]];
		if(i+1-A[i] == i+1+A[i]) ans--;
	}
	cout << ans << ln;
}

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

typedef long long int ll;

int main(){
  ll N,A,B,sum;
  cin >> N >> A >> B;
  sum = 0;
  ll pre_x = 0;
  for(int i = 0 ; i < N ; i++){
    ll x;
    cin >> x;
    if(i){
      ll cost = (x - pre_x)*A;
      if(cost > B)sum += B;
      else sum += cost;
    }
    pre_x = x;
  }
  cout << sum << endl;
  return 0;
}


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

long long ans;
string s;
long long cnt[200200][26];

int main(){
	cin>>s;
	long long l=s.length();
	memset(cnt,0,sizeof cnt);
	ans=(l-1)*l/2;
	cnt[0][s[0]-'a']++;
	for (int i=1;i<l;i++){
		ans-=cnt[i-1][s[i]-'a'];
		for (int j=0;j<26;j++) cnt[i][j]=cnt[i-1][j];
		cnt[i][s[i]-'a']++;
	}
	cout<<ans+1<<endl;
	return 0;
}

Measured memory_bytes: 41220
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
count = {}
cmax = 0
for i in range(n):
    s = input()
    c = count.get(s,0)+1
    cmax = max(c,cmax)
    count[s] = c
ans = sorted([kv[0] for kv in count.items() if kv[1] == cmax])
for item in ans:
    print(item)

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

int main(){
    double L; 
    cin >> L;

    double volum=0;
    volum=L/3*L/3*L/3;
    printf("%.7f\n", volum);
    return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <limits.h>
#include <float.h>
#include <numeric>
#include <queue>

using namespace std;

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

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return pow(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}

priority_queue<P, vector<P>, greater<P>> q;
set<string> se;

int main(){
    string s;   cin >> s;
    int K; cin >> K;
    for(int i = 0; i < s.length(); i++){
        q.push(P(s.substr(i, 1), i));
    }

    while(se.size() < K){
        P xx = q.top();
        auto it = se.find(xx.first);
        if(it == se.end()) {
            // cout << xx.first << endl;
            se.insert(xx.first);
            if (se.size() == K) {
                cout << xx.first << endl;
                break;
            }
        }
        int xxx = xx.second + xx.first.length() + 1;
        if (xx.second + xx.first.length() + 1 <= s.length()) {
            q.push(P(s.substr(xx.second, xx.first.length() + 1), xx.second));
        }
        q.pop();
    }

    return 0;
}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

one = a.count(1)
two = a.count(2)
three = a.count(3)

dp = [[[-1] * 301 for _ in range(301)] for _ in range(301)]

def dfs(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]

    if i == 0 and j == 0 and k == 0:
        return 0.0

    res = 0.0

    if i > 0:
        res += dfs(i - 1, j, k) * i
    if j > 0:
        res += dfs(i + 1, j - 1, k) * j
    if k > 0:
        res += dfs(i, j + 1, k - 1) * k
        
    res += N

    res /= i + j + k

    dp[i][j][k] = res
    return res

res = dfs(one, two, three)

print(res)


Measured memory_bytes: 398068
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int main(){
  int n,c,k;
  cin>>n>>c>>k;
  vector<int> t(n);
  REP(i,n){
    cin>>t[i];
  }
  sort(t.begin(),t.end());
  int ans=0;
  int limit=t[0]+k;
  int index=0;
  int cnt=0;
  while(index<n){
    if(t[index]<=limit && cnt<c){
      index++;
      cnt++;
      continue;
    }else{
      ans++;
      limit = t[index]+k;
      cnt = 1;
      index++;
    }
  }
  ans++;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
def is_biparate(links):
    colors = [-1] * n
    colors[0] = 0
    q = [(0, 0)]
    visited = set()
    cnt = 0
    while q:
        v, c = q.pop()
        if v in visited:
            if colors[v] != c:
                return False
            continue
        visited.add(v)
        colors[v] = c
        cnt += c
        for u in links[v]:
            q.append((u, c ^ 1))
    return cnt


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

bp1 = is_biparate(links)
if is_biparate(links):
    max_m = bp1 * (n - bp1)
else:
    max_m = n * (n - 1) // 2
print(max_m - m)


Measured memory_bytes: 44276
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	n := getInt()
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		a := getInt()
		m[a]++
	}

	ans := 0
	for _, cnt := range m {
		if cnt%2 == 1 {
			ans++
		}
	}
	fmt.Fprintln(wr, ans)
}

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

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func getRunes() []rune {
	return []rune(getString())
}


Measured memory_bytes: 7296
using System;
using System.Linq;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
      
     int N=int.Parse(Console.ReadLine());
      string[] str=Console.ReadLine().Split(' ');
      int[] dif=str.Select(int.Parse).ToArray();
      Array.Sort(dif);
      Console.WriteLine(dif[N/2]-dif[N/2-1]);
     
    }
     
  }

}
  

Measured memory_bytes: 35868
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mxe max_element
#define mne min_element
#define bg begin()
#define nd end()
#define u unsigned
 
void swap(int &a,int &b)
{
    int t=a;
    a=b;
    b=t;
    return ;
}





int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t,n,m;
    cin>>n;
    
    u ll sum=0;
    
    vector<u ll> v(n);
    unordered_map<u ll,u ll> mp;
    for(int i=0;i<n;i++){
        cin>>v[i];
        mp[v[i]]++;
        sum+=v[i];
    }
    
    cin>>m;
    
        
    for(int i=0;i<m;i++)
    {
        u ll a,b;
        cin>>a>>b;
        // v[mp[a]]=b;
        // for(auto x:mp[a])
        sum+=b*(mp[a]);
        sum-=a*mp[a];
        mp[b]+=mp[a];
        mp[a]=0;
        
        cout<<sum<<endl;
    }
    
    
    
    
    return 0;
}








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

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

  vector<double> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v.at(i);    //データ取得
  }
  sort(v.begin(), v.end());     //小さい順になった
  reverse(v.begin(), v.end());    //大きい順になった
  
  for (int i = 0; i < N-1; i++) {
    v.at(N-i-2) = ( v.at(N-i-1)+v.at(N-i-2) ) / 2.0;
  }
      
  cout << fixed << setprecision(10);
  cout << v.at(0) << endl;
 
}


Measured memory_bytes: 256
// Problem : E - Sequence Sum
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

/*

WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!

Falling down is an accident, Staying down is a choice.

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<long,long> pl;
typedef pair<ll,ll> pll;
typedef vector<long> vl;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef unordered_map<ll,ll> umll;

#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define REV(i,a,b) for(long long i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define tc ll tests;cin>>tests;while(tests--)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
#define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
#define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
#define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
#define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define newl cout<<"\n"
#define mod 1000000007
#define INF LLONG_MAX/2

int main()
{
    io;
    
    ll n,x,m,ans=0;
    cin>>n>>x>>m;
    
    vb vis(m+1);
    vll a;
    
    ll p=x*x;
    while(!vis[p%m])
    {
    	a.pb(p%m);
    	vis[p%m]=true;
    	p=p%m;
    	p*=p;
    }
    
    ll j=0;
    FOR(i,0,a.size())
    {
    	if(a[i]==p%m)
    	{
    		j=i;//cycle start end at j
    		break;
    	}
    }
    
    ans+=x;
    n--;
    FOR(i,0,min(n,j))
    {
    	ans+=a[i];
    	n--;
    }
    //cout<<n;newl;
    ll cycle=0;
    FOR(i,j,a.size())
    {
    	cycle+=a[i];
    }
    ll sz=(ll)a.size()-j; //size of cycle 
    
    ans+=cycle*(n/sz);
    n=n%sz;
    FOR(i,j,j+n)
    {
    	ans+=a[i];
    }
    
    cout<<ans;
    
    return 0;
}



Measured memory_bytes: 3816
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void) {
	int n;
	int d[100000];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &d[i]);
	}
	if (n % 2 == 1) {
		printf("0");
		return 0;
	}
	else {
		sort(d, d + n);
		int ans;
		ans = d[((n - 1) / 2) + 1] - d[(n - 1) / 2];
		printf("%d", ans);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
  int width, height;
  
  while(true) {
    cin >> height >> width;
    
    if(height == 0 && width == 0) {
      break;
    }
    
    for(int i = 0; i < height; i++) {
      string rect(width, '#');
      for(int j = (i + 1) % 2; j < width; j += 2) {
        rect[j] = '.';
      }
      cout << rect << endl;
    }
    cout << endl;
  }
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll x;
    cin>>x;
   ll z=100.0;
    ll yr=0;
    while(z<x)
    {
    	z+=z/100;
    	//cout<<z;
    	yr++;
	}
    cout<<yr<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#define MAX 101

main(){
  int i, j, m, k, value;
  int n;
  int G[MAX][MAX];
  scanf("%d",&n);

  for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++){

      G[i][j] = 0;

    }
  }

  for(i = 1; i <= n; i++){

    scanf("%d %d", &k, &m);

    for(j = 1; j <= m; j++){

      scanf("%d",&value);

      G[i][value] = 1;
    }
  }


 
 for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++){

      printf("%d",G[i][j]);

      if(j < n)printf(" ");
    }
    printf("\n");
 }
 return 0;
}

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

using namespace std;

int main(void) {
	int N;
	cin >> N;
	int p;
	vector<int> len;
	for (int i = 0; i < N; ++i) {
		cin >> p;
		if (((i+1)-p) == 0) {
			len.push_back(i);
		}
	}
	int res = 0;
	for (size_t i = 0; i < len.size(); ++i) {
		++res;
		if (i < len.size()-1 && abs(len[i]-len[i+1]) == 1) {
			++i;	
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 892
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

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

const int N = 1e5 + 10, inf = 1e9 + 42;

vector<pii> intervals;
pii pref[N], suff[N];

ll get(pii v);

int main() {
	fast_cin();
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int l, r;
		cin >> l >> r;
		intervals.pb({r, l});
	}
	sort(intervals.begin(), intervals.end());
	pref[0] = {intervals[0].second, intervals[0].first};
	for (int i = 1; i < n; ++i) {
		pref[i] = pref[i - 1];
		pref[i].first = max(pref[i].first, intervals[i].second);
		pref[i].second = min(pref[i].second, intervals[i].first);
	}
	suff[n] = {-inf, inf};
	for (int i = n - 1; i >= 0; --i) {
		suff[i] = suff[i + 1];
		suff[i].first = max(suff[i].first, intervals[i].second);
		suff[i].second = min(suff[i].second, intervals[i].first);
	}
	ll ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		ans = max(ans, get(pref[i]) + get(suff[i + 1]));
	}
	for (int i = 0; i < n; ++i) {
		pii other = (i == 0 ? make_pair(-inf, inf) : pref[i - 1]);
		other.first = max(other.first, suff[i + 1].first);
		other.second = min(other.second, suff[i + 1].second);
		ans = max(ans, get({intervals[i].second, intervals[i].first}) + get(other));
	}
	cout << ans << endl;
}

ll get(pii v) {
	return max(0, v.second - v.first + 1);
}


Measured memory_bytes: 2676
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1005
#define LL long long

using namespace std;

int n,a[maxn];

LL solve(LL avg)
{
    LL ret=0;
    for (int i=0;i<n;i++) ret+=(avg-a[i])*(avg-a[i]);
    return ret;
}

int main()
{
    scanf("%d",&n);
    int sum=0;
    for (int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];
    LL ans=0x7fffffff;
    ans=min(solve(sum/n),min(solve(sum/n-1),solve(sum/n+1)));
    cout <<ans;
    return 0;
}


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

int main() {
	int n,i,flag=1;
	long long h[100005];
	cin >> n;
	for(i=1;i<=n;i++) cin >> h[i];
	for(i=2;i<=n;i++){
		if(h[i]<h[i-1]){
			if(h[i-1]-h[i]>1){
				flag=0;
				break;
			} else {
				h[i]++;
			}
		}
	}
	if(flag==1) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
#include <unordered_map>
  
using namespace std;


int main(){

	int h;
	int st[10][5];
	bool next;
	while(cin>>h,h){
		next=true;
		
		for(int i=0;i<h;i++){
			for(int j=0;j<5;j++) scanf("%d",&st[i][j]);
		}
		
		int res=0;
		while(next){
			next=false;
			
			for(int i=0;i<h;i++){
				for(int left=0;left+2<5;left++){
					int right=left;
					while(right+1<5 && st[i][right+1]==st[i][left]) right++;
					
					//cout<<left<<" "<<right<<endl;
					
					if(right-left+1>=3){
						
						res+=(right-left+1)*st[i][left];
						for(int j=left;j<=right;j++) st[i][j]=0;
					}
					left=right;
				}
			}
			
			for(int i=h-2;i>=0;i--){
				for(int j=0;j<5;j++){
					if(st[i][j]==0) continue;
					int pos=i;
					while(pos+1<h && st[pos+1][j]==0){
						next=true;
						swap(st[pos][j],st[pos+1][j]);
						pos++;
					}
				}
			}
		}
		cout<<res<<endl;
		
	}
	
	return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	rep(i, n) cin >> p.at(i);

	int cnt = 0;
	for(int i = 1; i < n-1; i++){
		if(p.at(i-1) < p.at(i) && p.at(i) < p.at(i+1)) cnt++;
		else if(p.at(i+1) < p.at(i) && p.at(i) < p.at(i-1)) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<int>A(N);for(int i=0;i<N;i++)cin>>A[i];
  sort(A.begin(),A.end());
  
  int l=0;
  int ans=0;
  for(int i=0;i<N;i++){
    if(i==N-1||A[i]!=A[i+1]){
      ans+=i-l+1>=A[i]?i-l+1-A[i]:i-l+1;
      l=i+1;
    }
  }
  cout<<ans;
}

Measured memory_bytes: 640
# coding: utf-8 -*-

N, M, X, Y = map(int, input().split())

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

# print(X, a)

x_max = max(a)
y_min = min(b)


# print(x_max, y_min)

count = 'War'


for i in range(X, Y + 1):
    if i > x_max and i <= y_min and i > X and i < Y:
        count = 'No War'

print(count)










Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n)
  {
    int t;
    cin>>t;
    t--;
    a[t]=i+1;
  }

  rep(i,n)cout<<a[i]<<" ";
  cout<<endl;

  return 0;

}


Measured memory_bytes: 1280
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
  int H, W; cin >> H >> W;
  vector< vector<char> > s(H + 2, vector<char>(W + 2, '.'));
  FOR(i, 1, H + 1) {
    FOR(k, 1, W + 1) {
      cin >> s[i][k];
    }
  }

  FOR(i, 1, H + 1) {
    FOR(k, 1, W + 1) {
      if (s[i][k] == '#' && (s[i - 1][k] != '#' && s[i][k + 1] != '#' && s[i + 1][k] != '#' && s[i][k - 1] != '#')) {
        cout << "No" << endl;
        return 0;
      }
    }
  }

  cout << "Yes" << endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
s = [list('.' + input() + '.') for _ in range(H)]
alst = ['.'] * (W + 2)
s.insert(0, alst)
s.append(alst)

for i in range(1, H + 1):
    for j in range(1, W + 1):
        ansf = True
        if s[i][j] == '#':
            if s[i][j + 1] == '.' and s[i][j - 1] == '.' and\
                s[i - 1][j] == '.' and s[i + 1][j] == '.':
                  ansf = False
                  break
    if not ansf:
        print('No')
        exit()

print('Yes')

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

int main()
{
    int input_data[10000];
    int id_data = 0;

    while(1) {
        int input;
        cin >> input;
        input_data[id_data] = input;
        id_data++;
        if(input == 0) break;
    }

    for(int i = 0; i < id_data-1; i++) cout << "Case " << i+1 << ": " << input_data[i] << endl;

    return 0;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,a,b,ans=1000000000000000001;
  cin>>n>>a>>b;
  if((b-a)%2==0)
  	ans=(b-a)/2;
  else{ 
    ans=(b-a-1)/2+a;
    if((b-a-1)/2+n-b+1<ans)
      ans=(b-a-1)/2+n-b+1;
  } 
  cout<<ans<<endl;
  return(0);
}

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

using namespace std;

typedef long long ll;

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}

const int N = 1e5 + 9, M = 1e5 + 9, OO = 0x3f3f3f3f;
const ll llOO = 0x3f3f3f3f3f3f3f3f;

int main(){
    init();

  int n, m;	cin >> n >> m;
  cout << max(0,(n - 1) * n / 2) + max(0, (m - 1) * m / 2);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int a[4];

int main(void){
  int i,j,k,b,c,d;
  char str[10],s[4];
  
  fgets(str,sizeof(str),stdin);
  for(i=0;i<4;i++){
    a[i]=str[i]-'0';
  }
  for(i=0;i<2;i++){
    b=0;
    if(i==0){
      s[0]='+',b=a[0]+a[1];
    }else{
      s[0]='-',b=a[0]-a[1];
    }
    for(j=0;j<2;j++){
      c=b;
      if(j==0){
      s[1]='+',c=b+a[2];
      }else{
       s[1]='-',c=b-a[2];
      }
      for(k=0;k<2;k++){
        d=c;
        if(k==0){
         s[2]='+',d=c+a[3];
        }else{
         s[2]='-',d=c-a[3];
        }
        s[3]='\0';
        if(d==7){
          printf("%d%c%d%c%d%c%d=7\n",a[0],s[0],a[1],s[1],a[2],s[2],a[3]);
          return 0;
        }
      }
    }
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  int N;
  
  cin >> N;
  
  ll sum = 0;
  
  for (int i = 1; i <= N; i++) {
    if (i % 3 != 0 && i % 5 != 0) {
      sum += i;
    }
  }
  
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;


// chmax, chmin
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 <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };


using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T& data, vector<int>& iter) {
  cout << data << " ";
}
template <typename T>
void dump(const vector<T>& data, vector<int>& iter) {
  for (auto elem : data) dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>>& data, vector<int>& iter) {
  for (auto elem : iter) {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++) {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T>& data, int dummy) {
  for (int i = 0; i < data.size(); i++) {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T& data) {  // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////


void solve(long long K, long long A, long long B){
  for(int i=A; i<=B; i++) {
    if(i%K == 0) {
      cout << "OK" <<endl;
      return;
    }
  }
  cout << "NG" <<endl;

}

int main(){ 
    cout << setprecision(10);
    long long K;
    scanf("%lld",&K);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(K, A, B);
    return 0;
}


Measured memory_bytes: 3732
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{  int n,m,i;
char a[4];
	while(~scanf("%s",&a))
	{  
	m=0;
	for(i=0;i<4;i++)
	if(a[i]==a[i+1])
    m=1;
	if(m==1)
	printf("Bad\n");
	else
	printf("Good\n");	
	
	}
	
}

Measured memory_bytes: 1644
S = input()
Slist = list(S)
big = ord('A')
small = ord('a')
diff = big-small
for i in range(len(Slist)):
    w = ord(Slist[i])
    if small <= w:
        #?°?????????????
        Slist[i] = chr(w+diff)
    elif big <= w:
        Slist[i] = chr(w-diff)
print(''.join(Slist))

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

const int N = 1e6 + 100;

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    if(n%3 > 0) {
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if(x != 0) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    }
    else {
        map<int,int> cnt;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        vector<pair<int,int>> vec;
        for(auto t : cnt) {
            vec.push_back({t.first, t.second});
        }
        if(vec.size() > 3) cout << "No" << endl;
        else if(vec.size() == 3) {
            int Xor = 0;
            bool cnt_ok = 1;
            for(int i = 0; i < 3; i++) {
                Xor ^= vec[i].first;
                if(vec[i].second != n/3) cnt_ok = 0;
            }
            if(cnt_ok && Xor == 0) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else if(vec.size() == 2) {
            int cnt_x = vec[0].second, x = vec[0].first;
            int cnt_y = vec[1].second, y = vec[1].first;
            if(cnt_x == (n/3) && x == 0) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else {
            if(vec[0].first == 0) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 4988
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

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

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

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N, X = map(int, sys.stdin.readline().split())
    L = list(map(int, sys.stdin.readline().split()))
    L.append(X)
    L.sort()
    D = [abs(x2 - x1) for x1, x2 in zip(L, L[1::])]
    print(reduce(gcd, D))

Measured memory_bytes: 16264
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include "math.h"
#include "assert.h"

using namespace std;

#define ll long long

#define BUFF ios::sync_with_stdio(false)
#define epsilon 1e-07
#define pi 2 * acos(0.0);
#define mod 1000000007   // 1e9+7
#define cerr if(false)cerr
#define watch(x) cerr << #x << " = " << x << endl;

#define inf std::numeric_limits<int>().max();

int main() {
	int n;
	cin >> n; 
	vector<int> v(n); 
	for(int i=0; i<n; i++) {
		cin >> v[i];
	}
	int ct = 0;
	int ans = 0;
	for(int i=1; i<n; i++) {
		if (v[i] <= v[i-1]) ct++; 
		else {
			ans = max(ans, ct);
			ct = 0;
		}
	}
	ans = max(ans, ct);
	cout << ans << endl;
}


Measured memory_bytes: 640
N, X, Y = list(map(int,input().split()))
X -= 1
Y -= 1
ans = [0 for _ in range(N)]
for i in range(N - 1):
    for j in range(i + 1, N):
        ind = min(j - i, abs(X - i) + 1 + abs(j - Y))
        ans[ind] += 1
for i in range(1, N):  print(ans[i])

Measured memory_bytes: 74172
from collections import deque
import math

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x: x[0])

# 爆発範囲がとても広く、全ての爆発が右端まで及ぶとひとまず考える
# 各xを見る際に、影響の及ばない爆発分のダメージは引く

# 合計の爆発回数
ans = 0
# 爆発ダメージの合計
total_damage = 0
# 各爆発の情報
dq = deque()

# 左端から順にモンスターを見る
for x, h in XH:
    # 爆発が及ばない場合
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    # 爆発させる必要がある場合
    if total_damage < h:
        # 残っているHPに更新
        h -= total_damage
        # 必要な爆発回数
        cnt = math.ceil(h / A)
        ans += cnt
        # 爆発回数 * 単発のダメージ
        dmg = cnt * A
        total_damage += dmg
        # [爆発で与えるダメージ、及ぶ範囲の右端]
        dq.append((dmg, x + D * 2))

print(ans)


Measured memory_bytes: 60404
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	//map<int, int> a = {{1, 0}, {3, 0}, {5, 0}, {7, 0}, {8, 0}, {10, 0}, {12, 0}, {4, 1}, {6, 1}, {9, 1}, {11, 1}, {2, 2}};
	map<int, int> a;
	int x, y;
	a[1] = 0;
	a[2] = 1;
	a[3] = 0;
	a[4] = 2;
	a[5] = 1;
	
	a[6] = 2;
	a[7] = 1;
	a[8] = 1;
	a[9] = 2;
	a[10] = 1;

	a[11] = 2;
	a[12] = 1;

	cin >> x >> y;

	if (a[x] == a[y])
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define vll vector<long long> 
#define pll pair<ll,ll>
#define f(i,a,b) for(long long i=a;i<b;i++)
#define F first
#define S second
#define pb(i) push_back(i)
#define mp(x,y) make_pair(x,y)
#define all(v)  (v).begin(),(v).end()
#define sz 1001
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main(){
	FIO;
	ll n;cin>>n;
	ll dp[n][3];
	f(i,0,n){
		f(j,0,3) cin>>dp[i][j];
	}
	f(i,1,n){
		dp[i][0] += max(dp[i-1][1],dp[i-1][2]);
		dp[i][1] += max(dp[i-1][0],dp[i-1][2]);
		dp[i][2] += max(dp[i-1][1],dp[i-1][0]);
	}
	ll ans = max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	cout<<ans<<"\n";
}

Measured memory_bytes: 5908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

int main() {
  int n;
  string s;
  cin >> n >> s;
  int maxcnt = 0;
  for (int i = 0; i < n - 1; i++) {
    vi a(26, 0), b(26, 0);
    for (int j = 0; j < n; j++) {
      int memo;
      for (int k = 0; k < 26; k++) {
        if (s.at(j) == alp.at(k)) {
          memo = k;
          break;
        }
      }
      if (j <= i) a.at(memo) = 1;
      else b.at(memo) = 1;
    }
    int cnt = 0;
    for (int j = 0; j < 26; j++) {
      if (a.at(j) == 1 && b.at(j) == 1) cnt++;
    }
    maxcnt = max(maxcnt, cnt);
  }
  cout << maxcnt << endl;
}

Measured memory_bytes: 256
N = int(input())
S = input()

d = {"R": 0, "G": 0, "B": 0}
for i in range(N):
    d[S[i]] += 1
    
ans = d["R"] * d["G"] * d["B"]

cnt = 0
for i in range(1, N - 1):
    for j in range(i + 1, N):
        k = 2 * j - i
        if k > N or S[i - 1] == S[j - 1]:
            continue
            
        if S[i - 1] != S[k - 1] and S[j - 1] != S[k - 1]:
            cnt += 1
            
print(ans - cnt)



Measured memory_bytes: 68052
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;

template<class T>
void print(const vector<T>& v) {
  cout << "[";
  for (auto itr = v.begin(); itr != v.end() - 1; itr++) cout << *itr << ", ";
  cout << v.back() << "]" << endl;
}

//A以上B以下のxの倍数の個数
inline ll betNum(ll A, ll B, ll x) {
  return B / x - ceil(static_cast<ld>(A) / x) + 1;
}

ll gcd(ll A, ll B) {
  if (A % B == 0) return B;
  return gcd(B, A % B);
}
ll lcm(ll A, ll B) {
  return A / gcd(A, B) * B;
}

int main() {
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  ll t = betNum(A, B, C) + betNum(A, B, D) - betNum(A, B, lcm(C, D));
  //print(vector<ll>{betNum(A, B, C), betNum(A, B, D), betNum(A, B, lcm(C, D))});
  cout << betNum(A, B, 1) - t << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<map>
#define pb(a) push_back(a)
using namespace std;
typedef pair<int,int> P;
int main(){
  int c=0;
  int w,n,i,j,k;;
  while(cin >> w,w){
    c++;
    cout << "Case "<<c<<":"<<endl;
    cin >> n;
    string s;
    vector<P> v;
    v.clear();
    P p,ans;
    for(k=0;k<n;k++){
      cin >> s;
      for(i=0;i<s.size();i++) if(s[i]==',') s[i]=' ';
      stringstream ss(s);
      ss>>p.first >>p.second;
      v.pb(p);
    }
    int dp[1005][1005]={{}};
    int inf = 1 << 20;
    fill(dp[0],dp[1004],-inf);
    dp[0][0]=0;
    for(i=0;i<n;i++){
      //cout << v[i].first << ":" << v[i].second << endl;
      for(j=0;j<=w;j++){
	if(dp[i][j]==-inf) continue;
	dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
	if(j+v[i].second<=w)
	  dp[i+1][j+v[i].second]=max(dp[i+1][j],dp[i][j]+v[i].first);
	//cout << dp[i+1][j]<<endl;
      }
    }
    ans.first=0;ans.second=0;
    /*
    for(i=0;i<=n;i++)
      for(j=0;j<=w;j++)
	if(dp[i][j]!=-inf)cout << i << ":" << j << ":" << dp[i][j] << endl;
    */
    for(i=0;i<=w;i++){
      //cout << i << ":" << dp[1][i] << endl;
      if(dp[n][i]>ans.first){
	ans.first=dp[n][i];
	ans.second=i;
      }
    }
    cout << ans.first << endl << ans.second << endl;
  }
  return 0;
}

Measured memory_bytes: 5192
n, q = map(int, input().split())
s=input()
lr=[list(map(int, input().split())) for i in range(q)]
a=[0]*n
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        a[i]=1
        a[i+1]=1
S=[0]*n
S[0]=a[0]
for i in range(1, n):
    S[i]=S[i-1]+a[i]
S=[0]+S
for l, r in lr:
    print(S[r]//2-(S[l-1]+1)//2)

Measured memory_bytes: 33096
import fractions


def lcm(a, b):
    return a * b // fractions.gcd(a, b)


def list_lcm(number_list):
    lcm_number = 1
    for j in range(len(number_list)):
        lcm_number = lcm(lcm_number, number_list[j])

    return lcm_number


if __name__ == '__main__':
    number_count = int(input())
    numbers = []
    for i in range(number_count):
        numbers.append(int(input()))
    print(int(list_lcm(numbers)))


Measured memory_bytes: 5432