akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int,input().split()))
b = [0]*(n-1)
ans = a[0]
for i in range(1,n):
  b[i-1] = a[0]^a[i]
  ans ^= b[i-1]
print(ans,end=' ')
for i in range(1,n):
  print(ans^b[i-1],end=' ')

Measured memory_bytes: 31400
(S,) = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7


def modInverse(a, p):
    assert a % p != 0
    return pow(a, p - 2, p)


MAX_N = 10000
# Precompute all factorials: i!
fact = [1]
for i in range(1, MAX_N + 1):
    fact.append((fact[-1] * i) % MOD)

# Precompute all inverse factorials: 1 / (i!)
invFact = [0] * (MAX_N + 1)
invFact[MAX_N] = modInverse(fact[MAX_N], MOD)
for i in range(MAX_N - 1, -1, -1):
    invFact[i] = (invFact[i + 1] * (i + 1)) % MOD
    assert fact[i] * invFact[i] % MOD == 1


def nCr(n, r):  # mod
    # Modulo binomial coefficients
    return (fact[n] * invFact[r] * invFact[n - r]) % MOD


total = 0
for n in range(1, 1000):

    stars = S - n * 3
    bars = n - 1
    if stars >= 0:
        count = nCr(stars + bars, stars)
        total += count
        total %= MOD
print(total)


Measured memory_bytes: 66224
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define w(t) int t;cin>>t;while(t--)
#define pb push_back
#define mk make_pair
#define ascSort(v) sort(v.begin(), v.end())
#define descSort(v) sort(v.begin(), v.end(), greater<int>())
#define ff first
#define ss second
#define pi pair<int,int>
#define vi vector<int>
#define umapi unordered_map<int,int>
#define INF 1000000007
#define PI 3.14159265
const int mod=998244353;
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>PBDS;

void FIO(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
}
bool cmp(int a, int b){
	return a>b;
}
int32_t main(){
	
	FIO();
	
		int w,s;cin>>s>>w;
		if(w>=s)
			cout<<"unsafe";
		else
			cout<<"safe";
	return 0;
	
		
}


Measured memory_bytes: 3624
import java.util.Arrays;
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {

    	Scanner sc=new Scanner(System.in);

    	int N=sc.nextInt();
    	int Q=sc.nextInt();

    	int[] val=new int[N];

    	Arrays.fill(val, Integer.MAX_VALUE);

    	RMQ segtree=new RMQ(val);

    	for(int i=0;i<Q;i++) {

    		int c=sc.nextInt();
    		int x=sc.nextInt();
    		int y=sc.nextInt();

    		if(c==0) {
    			segtree.update(x, y);
    		}else {
    			System.out.println(segtree.query(x, y+1, 0, 0, -1));
    		}
    	}
    }




}

class RMQ{

	int n;

	int[] dat;


	RMQ(int[] val){

		int size=val.length;
		n=1;

		//元の配列のサイズ以上になる最小の2のべき乗をnとすると
		//セグメント木の大きさは2n-1である。
		while(n<size) {
			n *=2;
		}

		init();

		//セグメント木の最下段に元の配列の値を入れておく。
		for(int i=0;i<size;i++) {
			dat[i+n-1]=val[i];
		}

		//最下段から子を比べて親を格納していく。

		for(int i=n-2;i>=0;i--) {
			dat[i]=Math.min(dat[2*i+1],dat[2*i+2]);
		}

	}






	void init() {

		dat=new int[2*n-1];

		for(int i=0;i<2*n-1;i++) {
			dat[i]=Integer.MAX_VALUE;
		}

	}

	void update(int i,int val) {

		//葉のノード番号
		i+=n-1;
		dat[i]=val;

		//登りながら更新
		while(i>0) {

			//子から親を求めるには-1して/2
			//切り捨てられて、左からでも右からでも同じ値になる。
			i=(i-1)/2;

			//親は左右の子のうち、小さい値を持っている。
			dat[i]=Math.min(dat[i*2+1],dat[i*2+2]);
		}

	}

	//[a,b)クエリで求められる区間の端。
	//k自分が今いるノードのインデックス
	//今みてる区間[l,r)

	//呼び出す時はquery(a,b,0,0,n)とする。

	int query(int a,int b,int k,int l,int r) {

		if(r<0) {
			r=n;
		}

		if(r<=a||b<=l)return Integer.MAX_VALUE;//交差しない?
		if(a<=l && r<=b) return dat[k];		  //完全に含む?

			int vl=query(a,b,k*2+1,l,(l+r)/2);
			int vr=query(a,b,k*2+2,(l+r)/2,r);

			return Math.min(vl,vr);

	}



}




Measured memory_bytes: 103040
#include <bits/stdc++.h>
using namespace std;
#define ff        first
#define ss        second
#define ll        long long
#define int        long long
#define inf       ((ll)1e18)
#define double    long double
#define ull       unsigned long long
#define mod       1000000007
#define vi        vector<ll>
#define extreme   inline
#define ppi       pair<ll,pair<ll,ll>>
#define pb        push_back
#define mp        make_pair
#define pi        2*acos(0.0)
bool cust(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} 
#define pr(a,x,y) for(int i=x;i<y;i++){cout<<a[i]<<" ";}
#define p(a)      cout<<a;
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define all(v)    v.begin(), v.end()
#define rall(v)   v.rbegin(), v.rend()
#define test      cout<<"THIS_AND_THIS"<<endl;
#define str       string
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
void solve(){
	ll n;cin>>n;
	for(int i=-100;i<=200;i++){
		for(int j=-100;j<=200;j++){
			ll x=i*i*i*i*i;
			ll y=j*j*j*j*j;
			if((x-y)==n){
				cout<<i<<" "<<j;
				return;
			}
		}
	}
}
int32_t main(){
	kehsihba();
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 3564
#include <stdio.h>
int main(){
  
  int a, b;
  scanf("%d%d" ,&a,&b);
  if ( a < b ) {
    printf("a < b\n");  
 
  } else if (a > b ) {
    printf("a > b\n");
  } else {
    printf("a == b\n");
  }
  return 0;
} 



Measured memory_bytes: 2052
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    vector<ll> res(n);
    FOR(i,0,n)cin>>res[i];
    sortAl(res);
    vector<P> card(m);
    FOR(i,0,m)cin>>card[i].second>>card[i].first;
    sortAlr(card);

    ll po = 0;
    FOR(i,0,n){
      if(card[po].second == 0)po++;
      if(po>=m)break;
      res[i] = max(res[i], card[po].first);
      card[po].second--;
    }

    ll ans=0;
    FOR(i,0,n)ans+=res[i];
    cout<<ans<<endl;
}


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

using namespace std;

int main()
{
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 3624
# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
cnt = 0

for i in range(1, n - 1):
	if p[i - 1] < p[i] and p[i] < p[i + 1]:
		cnt += 1
	elif p[i - 1] > p[i] and p[i] > p[i + 1]:
		cnt += 1

print(cnt)

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

using namespace std;
#define ff first
#define ss second
#define pb push_back
#define quicker ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    // Base Case 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    ll x1, y1; // To store results of recursive call 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 
  
    // Update x and y using results of recursive 
    // call 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
}
ll modInverse(ll a, ll m) 
{ 
    ll x, y; 
    ll g = gcdExtended(a, m, &x, &y); 
    if (g != 1) 
        cout << "Inverse doesn't exist"; 
    else
    { 
        // m is added to handle negative x 
        ll res = (x%m + m) % m; 
        //cout << "Modular multiplicative inverse is " << res; 
        return res;
    } 
}
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
    quicker
    ll n, k, m, modu = 998244353, ans = 0;
    cin >> n >> m >> k;
    vector<ll> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % modu;
    for (int i = 0; i <= k; i++){
      ans += (((fact[n - 1] * modInverse(fact[n - i - 1], modu) % modu) * modInverse(fact[i], modu) % modu) * binpow(m - 1, n - i - 1, modu)) % modu;
      ans %= modu;
    }
    ans *= m;
    ans %= modu;
    cout << ans;
    return 0;
}


Measured memory_bytes: 4784
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <cmath>
#include <stack>
#include <iomanip>

using namespace std;
typedef long long ll;
using Pll = pair<ll,ll>;

const ll INF = 1LL<<60;
const ll MOD = 1000000007;

//cout << fixed << setprecision(10);

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll sum=0;
    ll odd=0;
    ll even=0;
    for(int i=0;i<N;i++) {
        cin >> A[i];
        sum+=A[i];
        if(i%2==0){
            even+=A[i];
        }
        else odd+=A[i];
    }
    sum/=2;
    vector<ll> ans(N,0);
    ans[N-1]=sum-odd;
    ans[0]=A[0]-ans[N-1];
    for(int i=1;i<N-1;i++){
        ans[i]=A[i]-ans[i-1];
    }
    cout << 2*ans[N-1] << " ";
    for(int i=0;i<N-1;i++){
        cout << 2*ans[i];
        if(i!=N-2) cout << " ";
    }
    cout << endl;



    return 0;
}

Measured memory_bytes: 2944
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		int days = input.nextInt();
		int assignment = input.nextInt();
		int daysToComplete= 0;
		for(int i = 0;i<assignment;i++){
		    daysToComplete+=input.nextInt();
		}
		if(assignment>days || daysToComplete>days){
		    System.out.println("-1");
		}else {
		    System.out.println(days- daysToComplete);
		}
	}
}


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

int main(){
    int n=0 ,a=0;
    cin >> n;
    char s[n];
    cin >> s;
    int ans=0;
    for (int i= 0 ; i<n; i++){
        if (s[i]==s[i+1]){
            a++;
        }
    }
    ans= n-a;
    cout << ans;
}

Measured memory_bytes: 384
n = list(map(int,input().split()))
k = n[0]
x = n[1]
ans = []

k_1 = k - 1

for n in range(x-k_1,x+k_1+1):
    n = str(n)
    ans.append(n)

aa = " ".join(ans)    
print(aa)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
int u[1100000];
vector<int> y;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a,b,c,d=0,e=0,f=1,g=0;
  cin >>a>>b;
  d=1900*b;
  d+=(a-b)*100;
  for(int n=0;n<b;n++) f=f*2;
  d=d*f;
  cout <<d<<'\n';
  return (0);
}


Measured memory_bytes: 256
n,m=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(n)]
b=[list(map(int,input().split())) for _ in range(m)]

c=[0 for i in range(n)]

for i in range(n):
    for j in range(m):
        c[i]+=A[i][j]*b[j][0]
    print(c[i])


Measured memory_bytes: 6036
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();
        int[] w = new int[N];
        int[] v = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
            sum += v[i];
        }

        long[] dp = new long[sum + 1];
        long INF = (long)1e18;
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = sum; j >= v[i]; j--) {
                dp[j] = Math.min(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        long res = 0;
        for (int j = 0; j <= sum; j++) {
            if (dp[j] <= W) {
                res = Math.max(res, j);
            }
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
#define endl '\n'
#define F first
#define S second
#define lowbit(x) (__builtin_ffs(x)-1)
const int MAX_N=20;

int n;
int a[MAX_N][MAX_N];
ll score[1<<MAX_N];
ll dp[1<<MAX_N];

ll getans(int mask)
{
	if(~dp[mask]) return dp[mask];
	dp[mask]=0;
	int MAX=(1<<__builtin_popcount(mask));
	for(int i=1,b;i<MAX;i++)
	{
		b=0;
		for(int j=1,cnt=1;j<=mask;j<<=1) if(j&mask)
		{
			if(cnt&i) b|=j;
			cnt<<=1;
		}
		dp[mask]=max(dp[mask],getans(mask^b)+score[b]);
	}
	return dp[mask];
}

int main()
{
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<(1<<n);i++)
	{
		int low=lowbit(i);
		score[i]=score[i^(1<<low)];
		for(int j=0;(1<<j)<=i;j++) if((1<<j)&i) score[i]+=a[low][j];
	}
	printf("%lld\n",getans((1<<n)-1));
	return 0;
}



Measured memory_bytes: 10496
import sys

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

As.sort()
for i in range(N):
    for j in range(i + 1, N):
        if As[i] == As[j]:
            print('NO')
            sys.exit(0)
        if As[j] > As[i]:
            break

print('YES')

Measured memory_bytes: 25684
n = int(input())
word = [input() for i in range(n)]

charactor = [[0 for j in range(n)] for i in range(26)]
for i in range(n):
    for j in range(len(word[i])):
        charactor[ord(word[i][j])-97][i] += 1

ans = ""
for i in range(26):
    ans += chr(i+97)*min(charactor[i])

print(ans)


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

#define int long long

const int H = 1e4 + 10 ;
int dp[H];

int solve(pair<int,int>* a , int n , int h){
	if(h <= 0) return 0 ;
	if(dp[h] != -1) return dp[h] ;
	int ans = INT_MAX ;
	for(int i = 0 ; i < n ; i++){
		ans = min(ans, solve(a , n , h - a[i].first) + a[i].second) ;
	}
	return dp[h] = ans ;
}

int32_t main(){
	memset(dp,-1,sizeof(dp)) ;
	int h, n ;
	cin >> h >> n ;
	pair<int,int> a[n] ;
	for(int i = 0 ; i < n ; i++){
		cin >> a[i].first >> a[i].second ;
	}
	cout << solve(a,n,h) ;
	return 0 ;
}


Measured memory_bytes: 896
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any((r1 != r2 or c1 != c2) and (r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break

Measured memory_bytes: 6564
num, back = map(int, input().split(' '))
r_point, s_point, p_point = map(int, input().split(' '))
t = input()
j_dict = {'r': 'p', 's': 'r', 'p': 's'}
score = {'r': r_point, 's': s_point, 'p': p_point, 'e': 0}
result = [j_dict[i] for i in t]
for i in range(back, num):
    if result[i] == result[i - back]:
        result[i] = 'e'
print(sum(score[i] for i in result))

Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define pi pair<int,int>
#define pb push_back
#define mp make_pair
#define endl '\n'
#define fi first
#define se second

void solve(){
  int n;
  cin>>n;
  int a[n],b[n];
  int fr[n+1] = {0};
  f(i,0,n) cin>>a[i],fr[a[i]]++;
  f(i,0,n) cin>>b[i],fr[b[i]]++;
  int ok = 1;
  f(i,0,n+1){
     if(fr[i]>n) ok = 0;
  }
  sort(b,b+n,greater<int>());
  if(!ok){
      cout<<"No";
      return;
  }
  int l = 0,r = n-1;
  for(int i = 0;i<n;i++){
     if(a[i] == b[i]){
         if(b[i]!=a[l] && b[i]!=b[l]){
             swap(b[i],b[l]);
             l++;
         }else{
             swap(b[i],b[r]);
             r--;
         }
     }
  }
  cout<<"Yes"<<endl;
  f(i,0,n) cout<<b[i]<<" ";
 
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while(t--) solve();
}


Measured memory_bytes: 8300
#ABC079 C:Train Ticket
import itertools

s = list(input())
num = []
calc = [1, -1]
for i in range(len(s)):
    a = int(s[i])
    num.append(a)

calc_comb = [_ for _ in itertools.product(calc, repeat=3)]

x = 0
while True:
    ans = num[0]
    for i in range(len(num)-1):
        ans += num[i+1] * calc_comb[x][i]

    if ans == 7:
        r = calc_comb[x]
        break
    else:
        x += 1

r_replace = ['+' if i==1 else '-' for i in r]
out = [None] * (len(s)+len(r_replace))
out[::2] = s
out[1::2] = r_replace
out = ''.join(out)
print(out, '=7', sep='')


Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
main(){
  ll n;
  cin>>n;
  vector<vector<ll>> a(n);
  rep(i,n){
    ll m;cin>>m;
    a[i].resize(m);
    rep(j,m)cin>>a[i][j];
  }
  priority_queue<ll> que;
  ll ans=0;
  for(ll i=n-1;i>=0;--i){
    for(const auto& x:a[i])que.push(x);
    ans+=que.top();
    que.pop();
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 19000
#include<bits/stdc++.h>
#include<math.h>
#include<map>
#include<sstream>
#define str string
#define ll long long int
#define con continue

#define rt return 0
#define fr first
#define sec second
#define pf push_front
#define pb push_back
#define vb vct.begin()
#define ve vct.end()
#define ib it.begin()
#define ie it.end()
#define lb lst.begin()
#define le lst.end()
#define mb mp.begin()
#define me mp.end()
#define sb st.begin()
#define se st.end()
#define strb s.begin()
#define stre s.end()


using namespace std;
str s,s1,s2,s3;

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

   //ll tc; cin>>tc;while(tc--){
   ll n,m,z,i,j,a=0,ans=0,k=0,cnt=0,b;
   ll c=0,x,y,d=0,sum=0,mn=INT_MAX,mx=0;
   str ss,strn;
   char ch;

   cin>>n;
   ll ara[n+1];
   for(i=1;i<=n;i++)cin>>ara[i];
   for(i=1;i<=n-2;i++)
   {
       for(j=i+1;j<=n-1;j++)
       {
           for(k=j+1;k<=n;k++)
           {
             if(ara[i]==ara[j] || ara[i]==ara[k] || ara[j]==ara[k]) continue;
             //cout<<ara[i]<<" "<<ara[j]<<" "<<ara[k]<<endl;
              x=ara[i];y=ara[j];z=ara[k];
              if(x>y)swap(x,y);
              if(z<y)swap(y,z);
              if(x>y)swap(x,y);
              if(x+y>z)
             ans++;
             //cout<<x<<" "<<y<<" "<<z<<endl;
           }
       }
   }


   cout<<ans<<endl;

// }


            return 0;

}











//map<str,ll>mp;
   //map<str,ll>::iterator it;
   /*vector<ll>vct;
   vector<ll>::iterator vit;
   set<ll>st;
   set<ll>::iterator sit;
   priority_queue<ll>pq;
   //priority_queue<ll>::iterator pqit;*/



Measured memory_bytes: 3660
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    static Scanner cin = new Scanner();
    static void Main() {
        string S = Console.ReadLine();
        const int mod = 1000000007;

        var dp = new long[100010, 5];
        for (int i = S.Length; i >= 0; i--) {
            for (int j = 3; j >= 0; j--) {
                if (i == S.Length) dp[i, j] = j == 3 ? 1 : 0;
                else {
                    dp[i, j] = dp[i + 1, j] * (S[i] == '?' ? 3 : 1);
                    if (j < 3 && (S[i] == '?' || S[i] == "ABC"[j])) {
                        dp[i, j] += dp[i + 1, j + 1];
                    }
                    dp[i, j] %= mod;
                }
            }
        }
        Console.WriteLine(dp[0, 0]);
        Console.ReadLine();
    }
}

Measured memory_bytes: 15200
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

#if 1
#define PRINT(x) { cout << #x << ": " << (x) << endl; }
#define PRINT_CONTAINER(x)  { cout << #x << ": ";                       \
        for (size_t ix = 0; ix < (x).size(); ++ix) cout << (x)[ix] << ", "; \
        cout << endl; }
#else
#define PRINT(x)
#define PRINT_CONTAINER(x)
#endif

int main(int argc, char *argv[])
{
    char buf[100];
    scanf("%s", buf);
    printf("2018/01/%s\n", &buf[8]);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<ll,pll> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1000003;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n,k;
vi a;

vi f(){
	vi b(n-k+1),c(n);
	stack<P> st;
	st.push({-inf,n});
	for(int i=n-1;i>=0;i--){
		while(a[i]<st.top().first) st.pop();
		c[i]=st.top().second;
		st.push({a[i],i});
	}
//	for(auto i:c) cout<<i<<' ';cout<<endl;
	deque<int> q;
	for(int i=0;i<n-k+1;i++){
		if(!q.empty()&&q[0]<i) q.pop_front();
		if(q.empty()){
			if(c[i]>=i+k) q.push_back(i);
			for(int j=i+1;j<i+k-1;j++){
				if(!q.empty()&&q.back()==j-1&&c[j]>=i+k) q.push_back(j);
				else break;
			}
		}
//		cout<<q.size()<<endl;
		while(!q.empty()){
			int id=q.back();
			if(id>=0&&c[id]<i+k) q.pop_back();
			else break;
		}
		if(!q.empty()&&q.back()==i+k-2&&c[i+k-1]>=i+k) q.push_back(i+k-1);
		b[i]=i+q.size();
		if(q.size()==k) b[i]=n;
	}
	return b;
}

int main(){
	cin>>n>>k;
	a=vi(n);
	for(auto &i:a) cin>>i;
	vi L=f(),R;
//	for(auto i:L) cout<<i<<' ';cout<<endl;
	reverse(a.begin(),a.end());
	for(int i=0;i<n;i++) a[i]*=-1;
	R=f();
	reverse(R.begin(),R.end());
	set<P> st;
	for(int i=0;i<n-k+1;i++) st.insert({L[i],R[i]});
	cout<<st.size()<<endl;
}

Measured memory_bytes: 12016
def uf_init(n):
    return list(range(n)), [1]*n

def uf_root(ufdata, x):
    uf,_ = ufdata
    update_node_arr = []
    while(uf[x] != x):
        update_node_arr.append(x)
        x = uf[x]
    for y in update_node_arr:
        uf[y] = x
    return x

def uf_same(ufdata, x, y):
    return uf_root(ufdata, x) == uf_root(ufdata, y)

def uf_size(ufdata, x):
    _,usize = ufdata
    return usize[uf_root(ufdata, x)]

def uf_unite(ufdata, x, y):
    uf,usize = ufdata
    x = uf_root(ufdata, x)
    y = uf_root(ufdata, y)
    if x == y:
        return
    xysize = uf_size(ufdata, x) + uf_size(ufdata, y)
    if uf_size(ufdata, x) > uf_size(ufdata, y):
        uf[y] = x
        usize[x] = xysize
    else:
        uf[x] = y
        usize[y] = xysize

N,M = (int(x) for x in input().split())

uf = uf_init(N)

AB_arr = []
for _ in range(M):
    AB_arr.append(tuple((int(x)-1 for x in input().split())))

ans = N*(N-1)//2
ans_arr = [ans]
for A,B in reversed(AB_arr):
    if not uf_same(uf, A, B):
        ans -= uf_size(uf, A) * uf_size(uf, B)
    ans_arr.append(ans)
    uf_unite(uf, A, B)

for ans in reversed(ans_arr[:-1]):
    print(ans)




Measured memory_bytes: 24068
import sys

input = sys.stdin.readline


def main():
    N, A, B = [int(x) for x in input().split()]
    H = [int(input()) for _ in range(N)]

    def isOK(mid):
        cnt = 0
        for h in H:
            if h > B * mid:
                sabun = h - B * mid
                cnt += 0 - - sabun // (A - B)
                if cnt > mid:
                    return False
        return True

    ok = 10 ** 9
    ng = 0

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()


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

int main() {
	int h,w;
	for(int j=0;j<1000;j++){
		cin>>h>>w;
		if(h==0 && w==0){
			break;
		}
		for(int j=0;j<h;j++){
			for(int i=0;i<w;i++){
				cout<<"#";
			}
			cout<<endl;
		}
		cout<<endl;
	}

	// your code goes here
	return 0;
}

Measured memory_bytes: 1156
n, m = map(int, input().split())
py = [list(map(int, input().split())) for _ in range(m)]
pysort = sorted(py, key=lambda val: val[1])

pcnt, ans_d = [0] * (10 ** 5 + 1), {}
for i, j in pysort:
    pcnt[i] += 1
    ans_d[j] = str(pcnt[i])

for i, j in py:
    print(str(i).zfill(6) + ans_d[j].zfill(6))


Measured memory_bytes: 42964
n = int(input())
preorder_list = list(map(int,input().split()))
inorder_list = list(map(int,input().split()))
postorder_list = []
cnt = 0
def make_postorder_list(arg_postorder_list, arg_tmp_lst):
    global cnt
    tmp_cnt = cnt
    root = arg_tmp_lst.index(preorder_list[cnt])
    left_lst = arg_tmp_lst[:root]
    right_lst = arg_tmp_lst[root+1:]
    if cnt+1<=n-1:
        if preorder_list[cnt+1] in left_lst:
            cnt+=1
            make_postorder_list(arg_postorder_list, left_lst)
    if cnt+1<=n-1:
        if preorder_list[cnt+1] in right_lst:
            cnt+=1
            make_postorder_list(arg_postorder_list, right_lst)
    arg_postorder_list.append(preorder_list[tmp_cnt])
    

make_postorder_list(postorder_list, inorder_list)

print(*postorder_list)


Measured memory_bytes: 5600
#import<bits/stdc++.h>
using namespace std;long N,n;vector<long> A;main(){for(cin>>N;cin>>n;n=1LL<<50)A.push_back(n);auto a=A.begin(),t=a+1,d=A.end(),b=t+1;partial_sum(a,d,a);for(--d;t+1!=d;++t){for(;a+1!=t&&*a<*t-*(a+1);++a);if(b==t)++b;for(;b+1!=d&&*b-*t<*d-*(b+1);++b);n=min(n,max({*a,*t-*a,*b-*t,*d-*b})-min({*a,*t-*a,*b-*t,*d-*b}));}cout<<n<<" ";}

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
typedef vector<vector<int>> Graph;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int main()
{
    ios::sync_with_stdio(false);

    int N; cin >> N;
    vector<ll> X(N), A(N);
    rep(i, N) cin >> A[i];
    ll ans = 0;

    bool ok = true;
    ll mx = N-1, cur = -1;
    for (int i=N-1; i>=0; i--) {
        if (A[i] > mx || (i < N-1 && A[i] < A[i+1] - 1)) {
            ok = false;
            break;
        }
        if (A[i] > 0 && A[i] <= mx) {
            if (A[i] == cur) {
                // do nothing
            } else {
                ans += A[i];
                cur = A[i];
            }
        }

        cur--, mx--;
    }

    cout << (ok ? ans : -1) << endl;

}


Measured memory_bytes: 3456
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;
 
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define loope(i,a,b) for(ll i=a;i<=b;i++)
#define test() ull t;cin>>t;while(t--)
#define f first
#define s second
#define pb push_back
#define mkp make_pair
#define ins insert
#define nl cout<<endl
#define P 1000000007
#define MOD(x) ((x%P)+P)%P
#define NMAX 100100

#define INF 100000000
int mod=1e9;

int main() 
{


    int n,k;
    cin>>n>>k;

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

    vector<int> dp(n,mod);

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

    cout<<dp[n-1];

	return 0;
    	
}

Measured memory_bytes: 1024
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())


    
a,b,c,k=mi()
s=0
if(k>=a):
    s+=a
    k-=a
    if(k>=b):
        k-=b
    # print(k,a,s)
    if(k>0):
        s-=k
    print(s)
else:
    print(k)
    

Measured memory_bytes: 61916
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("in.txt");ofstream coutt("out.txt");
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}
int ceil(const int &a,const int &b){return (a+b-1)/b;}
////Read:
//Use __builtin_popcountll for ll;
//Check corner cases, n==1;
//
////Some function:
//__builtin_popcountll(), 

signed main(){
    FASTER;
    int a1,a2,v1,v2;cin>>a1>>v1>>a2>>v2;
    int t;cin>>t;
    
    int d=abs(a1-a2)+v2*t;
    if((d<=t*v1 && v1>v2) || d==0){
        cout<<"YES\n";
    }else cout<<"NO\n";
}

Measured memory_bytes: 3664
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;

int gcd(int a, int b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d\n", gcd(max(a, b), min(a, b)));
}

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

int x , y , sum = 0 , a[100000] , dp[100000] ;
int main () {
	cin >> x ;
	
	for ( int i = 0 ; i  < x ; i++ ) {
		cin >> a[i] ;
	}
	dp[0] = 0 ;
	dp[1] = abs( a[1] - a[0] ) ;
	
	for ( int i = 2 ; i < x ; i++ ) { 
		dp[i] = min(dp[i-1] + abs( a[i] - a[i-1]), dp[i-2] + abs( a[i] - a[i-2]) ) ;
	} 
	cout << dp[x-1] ;
}


Measured memory_bytes: 4408
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using Graph = vector<vector<int>>;
using Wgraph = vector<vector<pair<int, long long int>>>;
constexpr long long int INF = 1001001001001001LL;
constexpr long long int MOD = 1000000007LL;
constexpr double PI = 3.1415926535897932;
constexpr long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
constexpr long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = 1; i <= (n); i++)
#define DREP(i,n) for(int i = (n)-1; i >= 0; i--)
#define SREP(i,s,t) for(int i = s; i < t; i++)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define PB push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/

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

  for(int i = 0; i < n; i++) {
    if(s.substr(0, i) == s.substr(i, n - i)) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  return 0;
}


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

int main() {
  int n, m;

  cin >> n >> m;
  vector<int> a(50), b(50), road(50, 0);

  for (int i = 0; i < m; i++) {
    cin >> a.at(i) >> b.at(i);
  }

  for (int i = 0; i < m; i++) {
    road.at(a.at(i) - 1) += 1;
    road.at(b.at(i) - 1) += 1;
  }

  for (int i = 0; i < n; i++) {
    cout << road.at(i) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
//参考 http://drken1215.hatenablog.com/entry/2019/05/19/224500
//木は閉路がないので適当にrootをとって典型的なdfsの形で全探索できる
//あるノードまでの距離の偶奇で色の整合が付くのでとりあえず全探索で埋められれば完成
#include <bits/stdc++.h>
using namespace std;

using edge = pair<int,int>;  //edge first 行先 second 重み
using Gragh = vector<vector<edge>>;
Gragh G;
int n;

vector<int> res;

//cは色 重み奇数なら反転
void dfs(int v, int p, int c) {
    res[v] = c;
    for (auto e: G[v]) {
        if (e.first == p) continue;
        if (e.second & 1) dfs(e.first, v, 1-c);
        else dfs(e.first, v, c);
    }
}

int main() {
    cin >> n;
    G.assign(n, vector<edge>());
    for (int i = 0; i < n-1; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        --u; --v;
        G[u].push_back(edge(v,w));
        G[v].push_back(edge(u,w));
    }
    res.assign(n, 0);
    dfs(0, -1, 1);
    for (auto v : res) cout << v << endl;
    return 0;
}

Measured memory_bytes: 8960
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n; cin>>n;
    vector<string> p(n);
    map<string,int> mp;
    rep(i,n){
        cin>>p[i];
        mp[p[i]]++;
    }
    bool ok=true;
    for(auto& v: mp){
        if(v.second>1) ok=false;
    }
    rep(i,n-1){
        if(p[i+1][0]!=p[i][p[i].size()-1]) ok=false;
    }
    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>

using namespace std;
typedef long long ll;

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

  double sum = 0.0;
  for (int i = 0; i < n; i++) {
    double x;
    string y;
    cin >> x >> y;
    if (y == "JPY") {
      sum += x;
    } else {
      sum += x * 380000.0;
    }
  }

  cout << fixed << setprecision(8) << sum << endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
arr = sorted([list(map(int, input().split())) for _ in range(N)])

count = 0
money = 0
for list in arr:
    for i in range(list[1]):
        money += list[0]
        count += 1
        if count == M:
            print(money)
            exit()





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

/*
Returns the gcd of a, b
g = ax+by
Say a = qb+r
Then gcd(a, b) = gcd(b, r)
g = X*b + Y*r = X*b + Y*(a - qb) = a * Y + b * (X - q*Y)
*/
int egcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int X, Y;
    int g = egcd(b, a % b, X, Y);
    x = Y;
    y = X - (a / b) * Y;
    return g;
}

int inv(int a, int m) {
    int g, x, y;
    g = egcd(a, m, x, y);
    if (g != 1) return -1;
    x %= m;
    if (x < 0) x += m;
    return x;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    // freopen("data.txt", "r", stdin);
    int r, g, b, n;
    scanf("%d%d%d%d", &r, &g, &b, &n);
    const int d = gcd(g, b);
    g /= d;
    b /= d;
    int ans = 0;
    for (int nr = 0; nr * r <= n; ++nr) {
        int m = n - r * nr;
        // gx+by = m
        if (m % d != 0) continue;
        m /= d;
        int x = inv(g, b) * m % b;
        if (g * x <= m) {
            ans += 1 + (m / g - x) / b;
        }
        // g(x+kb) <= m, k <= (m/g-x)/b
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))
m = 1000
s = 0
if a[0] < a[1]:
  s = s+m//a[0]
  m = m-(m//a[0])*a[0]
for i in range(N-2):
  if a[i+1] == a[i+2] and a[i+1] == a[i]:
    pass
  elif a[i+1]>=a[i+2] and a[i+1]>=a[i]:
    m = m+s*a[i+1]
    s = 0
  elif a[i+1]<=a[i+2] and a[i+1]<=a[i]:
    s = s+m//a[i+1]
    m = m-(m//a[i+1])*a[i+1]
  else:
    pass
m = m+s*a[-1]
print(m)

Measured memory_bytes: 9172
import Data.Graph.Inductive.Graph
import Data.List
import Data.Graph.Inductive.PatriciaTree

main = do
  [n,k]<-map read.words<$>getLine
  putStr $ solve n k

solve n k = case ans of
  Nothing -> "-1"
  Just g -> toAns g
  where
  ans = go k addingEdges (mkUGraph [1..n] []) :: (Maybe (Gr () ()))
  addingEdges = [(a,b,())|a<-[1..n-1],b<-[a+1..n-1]]
  go 0 _ g = Just g
  go _ [] _ = Nothing
  go k (e:es) g = go (k-1) es (insEdge e g)
  toAns = unlines . con . map f . go es . sort . edges
    where
    go es [] = es
    go []  _ = []
    go (e:es) (r:rs)
      | e == r = go es rs
      | otherwise = e : go es (r:rs)
    f (a,b) = unwords $ map show [a,b]
    es = [(a,b)|a<-[1..n],b<-[a+1..n]]
    con es = show (length es):es

Measured memory_bytes: 2684
N = input()
A, B, C, D = int(N[0]), int(N[1]), int(N[2]), int(N[3])
opes = ['-', '+']
for op1 in opes:
  for op2 in opes:
    for op3 in opes:
      result = 0
      if op1 == '-':
        result += A-B
      else:
        result += A+B
      if op2 == '-':
        result -= C
      else:
        result += C
      if op3 == '-':
        result -= D
      else:
        result += D
      if result == 7:
        print(str(A)+op1+str(B)+op2+str(C)+op3+str(D)+'=7')
        exit()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cerr << #v "=" << (v) << endl;
#define ppa(v) cerr << "----\n"; rep(i,v.size()) cerr << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

int main() {
  int n,s;cin>>n>>s;
  vector<int> a(n);rep(i,n)cin>>a[i];
  a.push_back(s);
  sort(ALL(a));
  vector<int> d(n);rep(i,n)d[i]=a[i+1]-a[i];
  int ans = d[0];
  repi(i,n-1) {
    ans = gcd(ans,d[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
int main() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> v(n);
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        v[i] = make_pair(b, a);
    }
    sort(all(v));

    ll now = 0;
    rep(i, n) {
        ll a, b;
        tie(b, a) = v[i];
        now += a;
        if (now > b) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int ps=str.find('C');
    if(ps==-1){
        puts("No");
        return 0;
    }
    if(str.find('F',ps)!=string::npos){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll n;
  cin >> n;
  ll p[n];
  for(int i=0;i<n;i++)cin >> p[i];

  ll s=0;
  for(int i=1;i<n-1;i++){
    if(max(p[i],max(p[i-1],p[i+1]))!=p[i] && min(p[i],min(p[i-1],p[i+1]))!=p[i])s++;
  }

  cout << s << endl;

}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    string divide[4] = {"dream", "dreamer", "erase", "eraser"};
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    for (int i = 0; i < 4; i++) reverse(divide[i].begin(), divide[i].end());

    bool can = true;
    for (int i = 0; i < s.size();) {
        bool can2 = false;
        for (int j = 0; j < 4; j++) {
            string d = divide[j];
            if (s.substr(i, d.size()) == d) {
                can2 = true;
                i += d.size();
            }
        }
        if (!can2) {
            can = false;
            break;
        }
    }
    if (can) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 512
def main():
    a = [list(map(int, (input().split()))) for _ in range(3)]
    n = int(input())
    ans = []
    for i in range(n):
        m = int(input())
        for j in range(3):
            for k in range(3):
                if a[j][k] == m:
                    ans.append((j,k))
    #print(ans)
    if (0,0) in ans and (1,1) in ans and (2,2) in ans:
        print("Yes")
    elif (0,0) in ans and (0,1) in ans and (0,2) in ans:
        print("Yes")
    elif (1,0) in ans and (1,1) in ans and (1,2) in ans:
        print("Yes")
    elif (2,0) in ans and (2,1) in ans and (2,2) in ans:
        print("Yes")
    elif (0,0) in ans and (1,0) in ans and (2,0) in ans:
        print("Yes")
    elif (0,1) in ans and (1,1) in ans and (2,1) in ans:
        print("Yes")
    elif (0,2) in ans and (1,2) in ans and (2,2) in ans:
        print("Yes")
    elif (0,2) in ans and (1,1) in ans and (2,0) in ans:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
typedef long long int lli;

int num[110];
int frag[110];
int q[8], p[8];
lli pp, qq, cnt=0;
void fx(int n, int k)
{
    int i, f, j;
    for (i = 0; i < n; ++i)
    {
        f = frag[i];
        if (f == 0)
        {
            frag[i] = 1;
            num[k] = i + 1;
            if (k == 1)
            {
                cnt++;
                int flg1, flg2;
                flg1 = flg2 = 0;
                for (j = n; j > 0; --j)
                {
                    if(num[j]!=q[n-j]){
                        flg1 = 1;
                        break;
                    }
                }
                for (j = n; j > 0;--j){
                    if (num[j] != p[n - j])
                    {
                        flg2 = 1;
                        break;
                    }
                }
                if(flg1==0){
                    qq = cnt;
                }
                if(flg2==0){
                    pp = cnt;
                }
            }
            else
            {
                fx(n, k - 1);
            }
            frag[i] = 0;
        }
    }
}

int int_comp(const void*a,const void*b){return *(int*)a-*(int*)b;}
int lli_comp(const void*a,const void*b){return *(lli*)a-*(lli*)b;}
int main(void)
{

    int n;

    pp = qq = 0;
    scanf("%d", &n);
    for (int i = 0;i < n;i++) scanf("%d", &q[i]);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);

    for (int i = 0; i < n; i++){
        num[i] = frag[i] = 0;
    }
    fx(n, n);
    printf("%lld\n", llabs(pp-qq));
    return 0;
}

Measured memory_bytes: 128
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  int x, y, z;
  cin >> x >> y >> z;
  int person = y + z, chair = x - z, ans = 0;
  while (chair >= 0) {
    ans++;
    chair -= person;
  }
  cout << ans - 1 << endl;
}


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

using namespace std;

#define ll long long
#ifdef __APPLE__
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...)
#endif


int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, a, b;
    cin >> n >> a >> b;
    puts(abs(a - b) % 2 == 0? "Alice" : "Borys");

    
    return 0;
}      

Measured memory_bytes: 256
#include <stdio.h>

#define NUMBER 3

void bsort(int b[], int n){
  int i, j;
  int temp;
  
  for(i=0; i<n-1; i++){
    for(j=n-1; j>i; j--){
      if(b[j-1]>b[j]){
	temp=b[j];
	b[j]=b[j-1];
	b[j-1]=temp;
      }
    }
  }
}

int main(void){
  int a[NUMBER];
  int x,y,z;
  int i;
  
  for(i=0; i<NUMBER; i++){
    scanf("%d", &a[i]);
    if(a[i]<1 || a[i]>10000){
      printf("??????????????\??????????????????\n");
      scanf("%d", &a[i]);
    }
  }
 
  bsort(a, NUMBER);
  
  for(i=0; i<NUMBER; i++){
    printf("%d",a[i]);
    if(i==0 || i==1){
      printf(" ");
    }else{
      printf("\n");
    }
  }
  return 0;
}
    

  

  

Measured memory_bytes: 1844
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(void){
	int a,b,i,j;
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0&&b==0) return 0;
		for(i=0;i<a;i++){
			for(j=0;j<b;j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}


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

int main() {
	int64_t N,K,d;
	d =1;
	cin >> N >> K;
	vector<int64_t>vec(N);
	vector<int64_t>visit;
	for(int64_t i=0;i<N;i++){
		cin >> vec.at(i);
	}
	for(int64_t i=0;i<N+1;i++){
		int64_t s;
		s = d-1;
		d = vec.at(s);
		visit.push_back(d);
	}
	vector<int64_t>count(N,0);
	for(int64_t i=0;i<N+1;i++){
		int64_t e;
		e = visit.at(i);
		count.at(e-1)++;
	}
	int64_t f =1;
	int64_t g;
	for(int64_t i=0;i<N;i++){
		if(f < count.at(i)){
			f = count.at(i);
			g = i+1;
		}
	}
	vector<int64_t>record;
	for(int64_t i=0;i<N+1;i++){
		if(visit.at(i)==g){
			record.push_back(i);
		}
	}
	int64_t h = record.at(1)-record.at(0);
	int64_t m = (K-record.at(0)-1)%h;
	if(K<record.at(0)){
		cout << visit.at(K-1) << endl;
	}
	else{

	cout << visit.at(record.at(0)+m)  << endl;
}
}



Measured memory_bytes: 10932
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int a,b,bj=0;
int main() {
	cin>>a>>b;
	if(!(a%3))bj=1;
	if(!(b%3))bj=1;
	if(!((a+b)%3))bj=1;
	if(bj)puts("Possible");
	else puts("Impossible");
	return 0;
}

Measured memory_bytes: 256