akhauriyash/Code-Regression huggingface dataset:
M, N = map(int, input().split())
K = int(input())
P = ['_' * (N + 1) for _ in range(M + 1)]
for mi in range(1, M + 1):
    P[mi] = '_' + input()
# for p in P:
#     print('p', p)

J = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
O = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
I = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
for i in range(1, M + 1):
    ji, oi, ii = 0, 0, 0
    for j in range(1, N + 1):
        ji += P[i][j] == 'J'
        oi += P[i][j] == 'O'
        ii += P[i][j] == 'I'
        J[i][j] = J[i - 1][j] + ji
        O[i][j] = O[i - 1][j] + oi
        I[i][j] = I[i - 1][j] + ii
# for j in J:
#     print('j', j)
# for o in O:
#     print('o', o)
# for i in I:
#     print('i', i)


def cum(mat, a, b, c, d):
    a -= 1
    b -= 1
    return mat[a][b] + mat[c][d] - mat[a][d] - mat[c][b]

for k in range(K):
    a, b, c, d = map(int, input().split())
    j = cum(J, a, b, c, d)
    o = cum(O, a, b, c, d)
    i = cum(I, a, b, c, d)
    print(j, o, i)

Measured memory_bytes: 128708
MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

if __name__ == '__main__':
    solve()


Measured memory_bytes: 29164
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename x>
using ordered_set = tree<x,null_type,less<x>,rb_tree_tag,tree_order_statistics_node_update>;
#define sorta(a,n) sort(a,a+n)
#define sortad(a,n) sort(a,a+n,greater<__typeof(a[0])>())
#define all(x) (x).begin(),(x).end()
#define ms0(x) memset((x),0,sizeof((x)))
#define ms1(x) memset((x),-1,sizeof((x)))
typedef pair<long long,long long> pi;
#define inarr(arr,n) for(long long i=0;i<n;i++)cin>>arr[i];
#define prinarr(arr) {for(long long x:arr)cout<<x<<" ";} cout<<"\n";
#define cout1(a) cout<<a<<"\n";
#define cout2(a,b) cout<<a<<" "<<b<<"\n";
#define cout3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define setpre(n) cout<<fixed<<setprecision(8)<<n<<"\n";
#define filldp(arr,n,m,k) for(long long i=0;i<n;i++){for(long long j=0;j<m;j++) arr[i][j]=k;}

#define mod 1000000007
#define mod1 998244353


vector<vector<long long>> adj;
vector<long long> dis;
vector<long long> parent;
vector<bool> visited;

void newgr(long long n){
    n+=10;
    adj=vector<vector<long long>>(n);
    dis=vector<long long>(n,0);
    //parent=vector<long long>(n,-1);
    visited=vector<bool>(n,false);
}

void dfs(long long s){
    visited[s]=true;
    for(auto u:adj[s]){
        if(!visited[u]){
            //parent[u]=s;
            dis[u]=dis[s]+1;
            dfs(u);
        }
    }
}

void bfs(long long s){
    queue<long long> q;
    q.push(s);
    visited[s]=true;
    dis[s]=0;
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(auto x:adj[u]){
            if(!visited[x]){
                //parent[x]=u;
                visited[x]=true;
                dis[x]=dis[u]+1;
                q.push(x);
            }
        }
    }
}

long long power(long long x,long long y){  
    long long ans=1;
    x%=mod;
    while(y>0){
        if(y&1) ans=(ans*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ans;
}

long long modinv(long long b){ 
    return power(b,mod-2);
}



int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    long long n;
    cin>>n;
    long long arr[n];
    inarr(arr,n);
    sort(arr,arr+n,greater<long long>());
    long long ans=arr[0];
    long long p=n-2;
    for(long long i=1;i<n and p>0;i++){
        ans+=arr[i];
        p--;
        if(p==0)break;
        ans+=arr[i];
        p--;
    }
    cout1(ans);
    return 0;
}

Measured memory_bytes: 5224
#include <stdio.h>

int	diff(int a, int b)
{
	if (a < b)
		return (b - a);
	else
		return (a - b);
}

void ft_sort(int *a, int n)
{
	int tmp;
	int j;
	int i = 0;
	while (i < n - 1)
	{
		j = i + 1;
		while (j < n)
		{
			if (a[i] < a[j])
			{
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
			j++;
		}
		i++;
	}
}

int main(void)
{
	int alice = 0;
	int bob = 0;
	int n;
	scanf("%d", &n);
	int a[n + 1];
	int i;
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	ft_sort(a, n);
	i = 0;
	while (i < n)
	{
		// printf("%d ", a[i]);
		if (i % 2 == 0)
			alice += a[i];
		else
			bob += a[i];
		i++;
	}
	printf("%d", diff(alice, bob));
	return (0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<long> A(N + 1);
  vector<long> B(N);
  for(int i = 0; i < N + 1; i++) cin >> A.at(i);
  for(int i = 0; i < N; i++) cin >> B.at(i);
  
  long cnt = 0;
  
  for(int i = 0; i < N; i++) {
    if(i % 2 == 0) {
      if(A.at(i / 2) >= B.at(i / 2)) {
        cnt += B.at(i / 2);
        A.at(i / 2) -= B.at(i / 2);
        B.at(i / 2) = 0;
      }
      else if(A.at(i / 2) + A.at(i / 2 + 1) <= B.at(i / 2)) {
        cnt += (A.at(i / 2) + A.at(i / 2 + 1));
        B.at(i / 2) -= (A.at(i / 2) + A.at(i / 2 + 1));
        A.at(i / 2) = 0;
        A.at(i / 2 + 1) = 0;
      }
      else if(A.at(i / 2) + A.at(i / 2 + 1) > B.at(i / 2)) {
        cnt += B.at(i / 2);
        A.at(i / 2 + 1) -= (B.at(i / 2) - A.at(i / 2));
        A.at(i / 2) = 0;
        B.at(i / 2) = 0;
      }
    }
    else {
      if(A.at(N - (i + 1) / 2 + 1) >= B.at(N - (i + 1) / 2)) {
        cnt += B.at(N - (i + 1) / 2);
        A.at(N - (i + 1) / 2 + 1) -= B.at(N - (i + 1) / 2);
        B.at(N - (i + 1) / 2) = 0;
      }
      else if(A.at(N - (i + 1) / 2 + 1) + A.at(N - (i + 1) / 2) <= B.at(N - (i + 1) / 2)) {
        cnt += (A.at(N - (i + 1) / 2 + 1) + A.at(N - (i + 1) / 2));
        B.at(N - (i + 1) / 2) -= (A.at(N - (i + 1) / 2 + 1) + A.at(N - (i + 1) / 2));
        A.at(N - (i + 1) / 2 + 1) = 0;
        A.at(N - (i + 1) / 2) = 0;
      }
      else if(A.at(N - (i + 1) / 2 + 1) + A.at(N - (i + 1) / 2) > B.at(N - (i + 1) / 2)) {
        cnt += B.at(N - (i + 1) / 2);
        A.at(N - (i + 1) / 2) -= (B.at(N - (i + 1) / 2) - A.at(N - (i + 1) / 2 + 1));
        A.at(N - (i + 1) / 2 + 1) = 0;
        B.at(N - (i + 1) / 2) = 0;
      }
    }
  }
    
  cout << cnt << endl;
    
}

Measured memory_bytes: 1792
// vim: shiftwidth=2 expandtab foldmethod=marker

// include {{{
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <utility>
#include <cstdlib>
// }}}

// misc {{{
using namespace std;
typedef long long ll;
#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++)
// }}}

// debug(...) {{{
bool debug_enabled = false;

void debug1(char const * x) { cout << x; }
template<class T> void debug1(const T& x) { cout << x; }
template<class T1, class T2> void debug1(const pair<T1, T2>& x) { cout << "(" << x.first << ", " << x.second << ")"; }
template<class T> void debug1(const vector<T>& x) {
  cout << "[";
  auto i = x.begin();
  while(i != x.end()) {
    debug1(*i);
	++i;
	if(i != x.end()) cout << ", ";
  }
  cout << "]";
}
template<class K, class V> void debug1(const map<K, V>& x) {
  cout << "{";
  auto i = x.begin();
  while(i != x.end()) {
    debug1(get<0>(*i));
    cout << ": ";
    debug1(get<1>(*i));
    ++i;
    if(i != x.end()) cout << ", ";
  }
  cout << "}";
}

void debug2() { cout << endl; }
template<class T, class... Ts> void debug2(const T& x, const Ts&... xs) {
  cout << ' ';
  debug1(x);
  debug2(xs...);
}

template<class T, class... Ts> void debug(const T& x, const Ts&... xs) {
  if(debug_enabled) {
	cout << "[D] ";
	debug1(x);
	debug2(xs...);
  }
}
// }}}

// main {{{
void solve();
int main() {
  auto v = getenv("DEBUG");
  if(v && string(v) == "1") debug_enabled = true;
  solve();
}
// }}}


void solve() {
  int N;
  cin >> N;
  map<int, vector<pair<int, int>>> UVW;
  map<int, vector<pair<int, int>>> VUW;
  rep(i, N - 1) {
    int u, v, w;
    cin >> u >> v >> w;
    UVW[u].push_back(make_pair(v, w));
    VUW[v].push_back(make_pair(u, w));
  }

  debug("UVW", UVW);
  debug("VUW", VUW);

  vector<int> WB(N + 1, -1);
  // v, color
  stack<tuple<int,int>> st;
  st.push(make_tuple(1, 0));

  while(!st.empty()) {
    auto x = st.top();
    st.pop();
    int cur = get<0>(x);
    int color = get<1>(x);
    debug("cur-color", cur, color, WB[cur]);
    if(WB[cur] != -1) continue;
    WB[cur] = color;
    for(auto vw: UVW[cur]) {
      int c = get<1>(vw) % 2 == 0 ? color : 1 - color;
      st.push(make_tuple(get<0>(vw), c));
      debug("push", vw);
    }
    for(auto uw: VUW[cur]) {
      int c = get<1>(uw) % 2 == 0 ? color : 1 - color;
      st.push(make_tuple(get<0>(uw), c));
      debug("push", uw);
    }
  }

  rep2(i, 1, N + 1) {
    cout << WB[i] << endl;
  }
}


Measured memory_bytes: 20736
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> m(n), a(n), b(n);
        vector<int> x;
        for (int i=0; i<n; ++i) {
            cin >> m[i] >> a[i] >> b[i];
            x.push_back(a[i]);
            x.push_back(b[i]);
        }
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());

        int sum[300] = {};
        for (int i=0; i<n; ++i) {
            int a2 = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
            int b2 = lower_bound(x.begin(), x.end(), b[i]) - x.begin();
            sum[a2] += m[i];
            sum[b2] -= m[i];
        }

        bool ok = true;
        for (int i=0; i<300; ++i) {
            sum[i] += (i == 0 ? 0 : sum[i-1]);
            if (150 < sum[i]) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "OK" : "NG") << endl;
    }
    return 0;
}

Measured memory_bytes: 1212
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.lang.String.format;

public class Main{
    final static int MAX = 1000 + 5;
    static int n, m;
    static int[] a = new int[MAX];
    
    static void solve(){
        int[] task = new int[MAX];
        for(int i=0;i<n;i++) task[i] = m / a[i] * a[i];
        int min = 1<<29, idx=-1;
        for(int i=0;i<n;i++) {
            if(task[i] < min) { min = task[i]; idx = i; }
            else if(idx>=0){
                if(task[i] == min && a[i] < a[idx]) { idx = i; }
                else if(task[i] == min && a[i] == a[idx]) { idx = -2; }
            }
        }
        if(idx == -2) out.println(n);
        else out.println(idx+1);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        while(true){
            n = sc.nextInt();
            m = sc.nextInt();
            if(n == 0 && m == 0) break;
            for(int i=0;i<n;i++) a[i] = sc.nextInt();
            solve();
        }
    }
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=2005,INF=1<<30;
ll dp[MAX];

void mul(int a){
    if(a<=0) return;
    for(int j=1;j<MAX;j++){
        dp[j]+=dp[j-1];
        if(dp[j]>=mod) dp[j]-=mod;
    }
    
    for(int j=MAX-1;j>=0;j--){
        if(j-(a+1)>=0){
            dp[j]-=dp[j-(a+1)];
            if(dp[j]<0) dp[j]+=mod;
        }
    }
}//1+x+x^2+...+x^aから選ぶ

void div(int a){
    for(int j=MAX-1;j>=1;j--){
        dp[j]-=dp[j-1];
        if(dp[j]<0) dp[j]+=mod;
    }
    
    for(int j=0;j<MAX;j++){
        if(j-(a+1)>=0){
            dp[j]+=dp[j-(a+1)];
            if(dp[j]>=mod) dp[j]-=mod;
        }
    }
}//逆

ll rui(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

ll comb(ll a,ll b){
    ll res=1;
    for(ll i=0;i<b;i++){
        res*=(a-i)%mod;
        res%=mod;
        res*=rui(i+1,mod-2);
        res%=mod;
    }
    return res;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        ll N,D,X;cin>>N>>D>>X;
        if(N==0) break;
        X-=2;
        
        ll ans=0;
        
        for(ll i=1;i<=min(N,D);i++){
            mul(X);
            
            ans+=dp[N-i]*comb(D,i);
            
            ans%=mod;
        }
        if(X<0) ans=0;
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 3176
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N;
int a[50], b[50];
int M;
int u[20], v[20];

vector<pair<int,int>> edge[50];

bool visited[50];
set<int> st[20];
bool dfs(int n, int g, int t){
	if(visited[n]) return false;
	visited[n] = true;
	if(n == g){
		return true;
	}
	rep(i, edge[n].size()){
		bool ret = dfs(edge[n][i].first, g, t);
		if(ret){
			st[t].insert(edge[n][i].second);
			return true;
		}
	}
	return false;
}

ll memo[50][1<<20];
ll solve(int n, int s){
	//cout << n << " " << bitset<20>(s) << endl;
	if(n == N-1){
		if(s == (1<<M)-1) return 1;
		else return 0;
	}
	if(memo[n][s] != -1) return memo[n][s];
	ll ret = solve(n+1, s);
	int s2 = s;
	rep(i, M){
		if((s2 >> i)%2 == 1) continue;
		if(st[i].count(n) == 1){
			s2 += (1<<i);
		}
	}
	ret += solve(n+1, s2);
	return memo[n][s] = ret;
}

signed main(){
	cin >> N;
	rep(i, N-1){
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		if(a[i] > b[i]) swap(a[i], b[i]);
		edge[a[i]].pb({ b[i],i });
		edge[b[i]].pb({ a[i],i });
	}
	cin >> M;
	rep(i, M){
		cin >> u[i] >> v[i];
		u[i]--; v[i]--;
		memset(visited, 0, sizeof(visited));
		dfs(u[i], v[i], i);
		/*for(auto itr=st[i].begin(); itr!=st->end(); itr++){
			cout << *itr << " ";
		}
		cout << endl;*/
	}

	memset(memo, -1, sizeof(memo));
	cout << solve(0, 0) << endl;
}

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

#define int long long
#define pb push_back 
#define pf push_front 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i, n) for ( int i = 0 ; i < (n); i++ )
#define All(v) v.begin(), v.end()

typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

signed main() {
  int N;
  vector<int> v;

  cin >> N;
  int pre = -1;
  Rep(i, N) {
    int a; cin >> a;
    if ( pre == a ) v.pb(i);
    pre = a;
  }
  v.pb(N);
  //Rep(i, v.size()) cout << v[i] << endl;

  int a = 0, b = 0, c = 0, d = 0;;
  int ans = 0;
  Rep(i, v.size()) {
    a = v[i];
    ans = max(ans, (a-b)+(b-c)+(c-d));
    d = c; c = b; b = a;
  }

  cout << ans << endl;
}

Measured memory_bytes: 3400
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(long long i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
const ll MOD = 1e9+7;
// const ll INF = 1000000000000000000LL;
 
 
 int main() {
	 string s; cin >> s;
	 ll k; cin >> k;
	 char ans;
	bool flag = true;
	rep(i,s.size()){
		if(s[i]!='1')
			flag = false;
		if(i==k-1) break;
	}
	if(flag){
		cout << 1 << endl;
		return 0;
	}

	 for(int i=0;i<s.size();i++){
		 if(s[i]!='1'){
			 ans = s[i];
			 break;
		 }
	 }
	 cout << ans << endl;
	 return 0;
 }


Measured memory_bytes: 3596
def calc():
    def mex(i):
        D = {}
        for j in X[i]:
            D[G[j]] = 1
        for g in range(N + 1):
            if g not in D:
                return g
    M = int(input())
    X = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        X[N - min(a, b)].append(N - max(a, b))
    G = [0] * N
    for i in range(N):
        G[i] = mex(i)
    H = [0] * 1024
    a = 1
    for i in range(N)[::-1]:
        a = a * A % P
        H[G[i]] = (H[G[i]] + a) % P
    return H

P = 998244353
A = pow(10, 18, P)
N = int(input())
H1, H2, H3 = calc(), calc(), calc()
ans = 0
for i in range(1024):
    if H1[i] == 0: continue
    for j in range(1024):
        if H2[j] == 0: continue
        ans = (ans + H1[i] * H2[j] * H3[i^j]) % P

print(ans)

Measured memory_bytes: 78112
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define testcase int t;cin>>t;while(t--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<long long int,long long int>
typedef long long int ll;
typedef unsigned long long int ull;
#define M 1000000007
using namespace std;
int main()
{
    fast
    string str;
cin>>str;
if(str[0]=='A'&&str[1]=='A'&&str[2]=='A'||str[0]=='B'&&str[1]=='B'&&str[2]=='B')
cout<<"No";
else
cout<<"Yes";
cout<<endl;
return 0;
}







Measured memory_bytes: 256
using System;

namespace agc023_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            char[,] ban = new char[n, n];
            for (int i = 0; i < n; i++)
            {
                string s = Console.ReadLine();
                for (int j = 0; j < n; j++) ban[i, j] = s[j];
            }
            int ret = 0;
            for (int i = 0; i < n; i++)
            {
                bool flag = true;
                for (int k = 0; k < n && flag; k++)
                {
                    for (int l = 0; l < n && flag; l++)
                    {
                        if (ban[(k + i) % n, l % n] != ban[(l + i) % n, k % n])
                            flag = false;
                    }
                }
                if (flag) ret += n;
            }
            Console.WriteLine(ret);
        }
    }
}

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

class D
{
	static void Main()
	{
		Console.ReadLine();
		int r = 0, t = 1;
		foreach (var v in Console.ReadLine().Split().Select(int.Parse))
			if (v == t) t++;
			else r++;
		Console.WriteLine(t == 1 ? -1 : r);
	}
}


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

int N, s[105];
int dp[100005];
int maxi = 0;

int main() {
    scanf("%d", &N);
    for (int i = 0; i != N; ++i) scanf("%d", &s[i]);
    dp[0] = true;
    for (int i = 0; i != N; ++i)
        for (int j = 10000; j >= s[i]; --j)
            dp[j] |= dp[j - s[i]];
    for (int i = 9999; i != 0; --i)
        if (i % 10 != 0 && dp[i]) maxi = max(maxi, i);
    printf("%d\n", maxi);
    return 0;
}


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

int main(void){
    int i, N, V, j, k;
    int *In;

    scanf("%d",&N);
    In = (int*)malloc(sizeof(int)*N);
      for(k=0 ; k<N ; k++){
            scanf("%d",&In[k]);
        }
  printf("%d",In[0]);
             for(k=1 ; k<N ; k++){
            printf(" %d",In[k]);
        }
        printf("\n");


    for(i=1 ; i<N ; i++){
        V=In[i];
        j=i-1;
        while(j>=0 && In[j]>V){
            In[j+1] = In[j];
            j--;
            In[j+1]=V;
        }
        printf("%d",In[0]);
        for(k=1 ; k<N ; k++){
            printf(" %d",In[k]);
        }
        printf("\n");
    }
    free(In);
    return 0;
}


Measured memory_bytes: 2084
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

void solve(int v, vector<int>& visited, const vector<vector<int> >& deg)
{
  visited[v] = 1;
  for (int i = 0; i < deg.size(); ++i) {
    if (deg[v][i] != 0 && !visited[i])
      solve(i, visited, deg);
  }
}

int main()
{
  int n;
  while (cin >> n) {
    if (n == 0)
      break;

    vector<vector<int> > deg(26, vector<int>(26, 0));
    set<char> v;
    for (int i = 0; i < n; ++i) {
      string s;
      cin >> s;
      ++deg[s[0]-'a'][s[s.size()-1]-'a'];
      v.insert(s[0]);
    }

    vector<int> visited(26, 0);
    solve(0, visited, deg);
    bool connected = true;
    int cnt = 0;
    for (int i = 1; i < 26; ++i) {
      if (visited[i])
	++cnt;
    }
    if (cnt != v.size()-1)
      connected = false;
    
    bool euler = true;
    for (int i = 0; i < 26; ++i) {
      int in = 0, out = 0;
      for (int j = 0; j < 26; ++j) {
	in += deg[j][i];
	out += deg[i][j];
      }
      if (in != out)
	euler = false;
    }

    if (connected && euler)
      cout << "OK" << endl;
    else
      cout << "NG" << endl;
  }
  return 0;
}

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

int main() {
  int i, j;
  long long int N;
  long long int K;
  long long int t_k;

  long long int p_k;
  long long int c;

  double sum;

  
  // scanf("%d%d", &N, &K);
  scanf("%lld%lld", &N, &K);

  // printf("end");
  // return 0;

  t_k = K;
  lli p_N = N;
  lli diff;
  // printf("%lld\n", t_k);
  c = 0;
  do{
    if(t_k > N){
      sum += 0;
    }
    else {
      if (p_N){
        diff = p_N - t_k + 1;
        p_N = 0;
      }
      else{
        diff = p_k - t_k;
      }
      double prob = pow(0.5, c);
      // printf("%f", prob);
      // sum = sum * (1-prob) + diff * prob;
      // sum += (p_k - t_k + 1) * prob;
      sum += diff * prob;
    }

    // afterward
    c++;
    p_k = t_k;
    if(t_k % 2 == 1){
      t_k = t_k/2 + 1;
    }
    else{
      t_k = t_k / 2;
    }
    // printf("%lld\n", t_k);
  } while (p_k > 1);

  printf("%.12f", sum / N);

  return 0;
}

Measured memory_bytes: 128
def main():
  x,y,a,b,c=map(int,input().split())
  ps=sorted(list(map(int,input().split())))
  qs=sorted(list(map(int,input().split())))
  rs=sorted(list(map(int,input().split())))
  points=sorted(ps[-x:]+qs[-y:])
  return sum(sorted(points+rs)[-x-y:])
print(main())
  

Measured memory_bytes: 111656
N, C = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(N)]

P.sort()

rec = []
rec_cha = [None] * C
for s, t, c in P:
    c -= 1
    if rec_cha[c] is None:
        for i, (pt, pc) in enumerate(rec):
            if pt < s:
                rec[i] = (t, c)
                rec_cha[pc] = None
                rec_cha[c] = i
                break
        else:
            rec.append((t, c))
            rec_cha[c] = len(rec) - 1
    else:
        rec[rec_cha[c]] = (t, c)

print(len(rec))


Measured memory_bytes: 65624
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}


template <typename T> T lcs_restore(T a, T b){
  int n = a.size(), m = b.size();
  vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
  vector<vector<pair<int,int>>> restore(n+1, vector<pair<int,int>>(m+1,make_pair(-1,-1)));
  
  REP(i,n){
    REP(j,m){
      if(a[i] == b[j]){
        dp[i+1][j+1] = dp[i][j] + 1;
        restore[i+1][j+1] = make_pair(i,j);
      }else{
        if(dp[i][j+1] > dp[i+1][j]){
          dp[i+1][j+1] = dp[i][j+1];
          restore[i+1][j+1] = restore[i][j+1];
        }else{
          dp[i+1][j+1] = dp[i+1][j];
          restore[i+1][j+1] = restore[i+1][j];
        }
      }
    }
  }

  T ret;
  pair<int,int> cur(n,m);

  while(1){
    cur = restore[cur.fst][cur.snd];
    if(cur == make_pair(-1,-1)) break;
    ret.push_back(a[cur.fst]);
  }

  reverse(ALL(ret));
    
  return ret;
}



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

  string s,t;
  while(cin >> s >> t){
    auto ans = lcs_restore(s,t);
    cout << ans << endl;
  }
  
  return 0;
}


Measured memory_bytes: 105984
#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 1e9

using namespace std;

typedef int long long ll;
typedef int long l;
typedef pair<int, int> Pii;
const ll MOD = 1000000007;

void ii(int x){
    x>=0?printf("+%d",x):printf("%d",x);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    char a[4];
    cin>>a;
    int x[4];
    for (int i = 0; i < 4; i++){
        x[i]=int(a[i])-int('0');
    }
    for (int i = -1; i < 2; i+=2){
        int ans=x[0];
        ans+=i*x[1];
        for (int j = -1; j < 2; j+=2){
            ans+=j*x[2];
            for (int k = -1; k < 2; k+=2){
                ans+=k*x[3];
                if(ans==7){
                    printf("%d",x[0]);
                    ii(x[1]*i);
                    ii(x[2]*j);
                    ii(x[3]*k);
                    printf("=%d\n",7);
                    return 0;
                }
                ans-=k*x[3];
            }
            ans-=j*x[2];
        }
    }

    
    return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
const int N = 1e5 + 5, mod = 1e9 + 7;
bool step[N];
int n, m, dp[N];
ll solve(int idx){
    if(idx > n || (step[idx] == false)) return 0;
    if(idx == n) return 1;
    if(dp[idx] != -1) return dp[idx];
    ll ans = 0;
    ans = (ans + (solve(idx + 1) % mod)) % mod;
    ans = (ans + (solve(idx + 2) % mod)) % mod;
    dp[idx] = ans;
    return dp[idx];
}
int main(){
    Hello
    cin >> n >> m;
    for(int i = 0; i < N; i++) step[i] = true;
    for(int i = 0, a; i < m; i++){
        cin >> a;
        step[a] = false;
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0);
    return 0;
}


Measured memory_bytes: 8612
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cassert>


using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;
//
//template <class T>
//ostream& operator<<(ostream& os, const vector<T>& vec) {
//	for (const auto& e : vec) os << e << (&e == &vec.back() ? "" : " ");
//	return os;
//}

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, K;
	cin >> N >> K;

	vector<Int> a(N);
	for (Int i = 0; i < N; i++) {
		cin >> a[i];
	}

	vector<pair<mint, mint>> count(N, pair<mint, mint>());

	mint before;
	mint after;
	for (Int i = 0; i < N; i++) {
		before = 0;
		after = 0;
		for (Int j = 0; j < N; j++) {
			if (i == j) continue;
			if ((j < i) && (a[i] > a[j]))before+=1;
			if ((j > i) && (a[i] > a[j]))after+=1;
		}
		count[i].first = before;
		count[i].second = after;
	}

	mint ans = 0;
	for (Int i = 0; i < N; i++) {
		ans += count[i].second * K + (count[i].second + count[i].first) * K * (K - 1) / 2;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define print(v) cout<<v<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

#define MAX 100007
long long fac[100007], finv[100007], inv[100007];

// テーブルを作る前処理
void fact() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long comb(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    fact();
    ll N;
    cin >> N;
    vector<ll> a(N+1,0);
    for(ll i=0;i<N+1;i++)cin>>a[i];
    ll A=INF,B=INF;
    Map M;
    for(ll i=0;i<N+1;i++)M[a[i]]++;
    ll mark;
    for(auto p: M)if(p.second==2){mark=p.first;}
    for(ll i=0;i<N+1;i++){
        if(a[i]==mark&&A==INF)A=i;
        else if(a[i]==mark)B=i;
    }
    print(N)
    for(ll i=2;i<=N+1;i++){
        ll ans=0;
        ans+=comb(N-1,i);
        ans+=comb(N-1,i-2);
        ans-=comb(N+A-B,i-1);
        ans+=comb(N-1,i-1)*2;
        print((ans+MOD)%MOD)
    }

    return 0;
}


Measured memory_bytes: 10624
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
signed main(void) {
    int N, A, B;
    cin >> N >> A >> B;
    int ans = A * (N / (A + B));
    if(N % (A + B) < A)
        cout << ans + N % (A + B) << endl;
    else
        cout << ans + A << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define ll long long
#define double long double
#define INF LLONG_MAX/10000
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, u, v, w;
vector<P> vec[100010];
int d[100010];
bool used[100010];
void dfs(int s, int far) {
	d[s] = far;
	used[s] = true;
	for (P p : vec[s]) {
		if (!used[p.first])dfs(p.first, far + p.second);
	}
}
signed main() {
	cin >> n;
	rep(i, n - 1) {
		cin >> u >> v >> w;
		vec[u].push_back(make_pair(v, w));
		vec[v].push_back(make_pair(u, w));
	}
	dfs(1, 0);
	REP(i, n) {
		if (d[i] % 2)cout << 0 << endl;
		else cout << 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 9472
#include "bits/stdc++.h"
using namespace std;
const int K = 2005;
int N, M, U[K][K], D[K][K], L[K][K], R[K][K];
char S[K][K];
int main(){
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) { scanf("%s", S[i]+1); }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      if (S[i][j] == '.') {
        U[i][j] = U[i-1][j] + 1;
        L[i][j] = L[i][j-1] + 1;
      }
    }
  }
  for (int i = N; i >= 1; i--) {
    for (int j = M; j >= 1; j--) {
      if (S[i][j] == '.') {
        D[i][j] = D[i+1][j] + 1;
        R[i][j] = R[i][j+1] + 1;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      if (S[i][j] == '.') {
        ans = max(ans, U[i][j]+D[i][j]+L[i][j]+R[i][j]-3);
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 66944
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    cin >> a;
    b = a%10;
    if(b==2||b==4||b==5||b==7||b==9){
        cout << "hon";
    }
    else if(b==3){
        cout << "bon";
    }
    else{
        cout << "pon";
    }
}

Measured memory_bytes: 3080
N=int(input())
max_num=[0,0]
pass_time=0
for i in range(1,N+1):#1以上7以下
  num=0
  init_i=i
  while i%2==0:#偶数のあいだは
    i=i/2
    num+=1
  #print(init_i,num)
  if num>max_num[1]:
    max_num[0]=init_i
    max_num[1]=num
    pass_time+=1
if pass_time==0:
  max_num[0]=init_i
print(max_num[0])



Measured memory_bytes: 3060
s = input()
yy = int(s[0:2])
mm = int(s[2:4])
def month(num):
  return True if 1 <= num and num <= 12 else False
  
if month(mm) and month(yy):
  print("AMBIGUOUS")
elif month(mm):
    print("YYMM")
elif month(yy):
    print("MMYY")
else:
  print("NA")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  int a, b;
  cin >> a >> b;

  int flag = 0;
  int s;
  for (int c = 1; c < 4; c++){
    s = a * b * c;
    if ((s % 2) != 0){
      flag = 1;
    }
  }

  if (flag == 1){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


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

using namespace std;

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

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

    sort(a.begin(), a.end());

    int ans = 0;
    ll cur = 0;
    for (int i = 0; i < n; i++)
    {
        if (i == n - 1)
        {
            ans++;
            break;
        }
        cur += a[i];
        if (cur * 2 >= a[i + 1])
            ans++;
        else
            ans = 0;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3748
import java.util.Scanner;
 
public class Main {
    public static void main(String [] args){
        Scanner scan = new Scanner(System.in);
        int i = 1;
         
        while(true){
            int n = scan.nextInt();
             
            if(n == 0) break;
             
            System.out.println("Case " + i++ + ": " + n);
        }
    }
}

Measured memory_bytes: 31432
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>
#include<map>
#include<queue>
#include<deque>

#define rep(i, n) for (ll i = 0; i < n; i++) 
#define rrep(i, n) for(ll i = n-1; i>=0; i--)
#define range(i, n, m) for (ll i = n; i < m; i++) 
#define rrange(i, n, m) for (ll i = n - 1; i => m; i--) 
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vp vector<pair<ll, ll> >
#define vvp vector<vector<pair<ll, ll> > >
//#define MOD 998244353

typedef long long int ll;
typedef unsigned long long int ull;

using namespace std;

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() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	ll N, K;
	cin >> N >> K;

	vector<ll> V(N);
	rep(i, N) {
		cin >> V[i];
	}
	ll max = 0;

	rep(A, min(N,K)+1) {
		rep(B, min(N, K) - A+1) {
			vl minus;
			ll sum = 0;

			rep(l, A) {
				sum += V[l];
				if (V[l] < 0)minus.push_back(V[l]);
			}

			rep(r, B) {
				sum += V[N-1-r];
				if (V[N-1-r] < 0)minus.push_back(V[N-1-r]);
			}

			sort(minus.begin(), minus.end(), greater<ll>());

			rep(k, K - A - B) {
				if (minus.size() == 0) break;
				sum -= minus.back();
				minus.pop_back();
			}

			chmax(max, sum);
		}
	}


	cout << max << endl;



	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    while(true){
	int a=sc.nextInt();
	char op=sc.next().charAt(0);
	int b=sc.nextInt();
	if(op=='?'){
	    break;
	}
	else if(op=='+'){
	    System.out.println(a+b);
	}
	else if(op=='-'){
	    System.out.println(a-b);
	}
	else if(op=='*'){
	    System.out.println(a*b);
	}
	else if(op=='/'){
	    System.out.println(a/b);
	}
    }
  }
}


Measured memory_bytes: 26252
#include<stdio.h>
#include<math.h>
int isprime();

int main(){
    int i,data[10000],n,sum = 0;
    scanf("%d",&n);
    for(i = 0;i < n;i++){
    scanf("%d",&data[i]);
    }
    for(i = 0;i < n; i++){
    if(isprime(data[i]) == 1) sum++;
    }
    printf("%d\n",sum);
    return 0;
}

int isprime(x){
    int i;
    if(x == 2){
        return 1;
    }
    if(x<2||x%2==0){
        return 0;
    }
    i = 3;
    while(i <= sqrt(x)){
        if(x%i==0){
            return 0;
        }
        i = i +2;
    }
    return 1;
}


Measured memory_bytes: 2044
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::setprecision(15);}}fIO;
template<typename T> using V = std::vector<T>;
template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; }
/*-*/

int main() {
	constexpr int N=1e6+1;
	V<int> factor(N,0);
	for(int i=2;i<N;i++) {
		if(factor[i]) continue;
		for(int j=1;j*i<N;j++) {
			if(factor[i*j]) continue;
			factor[i*j]=i;
		}
	}

	int n;
	std::cin >> n;
	V<int> a(n);
	fill(a);
	if([&]()->int{
		V<int> pr(N,0);
		for(int e:a) {
			while(e>1) {
				int x=factor[e];
				if(pr[x]) {
					return 0;
				}
				pr[x]++;
				while(e%x==0) e/=x;
			}
		}
		return 1;
	}()) {
		print("pairwise coprime");
		return 0;
	}
	int g=0;
	for(int e:a) g=std::gcd(g,e);
	if(g==1) print("setwise coprime");
	else print("not coprime");
}


Measured memory_bytes: 14764
require 'set'
N, K = gets.split.map &:to_i
A = gets.split.map &:to_i
seq = [1]
set = Set.new([1])
idx = nil
while true
    next_one = A[seq[-1] - 1]
    seq << next_one
    added = set.add?(next_one)
    if !added
        idx = seq.find_index(next_one)
        break
    end
end
if K < seq.size
    p seq[K]
else
    mod = (K - idx) % (seq.size - idx - 1)
    p seq[idx + mod]
end


Measured memory_bytes: 38040
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

int main() {
  i64 N, K;
  std::cin >> N >> K;
  std::vector<i64> V;
  tools::read(V, N);

  std::vector<i64> cumsum({0});
  cumsum.reserve(N + 1);
  std::partial_sum(V.begin(), V.end(), std::back_inserter(cumsum));
  i64 answer = 0;
  for (i64 l = 0; l <= std::min(N, K); ++l) {
    for (i64 r = 0; r <= std::max<i64>(std::min(N, K) - l, 0); ++r) {
      i64 sum = cumsum[l] + (cumsum.back() - cumsum[N - r]);
      std::vector<i64> negative;
      for (i64 i = 0; i < l; ++i) {
        if (V[i] < 0) negative.push_back(V[i]);
      }
      for (i64 i = 0; i < r; ++i) {
        if (V[N - i - 1] < 0) negative.push_back(V[N - i - 1]);
      }
      std::sort(negative.begin(), negative.end());
      sum -= std::accumulate(negative.begin(), negative.begin() + std::min<i64>(negative.size(), K - l - r), static_cast<i64>(0));
      answer = std::max(answer, sum);
    }
  }

  std::cout << answer << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    ll n;cin>>n;
    string s;cin>>s;
    ll r=0,g=0,b=0;
    rep(i,0,n-1){
        if(s[i]=='R'){
            r++;
        }else if(s[i]=='G'){
            g++;
        }else{
            b++;
        }
    }
    ll ans=r*g*b;
    rep(i,1,n){
        rep(j,0,n-1){
            if(j+2*i>=n){
                break;
            }
            if(s[j]!=s[j+i] && s[j+i]!=s[j+2*i] && s[j+2*i]!=s[j]){
                ans--;
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}





Measured memory_bytes: 3624
#include <stdio.h>

int main(){
    int temp, i = 0;
    int arr[3];
    
    scanf("%d%d%d", &arr[0], &arr[1], &arr[2]);

    if(arr[0] > arr[2]){
        temp = arr[0];
        arr[0] = arr[2];
        arr[2] = temp;
    }
    if(arr[1] > arr[2]){
        temp = arr[1];
        arr[1] = arr[2];
        arr[2] = temp;
    }
    if(arr[0] > arr[1]){
        temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;
    }

    printf("%d %d %d\n", arr[0], arr[1], arr[2]);
    
    return 0;
}


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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define rep1(i,n) rep(i,1,n+1)

#define BR "\n"
#define SP " "

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

  vector<ll> A(N), C(K + 1, 0);

  rep0(i, N) cin >> A[i];

  ll ans = 1e9;
  ll l = 0, r = 0;
  ll cnt = 0;
  rep0(i, N) {
    ll a = A[i];
    if (a > K) continue;

    if (C[a] == 0) cnt++;
    C[a]++;

    if (cnt == K) {
      ans = min(ans, i - l + 1);
      
      while (true) {
        ll al = A[l];
        if (al > K) {
          l++;
          ans = min(ans, i - l + 1);
          continue;
        }
        if (C[al] <= 1) break;
        C[al]--;
        l++;
        ans = min(ans, i - l + 1);
      }
    }
  }

  if (ans == 1e9) ans = 0;
  cout << ans << BR;
  return 0;
}


Measured memory_bytes: 4396
using System;

namespace _1_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Console.Write(n + ":");
            for (int i = 2; i <= Math.Sqrt(n); i++)
            {
                while (n % i == 0)
                {
                    Console.Write(" " + i);
                    n = n / i;
                }
            }
            Console.WriteLine(n == 1 ? "" : " " + n.ToString());
        }
    }
}

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

using namespace std;

int main()
{
   char a[6];
   for(int i=0;i<6;i++)
   {
       cin>>a[i];
   }
    if(a[2]==a[3] && a[4]==a[5])
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }

}


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

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

int H, W;
string S[120];
int dp[110][110];

signed main()
{
    cin >> H >> W;
    rep(i, H)cin >> S[i];

    rep(i, H)rep(j, W)
    {
        if(i == 0 && j == 0)continue;
        dp[i][j] = 10000;

        if(i)dp[i][j] = min(dp[i][j], dp[i - 1][j] + (S[i - 1][j] != S[i][j]));
        if(j)dp[i][j] = min(dp[i][j], dp[i][j - 1] + (S[i][j - 1] != S[i][j]));
    }

    int ans = 0;
    if(dp[H - 1][W - 1] % 2)
        cout << dp[H - 1][W - 1] / 2 + 1 << endl;
    else
        cout << dp[H - 1][W - 1] / 2 + (S[0][0] == '#') << endl;

    return 0;
}


Measured memory_bytes: 3740
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  cout << "square1001" << endl;

  return 0;
}



Measured memory_bytes: 3068
using System;
using System.Collections.Generic;
using System.Linq;
class Ho{
  static void Main(){
    var zen = Console.ReadLine().Split();
    var n = int.Parse(zen[0]);
    var m = int.Parse(zen[1]);
    var a = new int[n];
    if(n == 1 && m == 0){Console.WriteLine("0");return;}
    if(m == 0){
      string f = "1";
      for(var i = 0;i<n-1;i++){
        f = f+"0";
      }
      Console.WriteLine(f);
      return;
    }
    
    for(var i = 0;i<n;i++){
      a[i] = 10;
    }
    for(var i = 0;i< m ;i++){
      var sc = Console.ReadLine().Split();
      var s = int.Parse(sc[0]);
      var c = int.Parse(sc[1]);
      if(a[s-1] == 10){a[s-1] = c;}
      else if(a[s-1] == c){a[s-1] = c;}
      else{
        Console.WriteLine("-1");
        return;
      }  
    }
    for(var i = 0;i<n;i++){
      if(a[0] == 10){a[0] = 1;continue;}
      if(a[i]== 10){a[i] =0;}
    }
    for(var i = 0;i<n;i++){
      if(n>=2&&a[0] == 0){Console.WriteLine("-1");return;}
      Console.Write(a[i]);
    }
  }
}

Measured memory_bytes: 13140