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

using namespace std;

void solve()
{
	int n;
	cin >> n;
	while(n--)
	{
		string l, s;
		cin >> l >> s;
		if(l.size() < s.size())
		{
			swap(l, s);
		}
		reverse(l.begin(), l.end());
		reverse(s.begin(), s.end());
		string sum;
		
		int sizel = l.size();
		int sizes = s.size();
		int buf = 0;
		for(int i = 0; i < sizes; ++i)
		{
			sum += (l[i] + s[i] - '0' - '0' + buf) % 10 + '0';
			buf = (l[i] + s[i] - 2 * '0' + buf) / 10;
		}
		for(int i = sizes; i < sizel; ++i)
		{
			sum += (l[i] - '0' + buf) % 10 + '0';
			buf = (l[i] - '0' + buf) / 10;
		}
		if(buf > 0)
		{
			sum += buf + '0';
		}
		int size = sum.size();
		if(size > 80)
		{
			cout << "overflow" << endl;
			continue;
		}
		for(int i = size - 1; i >= 0; --i)
		{
			cout << sum[i];
		}
		cout << endl;
	}
}

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

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;

int kaibun(string SA){
    int a=0;
 
    for(int i=0;i<(SA.size()+1)/2;i++){
        if(SA[i]!=SA[SA.size()-1-i]){a++;}
    }
    return a;

}

int main(){
    string S;
    cin >> S;
    int b,c;
    char T[(S.size()-1)/2];
    for(int i=0;i<(S.size()-1)/2;i++){
      T[i]=S[i];
    }
string A=T;
    b= kaibun(S);
	   c = kaibun(A);
    if(b==0 && c==0){ cout << "Yes" << endl;}
    else{cout << "No" << endl;}

}

Measured memory_bytes: 256
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

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

int n;
// 青木くんが移動する回数
int ret;
int u,v;
vvi edge;
int par[20][100010],depth[100010];
int a,b;

signed main(){
    I(n); I(u); I(v);
    u--; v--;
    edge.resize(n);
    REP(i,n-1){
        I(a); I(b);
        a--; b--;
        edge[a].pb(b);
        edge[b].pb(a);
    }

    deque<int> q;
    q.pb(v);
    par[0][v] = -1;
    while(!q.empty()){
        auto p = q.front();
        q.pop_front();
        for(auto pv: edge[p]){
            if (par[0][p] == pv) continue;
            par[0][pv] = p;
            depth[pv] = depth[p] + 1;
            q.pb(pv);
        }
    }
    REP(k,19) REP(i,n)
        par[k+1][i] = par[k][i] < 0 ? -1 : par[k][par[k][i]];

    vi trace;
    int ui = u;
    while(ui != v){
        trace.pb(ui);
        ui = par[0][ui];
    }
    trace.pb(ui);
    
    v = trace[sz(trace)/2 + sz(trace)%2];
    u = trace[sz(trace)/2-1];
    int pret = 0;
    REP(i,n){
        if (depth[i] < depth[u]) continue;
        int ai = i;
        REP(k,19) 
            if ((depth[ai] - depth[u]) >> k & 1) ai = par[k][ai];
        
        if (ai != u) continue;
        ret = max(ret, depth[i]-1);
    }
    cout << ret << endl;
}

Measured memory_bytes: 22912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll arr[101];
ll n, k;
ll dp[101][100001];
ll pre[101][100001];
int main(){
    cin>>n>>k;
    for(int x=1;x<=n;x++)
        cin>>arr[x];

    dp[0][0] = 1;
    pre[0][0] = 1;
    for(int x = 1;x<=k;x++){
        pre[0][x] = 1;
    }
    for(int x=1;x<=n;x++){
        for(int y=0; y<=k; y++){
            int l = max((ll)0, y-arr[x]);
            int r = y;

            //cout<<l << " "<<r<<endl;

            int sub = 0;
            if(l != 0) sub = pre[x-1][l-1];

            dp[x][y] += pre[x-1][r] - sub;
            dp[x][y] %= mod;

//            int dl, dr;
//            for(int z=0;z<=min(arr[x],(ll) y);z++){
//
//            }
        }
        pre[x][0] = 1;
        for(int y=1;y<=k;y++){
            pre[x][y] += dp[x][y]+pre[x][y-1];
            pre[x][y] %= mod;
        }
    }

//    for(int x=0;x<=n;x++){
//        for(int y=0;y<=k;y++){
//            cout<<dp[x][y]<<"  ";
//        }
//        cout<<endl;
//    }
    cout<<(dp[n][k] % mod + mod ) % mod;
}


Measured memory_bytes: 160588
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Stack<Long> stack = new Stack<Long>();
		Scanner scanner0 = new Scanner(System.in);
		Scanner scanner = new Scanner(scanner0.nextLine());
		scanner0.close();
		
		while (scanner.hasNext()) {
			if (scanner.hasNextLong()) {
				stack.push(scanner.nextLong());
			} else {
				long operand2 = stack.pop();
				long operand1 = stack.pop();
				String operator = scanner.next();
				
				if (operator.equals("+")) {
					stack.push(operand1 + operand2);
				} else if (operator.equals("-")) {
					stack.push(operand1 - operand2);
				} else {
					stack.push(operand1 * operand2);
				}
			}
		}
				
		scanner.close();
		
		System.out.println(stack.pop());
	}
} 



Measured memory_bytes: 26508
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define FOR(i, first, last) for (int i = (first); i < (last); ++i)
#define REP(i, n) FOR(i, 0, n)
#define CLR(a) memset((a), 0, sizeof(a))
#define DUMP(x) std::cerr << #x << " = " << (x) << std::endl;
#define DUMPR(v) REP(_i,v.size()){std::cerr<< #v << "[" << _i << "] = " << (v[_i]) << std::endl;}
#define CIN_VEC(v,N) {v.clear(); v.reserve(N); REP(i,N){typename decltype(v)::value_type x; cin>>x; v.emplace_back(x);}};

inline int to_int(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string to_string(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

typedef unsigned long long ull;
typedef unsigned long ul;

static const int NMAX=100000;
static const int MMAX=100000;
vector<vector<int>> G(NMAX);
int N,M;

int memo[NMAX];

int solve(int u) {
  if(memo[u] != -1)  return memo[u];
  int res = 0;
  for(int v : G[u]) {
    res = max(res, solve(v)+1);
  }
  return memo[u] = res;
}

int main() {
  cin>>N>>M;
  REP(i,M) {
    int x,y;
    cin>>x>>y;
    --x;--y;
    G[x].push_back(y);
  }
  memset(memo,-1,sizeof(memo));

  int ans = 0;
  REP(u,N) ans = max(ans, solve(u));
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8192
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	string a;
	cin>>a;
	int asize=a.size();
	for(int i=0;i<asize;i++){
		if(i%2==0&&a[i]=='L'){
			cout<<"No\n";
			return 0;
		}
		if(i%2==1&&a[i]=='R'){
			cout<<"No\n";
			return 0;
		}
	}
	cout<<"Yes\n";
	return 0;
}

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

int main()
{

#ifdef _d
    freopen("input.txt", "r", stdin);
#endif

    long long n;
    cin >> n;
    vector<long long> f(n+1, 1);
    for (long long i = 1; i <= n/2+1; ++i) {
        long long k = 2*i;
        while (k <= n) {
            ++f[k];
            k += i;
        }
    }
    long long ans = 0;
    for (long long i = 1; i <= n; ++i) {
        ans += i*f[i];
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 81400
import java.util.*;
import java.util.Map.Entry;
 
 
 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
	 static List<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int N = sc.nextInt();
        
        int[] a = new int[N];
        int[] b = new int[N];
        long[] dp = new long [H+100];
        for(int i=0;i<N;i++) {
        	a[i]=sc.nextInt();
        	b[i]=sc.nextInt();
        }
        dp[0]=0;
        long pre=0;
        long min=0;
        //ダメージiの時の最小魔力を計算
        for(int i=1;i<H+100;i++) {
    		min=dp[i]+100000000;
        	for(int j=0;j<N;j++) {
        		if(i-a[j]<0) {
        			pre=0;
        		} else {
        			pre=dp[i-a[j]];
        		}
        		    min=Math.min(min, pre+b[j]);
        	}
        	dp[i]=min;
        }
        
        System.out.println(dp[H]);
        		
    }
}

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

#define _GLIBCXX_DEBUG

using namespace std;
int main() {
	int n = 0,c=0,d=0,f=0;
	bool flag=false;
	
	cin >> n;
	vector<int>a(n);
	vector<int>b(n);

	for (int i = 0; i < n; i++) {
		cin >> a.at(i) >>b.at(i);
	}
	
	for (int i = 0; i < n; i++) {
		if (a.at(i)==b.at(i)) {
			f++;
			if (f == 3)
				flag = true;
		}
		else
			f = 0;
		c = a.at(i);
		d = b.at(i);
	}

	if (flag == true)
		cout << "Yes";
	else
		cout << "No";
}

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

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll ans = 0;
  sort(a.begin(), a.end(), greater<ll>());
  ans += a[0];
  int cn = 0;
  int j = 1;
  rep(i, n-2){
    ans += a[j];
    cn++;
    if(cn == 2){
      cn = 0;
      j++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 4840
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int bef[200],aft[200];

int main(){
  memset(bef,0,sizeof(bef));
  memset(aft,0,sizeof(aft));

  int n,count,i,k,l,a,b;

  cin>>n>>count;

  for(i=1;i<=2*n;i++){
    bef[i-1]=i;
  }
  
  for(i=0;i<count;i++){
    cin>>k;

    if(k==0){
      a=0;b=0;

      for(l=0;l<2*n;l++){
        if(l%2==0){
	  aft[l]=bef[a];
	  a++;
	}
	else{
	  aft[l]=bef[n+b];
	  b++;
	}
      }
    }
    else{
      a=0;
      for(l=0;l<2*n-k;l++){
        aft[l]=bef[k+a];
	a++;
      }
      for(l=2*n-k;l<2*n;l++){
        aft[l]=bef[l-(2*n-k)];
      }
    }

    for(l=0;l<2*n;l++){
      bef[l]=aft[l];
    }
  }

  for(l=0;l<2*n;l++){
    printf("%d\n",bef[l]);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#define ll long long int
#define rep(i,n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair

using namespace std;

int main(){
    
    int h,w,a,b;
    cin >> h>>w>>a>>b;

    for(int i = 0;i < b;i++){
        for(int j = 0;j < w;j++){
            if(j < a){
                cout << 0;
            }
            else{
                cout << 1;
            }
        }
        cout << endl;
    }
    for(int i = b;i < h;i++){
        for(int j = 0;j < w;j++){
            if(j < a){
                cout << 1;
            }
            else{
                cout << 0;
            }
        }
        cout << endl;
    }
    return 0;
}

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

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

  int N; cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  
  sort(d.rbegin(), d.rend());
  int ans = 1;
  for (int i = 1; i < N; i++) {
    if (d[i] < d[i - 1]) ans++;
  }

  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < n; ++i)
#define FORR(i, m, n) for (ll i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
template <typename T, typename E, typename F, typename G>
struct SegmentTree{
    int n;
    F f;
    G g;
    T ti;
    vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f,G g,T ti):f(f),g(g),ti(ti){}
    void init(int n_){    
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,ti);
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void update(int k,const E &x){
        k += n;
        dat[k] = g(dat[k], x);
        while(k>>=1)
            dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
    }
    T operator [](int k) const { return dat[k+n]; }
    // [a,b)
    T query(int a,int b) const {
        T vl=ti,vr=ti;
        for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
            if(l&1) vl=f(vl,dat[l++]);
            if(r&1) vr=f(dat[--r],vr);
        }
        return f(vl,vr);
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    using T = ll;  // type T　
    using E = ll;  // type E
    // 区間**
    auto f = [](T a, T b){ // return type T value
        return max(a,b);
    };
    auto g = [](T a, E b){ // return type T value
        return b;  // return b;
    };
    T ti = 0;  // identify element　入れる値
    SegmentTree<T,E,decltype(f),decltype(g)> seg(f,g,ti);
    int n;cin >> n;
    vector<ll> h(n),a(n);
    REP(i,n){
        cin >> h[i];
        h[i]--;
    }
    REP(i,n) cin >> a[i];
    vector<ll> b(n);
    seg.build(b);
    ll ans=0;
    REPR(i,n){
        ll tmp=seg.query(h[i],n);
        chmax(ans,tmp+a[i]);
        seg.update(h[i],tmp+a[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 11916
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
set<int>st;
int main() {
	int n, m;
	cin >> n;
	rep(i, n) {
		int a;
		cin >> a;
		st.insert(a);
	}
	cin >> m;
	rep(i, m) {
		int a;
		cin >> a;
		st.insert(a);
	}
	for (auto i : st)cout << i << endl;
	return 0;
}


Measured memory_bytes: 21816
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;

const int MOD=1000000007;
int INF=100100100100100;

signed main(){
  int x,y;cin>>x>>y;
  string ans="No";
  if(x*2<=y && y<=4*x && y%2==0)ans="Yes";
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	unordered_map<string ,int> m;
	for(int i=0;i<n;i++)
	{
		string str;
		cin>>str;
		m[str]++;
	}
	cout<<"AC x "<<m["AC"]<<endl;
	cout<<"WA x "<<m["WA"]<<endl;
	cout<<"TLE x "<<m["TLE"]<<endl;
	cout<<"RE x "<<m["RE"]<<endl;
return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
#define pb push_back
#define M6 1000009
#define M5 500009
#define pi 3.14159265
#define epsilon 1e-6
ll power(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=(res*x)%M;
        n/=2;
        x=(x*x)%M;
    }
    return res;
}
// ll sp[M6*10];
// void sieve(){
//     for(int i=2;i<M6*10;i++) sp[i]=i;
//     for(int i=2;i*i<M6*10;i++){
//         if(sp[i]!=i) continue;
//         for(int j=i*2;j<M6*10;j+=i) {
//             if(sp[j]==j) sp[j]=i;
//         }
//     }
// }
ll n,m,A[M5];
ld K[M5],C[M5];
bool same(ld a,ld b){
    return fabs(a-b)<epsilon;
}
int  main()
{   ios_base::sync_with_stdio (0), cin.tie (0);
    //sieve();
    //init();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll tc=1,t=0,i,j,k,l,r,a,b,c;
    //cin>>tc;
    while(t++<tc){
        //cout<<"Case #"<<t<<": ";
        cin>>n;
        for(i=1;i<=n;i++) cin>>A[i];
        A[1]--;
        ll flag=0;
        for(i=2;i<=n;i++){
            if(A[i]-1>=A[i-1]) A[i]--;
            else if(A[i]>=A[i-1]) {}
            else {flag=1; break;}
        }
        if(flag) cout<<"No";
        else cout<<"Yes";
    }
    return 0;
}

Measured memory_bytes: 4352
s = gets.chomp
# puts s[0..((s.size - 1) / 2) - 1]
# puts s[((s.size + 3) / 2) - 1..-1]
if s.reverse == s && s[0..((s.size - 1) / 2) - 1].reverse == s[0..((s.size - 1) / 2) - 1] && s[((s.size + 3) / 2) - 1..-1].reverse == s[((s.size + 3) / 2) - 1..-1]
  puts "Yes"
else
  puts "No"
end


Measured memory_bytes: 1788
s = list(input())
ans = 0
for i in range(2**(len(s)-1)):
    
    a = list(format(i,'b').zfill(len(s)-1)+'0')
    b = []
    for j in range(len(s)):
        b.append(s[j])
        if a[j] == '1':
            b.append('+')
            
    ans += eval(''.join(b))

print(ans)

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
#a = [0 for _ in range(N + 1)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))


Measured memory_bytes: 84248
import fractions

A, B = map(int,input().split())
C = fractions.gcd(A,B)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

prime = prime_factorize(C)

print(len(set(prime))+1)

Measured memory_bytes: 5048
import scala.io.StdIn._
import scala.collection._

object Main {

  class Sieve(val n: Int){
    private[this] val top = (n - 3) / 2 + 1
    private[this] val sqrtLimit = (Math.sqrt(n).toInt - 3) / 2

    private[this] val cmpsts = new Array[Int]((top >>> 5) + 1)
    def isPrime(ci: Int): Boolean = (cmpsts(ci >>> 5) & (1 << (ci & 31))) == 0
    def notPrime(ci: Int): Unit = cmpsts(ci >>> 5) |= 1 << (ci & 31)

    def next(i: Int): Int = if((i > top) || isPrime(i)) 2 * i + 3 else next(i + 1)

    def exec: Iterator[Int] = {
/*
      for{
        i <- 0 to sqrtLimit
        if isPrime(i)
        val p = 2 * i + 3
        j <- Range((p * p - 3)/2, top, p)
      } notPrime(j)
*/
      /*
      (0 to sqrtLimit).map{ i =>
        val p = 2 * i + 3
        if(isPrime(i))Range((p*p-3)/2, top, p).map{notPrime}
      }
      */

      (0 to sqrtLimit).withFilter(ci => (cmpsts(ci >>> 5) & (1 << (ci & 31))) == 0).map { i =>
        val p = 2 * i + 3
        Range((p*p-3)/2, top, p).map(ci => cmpsts(ci >>> 5) |= 1 << (ci & 31))
      }

      if(n==2)Iterator.single(2)
      else Iterator.single(2) ++ Iterator.iterate(3)(p => next((p - 1) / 2)).takeWhile(_ <= n)
    }
  }

  def loop(s: String){
    if(s != null){
       val Array(n,_*) = s.split(" ").map(_.toInt)
       if(n<2) println(0)
       else println(new Sieve(n).exec.size)
       loop(readLine)
    }
  }

  def main(args: Array[String]): Unit = loop(readLine)
}

Measured memory_bytes: 306120
class Facts

  def initialize(mod=10**9+7, n_max=1)
    @mod = mod
    @n_max = n_max
    @fact = [1, 1]
    @inv = [0,1]
    @factinv = [1, 1]
    setup_table(n_max) if 1 < @n_max
  end

  def cmb(n,r)
    return 0 if r < 0 || n < r
    setup_table(n) if @n_max < n
    @fact[n] * (@factinv[r] * @factinv[n-r] % @mod) % @mod
  end

  def factorial(n)
    setup_table(n) if @n_max < n
    @fact[n]
  end

  def prm(n,k)
    setup_table(n) if @n_max < n
    @fact[n] * @factinv[n-k] % @mod
  end
  
  def hom(n,k)
    cmb(n+k-1, k)
  end

  private
    # O(t)
    def setup_table(t)
      (@n_max+1).upto(t) do |i|
        @fact.push( @fact[-1] * i % @mod )
        @inv.push( -@inv[@mod % i] * (@mod / i) % @mod )
        @factinv.push( @factinv[-1] * @inv[-1] % @mod )
      end
      @n_max = t
    end
end

mod = 10 ** 9 + 7

n, k = gets.to_s.split.map{|t|t.to_i}

ans = 0
f = Facts.new

[n-1, k].min.downto(0) do |i|
  ans += f.cmb(n, i) * f.hom(n-i, i)
  ans %= mod if ans >= mod
end

puts ans

Measured memory_bytes: 6632
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define STARTUP {(cin.tie(0));\
 (ios::sync_with_stdio(false));}

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define VECCIN(vec) const int size = (vec).size(); REP(i,size) cin>>(vec)[i];

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

using ll = long long;
using namespace std;
ll mod = 1'000'000'007;

const int INF = 1'050'000'000;

int main() {
    STARTUP;

    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << max(0, min(B, D) - max(A, C)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
int main(){
  int n,s[1001],i,sum=0;
  double ave,a=0;
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    for(i=0; i<n; i++){
      scanf("%d",&s[i]);
      sum+=s[i];
    }
    ave=(double)sum/n;
    for(i=0; i<n; i++){
      a+=((s[i]-ave)*(s[i]-ave));
    }
    printf("%f\n",sqrt((double)a/n));
    sum=0; a=0;
  }
  return 0;
}


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

using std::pair;
using std::make_pair;
typedef pair<int, int> Pair;

#define update_max(a, b) if ((a) < (b)) (a) = (b)
#define update_min(a, b) if ((a) > (b)) (a) = (b)

void run(int case_id = 0) {
  int a, b;
  std::cin >> a >> b;
  int result = 0;
  if (b == 1) {
    result = 0;
  } else {
    int x = 1;
    while (x < b) {
      x = x - 1 + a;
      result ++;
    }
  }
  std::cout << result << "\n";
}

void multi_cases_main() {
  int num_tests;
  std::cin >> num_tests;
  for (int t = 1; t <= num_tests; ++ t) {
    run(t);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  run();
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

void initialize(void);
int isEmpty(void);
int isFull(void);
void enqueue(P);
P dequeue(void);


P Q[LEN+1];
int head, tail, n;

void initialize(){
  head = tail = 0;
}

int isEmpty(){
  return head == tail;
}

int isFull(){
  return head == ( tail + 1 ) % LEN;
}

void enqueue(P x){
  if(isFull()) return;
  Q[tail] = x;
  if(tail+1 == LEN) tail = 0;
  else tail++;
}

P dequeue(){
  P x;
  if(isEmpty()) return;
  x = Q[head];
  if(head+1 == LEN) head = 0;
  else head++;
  return x;
}


int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);
  initialize();
  tail=n;
  for ( i = 0; i < n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  while(!isEmpty()){
    u = dequeue();

    if(u.t-q>0){
      u.t-=q;
      enqueue(u);
      elaps+=q;
    }else if(u.t!=(-1)){
      elaps+=u.t;
      printf("%s %d\n", u.name,elaps);
      u.t=(-1);
    }
  }
  

  
  return 0;
}

Measured memory_bytes: 10752
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find(x)]
n,m = rl()    
uf = UnionFind(n)
for i in range(m):
    a,b = rl()
    uf.unite(a,b)
print(-min(uf.root))

Measured memory_bytes: 32288
n=int(input())
C, S, F=[],[],[]
for _ in range(n-1):
    c, s, f=map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)

for i in range(n-1):
    t=0
    for j in range(i, n-1):
        c, s, f=C[j], S[j], F[j]
        if t<s:
            t=s
        elif t%f==0:
            t=t
        else:
            t=t+f-(t%f)
        t+=c
    print(t)
print(0)
            
    


Measured memory_bytes: 3064
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,K = MI()
p = LI()
p.sort()
print(sum(p[i] for i in range(K)))


Measured memory_bytes: 62604
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
string s, ss;
int n, ans = 0;

int main(void)
{
    cin >> s >> n;
    for(int i=0; i<n; i++) {
        cin >> ss;
        ss += ss;
        if(ss.find(s, 0) != string::npos) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int n, k;
vector<ll> xs, ys, zs;
map<ll, ll> zipx, zipy, zipz;//<???, ??§??????>
map<ll, ll> unzipx, unzipy, unzipz;//<??§??????, ???>
int num[100][100][100];//???????¨?????????\??????

int main(void){
	cin >> n >> k;
	ll x1[51], x2[51], y1[51], y2[51], z1[51], z2[51];//?????????????????§?¨?
	rep(i, n){
		cin >> x1[i] >> y1[i] >> z1[i];
		cin >> x2[i] >> y2[i] >> z2[i];
		xs.push_back(x1[i]); xs.push_back(x2[i]);
		ys.push_back(y1[i]); ys.push_back(y2[i]);
		zs.push_back(z1[i]); zs.push_back(z2[i]);
	}
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(),xs.end()), xs.end());//???????¶????
	sort(ys.begin(), ys.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	sort(zs.begin(), zs.end());
	zs.erase(unique(zs.begin(), zs.end()), zs.end());

	rep(i, xs.size()){
		zipx[i] = xs[i];
		unzipx[xs[i]] = i;
		// printf("unzip[%d] = %d\n", xs[i], i);
		// printf("zip[%d] = %d\n", i, xs[i]);
	}
	rep(i, ys.size()){
		zipy[i] = ys[i];
		unzipy[ys[i]] = i;
		// printf("unzip[%d] = %d\n", ys[i], i);
		// printf("zip[%d] = %d\n", i, ys[i]);
	}
	rep(i, zs.size()){
		zipz[i] = zs[i];
		unzipz[zs[i]] = i;
		// printf("unzip[%d] = %d\n", zs[i], i);
		// printf("zip[%d] = %d\n", i, zs[i]);
	}

	memset(num, 0, sizeof(num));
	for (int i = 0; i < n; ++i){
		// printf("%d %d %d %d %d %d\n", unzipx[x1[i]], unzipy[y1[i]], unzipz[z1[i]], unzipx[x2[i]], unzipy[y2[i]], unzipz[z2[i]]);
		for (int x = unzipx[x1[i]]; x < unzipx[x2[i]]; ++x){
			for (int y = unzipy[y1[i]]; y < unzipy[y2[i]]; ++y){
				for (int z = unzipz[z1[i]]; z < unzipz[z2[i]]; ++z){
					// printf("%d %d %d \n", x, y, z);
					num[x][y][z]++;
				}
			}
		}
	}
	ll ans = 0;
	rep(x, 100)rep(y, 100)rep(z, 100){
		if(num[x][y][z] >= k){
			// printf("%lld\n", zipx[x + 1] - zipx[x]);
			// printf("%lld\n", zipy[x + 1] - zipy[y]);
			// printf("%lld\n", zipz[x + 1] - zipz[z]);
			ans += ((zipx[x + 1] - zipx[x]) * (zipy[y + 1] - zipy[y]) * (zipz[z + 1] - zipz[z]));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5172
import Control.Monad
import Control.Monad.State
import Data.Maybe
import qualified Data.Map as Map

main :: IO ()
main = do
  n <- readLn :: IO Integer
  print $ (`evalState` Map.empty) $ do
    forM_ [1..n] $ \i -> do
      let x = show i
          key = (head x, last x)
      res <- gets (Map.lookup key)
      modify $ case res of
        Just value -> Map.insert key (value + 1)
        Nothing -> Map.insert key 1
    
    sum . catMaybes <$> do
      forM [1..n] $ \i -> do
        let x = show i
            key = (last x, head x)
        gets (Map.lookup key)

Measured memory_bytes: 83324
x, n = map(int,input().split())
lst = set(map(int,input().split()))
df = 0
while True:
    if not (x + df) in lst:
        print(x + df)
        exit()
    df = -df
    if not (x + df) in lst:
        print(x + df)
        exit()
    df = -df
    df -= 1

Measured memory_bytes: 9100
n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])


Measured memory_bytes: 13980
#include<bits/stdc++.h>
#include<climits>
#include<iostream>
typedef long long int ll;
using namespace std;

int main(){
    ll n,d;cin>>n>>d;
    ll count =0;
    for (int i = 0; i < n; i++)
    {
        int x,y;cin>>x>>y;
        double dis = sqrt(pow(x,2)+pow(y,2));
        if(dis<=d)
            count++;
    }
    cout<<count;
}

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

int main(){
    int n,d,a,b,p=0;
    cin >> n >> d;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        if(pow(a,2)+pow(b,2)<=pow(d,2)) p++;
    }
    cout << p << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1e3 + 5;
 
int cnt[MAX];
 
int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    ++cnt[a[i]];
  }
  for (int i = MAX - 2; i >= 0; i--) {
    cnt[i] += cnt[i + 1];
  }
  sort(a.begin(), a.end());
  long long ans = (n * 1LL * (n - 1) * 1LL * (n - 2)) / 6;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (a[i] + a[j] < MAX) {
        ans -= cnt[a[i] + a[j]];
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
	public static String implementation(List<String> array){
		List<Integer> list = Arrays.stream(array.get(0).split(" ")).map(s -> {
			return Integer.parseInt(s);
		}).collect(Collectors.toList());

		return Math.min(list.get(1), list.get(2)) + " " + Math.max(0, (list.get(1) + list.get(2) - list.get(0)));
	}

	public static void main(String[] args){
		// Input
		Scanner sc = new Scanner(System.in);

		// Read input and execute method
		String tmp;
		List<String> array = new ArrayList<String>();
		while(true) {
			try {
				tmp = sc.nextLine();
				if (tmp.length() == 0) {
					exec(array);
					array.clear();
				} else {
					array.add(tmp);
				}
			} catch (Exception e){
				exec(array);
				break;
			}
		}
	}

	public static void exec(List<String> array){
		// Output variable
		String out = implementation(array);

		// Output
		PrintWriter stdOut = new PrintWriter(System.out);
		stdOut.println(out);
		stdOut.flush();

		// Debug
		if(array.get(array.size()-1).startsWith("a:")) {
			if (!array.get(array.size() - 1).substring(2).equals(out)) {
				System.out.println("error included");
				System.out.println("output : " + out);
				System.out.println("expected : " + array.get(array.size()-1).substring(2));
			} else {
				System.out.println("correct answer!!");
			}
			System.out.println("");
		}
	}
}


Measured memory_bytes: 27220
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
    long long n; cin >> n;
    long long p[3][2], tmp[3][2];
    for (int i = 0; i < 3; i++) cin >> tmp[i][0];
    for (int i = 0; i < 3; i++) cin >> tmp[i][1];
    vector<int> pr({0, 1, 2});
    sort(pr.begin(), pr.end(), [&](int i, int j) {
            return tmp[i][1] * tmp[j][0] > tmp[i][0] * tmp[j][1];
        });
    for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) p[i][j] = tmp[pr[i]][j];

    long long ans = 0;
    if (p[2][0] < p[2][1]) {
        for (int x = 0; x*p[0][0] <= n; x++)
            for (int y = 0; x*p[0][0]+y*p[1][0] <= n; y++) {
                int n1 = n - x*p[0][0] - y*p[1][0];
                int z = n1 / p[2][0];
                ans = max(ans, n1%p[2][0] + p[0][1] * x + p[1][1] * y + p[2][1] * z);
            }
    } else if (p[1][0] < p[1][1]) {
        for (int x = 0; x*p[0][0] <= n; x++) {
            int n1 = n - x*p[0][0];
            int y = n1 / p[1][0];
            int n2 = n1 % p[1][0] + x * p[0][1] + y * p[1][1];
            long long z = n2 / p[2][1];
            ans = max(ans, n2%p[2][1] + z*p[2][0]);
        }
    } else if (p[0][0] < p[0][1]) {
        long long z = n / p[0][0];
        n = n % p[0][0] + z * p[0][1];
        for (int x = 0; p[1][1]*x <= n; x++) {
            long long n1 = n - p[1][1]*x;
            long long y = n1 / p[2][1];
            ans = max(ans, n1%p[2][1] + p[1][0]*x + p[2][0]*y);
        }
    } else {
        for (int x = 0; x*p[0][1] <= n; x++)
            for (int y = 0; x*p[0][1]+y*p[1][1] <= n; y++) {
                int n1 = n - x*p[0][1] - y*p[1][1];
                int z = n1 / p[2][1];
                ans = max(ans, n1%p[2][1] + p[0][0] * x + p[1][0] * y + p[2][0] * z);
            }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
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  = Integer.parseInt(sc.next());
		long a[] = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = Long.parseLong(sc.next());
		Arrays.sort(a);
		int rem = 0;
		int tem = 1;
		for (int i = 1; i < n; i++) {
			if (a[i - 1] == a[i]) {
				tem++;
			}
			if (a[i - 1] != a[i] || i == n - 1)  {
				if (tem < a[i - 1]) {
					rem += tem;
				}
				else if (tem > a[i - 1]) {
					rem += tem - a[i - 1];
				}
				tem = 1;
			}
			if (a[i - 1] != a[i] && i == n - 1)  {
				rem += tem;
			}

		}
		if (n == 1 && a[0] != 1)
			rem = 1;
		System.out.println(rem);
	}
}

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

typedef long long ll;

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

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

  int res = 0;
  for (int i = 0; i != s.size(); ++i) {
    if (s.at(i) == '+') ++res;
    else if (s.at(i) == '-') --res;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

class CumulativeSum {
  private:
    std::vector<long long> s;

  public:
    explicit CumulativeSum (int N) {
      s.resize(N+1);
    }

    // s0 = 0, s1 = a0, s2 = a0 + a1, ...
    void build ( const std::vector<long long> &a ) {
      s[0] = 0;
      for(int i=1; i<s.size(); i++) s[i] = s[i-1] + a[i-1];
    }

    // Get [ i, j )
    long long Get ( int i, int j ) {
      return s[j] - s[i];
    }
};


int main (void) {

  int N;  std::cin >> N;

  std::vector<long long> A(N);
  for(int i=0; i<N; i++) std::cin >> A[i];

  CumulativeSum s(N);
  s.build(A);

  ll ans = 1e15;
  int r = 1;
  int l = -1;
  for(int centre = 2; centre <= N-2; centre++) {
    ll Rmin = 1e15;
    int rnext = r;
    for(int rr = r; rr<centre; rr++) {
      ll RR = s.Get(0,rr);
      ll RL = s.Get(rr, centre);
      if ( Rmin >= std::abs(RR-RL) ) {
        Rmin = std::abs(RR-RL);
        rnext = rr;
        r = rnext;
        continue;
      }
      r = rnext;
      break;
    }

    if ( l <= centre ) l = centre+1;
    Rmin = 1e15;
    rnext = l;
    for(int rr = l; rr<N; rr++) {
      ll RR = s.Get(centre,rr);
      ll RL = s.Get(rr, N);
      if ( Rmin >= std::abs(RR-RL) ) {
        Rmin = std::abs(RR-RL);
        rnext = rr;
        l = rnext;
        continue;
      }
      l = rnext;
      break;
    }

    ans = std::min(ans, 
        std::abs( 
          std::max({s.Get(0,r),s.Get(r,centre), s.Get(centre,l), s.Get(l,N)}) - std::min({s.Get(0,r),s.Get(r,centre), s.Get(centre,l), s.Get(l,N)})
          ));
    /*
    for(int i=0; i<r; i++) std::cout << A[i] << " ";
    std::cout << " : ";
    for(int i=r; i<centre; i++) std::cout << A[i] << " ";
    std::cout << " ^ ";
    for(int i=centre; i<l; i++) std::cout << A[i] << " ";
    std::cout << " : ";
    for(int i=l; i<N; i++) std::cout << A[i] << " ";
    std::cout << std::endl;
    std::cout << "( " << s.Get(0,r) << " " << s.Get(r,centre) << " " << s.Get(centre,l) << " " <<  s.Get(l,N) << " ) " << std::endl;
    */
  }
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 3456
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def enum_prime(limit):
    L = list(range(2, limit + 1))
    P = []
    while L[0] ** 2 < limit:
        P.append(L[0])
        L = [i for i in L if i % P[-1]]
    return P + L

p = enum_prime(104730)
for line in stdin:
    n = int(line)
    if not n:
        break
    print(sum(p[:n]))

Measured memory_bytes: 8172
N = int(input())
A = list(map(int, input().split()))

x0 = 0

for i in range(N):
    x0 += A[i] * (-1)**i / 2

x = [x0]

for i in range(N - 1):
    x.append(A[i] - x[i])

ans = []

for i in range(N):
    ans.append(int(x[i] * 2))

print(*ans)

Measured memory_bytes: 70884
#include <stdio.h>

int a[100010];
int b[100010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(a[x]||b[y]){
			puts("-1");
			return 0;
		}
		a[x]=y;
		b[y]=x;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		while(a[i]!=i){
			int t=a[i];
			a[i]=a[t];
			a[t]=t;
			ans++;
		}
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 2568
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

//Nayeem Shahriar Joy ,Applied Physics And Electronic Engineering , University of Rajshahi.


int main(){

    bool prime[1000002];

    memset(prime,true,sizeof(prime));

    prime[0]=false;

    prime[1]=false;

    for(int i=2;i*i<=999999;i++)
    {
        if(prime[i]==true)
        {
            for(int j=i*2;j<=999999;j=j+i)
            {
                prime[j]=false;
            }
        }
    }

 int n;

 while(cin>>n)

 {
     int count=0;

     for(int i=0;i<=n;i++)

     {
         if(prime[i]==true)
         {
             count++;
         }
     }
     cout<<count<<endl;
 }

    return 0;
}

Measured memory_bytes: 4044
#include <bits/stdc++.h>
typedef long long int ll;

using namespace std;

int main()
{
    int K;
    string S;

    cin >> K;
    cin >> S;

   

    int a = S.length();

    if(a>K){

        string A = S.substr(0,K);

        A  = A + "...";
        cout << A << endl;


    }
    else{


        cout << S << endl;


    }


    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
  	cin>>s;
  	int n;
  	vector<string>vec={"SUN","MON","TUE","WED","THU","FRI","SAT"};
  	for(int i=0;i<7;i++){
    if(s==vec.at(i)){
    	n=i;
      	break;
    }
    }
  	cout<<7-n<<endl;
}

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

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

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

const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n, x;
int p[N];
set<int> st;

void no() {
	puts("No");
	exit(0);
}

int mid(int a, int b, int c) {
	vector<int> v = {a, b, c};
	sort(all(v));
	return v[1];
}

int main() {
	megaRandom();
	cin >> n >> x;
	if(n == 3) {
		for(int i = 1; i < 6; i ++)
			p[i] = i;
		do {  
			int a = mid(p[1], p[2], p[3]);
			int b = mid(p[2], p[3], p[4]);
			int c = mid(p[3], p[4], p[5]);
			if(mid(a, b, c) == x) {
				cout << "Yes\n";
				for(int i = 1; i < 6; i ++)
					cout << p[i] << "\n";
				return 0;
			}
		} while(next_permutation(p + 1, p + 5 + 1));
		no();
		return 0;		
	}
	if(x == 2 * n - 1 || x == 1) 
		no();
	for(int i = 1; i < 2 * n; i ++)
		st.insert(i);
	st.erase(x), st.erase(x - 1), st.erase(x + 1);
	p[n] = x;
	p[n - 1] = x - 1;
	p[n + 1] = x + 1;
	for(int i = 1; i < 2 * n; i ++) {
		if(p[i]) continue;
		p[i] = *st.begin();
		st.erase(st.begin());
	}
	cout << "Yes\n";
	for(int i = 1; i < 2 * n; i ++) {
		cout << p[i] << "\n";
	}
	return 0;  
}


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

const int D = 365, N = 26;
int d;
ll c[N+1];
ll s[D+1][N+1];
ll last[N];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> d;
	for(int i = 1; i <= N; i++)
		cin >> c[i];
	for(int i = 1; i <= d; i++) {
		for(int j = 1; j <= N; j++)
			cin >> s[i][j];
	}
	ll ans = 0;
	for(int i = 1; i <= d; i++) {
		ll penalty = 0;
		for(int j = 1; j <= 26; j++)
			penalty += c[j] * (last[j] - i);
		ll best = -1, idx = -1;
		for(int j = 1; j <= 26; j++) {
			ll cur = s[i][j] - penalty + c[j] * (last[j] - i);
			if(best < cur)
				best = cur, idx = j;
		}
		ans += best;
		cout << idx << '\n';
	}

	return 0;
}

Measured memory_bytes: 3724
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int i, j;
	int n, k;
	vector<int>list;


	cin >> n >> k;

	for (i = 0; i < n; i++) {
		int num;
		cin >> num;
		list.push_back(num);
	}

	sort(list.begin(), list.end(), greater<int>());

	int minn = 999999999;


	for (i = 0; i < n - (k-1); i++) {
		minn = min(minn, list[i] - list[i + (k - 1)]);
	}


	cout << minn << endl;









	getchar();
	getchar();
	return 0;
}

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

inline char get(void) {
	static char buf[100000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 100000, stdin);
		if(S == T) return EOF;
	}
	return *S++;
}
template<typename T>
inline void read(T &x) {
	static char c; x = 0; int sgn = 0;
	for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
	if (sgn) x = -x;
}

const int N = 101010;

int a[N << 2];
int n;
long long sum;

int main(void) {
	read(n);
	for (int i = 0; i < n * 3; i++) {
		read(a[i]); a[i] = -a[i];
	}
	sort(a, a + n * 3);
	for (int i = 0; i < n; i++) sum -= a[i << 1 | 1];
	cout << sum << endl;
}

Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>

using namespace std;

int v[100001],w1[100001],w2[100001];

int main(){
  int i,n,maxi1=0,maxi2=0;
  cin >> n;
  for (i=0;i<100001;++i) {
    w1[i]=0;
    w2[i]=0;
  }
  for (i=0;i<n;++i) {
    cin >> v[i];
    if (i%2==0) {
      w1[v[i]]++;
      if (w1[v[i]] > w1[maxi1]) {
        maxi1=v[i];
      }
    } else {
      w2[v[i]]++;
      if (w2[v[i]] > w2[maxi2]) {
        maxi2=v[i];
      }
    }
  }
  sort(w1, w1+100001);
  sort(w2, w2+100001);
  if (maxi1!=maxi2) {
    cout << n-w1[100000]-w2[100000] << endl;
  } else {
    if (n-w1[100000]-w2[99999] < n-w1[99999]-w2[100000]) {
      cout << n-w1[100000]-w2[99999] << endl;
    } else {
      cout << n-w1[99999]-w2[100000] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1408