akhauriyash/Code-Regression huggingface dataset:
#include<iostream>   
#include<string>
#include<vector>
using namespace std; 
 
int main()
{
	int c, a, b;
	cin >> a >> b >> c; 
	if ((b - a) == (c - b))
	{
		cout << "YES" << "\n";
	}
	else
	{
		cout << "NO" << "\n";
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

int main() {
    cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);

    char c;
    cin >> c;
    if('a' <= c && c <= 'z') cout << 'a' << endl;
    else cout << 'A' << endl;
}


Measured memory_bytes: 3600
h, w = map(int, input().split())
n2a = ["A", "B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

for i in range(h):
    row = input().split()
    for j in range(w):
        if(row[j]=="snuke"):
            print(n2a[j] + str(i+1))

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

typedef long long int ll;

ll N,M;
ll a[1000000];
bool eds[1000000], ena[1000000];
const ll val = 1000000007;
int main(void){
  cin>>N>>M;
  for(ll i=0;i<M;i++) cin>>a[i];
  sort(a,a+M);

  for(ll i=0;i<=N;i++){
    eds[i]=true;
    ena[i]=true;
  }

  for(ll i=0;i<M;i++){
    ena[a[i]]=false;
    ena[a[i]-1]=false;
    if(a[i]>1) eds[a[i]-2]=false;
    if(i>0){
      if(a[i]-a[i-1]==1){
        cout<<0<<endl;
        return 0;
      }
    }
  }

  ll an, bn;
  if(ena[0]) an=1, bn=1;
  else       an=1, bn=0;
  for(ll i=1;i<N;i++){
    if(ena[i]){
      ll _an=an+bn;
      if(eds[i]) bn=an;
      else       bn=0;
      an=_an%val;
    }
  }

  cout<<an<<endl;
  return 0;
}


Measured memory_bytes: 2560
//Mahir Ratanpara (DA-IICT)
#include<bits/stdc++.h>
using namespace std;
#define Ff(i,a,n) for(i=a;i<n;i++)
#define Fr(i,a,n) for(i=a;i>n;i--)
#define ll long long
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef pair<ll, ll>	pa;
typedef vector<ll>		vc;
typedef vector<pa>		vp;
typedef vector<vc>		vvc;
int mpow(int base, int exp); 
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vc g[N];

int main() {
    FAST;
    ll x;
    cin>>x;
    for(int i = -120; i < 121; i++) {
        for(int j = -120; j < 121; j++) {
            if(i*i*i*i*i-j*j*j*j*j == x) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 10676
//Andrew Yang
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>	
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <climits>
using namespace std;
#define FOR(index, start, end) for(int index = start; index < end; ++index)
#define RFOR(index, start, end) for(int index = start; index > end; --index)
#define FOREACH(itr, b) for(auto itr = b.begin(); itr != b.end(); ++itr)
#define RFOREACH(itr, b) for(auto itr = b.rbegin(); itr != b.rend(); ++itr)
#define INF 1000000000
#define M 1000000007
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	int ans = 0;
	while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
		if (a == b && b == c) {
			cout << -1 << endl;
			return 0;
		}
		int a1 = (b + c) / 2;
		int b1 = (a + c) / 2;
		int c1 = (a + b) / 2;
		a = a1;
		b = b1;
		c = c1;
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 764
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51,51]
k=int(input())
k-=1
print(l[k])

Measured memory_bytes: 3060
from copy import deepcopy


class EightQueen:
    NQUEENS = 8
    SIZE = 8

    class Board:
        def __init__(self, size):
            self.queens = []
            self.size = size

        def place(self, i, j):
            self.queens.append((i, j))

        def count(self):
            return len(self.queens)

        def ok(self, i, j):
            for qi, qj in self.queens:
                if qi == i:
                    return False
                if qj == j:
                    return False
                if i - j == qi - qj:
                    return False
                if i + j == qi + qj:
                    return False
            return True

        def __str__(self):
            result = []
            for i in range(self.size):
                s = ''
                for j in range(self.size):
                    if (i, j) in self.queens:
                        s += "Q"
                    else:
                        s += "."
                result.append(s)
            return '\n'.join(result)

    def __init__(self):
        self.board = self.Board(self.SIZE)

    def add_queen(self, i, j):
        self.board.place(i, j)

    def solve(self):
        def _solve(board, si, sj):
            if board.count() == self.NQUEENS:
                return board

            for i, j in _from_pos(si, sj):
                if board.ok(i, j):
                    b = deepcopy(board)
                    b.place(i, j)
                    result = _solve(b, i, j)
                    if result is not None:
                        return result
            else:
                return None

        def _from_pos(i, j):
            for n in range(i*self.SIZE + j, self.SIZE*self.SIZE):
                yield (n // self.SIZE, n % self.SIZE)

        self.board = _solve(self.board, 0, 0)

    def __str__(self):
        if self.board is None:
            return 'no solution'
        else:
            return str(self.board)


def run():
    n = int(input())
    q = EightQueen()

    for _ in range(n):
        i, j = [int(i) for i in input().split()]
        q.add_queen(i, j)

    q.solve()
    print(q)


if __name__ == '__main__':
    run()



Measured memory_bytes: 6352
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
	int id,d;
}w[100005];
bool cmp(node a,node b){
	return a.d<b.d;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>w[i].d;
		w[i].id=i+1;
	}
	sort(w,w+n,cmp);
	for(int i=0;i<n;i++){
		cout<<w[i].id<<(i==n-1?'\n':' ');
	}
	return 0;
}

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

#define ll long long
#define pu push
#define pb push_back
#define ull unsigned long long
#define set_pre setprecision
#define cl clear
#define fi first
#define se second
#define For(i,a,b) for(int i = a; i <= b; i++)
#define Fors(i,a,b) for(int i = a; i < b; i++)

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

const int maxn = 1e6 + 7;
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;
const int max_dsk = 3e5 + 7;
const int maxc_IT = 4 * maxn;

vector<ii>pre;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    For(i,1,n)
    {
        int x;
        cin >> x;
        pre.pb(ii(x,i));
    }
    sort(pre.begin(),pre.end());
    for(ii w : pre) cout << w.se << endl;
}


Measured memory_bytes: 1780
import fractions
from functools import reduce

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

def list_lcm(*numbers):
    return reduce(lcm,numbers)

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

l=list_lcm(*a)
ans,mod=0,1000000007
for i in a:
    ans+=l//i

print(ans%mod)

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

int main(){
  string s,yaki="YAKI";
  int check = 1;
  cin >> s;
  for(int i = 0;i < 4;i++){
    if(s[i] != yaki[i]){
      check = 0;
    }
  }
  
  if(check == 1){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
}

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

num_of_sorting = 0
for i in range(0, N-1):
  minj = i
  for j in range(i+1, N):
    if A[j] < A[minj]:
      minj = j
  if i is not minj:
    temp = A[i]
    A[i] = A[minj]
    A[minj] = temp
    num_of_sorting += 1
  
print(' '.join(map(str, A)))
print(f"{num_of_sorting}")


Measured memory_bytes: 5604
using System;

namespace AtC155
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] Astr = Console.ReadLine().Split(' ');

            bool Denied = false;
            for(int i = 0; i < N; i++)
            {
                int A = int.Parse(Astr[i]);
                if(A%2 == 0)
                {
                    if (A % 3 > 0 && A % 5 > 0) Denied = true;
                }
            }

            if (Denied) Console.WriteLine("DENIED");
            else Console.WriteLine("APPROVED");
        }
    }
}


Measured memory_bytes: 11092
/*
Author- Aasav Badera
Time- Sun Apr 26 17:28:29 2020
*/
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
#define ll                 long long    
#define vi                 vector<ll >
// -------------------Standard Traversal Moves---------------------
// vi fx = {1 ,-1 ,0, 0}, fy = {0, 0, -1, 1};
// vi fx = {2, -2, 2, -2,  1, -1, 1, -1}, fy = {1, 1, -1, -1, 2, 2, -2, -2};
// vi fx = {1, 1, 1, -1, -1 , -1, 0, 0}, fy = {1, -1, 0, 1, -1, 0, 1, -1};
// ----------------------------------------------------------------

#define int                long long                        
#define pb                 push_back                                                     
#define mii                map<ll ,ll >
#define rep(i, a, b)       for(ll  i=a;i<b;i++)
#ifdef LOCAL
#define dbg(args...)       { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#else
#define dbg(args...)
#endif
#define pii                pair<ll ,ll >
#define ppb                pop_back
#define vii                vector<pair<ll , ll >>
#define si                 set <ll>
#define hell               1000000007
// #define hell               (ll)998244353
#define all(a)             (a).begin(),(a).end()
#define sz(x)              (ll )x.size()
#define mp                 make_pair
#define yes                cout << "YES" << endl
#define no                 cout << "NO" << endl
#define inf                9223372036854775807
#define endl               '\n' 
#define N                  200005
ll n, m, k, a[N];


int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef LOCAL
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    ll tests = 1;
    // cin >> tests;
    rep(test, 1, tests+1)
    {
        cin >> n;
        cin >> m;
        if(m >= n)cout << "unsafe";
        else cout << "safe";
    }
    return 0;
}

Measured memory_bytes: 3656
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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

void trace(int A[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

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

const unsigned long long INF = 1LL << 60;

////////////////////////////////////////////////////////////

int n, b, f, r, v;
int a[4][3][10];

int main() {
    rep(i, 4) rep(j, 3) rep(k, 10) a[i][j][k] = 0;;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> b >> f >> r >> v;
        a[b - 1][f - 1][r - 1] += v;
    }

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 10; ++k) {
                printf(" %d", a[i][j][k]);
            }
            cout << endl;
        }
        if (i < 3) {
            cout << "####################" << endl;
        }
    }
}



Measured memory_bytes: 3224
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main()
{
	string s;
	getline(cin, s);

	for (int i = 0; i < s.size(); ++i)
	{
		if (isupper(s[i]))
			s[i] = tolower(s[i]);

		else if (islower(s[i]))
			s[i] = toupper(s[i]);

		cout << s[i];
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 1176
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n, b, c, k;
vector<int> h;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>k;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        h.push_back(temp);
    }
    int dp[n+1];
    for(int i=1;i<n;i++){
        dp[i]=INF;
    }
    dp[0]=0;
    for(int i=1;i<n;i++){
        for(int j=i-1;j>=max(i-k,0);j--){
        dp[i]=min(dp[j]+abs(h[j]-h[i]),dp[i]);
        }
    }
    cout<<dp[n-1]<<"\n";
}


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


int main(){
    int a;
    string s;
    string red = "red";
    cin >> a;
    cin >> s;

    if( a >= 3200){
        cout << s << endl;
    }else{
        cout << red << endl;
    }

} 

Measured memory_bytes: 256
class segtree:
    ## define what you want to do ,(min, max)
    sta = -1
    func = max

    def __init__(self,n):
        self.n = n
        self.tree = [self.sta]*(2*n)

    def build(self, list):
        for i,x in enumerate(list,self.n):
            self.tree[i] = x

        for i in range(self.n-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.n
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.n
        r += self.n
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

    def max_right(self, l, x):
        """[l,r) が ok であるような最大の r を返す"""
        N = self.n
    
        def is_ok(v):
            return v < x
    
        def get_max(a,b):
            if a is None:
                return b
            if b is None:
                return a
            return max(a,b)
        v = None
        i, node_l, node_w = l + N, l, 1
        while True:
            if not (i & 1):
                i >>= 1
                node_w <<= 1
                continue
            if node_l + node_w > N:
                break
            v1 = get_max(v, self.tree[i])
            if is_ok(v1):
                v, i = v1, (i + 1) >> 1
                node_l, node_w = node_l + node_w, node_w << 1
            else:
                break
        # 奇数セルに居て、とりきれないことが分かっている。偶数をとっていく
        i, node_w = i << 1, node_w >> 1
        while node_w:
            if node_l + node_w > N:
                i, node_w = i << 1, node_w >> 1
                continue
            v1 = get_max(v, self.tree[i])
            if is_ok(v1):
                v, i = v1, (i + 1) << 1
                node_l, node_w = node_l + node_w, node_w >> 1
            else:
                i, node_w = i << 1, node_w >> 1
        i >>= 1
        return i - N


n,q = map(int,input().split())
a = list(map(int,input().split()))

seg = segtree(n)
seg.build(a)
for _ in range(q):
    t,x,v = map(int,input().split())
    if t == 1:
        seg.set(x-1,v)
    elif t == 2:
        print(seg.get(x-1,v))
    else:
        print(seg.max_right(x-1,v)+1)

Measured memory_bytes: 31552
// abc165_a
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
  int k,a,b;
  cin>>k>>a>>b;
  for (int i=a; i<=b; ++i){
    if (i%k==0) {
      cout<<"OK"<<endl;
      return 0;
    }
  }
  cout<<"NG"<<endl;
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

vector<pair<long long, long long>> prime_foctorize(long long N) {
  vector<pair<long long, long long>> res;
  for (long long i = 2; i * i <= N; i++) {
    if (N % i != 0) continue;
    long long ex = 0;
    while (N % i == 0) {
      ex++;
      N /= i;
    }
    res.push_back({i, ex});
  }
  if (N != 1) res.push_back({N, 1});
  return res;
}

int main() {
  long long N, P;
  cin >> N >> P;

  const auto &pf = prime_foctorize(P);
  long long ans = 1;
  for (auto p : pf) {
    for (int i = 0; i < p.second / N; ++i) ans *= p.first;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
min_ = inf
for _ in range(n):
    min_ = min(min_, sum(rm()))
print(min_)

Measured memory_bytes: 27036
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 998244353, N = 3e3 + 211;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int n, ans = inf;

main () {
	cin >> n;
	for (int i = 0; i < N; ++i)
		if (i*1000 >= n)
			ans = min(ans, i*1000 - n);
	cout << ans << endl;
}
        	
//check for the constants

                                                                                   	



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

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  ll ans = 0;
  for (int i = 1; i <= N; i++)
  {
    if (!(i % 3 == 0 or i % 5 == 0))
      ans += i;
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
    int N;
    cin >> N;
    vector<vector<pair<int, int>>> shougen(N + 1, vector<pair<int, int>>(0));
    for(int i = 1 ; i <= N; i++){
        int a;
        cin >> a;
        for(int j = 1 ; j <= a; j++){
            int x, y;
            cin >> x >> y;
            shougen.at(i).emplace_back(x, y);
        }
    }
    int answer = 0;
    for(ll i = 0; i < (1 << N); i++){
        bool correct = true;
        for(ll j = 1; j <= N; j++){
            bool isShoujiki = ((i & (1 << j - 1)) != 0);
            if(!isShoujiki){
                continue;
            }
            for(auto p:shougen.at(j)){
                ll testBit = 1 << (p.first - 1);
                bool shoujikiSengen = (p.second == 1);
                if(shoujikiSengen){
                    if((testBit & i) == 0){
                        correct = false;
                        break;
                    }
                } else{
                    if((testBit & i) != 0){
                        correct = false;
                        break;
                    }
                }
            }
            if(!correct){
                break;
            }
        }
        if(!correct){
            continue;
        }
        int currentAnswer = 0;
        ll tempI = i;
        while(tempI > 0){
            if(tempI % 2 == 1){
                currentAnswer++;
            }
            tempI /= 2;
        }
        answer = max(answer, currentAnswer);
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct modint{
    using i64=int_fast64_t;
    i64 a;
    static constexpr i64 MOD=1000000007;
    modint(i64 a_=0){
        a=a_%MOD;
        if(a<0) a+=MOD;
    }
    modint inv()const{
        i64 n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y(n);
        return y;
    }
    bool operator==(const modint& x){
        return a==x.a;
    }
    bool operator!=(const modint& x){
        return a!=x.a;
    }
    modint& operator=(const modint& x){
        a=x.a;
        return *this;
    }
    modint operator+(const modint& x){
        modint y;
        y.a=a+x.a;
        if(y.a>MOD) y.a-=MOD;
        return y;
    }
    modint operator-(const modint& x){
        modint y;
        y.a=a-x.a;
        if(y.a<0) y.a+=MOD;
        return y;
    }
    modint operator*(const modint& x){
        modint y;
        y.a=(a*x.a)%MOD;
        return y;
    }
    modint operator/(const modint& x){
        modint y;
        y.a=(a*x.inv().a)%MOD;
        return y;
    }
    modint& operator+=(const modint& x){
        a+=x.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    modint& operator-=(const modint& x){
        a-=x.a;
        if(a<0) a+=MOD;
        return *this;
    }
    modint& operator*=(const modint& x){
        (a*=x.a)%=MOD;
        return *this;
    }
    modint& operator/=(const modint& x){
        (a*=x.inv().a)%=MOD;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x){
    int_fast64_t a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x){
    out<<x.a;
    return out;
}
modint pwr(int_fast64_t a,int_fast64_t b){
    modint _;
    int_fast64_t n=1,A=a,MOD=_.MOD;
    while(b){
        if(b&1) (n*=A)%=MOD;
        (A*=A)%=MOD;
        b>>=1;
    }
    _.a=n;
    return _;
}

class FSmallProducts {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n,k,m;
        in>>n>>k;
        m=(int)sqrt(n);
        vector<modint> c(2*m),s(2*m+1),ns(2*m+1);
        fr(i,m) c[i]=1,c[i+m]=n/(m-i)-n/(m-i+1);
        if(n/m==m) c[m]-=1;
        s[0]=1;
        fr(_,k){
            ifr(i,2*m) ns[i]=ns[i+1]+(s[0]-s[2*m-i])*c[i];
            s.swap(ns);
        }
        out<<s[0]<<endl;
    }
};

int main() {
    FSmallProducts solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 1792
from math import gcd


def prime_fac(x):
    pfs = set()
    for i in range(2, x):
        if i * i > x:
            break
        while x % i == 0:
            pfs.add(i)
            x //= i
    if x > 1:
        pfs.add(x)
    return pfs


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

g = a[0]
for v in a[1:]:
    g = gcd(g, v)

if g != 1:
    print("not coprime")
    exit()

s = set()
for v in a:
    p = prime_fac(v)
    ls, lp = len(s), len(p)
    s.update(p)
    if len(s) < ls + lp:
        print("setwise coprime")
        exit()
print("pairwise coprime")


Measured memory_bytes: 189252
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <functional>
#include <cstring>
#include <cmath>
#include <random>
using namespace std;

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

    string s, r;
    cin >> s;
    r = s;

    for (int k = 0; k < 4; k++) {
        int p[2] = { k % 2, k / 2 };
        for (int i = 0; i < n; i++) {
            r[i] = p[1] == 0 ? 'S' : 'W';
            int t = (s[i] == 'o' ^ p[1] == 1) ? p[0] : (p[0] ^ 1);
            p[0] = p[1];
            p[1] = t;
        }
        if (p[0] == k % 2 && p[1] == k / 2) {
            cout << r << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 512
import re
A = input()
B = []
c,A = A.split(" ",1)
while(1):
    if c == "+":
        temp1 = int(B.pop())
        temp2 = int(B.pop())
        B.append(temp1+temp2)
    elif c == "-":
        temp1 = int(B.pop())
        temp2 = int(B.pop())
        B.append(temp2-temp1)
    elif c == "*":
        temp1 = int(B.pop())
        temp2 = int(B.pop())
        B.append(temp1*temp2)
    else:
        B.append(c)
    if len(A) ==1 :
        c = A
        A = ""
    elif len(A) == 0:
        break
    else:
        c,A = A.split(" ",1)
print(*B)          



Measured memory_bytes: 6492
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
    int N; cin >> N;
    vector<int> t(N+1);
    int total = 0;
    for(int i=1; i<=N; i++){
        cin >> t[i]; total += t[i];
    }

    int M; cin >> M;
    vector<int> ans;
    for(int i=0; i<M; i++){
        int p, x; cin >> p >> x;
        ans.push_back(total - t[p] + x);
    }
    for(int i=0; i<ans.size(); i++) cout << ans[i] << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    
    public static void main(String[] args) {

        Scanner sc = null;
        sc = new Scanner(System.in);
        long s = sc.nextLong();
        sc.close();

        long mod = (long) Math.pow(10, 9) + 7;
        long all = powmod(10, s, mod);
        long notexist0 = powmod(9, s, mod);
        long notexist9 = powmod(9, s, mod);
        long notexistBoth = powmod(8, s, mod);
        long notexistOne = (notexist0 + notexist9 - notexistBoth);
        long total = (all - notexistOne) % mod;

        System.out.println((total + mod)%mod);

    }

    public static long powmod(long x, long y, long mod) {
        long total = 1;
        for (int i = 0; i < y; i++) {
            total = (total*x) % mod;
        }
        return total;
        
    }
}

Measured memory_bytes: 35744
import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = set()

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

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a |= set(tmp)
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')

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

int main()
{
    string S, T;
    cin >> S >> T;

    int A,B;
    cin >> A >> B;

    string U;
    cin >> U;

    if(U == S) A-- ;
    else if(U == T) B-- ;

    cout << A << " " << B << endl;


    
}

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

int main(){
  int a,b;
  cin >> a >> b;
  int count=0;
  bool test=false;
  
  for(int i=a;i<=b;i++){
    string x,y;
    
    if(i%10!=0){
      x = to_string(i);
      y = x;
      reverse(y.begin(),y.end());
      if(x.compare(y) == 0) test=true;
      else test=false;
    }
    else{
      test=false;
      continue;
    }
    
    if(test){
      count++;
    }
  }

  cout << count << endl;
  
  return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i

ans = []

n.times do |i|
  ans_count = gets.chomp.to_i
  ans[i] = []
  ans_count.times do |j|
    x, y = gets.chomp.split.map(&:to_i)
    ans[i][j] = [x - 1, y == 1]
  end
end

[true, false].repeated_permutation(n) do |comb|
  catch :next_comb do
    n.times do |i|
      next unless comb[i]
      #i番目の人が正直なとき矛盾するかどうか
      ans[i].each do |an|
        #an[0]番目の人がan[1]だと言っている
        throw :next_comb if comb[an[0]] != an[1] #矛盾していたら終了
      end
    end
    puts comb.count(true)
    exit
  end
end


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
struct Mat{int c[3][3];}A[32], B, I, U, F; int X[100005], n, m;
inline Mat& operator *= (Mat &A, Mat B)
{
	ll c[3][3] = {{(ll)A.c[0][0]*B.c[0][0]+(ll)A.c[0][1]*B.c[1][0]+(ll)A.c[0][2]*B.c[2][0],
				   (ll)A.c[0][0]*B.c[0][1]+(ll)A.c[0][1]*B.c[1][1]+(ll)A.c[0][2]*B.c[2][1],
				   (ll)A.c[0][0]*B.c[0][2]+(ll)A.c[0][1]*B.c[1][2]+(ll)A.c[0][2]*B.c[2][2]},
				  {(ll)A.c[1][0]*B.c[0][0]+(ll)A.c[1][1]*B.c[1][0]+(ll)A.c[1][2]*B.c[2][0],
				   (ll)A.c[1][0]*B.c[0][1]+(ll)A.c[1][1]*B.c[1][1]+(ll)A.c[1][2]*B.c[2][1],
				   (ll)A.c[1][0]*B.c[0][2]+(ll)A.c[1][1]*B.c[1][2]+(ll)A.c[1][2]*B.c[2][2]},
				  {(ll)A.c[2][0]*B.c[0][0]+(ll)A.c[2][1]*B.c[1][0]+(ll)A.c[2][2]*B.c[2][0],
				   (ll)A.c[2][0]*B.c[0][1]+(ll)A.c[2][1]*B.c[1][1]+(ll)A.c[2][2]*B.c[2][1],
				   (ll)A.c[2][0]*B.c[0][2]+(ll)A.c[2][1]*B.c[1][2]+(ll)A.c[2][2]*B.c[2][2]}};
	A.c[0][0] = c[0][0]%MOD; A.c[0][1] = c[0][1]%MOD; A.c[0][2] = c[0][2]%MOD;
	A.c[1][0] = c[1][0]%MOD; A.c[1][1] = c[1][1]%MOD; A.c[1][2] = c[1][2]%MOD;
	A.c[2][0] = c[2][0]%MOD; A.c[2][1] = c[2][1]%MOD; A.c[2][2] = c[2][2]%MOD; return A;
}	inline Mat fxp(int n){Mat A(I);for(rint i=0;n;n&1?A*=::A[i],0:0,i++,n>>=1);return A;}
int main()
{
	A->c[0][0] = 1; A->c[0][2] = 1; A->c[1][0] = 2; A->c[1][1] = 1; A->c[1][2] = 2; A->c[2][0] = 1; A->c[2][1] = 1; A->c[2][2] = 2;
	B.c[0][0] = 1; B.c[1][0] = 2; B.c[1][1] = 1; B.c[2][0] = 1; B.c[2][1] = 1; B.c[2][2] = 1; I.c[0][0] = I.c[1][1] = I.c[2][2] = 1;
	for(rint i = 1; i < 32; A[i] = A[i-1], A[i] *= A[i-1], i++); n = rf(); m = rf(); generate(X+1,X+m+1,rf); X[++m] = n; U = I;
	for(rint i = m; i; i<m?U*=B,0:0, U *= fxp(X[i]-X[i-1]-1), i--); F.c[0][0] = 1; F.c[1][0] = 2; F.c[2][0] = 1; U *= F; return !printf("%d\n",U.c[2][0]);
}

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

int main(){
  int K;
  cin >> K;
  vector<string> v(K);
  long long ans = 0;
  
  for(int i = 0; i < K; i++){
    cin >> v[i];
    sort(v[i].begin(),v[i].end());
  }
  sort(v.begin(), v.end());
  
  long long num = 0;
  for(int i = 1; i< K; i++){
    if(v[i] != v[i - 1]){
      ans += ((num + 1) * num )/2;
      num = 0;
    }else if(i != K - 1){
      num++;
    }else{//i == K-1 && v[i] == v[i-1]
      num++;
      ans += ((num + 1) * num )/2;
    }
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 9344
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  2 11:49:26 2018
ABC056C
@author: maezawa
"""

x = int(input())

fib = [0]
i = 1
j = 0
while True:
    j = fib[i-1] + i
    fib.append(j)
    if j >= x:
        break
    i += 1
if x == 0:
    print(0)
else:
    print(i)

Measured memory_bytes: 4932
def sumCifre(n):
	sum = 0
	while n > 0:
		sum = sum + n % 10
		n //= 10
	return sum
	
def main():
	linie = input()
	vector = [int(x) for x in linie.split()]	
	n = vector[0]
	a = vector[1]
	b = vector[2]
	sum2 = 0
	for i in range(0, n + 1):
		if sumCifre(i) >= a and sumCifre(i) <= b:
			sum2 += i
	print(sum2)
 
if __name__ == "__main__":
	main()

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

int main(){
  ll n,k;
  cin >> n >> k;
  vector<pair<ll,ll>> ab(n);

  rep(i,n){
    ll anum,bnum;
    scanf("%lld %lld",&anum,&bnum);
    ab.at(i).first = anum;
    ab.at(i).second = bnum;
  }
  sort(ab.begin(),ab.end());
  
  ll cnt = 0;
  rep(i,n){
    cnt += ab.at(i).second;
    if( cnt >= k ){
      cout << ab.at(i).first << endl;
      return 0;
    }
  }
  return 0;
  
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define x first
#define y second
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
ll in()
{
  ll x = 0 , f = 1 ;
  char ch = getchar() ;
  while(!isdigit(ch)) {if(ch == '-') f = -1 ; ch = getchar() ;}
  while(isdigit(ch)) x = x * 10 + ch - 48 , ch = getchar() ;
  return x * f ;
}
string s[7] ;
int main()
{
  int n = in() , m = in() , k = in() ;
  for(int i = 0 ;i < n ;i ++ ) cin >> s[i] ;
  int res = 0 ;
  for(int i = 0 ;i < 1 << n ;i ++ )
   {
     for(int j = 0 ;j < 1 << m ;j ++ )
      {
        int ans = 0 ;
        for(int h = 0 ;h < n ;h ++ )
         {
           for(int w = 0 ;w < m ;w ++ )
            {
              if(s[h][w] == '.') continue ;
              if((i >> h) & 1) continue ;
              if((j >> w) & 1) continue ;
              ans ++ ;
            }
         }
         if(ans == k) res ++ ;
      }
   }
  cout << res << endl ;
  return 0 ;
}
/*
*/


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; ++i)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define PB push_back
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> Point;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1ll << 60;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

#ifdef WIN32
#include "gtest/gtest.h"
#pragma comment (lib, "gtest.lib")
#define dump(x) cerr << #x << " = " << (x) << "\n"
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n"
#else
#define dump(x)
#define debug(x)
#endif

int n;
#define severalTestCases
static VI primes( 1, 2 );
static bool is_prime[10001];

bool input() {
  cin >> n;
  return n;
}

static short dp[ 1229 ][ 10001 ][ 2 ];

int dfs( int now, int sum, bool check ) {
  if ( !sum ) {
    return 1;
  }
  if ( now == primes.size() || sum < primes[ now ] ) {
    return 0;
  }
  if ( !dp[ now ][ sum ][ check ] ) {
    return dp[ now ][ sum ][ check ];
  }
  int res = 0;
  if ( !check ) {
    res += dfs( now + 1, sum, false );
  }
  res += dfs( now + 1, sum - primes[ now ], true );
  return dp[ now ][ sum ][ check ] = res;
}

int solve(int _n) {
  static bool check = true;
  if ( check ) {
    NCLR( is_prime );
    for ( int i = 3; i * i <= 10000; i += 2 ) {
      if ( is_prime[ i ] ) {
        for ( int j = i * i; j <= 10000; j += i * 2 ) {
          is_prime[ j ] = false;
        }
      }
    }
    for ( int i = 3; i <= 10000; i += 2 ) {
      if ( is_prime[ i ] ) {
        primes.push_back( i );
      }
    }
    NCLR( dp );
    check = false;
  }
  return dfs( 0, n, false );
}

void putsanswer() {
  cout << solve( n ) << "\n";
}

int main( int argc, char **argv ) {
//#ifndef WIN32
#ifdef severalTestCases
  while ( input() ) {
#else
  input();
  putsanswer();
#endif
  /*#else
  ::testing::InitGoogleTest( &argc, argv );
  return RUN_ALL_TESTS();    // gtest 
  #endif*/
#ifdef severalTestCases
  putsanswer();
  }
#endif
  return 0;
}

/*#ifdef WIN32
TEST( testcase, solve ) {
}
#endif*/

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

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		String[] C = new String[N];
		for (int i = 0; i < N; i++) {
			C[i] = scan.next();
		}
		// bubble sort
		String[] bubbleC = bubbleSort(Arrays.copyOf(C, N), N);
		String outputB = Arrays.toString(bubbleC).replaceAll(",", "");
		System.out.println(outputB.substring(1, outputB.length() - 1));
		System.out.println("Stable"); // ????????????????????????
		
		// selection sort
		String[] selectionC = selectionSort(Arrays.copyOf(C, N), N);
		String outputC = Arrays.toString(selectionC).replaceAll(",", "");
		System.out.println(outputC.substring(1, outputC.length() - 1));
		String message = "Not stable";
		if (isStable(bubbleC, selectionC)) {
			message = "Stable";
		}
		System.out.println(message); // bubble sort???????????¨??????
		scan.close();
	}

	public static String[] bubbleSort(String[] C, int N) {
		for (int i = 0; i < N; i++) {
			for (int j = N - 1; j > i; j--) {
				
				if ( Character.getNumericValue(C[j].charAt(1)) < Character.getNumericValue(C[j - 1].charAt(1))) {
					String temp = C[j];
					C[j] = C[j - 1];
					C[j - 1] = temp;
				}
			}
		}
		
		return C;
	}
	
	public static String[] selectionSort(String[] C, int N){
		for (int i = 0; i < N; i++) {
			int minj = i;
			for (int j = i; j < N; j++) {
				if (Character.getNumericValue(C[minj].charAt(1)) > Character.getNumericValue(C[j].charAt(1))) {
					minj = j;
				}
			}
			String temp = C[i];
			C[i] = C[minj];
			C[minj] = temp;
		}
		
		return C;
	}
	
	public static boolean isStable(String[] C1, String[] C2){
		for (int i = 0; i < C2.length; i++) {
			if (!C1[i].equals(C2[i])) {
				return false;
			}
		}
		return true;
	}
}

Measured memory_bytes: 26252
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
ll calc(ll x){
	ll res=0;
	rep(i,1,100){
		if((i*(i+1))/2<=x)res=i;
	}
	return res;
}
void solve(){
	ll n;
	cin>>n;
	vector<pp> v(n);
	rep(i,0,n){
		cin>>v[i].fi>>v[i].se;
	}
	ll mini=0, maxi=0;
	vector<ll> tmp1, tmp2;
	for(auto u : v){
		tmp1.pb(u.fi);
		tmp2.pb(u.se);
	}
	sort(all(tmp1));
	sort(all(tmp2));
	if(n%2){
		mini=tmp1[n/2];
		maxi=tmp2[n/2];
	} else {
		mini=tmp1[n/2]+tmp1[n/2-1];
		maxi=tmp2[n/2]+tmp2[n/2-1];
	}
	cout<<maxi-mini+1;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 9824
from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良いので入れておく
l = [0]
num = 0
for i in range(len(S)):
    # 繰り返し二乗法で累乗の部分を高速化
    # 自分で書かなくてもpow()で既に実装されている
    # 一つ前のmodを利用するとPythonで通せた、それをしなくてもPyPyなら通る
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)


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

constexpr int N_MAX = 8;
bool graph[N_MAX][N_MAX];

int dfs(int v, int n, bool* visited) {
  int count = 0;
  rep(i, n) { if (visited[i]) count++; }
  if (count == n) return 1;

  int result = 0;
  rep(i, n) {
    if (graph[v][i] == false) continue;
    if (visited[i]) continue;

    visited[i] = true;
    result += dfs(i, n, visited);
    visited[i] = false;
  }
  return result;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);

  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int a, b;
    cin >> a >> b; --a; --b;
    graph[a][b] = graph[b][a] = true;
  }

  bool visited[n] {};
  fill(visited, visited+n, false);
  visited[0] = true;
  cout << dfs(0, n, visited) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n, s[100], dp[10000];
int main() {
  cin >> n;
  read_n(s, n);

  dp[0] = 1;
  for (i64 i = 0; i < n; ++i) {
    for (i64 x = 10000; x >= s[i]; --x) {
      dp[x] += dp[x - s[i]];
    }
  }

  i64 ans = 0;
  for (i64 x = 10000; x >= 0; --x) {
    if (dp[x] > 0 && x % 10 != 0) ans = max(ans, x);
  }
  
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 384