akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>

using ll = long long;
const ll MOD = 1000000007;

int main(){
    ll n;
    std::cin >> n;
    std::vector<ll> a(n);
    for(int i = 0; i < n; i++){
        std::cin >> a[i];
    }

    std::vector<ll> csum(n);
    csum[0] = a[0] % MOD;
    for(int i = 1; i < n; i++){
        csum[i] = (csum[i - 1] + a[i]) % MOD;
    }

    ll ans = 0;
    for(int i = 0; i < n - 1; i++){
        ans += (a[i] % MOD) * ((csum[n - 1] - csum[i] + MOD) % MOD);
        ans = ans % MOD;
    }
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 6424
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include <string>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;
int main(){
 	string s; cin >>s;
 	int n=s.size();
 	int cnt=0;
 	int ans=0;
 	for(int i=0;i<n;i++){
 		if(s[i]=='g'&&cnt>0){
 			cnt--;
 			ans++;
 		}
 		else if(s[i]=='g'&&cnt==0){
 			cnt++;
 		}
 		else if(s[i]=='p'&&cnt==0){
 			cnt++;
 			ans--;
 		}
 		else{
 			cnt--;
 		}
 	}
 	cout << ans << endl;
 }

Measured memory_bytes: 512
#include <cstdio>
#include <queue>
#include <set>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct par{
	int x, y;
	par ( int nx = 0, int ny = 0 ){
		x = nx; y = ny;
	}
	friend bool operator < ( par a, par b ){
		return a.y < b.y;
	}
};

int n, m, a[310][310], p[310], sol;
bool ok[310];
queue<int> q[310];
priority_queue<par> pq;
multiset<int> s;

int main(){
	scanf("%d %d", &n, &m);
	for ( int i = 0; i < n; i++ ){
		p[i] = 0;
		for ( int j = 0; j < m; j++ ){
			scanf("%d", &a[i][j]);
			--a[i][j];
		}
		q[a[i][0]].push(i);
	}
	
	for ( int i = 0; i < m; i++ ){
		ok[i] = true;
		pq.push(par(i, q[i].size()));
		s.insert(q[i].size());
		sol = max(sol, (int)q[i].size());
	}
	while ( !pq.empty() ){
		
		par h = pq.top();
		pq.pop();
		
		if ( !ok[h.x] ) continue;
		ok[h.x] = false;
		s.erase(s.find(q[h.x].size()));
		
		while ( !q[h.x].empty() ){
			int in = q[h.x].front(); q[h.x].pop();
			
			for ( ; p[in] < m && !ok[a[in][p[in]]] ; p[in]++ )
				;
			
			if ( p[in] < m ){
				s.erase(s.find(q[a[in][p[in]]].size()));
				q[a[in][p[in]]].push(in);
				pq.push(par( a[in][p[in]], q[a[in][p[in]]].size() ));
				s.insert(q[a[in][p[in]]].size());
			}
			else{
				printf("%d\n", sol);
				return 0;
			}
		}
		sol = min(sol, *(--s.end()) );
		
	}
	
	return 0;
}


Measured memory_bytes: 1912
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int sx = sc.nextInt();
        int sy = sc.nextInt();
        int tx = sc.nextInt();
        int ty = sc.nextInt();
        StringBuilder res = new StringBuilder("");
        for(int i = 0; i < ty - sy; i++)
            res.append('U');
        for(int i = 0; i < tx - sx; i++)
            res.append('R');
        for(int i = 0; i < ty - sy; i++)
            res.append('D');
        for(int i = 0; i < tx - sx; i++)
            res.append('L');
        res.append('D');
        for(int i = 0; i < tx - sx + 1; i++)
            res.append('R');
        for(int i = 0; i < ty - sy + 1; i++)
            res.append('U');
        res.append('L');
        res.append('U');
        for(int i = 0; i < tx - sx + 1; i++)
            res.append('L');
        for(int i = 0; i < ty - sy + 1; i++)
            res.append('D');
        res.append('R');
        System.out.println(res.toString());
        
    }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define Dracarys ios_base::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
 
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()

inline void fileIO(bool &ptime){ 
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);ptime=true;
    #endif
}

clock_t start_time;
inline double getTime(){ return ((double)(clock()-start_time)/CLOCKS_PER_SEC); }

int n;
const int mxn=1e7+5;
vector<int> v(mxn);
inline void solve(ll tt){
    cin>>n;
    ll cnt=(n*(n+1ll))/2ll;

    for (int i=2;i<=n;i++){
        for (int j=1;(j*i)<=(n);j++)
            v[i*j]++;
        cnt+=((ll)i*((ll)v[i]));
    }
    cout<<cnt<<"\n";
}

int main(){
        
    srand((unsigned)time(0));

    bool ptime=false;
    fileIO(ptime);
    start_time=clock();

    Dracarys

    ll tt=0,t=1;
    //cin>>t;

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

    if (ptime)
    cerr<<getTime()<<endl;

    return 0;
}

Measured memory_bytes: 42220
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

// 連結な重みなしグラフGは二部グラフであるか？
// 二部グラフなら各頂点集合の要素数をPairで返し，そうでなければmake_pair(-1, -1)を返す．
LLP getBipartiteGraphCount(vector< vector<long long> > G) {
    vector<long long> color(G.size(), 0);
    stack<long long> st;
    st.push(0);
    color[0] = 1;
    bool isBipartite = true;

    while (!st.empty()) {
        int p = st.top(); st.pop();
        for (int i = 0; i < G[p].size(); i++) {
            if (color[G[p][i]] == color[p]) {
                // G is not bipartite
                isBipartite = false;
                while(!st.empty()) st.pop();
                break;
            }
            if (color[G[p][i]] == 0) {
                st.push(G[p][i]);
                color[G[p][i]] = (-1) * color[p];
            }
        }
    }
    if (isBipartite) {
        long long countPlus = 0;
        long long countMinus = 0;

        for (int i = 0; i < G.size(); i++) {
            if (color[i] > 0) countPlus++;
            else if (color[i] < 0) countMinus++;
        }
        // if countPlus + countMinus < G.size(), G is not connected
        return (countPlus + countMinus == G.size() ? make_pair(countPlus, countMinus) : make_pair((long long)-1, (long long)-1));
    } else return make_pair(-1, -1);
}

int main() {

    long long N, M;
    cin >> N >> M;

    vector< vector<long long> > G(N, vector<long long>(0));
    for (int i = 0; i < M; i++) {
        long long A, B;
        cin >> A >> B;
        A--; B--;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    LLP result = getBipartiteGraphCount(G);

    if (result.first > 0) cout << (result.first * result.second - M) << endl;
    else cout << (N * (N - 1) / 2 - M) << endl;

    return 0;
}

Measured memory_bytes: 12800
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD=1000000007;
long long a[100005];
int myabs (int x) {
	if (x<0) return -x; else return x;
}
int main ( ) {
	int n,m,i;
	scanf("%d%d",&n,&m);
	if (myabs(n-m)>1) {
		puts("0");return 0;
	}
	a[1]=1;
	for (i=2;i<=100000;i++) {
		a[i]=a[i-1]*i%MOD;
	}
	if (myabs(n-m)==1) {
		printf("%I64d\n",a[n]*a[m]%MOD);
	}
	else {
		printf("%I64d\n",2*a[n]*a[m]%MOD);
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-9;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

constexpr ll INF=1e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int n;
  ll x[252521], y[252521];
  cin>>n;
  REP(i, n){
    cin>>x[i]>>y[i];
  }
  ll maa=-INF, mia=INF, mab=-INF, mib=INF;
  REP(i, n){
    ll a, b;
    a=x[i]-y[i];
    b=x[i]+y[i];
    CHMAX(maa, a);
    CHMIN(mia, a);
    CHMAX(mab, b);
    CHMIN(mib, b);
  }
  cout<<max(maa-mia, mab-mib)<<'\n';
  return 0;
}


Measured memory_bytes: 6780
import java.io.*;
import java.util.*;
 
public class Main {
  private static boolean debug = false;
  private static boolean elapsed = true;
 
  private static PrintWriter _err = new PrintWriter(System.err);
 
  private void solve(Scanner sc, PrintWriter out) {
    long a = sc.nextLong();
    long b = sc.nextLong();
    long x = sc.nextLong();
 
    out.println((b / x) - (a / x) + (a % x == 0 ? 1 : 0));
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();
 
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();
 
    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 22996
h,w,a,b = map(int,input().split())

MOD = 1000000007
fac = [1]
inv = [1]
for i in range(1,200010):
	fac.append(fac[i-1]*i%MOD)
	inv.append(pow(fac[i],MOD-2,MOD))

ans = 0

for i in range(b+1,w+1):
	ans += fac[h-a+i-2]*inv[h-a-1]*inv[i-1]*fac[a+w-i-1]*inv[a-1]*inv[w-i]%MOD
	ans %= MOD

print(ans)

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

int main () {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) {cin >> A[i];}
  
  bool flag = true;
  rep(i, N) {
    if (A[i]%2 == 0) {
      if ((A[i]%3 != 0) && (A[i]%5 != 0)) {
        flag = false;
      }
    }
  }
  if (flag) {
    cout << "APPROVED" << endl;
  } else {
    cout << "DENIED" << endl;
  }
}

Measured memory_bytes: 256
# ABC085D - Katana Thrower
import sys
input = sys.stdin.readline

def main():
    N, H = tuple(map(int, input().split()))
    AB = tuple(tuple(map(int, input().split())) for _ in range(N))
    A, B = zip(*AB)
    C = sorted([(i, 0) for i in A] + [(i, 1) for i in B], reverse=1)
    ans = 0
    for i, t in C:
        if t == 0:
            ans += (H + i - 1) // i
            break
        else:
            ans += 1
            H -= i
            if H <= 0:
                break
    print(ans)


if __name__ == "__main__":
    main()

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

struct UF{
	vector<int> e;
	UF(int n): e(n, -1) {}
	bool same_set(int a, int b) { return find(a) == find(b); }
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
	void join(int a,int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(e[a] > e[b]) swap(a, b);
		e[a] += e[b], e[b] = a;
	}
};

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1), id(n + 1);
	UF uf(n + 1);
	for(int i = 1; i <= n; ++i) cin >> a[i], id[a[i]] = i;
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		uf.join(u, v);
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(uf.same_set(i, id[i])) ans ++;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 1408
import itertools

# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
pf = trial_division(n)
numSet = set()
ans = 10**9

# print('pf:', pf)

for i in range(1, len(pf)+1):
    combs = list(itertools.combinations(pf, i))
    # print('combs:', combs)

    for comb in combs:
        # print('comb:', comb)
        temp = 1
        for num in comb:
            temp *= num
        numSet.add(temp)

numSet.add(1)
# print('numSet:', numSet)

for num in numSet:
    q1 = num
    q2 = n // q1
    length = max(len(str(q1)), len(str(q2)))
    ans = min(ans, length)

print(ans)

Measured memory_bytes: 134624
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        String str[]=br.readLine().split(" ");
        int x=Integer.parseInt(str[0]);
        int y=Integer.parseInt(str[1]);
        boolean b=false;;
        for(int i=0;i<=x;i++)
        {
            if(i*2+(x-i)*4==y)
            {
                b=true;
                break;
            }
        }
        if(b)
        pw.println("Yes");
        else
        pw.println("No");
        pw.flush();
        pw.close();
    }
}

Measured memory_bytes: 32716
#include <iostream>
#include <utility>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
	int q;
	cin>>q;
	while(q--){
		int c,a,n,ans;
		cin>>c>>a>>n;
		int k=min(c,min(a,n));
		ans=k;
		c-=k;
		a-=k;
		n-=k;
		k=min(c/2,a);
		ans+=k;
		c-=2*k;
		a-=k;
		ans+=c/3;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;

int main() {
  ll l, r;
  cin >> l >> r;
  r = min(r, l + 4038);
  int ans = 2018;
  for (ll i = l; i <= r; i++) {
    for (ll j = i + 1; j <= r; j++) {
      int x = i * j % 2019;
      ans = min(ans, x);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3116
#include <stdio.h>

int main(){

	int N,i;
  	scanf("%d",&N);
  	int A[N],B[N],C[N-1];
  	int count = 0;
  	for(i=0;i<N;i++){
    	scanf("%d",&A[i]);
  	}
  	for(i=0;i<N;i++){
      	scanf("%d",&B[i]);
    }
	 for(i=0;i<N-1;i++){
    	scanf("%d",&C[i]);
  	}
  	for(i=0;i<N;i++){
    	count += B[i];
    }
  	for(i=0;i<N;i++){
     	if(A[i+1] - A[i] == 1) count = count + C[A[i]-1]; 
    }
  	printf("%d\n",count);
}

Measured memory_bytes: 128
#include <stdio.h>

int main(void) {
	int i, n;
	int a;
	long sum = 0;
	int min, max;
	scanf("%d", &n);
	for(i = 0; i < n; i++) {
		scanf("%d", &a);
		if(i == 0) {
			min = max = a;
		}
		sum += a;
		if(a > max) max = a;
		else if(a < min) min = a;
	}
	printf("%d %d %ld\n", min, max, sum);
	return 0;
}


Measured memory_bytes: 2100
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <climits>

using namespace std;

typedef unsigned long ulong;
typedef pair<ulong,int> pli;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP(f,s) make_pair(f,s)

priority_queue<pli> p;
ulong t[100000];
int n=0;
int l=0;
ulong g=ULONG_MAX;

bool check(int c){
	if(c==0)
		return t[c]>t[c+1];
	if(c==n-1)
		return t[c]>t[c-1];
	return t[c]>t[c+1]&&t[c]>t[c-1];
}

int main(){
	scanf("%d %d",&n,&l);
	REP(i,n)
		scanf("%lu",&t[i]);
	REP(i,n){
		if(check(i))
			p.push(MP(g-(l-t[i]),i));
	}
	pli m;
	ulong res=0;
	while(!p.empty()){
		do{
		m=p.top();
		p.pop();
		t[m.second]=0;
		if(m.second>0)
			if(check(m.second-1))
				p.push(MP(m.first-(l-t[m.second-1]),m.second-1));
		if(m.second<n-1)
			if(check(m.second+1))
				p.push(MP(m.first-(l-t[m.second+1]),m.second+1));
		if(p.empty())
			break;
		}while(m.first == p.top().first);
		res+=g-m.first;
		g=m.first;
	}
	printf("%lu\n",res);
}

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

char NOT[3] = {'2', '1', '0'};
char AND[3][3] = {{'0', '0', '0'}, {'0', '1', '1'}, {'0', '1', '2'}};
char OR[3][3] = {{'0', '1', '2'}, {'1', '1', '2'}, {'2', '2', '2'}};

char s[100];
char s1[100];

char getNumber() {
  char k[100], kLeft[100], kN[100], notCounter[100], kNumber = 0;
  for (char i = 0; i < 100; i++) notCounter[i] = 0;
  char ans;
  for (char i = 0; s1[i] != 0; i++) {
    if (s1[i] == '*' || s1[i] == '+') kLeft[kNumber] = s1[i-1] - '0';
    if (s1[i] == '-') notCounter[kNumber]++;
    else if (s1[i] == '(') kNumber++;
    else if (s1[i] == '*') kN[kNumber] = 0;
    else if (s1[i] == '+') kN[kNumber] = 1;
    else if (s1[i] == ')') {
      if (kN[kNumber] == 0) {
        s1[i] = AND[kLeft[kNumber]][s1[i-1] - '0'];
      } else {
        s1[i] = OR[kLeft[kNumber]][s1[i-1] - '0'];
      }
      kNumber--;
      if (notCounter[kNumber] % 2 == 1) s1[i] = NOT[s1[i] - '0'];
      ans = s1[i];
      notCounter[kNumber] = 0;
    } else {
      if (notCounter[kNumber] % 2 == 1) s1[i] = NOT[s1[i] - '0'];
      ans = s1[i];
      notCounter[kNumber] = 0;
    }
  }
  return ans - '0';
}

char check(char p, char q, char r) {
  for (char i = 0; s[i] != 0; i++) {
    s1[i] = s[i];
    if (s1[i] == 'P') s1[i] = p + '0';
    if (s1[i] == 'Q') s1[i] = q + '0';
    if (s1[i] == 'R') s1[i] = r + '0';
    s1[i+1] = 0;
  }
  if (getNumber() == 2) return 1;
  return 0;
}

int main() {
  while (1) {
    scanf("%s", s);
    if (s[0] == '.') break;
    char ans = 0;
    for (char p = 0; p < 3; p++)
      for (char q = 0; q < 3; q++)
        for (char r = 0; r < 3; r++)
          ans += check(p, q, r);
    printf("%d\n", (int)ans);
  }
}



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

int main(void){
    vector<int> num(3);
    cin >> num.at(0) >> num.at(1) >> num.at(2);

    int count=0;
    if(num[0]%2!=num[1]%2 && num[1]%2==num[2]%2){
        num[1]++; num[2]++; count++;
    }else if(num[0]%2!=num[1]%2 && num[0]%2==num[2]%2){
        num[0]++; num[2]++; count++;
    }else if(num[1]%2!=num[2]%2 && num[0]%2==num[1]%2){
        num[0]++; num[1]++; count++;
    }
    sort(num.begin(),num.end());
    count += (2*num[2]-num[1]-num[0])/2;

    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <vector>
/* 変数i を n回繰り返すマクロ */
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
int main()
{
    cout << fixed << setprecision(10);//小数点以下10桁出力
    long double a,b,c;

    cin >> a >> b >> c;

    long double sum;

    sum = a + b + (2 * sqrt(static_cast<long double>(a * b)));

    if(sum < c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
da = deque(sorted(a))
dans = deque()
dans.append(da.popleft())
for _ in range(1,n):
  if len(dans) == 0:
    dans.append(da.popleft())
  else:
    dlast = dans.pop()
    daleft = da.popleft()
    if dlast != daleft:
      dans.append(dlast)
      dans.append(daleft)
print(len(dans))
    

Measured memory_bytes: 14624
#include <stdio.h>
using namespace std;
 int main(){
 int a,b;scanf("%d%d",&a,&b);
 if(a<b){
 for(int i=0;i<b;i++)printf("%d",a);
 }else{
 for(int i=0;i<a;i++)printf("%d",b);
}
 printf("\n");
 }


Measured memory_bytes: 1700
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def precompute():
    maxAS = 1000000
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    import pickle
    pickle.dump(eratree, open("eratree.pickle", "wb"))


def solve(N, AS):
    import pickle
    eratree = pickle.load(open("eratree.pickle", "rb"))
    num_division = 0

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

if sys.argv[-1] == 'ONLINE_JUDGE':
    precompute()
elif sys.argv[-1] != "DONTCALL":
    import subprocess
    subprocess.call("pypy3 Main.py DONTCALL", shell=True, stdin=sys.stdin, stdout=sys.stdout)
else:
    main()


Measured memory_bytes: 212740
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ull unsigned long long
#define mp make_pair
#define F first
#define S second
#define mod 1000000007

int n;
double dp[302][302][302];
double ev[302][302][302];
int cnt[4];

int main()
{
    cin >> n;
    int x;
    for(int i=0;i<n;i++)
    {
        cin >> x;
        cnt[x]++;
    }

    dp[cnt[1]][cnt[2]][cnt[3]] = 1;

    for(int c = n; c>=0; c--)
    {
        for(int b=n; b>=0; b--)
        {
            for(int a =n; a>=0; a--)
            {
                
                if(a == 0 && b == 0 && c == 0)
                    continue;
                if(a+b+c > n)
                    continue;

                double p_wasted = (double)(n-(a+b+c))/n;
                double ev_wasted = p_wasted/(1-p_wasted);
                ev[a][b][c] += ev_wasted * dp[a][b][c];

                if(a>0)
                {
                    double p = (double)a/(a+b+c);
                    dp[a-1][b][c] += dp[a][b][c] * p;
                    ev[a-1][b][c] += ev[a][b][c] * p;
                }

                if(b>0)
                {
                    double p = (double)b/(a+b+c);
                    dp[a+1][b-1][c] += dp[a][b][c] * p;
                    ev[a+1][b-1][c] += ev[a][b][c] * p;
                }

                if(c>0)
                {
                    double p = (double)c/(a+b+c);
                    dp[a][b+1][c-1] += dp[a][b][c] * p;
                    ev[a][b+1][c-1] += ev[a][b][c] * p;
                }
            }
        }
    }

    printf("%.10lf\n", ev[0][0][0] + cnt[1] + 2*cnt[2] +3*cnt[3]);




}


Measured memory_bytes: 430336
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <bitset>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
 
const int mod = 1000000007;
//const int mod = 998244353;
 

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
 
 
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} c(200005);
 
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
vector<long long> enum_divisors(long long N) {
    vector<long long> res;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // 重複しないならば i の相方である N/i も push
            if (N/i != i) res.push_back(N/i);
        }
    }
    // 小さい順に並び替える
    sort(res.begin(), res.end());
    return res;
}

// M * (M-1)^(N-1-K) * N-1 C K
int main(int argc, const char * argv[]) {
    string S,T;
    cin >> S >> T;
    ll A,B; cin >> A >> B;
    string U; cin >> U;
    
    if(U.compare(S)==0){
        cout << A -1 << " " << B << endl;
    }else{
        cout << A << " " << B-1<< endl;
    }
    return 0;
}



Measured memory_bytes: 3328
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
const int N=1e6+4;
int32_t main()
{
	#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
	#endif

	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(auto &i:a)cin>>i;


	auto ok=[&](int x)
	{
		int c=0;
		for(auto i:a)
		{
			c+=(i+x-1)/x - 1;
		}
		return c<=k;
	};


	int lo=1;int hi=1e9;
	int ans=-1;
	while(lo<=hi)
	{
		int mid=(lo+hi)/2;
		if(ok(mid)){ans=mid;hi=mid-1;}
		else lo=mid+1;
	}

	//assert(ans>0);

	cout<<ans;
	
	
}

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

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



    for (int i = X; i < X+1000;i++) {
      int a=0;
      for (int j = 2; j <= sqrt(i)/1; j++) {
        if(i%j==0){
          a=1;
          break;
        }
        
      }
      if(a==0){
        
       cout <<i<< endl;
        break;
      }
    }
  
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s,p;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long t,i,j,n,m,l,r,k,c,ans=0;
    cin>>s>>c;
    n=s.size();
    for(i=0; i<n; i++)
    {
        p+='0';
    }
    if(c==1)
    {
        n=s.size();
        ans+=(9*(n-1));
        int f=0;
        for(i=0; i<n; i++)
        {
            if(s[i]!='0')
            {
                f++;
            }
        }
        ans+=(s[0]-48);
    }
    else if(c==2)
    {
        m=n-2;
        ans+=81*((m*(m+1))/2);
        for(i=1; i<10; i++)
        {
            p[0]=(char)(i+48);
            for(j=1; j<10; j++)
            {
                for(int k=1; k<n; k++)
                {
                    p[k]=(char)(j+48);
                    if(p<=s)
                    {
                        ans++;
                    }
                    p[k]='0';
                }
            }
        }
    }
    else
    {
        m=n-3;
        l=0,r=1;
        while(m>0)
        {
            l+=(m*r);
            m--,r++;
        }
        ans+=729*l;
        for(i=1; i<10; i++)
        {
            p[0]=(char)(i+48);
            for(j=1; j<10; j++)
            {
                for(k=1; k<n-1; k++)
                {
                    p[k]=(char)(j+48);
                    for(r=1; r<10; r++)
                    {
                        for(l=k+1; l<n; l++)
                        {
                            p[l]=(char)(r+48);
                            if(p<=s)
                            {
                                ans++;
                            }
                            p[l]='0';
                        }
                    }
                    p[k]='0';
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

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

ll N, K;

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

   ll ans = 0;
   ll a = 0, b = 0;
   if (K&1) {
      for (ll x = 1; x <= N; x++) {
         if (x % K == 0) {
            a++;
         }
      }
      ans = a*a*a;
   } else {
      for (ll x = 1; x <= N; x++) {
         if (x % K == 0) {
            a++;
         } else if (x % K == K/2) {
            b++;
         }
      }
      ans = a*a*a + b*b*b;
   }
   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] n_k = sc.nextLine().split(" ");
		int k = Integer.parseInt(n_k[1]);
		Map<Integer,Integer> balls = Arrays.asList(sc.nextLine().split(" "))
				.parallelStream()
				.map(Integer::valueOf)
				.collect(Collectors.toMap(i->i,j->1,(s,a)->s+a));
		List<Integer> count=balls
				.values()
				.parallelStream()
				.sorted()
				.collect(Collectors.toList());
		int nowK=balls.size(),result=0;
		for(Integer i:count) {
			if(nowK--<=k)break;
			result+=i;
		}
		System.out.println(result);
	}
}

Measured memory_bytes: 89648
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
// #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef int ll;
const ll MAXN = 5e5+5;
const ll MAX = 1e5+5;
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll powmod(ll a,ll b,ll mod){ll ret=1;while(b>0){if(b&1)ret=ret*a%mod;b>>=1;a=a*a%mod;}return ret;}
inline ll multi(ll a,ll b,ll mod){ll ret=0;while(b){if(b&1)ret=(ret+a)%mod;b>>=1;a<<=1;a%=mod;}return ret;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll d=exgcd(b,a%b,x,y);ll tmp=x;x=y;y=tmp-a/b*x;return d;}
inline ll inverse(ll a,ll b){ll x,y;ll d=exgcd(a,b,x,y);if(d!=1)return -1;return (x%b+b)%b;}
char s[MAX];
LL R[MAX];
LL G[MAX];
LL B[MAX];
LL slove(char a,char b,char c,int n){
	memset(R,0,sizeof(R));
	memset(G,0,sizeof(G));
	memset(B,0,sizeof(B));
	for(int i=1;i<=n;++i){
		if(s[i]==a)R[i]=1;
		R[i]+=R[i-1];
	}
	for(int i=1;i<=n;++i){
		if(s[i]==b)G[i]=R[i];
		G[i]+=G[i-1];
	}
	for(int i=1;i<=n;++i){
		if(s[i]==c)B[i]=G[i];
		B[i]+=B[i-1];
	}
	LL sum=B[n];
	// cout<<sum<<endl;
	for(int i=1;i<=n;++i){
		if(s[i]==a){
			int l=i-1,r=i+1;
			while(l>=1&&r<=n){
				if(s[l]==b&&s[r]==c)
					--sum;
				--l;
				++r;
			}
		}
	}
	return sum;
}
int main(){
	int n;
	scanf("%d%s",&n,s+1);
	LL sum=0;
	sum+=slove('R','G','B',n);
	sum+=slove('R','B','G',n);
	sum+=slove('G','R','B',n);
	sum+=slove('G','B','R',n);
	sum+=slove('B','R','G',n);
	sum+=slove('B','G','R',n);
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 6172
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007

vector<int> g[1<<20];
vector<bool> visited(1<<20, false);
vector<int> parent(1<<20, -1);
int n, a, b;

void fdfs(int s, int p) {
	parent[s] = p;
	for(auto &x: g[s]) {
		if(x != p) {
			fdfs(x, s);
		}
	}
}

int dfs(int s) {
	visited[s] = true;
	int tsum = 1;
	for(auto &x: g[s]) {
		if(not visited[x]) {
			tsum += dfs(x);
		}
	}
	return tsum;
}

int main() {
	ios::sync_with_stdio(false);
    //freopen("input.in","r",stdin);
 	//freopen("output.out","w",stdout);
	cin>>n;
	rep(i, n-1) {
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}

	fdfs(1, -1);
	vector<int> dia;
	int in = n;
	while(in != -1) {
		dia.pb(in);
		in = parent[in];
	}

	reverse(dia.begin(), dia.end());
	int sz = dia.size();
	rep(i, sz) visited[dia[i]] = true;
	int sum1 = 0;
	int sum2 = 0;

	rep(i, sz) {
		if(i < (sz+1)/2) {
			sum1 += dfs(dia[i]);
		} else {
			sum2 += dfs(dia[i]);
		}
	}

	sum1 -= 1;
	sum2 -= 1;

	if(sum1 > sum2) {
		cout<<"Fennec"<<endl;
	} else cout<<"Snuke"<<endl;

	return 0;
}


Measured memory_bytes: 37500
#include<iostream>
#include<string>
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
using namespace std;
int y[100];
int main() {
    while(1) {
        int n, a, b, c, x;
        cin >> n >> a >> b >> c >> x;
        if (n == 0) break;
        REP(i, n) cin >> y[i];

        int i = 0;
        int frame;
        for (frame = 0; frame <= 10000; ++frame) {
            if (y[i] == x) {
                i++;
                if (i == n) break;
            }
            x = (x * a + b) % c;
        }
        cout << (frame > 10000 ? -1 : frame) << endl;
    }
}


Measured memory_bytes: 3008
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		for(;;){
			int b=sc.nextInt();// rbO{[iX 5
			int r=sc.nextInt();// M[{[iX 3
			int g=sc.nextInt();// ÊíuhE
			int c=sc.nextInt();// `F[
			int s=sc.nextInt();// X^[
			int t=sc.nextInt();// Q[
			if((b|r|g|c|s|t)==0){
				break;
			}
			int ans=100+95*b+63*r+7*g+2*c+3*s-3*t;
			println(""+ans);
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
using System;
using System.Linq;

namespace ABC148C
{
    class Program
    {
        static void Main(string[] args)
        {
            var AB = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var A = AB[0];
            var B = AB[1];

            Console.WriteLine(Lcm(A, B));
        }

        static long Gcd(long m, long n)
        {
            long tmp;
            while (m % n != 0)
            {
                tmp = n;
                n = m % n;
                m = tmp;
            }
            return n;
        }

        static long Lcm(long m, long n)
        {
            return m * n / Gcd(m, n);
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

int main()
{
  int n, m;
  cin >> n >> m;
  ll cnt;
  if (n == m)
  {
    cnt = 2;
    for (int i = 1; i <= n; ++i)
    {
      cnt = (cnt * i) % MOD;
    }
    for (int i = 1; i <= m; ++i)
    {
      cnt = (cnt * i) % MOD;
    }
  }
  else if (abs(n - m) == 1)
  {
    cnt = 1;
    for (int i = 1; i <= n; ++i)
    {
      cnt = (cnt * i) % MOD;
    }
    for (int i = 1; i <= m; ++i)
    {
      cnt = (cnt * i) % MOD;
    }
  }
  else
    cnt = 0;
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,x;
  cin>>n>>m>>x;
  vector<int>a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
  }
int s1=0;
int s2=0;
for(int i=0;i<m;i++){
  if(a[i]<x){
    s1++;
  }else{
    s2++;
  }
  
  }
  cout<<min(s1,s2)<<endl;

}

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

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int);
void init();
void printList();
void deleteNode(NodePointer);
void deleteFirst();
void deleteLast();
void delete(int);
void insert(int key);

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
  }

  printList();
  return 0;
}

NodePointer listSearch(int key){
  NodePointer n;
  for(n = nil->next; n != nil; n = n->next ){
    if(n->key == key) return n;
  }
  return NULL;
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  (t->prev)->next = t->next;

  (t->next)->prev = t->prev;

  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  NodePointer t = nil->prev;
  if ( t == nil ) return;
  deleteNode(t);
}

void delete(int key){
  NodePointer n = listSearch(key);
  if(n != NULL) deleteNode(n);
  else return;
}


void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;

  x->next = nil->next;
  x->prev = nil;

  nil->next = x;
  if(nil->prev == nil) nil->prev = x;
  else (x->next)->prev = x;
}



Measured memory_bytes: 33000
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

let main() =
    let [| N; K; S |] = reada int
    let S = int64 S

    let lim = int64 1e9

    let gomi =
        if S <> lim then S + 1L else 1L

    let ass = ResizeArray<int64>()
    for i in 1 .. K do
        ass.Add(S)
    for i in 1 .. N - K do
        ass.Add(gomi)

    String.Join(" ", ass) |> puts

    ()

main()
writer.Close()


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

int main() {
    ll n,x,ans=0;
    cin >> n >> x;
    ll a[n+2];
    for(ll i=1;i<=n;i++) cin >> a[i];
    a[0]=0;
    a[n+1]=0;
    for(ll i=0;i<=n;i++){
        ll cur=0;
        if(a[i+1]+a[i]-x > 0) cur =a[i+1]+a[i]-x;
        ans += cur;
        a[i+1] -= cur;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    int a, b, c, d, e = 0;
    cin >> a >> b >> c >> d;
    if(a == 1 or a == 9 or a == 7 or a == 4){
        if((b == 1 or b == 9 or b == 7 or b == 4) and b != a){
            if((c == 1 or c == 9 or c == 7 or c == 4) and (c != a and c != b)){
                if((d == 1 or d == 9 or d == 7 or d == 4) and (d != a and d != b and d != c)){
                    e = 1;
                }
            }
        }
    }
    
    if(e == 0){
        cout << "NO";
    }
    else if (e == 1){
        cout << "YES";
    }
    
}


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

int main() {
  string s;
  cin >> s;
  int ans = 0;  int countI = 0; int minAns = 0;
  string count;
  	for(int i = 0;i < s.size()-2;i++){
    count = s.substr(i,3);
    countI = atoi(count.c_str());
    minAns = abs(753 - countI);
   if(i == 0){
     ans = minAns;
   }else{
     ans = min(ans,minAns);
    }
   }
  cout << ans << endl;
}

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

int main()
{
    string s;
    cin>>s;
    s=s+"S";
    int count=0,finalc=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='R')
        count++;
        else
        {
            if(count>finalc)
            finalc=count;
            count=0;
        }
        
    }
   cout<<finalc;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<sstream>
using namespace std;
#define MOD 1000000007
#define ll long long
const long long INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

class UnionFind {
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};


int find(vector<long long> &arr, long long obj) {
	if (arr[arr.size() - 1] < obj)return arr.size()-1;
	if (arr[0] > obj)return -1;

	int min = 0; int max = arr.size() - 1;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[min+(max-min) / 2] > obj) {
			max = min + (max - min) / 2;
		}
		else {
			min = min + (max - min) / 2;
		}
		if (max - min == 1) {
			return min;
		}
	}


}

void divisor(ll n,vector<ll> &ret) {
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(ret.begin(), ret.end());
	
}//約数求める


ll kaijou(int n) {
	ll temp = 1;
	for (int i = 2; i <= n; i++) {
		temp *= i;
		temp %= MOD;
	}
	return temp;
}

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b >= c-1) {
		cout << b + c;
	}
	else {
		cout << b + (a + b + 1);
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define EPS 1e-14
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) FOR(i, 0, n)
#define PI 2*acos(0.0)
#define ALL(a) (a).begin(),(a).end()
#define DEBUG(x) cout<<#x <<": "<< x << "\n"
#define DEBUG_ARR(a) REP(i, size(a)){ cout << #a << "[" << i << "]: " << a[i] << "\n"; }
const int VX[] = { 0, 1, 0, -1 };
const int VY[] = { 1, 0, -1, 0 };
const long MOD = 1000000007;

typedef long long ll;

int main()
{
	int N, D, X;
    cin >> N >> D >> X;
    
    int A = 0, a;
    REP(i, N)
    {
        cin >> a;
        A += (D / a) + (D % a == 0 ? 0 : 1);
    }
    
    cout << X + A << endl;

	return 0;
}



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

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;


int main(){
  int n;
  cin >> n;
  vector<int> v(n, 0);
  rep(i, n){
    cin >> v[i];
    v[i]--;
  }
  vector<int> v2(n, -1);
  v2[0] = 0;
  int next = v[0];
  int count = 1;
  while(v2[next] == -1){
    v2[next] = count;
    next = v[next];
    count++;
  }

  cout << v2[1] << endl;
  
  return 0;
}


Measured memory_bytes: 1656
k,n=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)

b=Array.new(n)
(n-1).times do |i|
    b[i]=a[i+1]-a[i]
end
b[n-1]=k-a[n-1]+a[0]
puts k-b.max


Measured memory_bytes: 29012
#include <iostream>
#include <sstream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

typedef   signed long long int slli;
typedef unsigned long long int ulli;
const slli MAX_SLLI = 0x7FFFFFFFFFFFFFFF;
const slli MIN_SLLI = 0x8000000000000000;
const ulli MAX_ULLI = 0xFFFFFFFFFFFFFFFF;
const ulli MIN_ULLI = 0x0000000000000000;

#define N_TIMES(i, n)     for (ulli i = 0;     i <  n; ++i)
#define N_TIMES_REV(i, n) for (slli i = n - 1; i >= 0; --i)

#ifdef __DEBUG__
template<typename T>
std::ostream& operator<<(std::ostream &os, const std::list<T> &list)
{
  const std::string delim = ", ";
  typename std::list<T>::const_iterator itr = list.begin();
  while (itr != list.end()) {
    os << *itr;
    ++itr;
    if(itr != list.end()) os << delim;
  }
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream &os, const std::vector<T> &v)
{
  const std::string delim = ", ";
  for (unsigned n = 0; n < v.size(); ++n) {
    os << v[n];
    if((n + 1) < v.size()) os << delim;
  }
  return os;
}
#endif

int main()
{
  ulli N, M;
  std::cin >> N >> M;
  
  if (N > (M / 2)) { // Sピースの方が多い → cピースの半分だけできる
    std::cout << (M / 2) << std::endl;
  } else { // cピースの方が多い
    // もともとのSピースでつくれるSccの数はN個(Sピースの個数と同じ)
    
    // 作ったあとで余るcピースの数d
    ulli d = M - (N * 2);
    
    // Sccを全部cピースで作るとひとつあたり4個ピースが必要
    ulli r = d / 4;
    
    // Sccは合計N + (d / 4)個
    std::cout << (N + r) << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
K = int(input())
if K % 7 == 0:
    L = 9 * K / 7
else:
    L = 9 * K
if L % 2 == 0 or L % 5== 0:
    print(-1)
else:
    c = 1
    i = 10
    while True:
        if i % L == 1:
            print(c)
            break
        c += 1
        i = (i % L) * 10

Measured memory_bytes: 9192