akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

struct UnionFind {
    vector<int> d;
    // コンストラクタ　親は-頂点数を保管
    UnionFind(int N) : d(N, -1) {}

    int find(int x) {
        if (d[x] < 0) {
            return x;
        }
        return d[x] = find(d[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (d[x] > d[y]) {
            swap(x, y);
        }
        d[x] += d[y];
        d[y] = x;
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return -d[find(x)];
    }
};

int main() {
    int n, k, l;
    cin >> n >> k >> l;
    UnionFind u(n), v(n);
    rep(i, k){
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        u.unite(p, q);
    }
    rep(i, l){
        int r, s;
        cin >> r >> s;
        r--;
        s--;
        v.unite(r, s);
    }
    map<P, int> mp;
    rep(i, n)mp[make_pair(u.find(i), v.find(i))]++;

    rep(i, n)cout << mp[make_pair(u.find(i), v.find(i))] << ' ';
    cout << endl;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define ll long long int
#define forr(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define oo 100000000000000000
using namespace std;



void _sol(){
    string s; cin >> s;
    ll cnt = 0;
    forr(i,s.size()){
        cnt += s[i] - '0';
    }
    if(cnt%9) cout << "No";
    else cout << "Yes";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    _sol();
}


Measured memory_bytes: 3744
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n,k;
    cin >> n >> k;
    vector<vi> v(10);
    rep(i,n){
        int a,b;
        cin >> a >> b;
        v[b-1].push_back(a);
    }
    rep(i,10)if(v[i].size()){
        sort(all(v[i]));
        reverse(all(v[i]));
        //rep(j,v[i].size())cout << " " << v[i][j];cout << endl;
        rep(j,v[i].size()-1)v[i][j+1] += v[i][j];
        rep(j,v[i].size())v[i][j] += j*(j+1);
        //rep(j,v[i].size())cout << " " << v[i][j];cout << endl;
    }
    int dp[15][2005] = {};
    rep(i,10)rep(j,k+1){
        //cout << i << " " << j << " " << dp[i][j] << endl;
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
        rep(x,v[i].size()){
            if(j+x+1 <= k)dp[i+1][j+x+1] = max(dp[i+1][j+x+1], dp[i][j] + v[i][x]);
        }
    }
    cout << dp[10][k] << endl;
}



Measured memory_bytes: 3396
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.*;
public class Main {
	int W,N;
	int[] v,w;
	int[] dp;
	public void solve(){
		for(int cc = 1;;cc++){
			W = nextInt();
			if(W == 0)break;
			
			N = nextInt();
			v = new int[N];
			w = new int[N];
			for(int i = 0;i < N;i++){
				String[] s = next().split(",");
				v[i] = Integer.parseInt(s[0]);
				w[i] = Integer.parseInt(s[1]);
			}
			
			dp = new int[W + 1];
			for(int i = 1;i <= N;i++){
				for(int j = W;j >= 0;j--){
					if(j + w[i - 1] <= W)dp[j + w[i - 1]] = Math.max(dp[j + w[i - 1]],dp[j] + v[i - 1]);
				}
			}
			int ans = 0;
			for(int j = 0;j <= W;j++){
				if(dp[ans] < dp[j]){
					ans = j;
				}
			}
			out.println("Case "+cc+":");
			out.println(dp[ans]);
			out.println(ans);
		}
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

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

typedef long long ll;

int main(){
	ll n,k;
	string s;
	cin >> n >> k >> s;

	vector<int> B(0);
	char c;
	for(int i=0; i<n; i++){
		if(s[i]!=c){
			B.push_back(i);
			c = s[i];
		}
	}

	int m = B.size();
	for(int i=0; i<=2*k; i++) B.push_back(n);

	int ans = 0;
	for(int i=0; i<m; i++){
		if(s[B[i]]=='0') ans = max(ans,B[i+2*k]-B[i]);
		else ans = max(ans,B[i+2*k+1]-B[i]);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4368
N=int(input())
C=list(map(int,input().split()))
MOD=10**9+7

fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*2%MOD

#コストの小さいbitから変更した方が得
C.sort()

ans=0
for i,c in enumerate(C):
    l=i
    r=N-l-1
    tmp=fac[r]%MOD
    tmp+=r*fac[r-1]%MOD if r>0 else 0
    tmp*=c*fac[l]%MOD
    ans+=tmp%MOD
ans*=fac[N]
ans%=MOD
print(ans)


Measured memory_bytes: 26024
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cctype>
#include<cassert>
#include<cmath>
#include<climits>
 
#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define D(x) cout << #x " is " << (x) << endl
#define is_palindrome(c) equal((c).begin(),(c).end(),(c).rbegin())
#define rep(i,n) for(int i = 0; i < n; i++)
#define foreach(it,c) for(__typeof__((c).begin()) it=(c).begin();it!=(c).end();it++)
#define x first
#define y second
 
using namespace std;
 
typedef unsigned int uint;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;
 
string toStr(int num){
  if(num==0)return "0";
  string res = "";
  while(num){
    res+=(num%10)+'0';
    num/=10;
  }
  reverse(res.begin(),res.end());
  return res;
}
 
int toInt(string s){return atoi(s.c_str());}
 
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
 
ll dp[1001][1001];
 
int main(void){
   
  int n;
  cin >> n;
 
  vector<pii>v(n);
  rep(i,n)cin >> v[i].x >> v[i].y;
 
 
  fill(dp[0],dp[1001],INT_MAX);
 
  rep(i,1001)dp[i][i]=0;
   
  for(int w=0;w<n;w++){
    for(int i=0;i+w<n;i++){
      for(int s=i;s<i+w;s++){
    ll cost=abs(v[i].x-v[s+1].x)+abs(v[s].y-v[i+w].y);
    dp[i][i+w]=min(dp[i][i+w],dp[i][s]+dp[s+1][i+w]+cost);
      }
    }
  }
 
  cout << dp[0][n-1] << endl;
   
  return 0;
}

Measured memory_bytes: 9032
a,b,k=map(int,input().split())
if b-a+1<=k*2:
    for i in range(a,b+1): print(i)
else:
    for i in range(k): print(a+i)
    arr=[]
    for i in range(k): arr.append(b-i)
    for i in arr[::-1]: print(i)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll A[303030];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll ret=0;
	FOR(i,60) {
		ll C[2]={};
		FOR(j,N) C[(A[j]>>i)&1]++;
		ll num=C[0]*C[1]%mo;
		ll s=(1LL<<i)%mo;
		(ret+=num*s)%=mo;
	}
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define p(s) cout<<s<<endl;
typedef long long LL;
template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}


int main()
{
    LL n;
    double x,ans=0;
    string u;
    cin>>n;
    rep(i,n){
        cin>>x>>u;
        if (u == "JPY"){
            ans+=x;
            // cout<<1<<endl;
        }else{
            ans+=380000*x;
            // cout << 2 << endl;
        }
    }
    printf("%.5lf\n",ans);
}

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

char b;
int main()
{
	cin >> b;
    char ans = 'A';
	if(b == 'A')
        ans = 'T';
	else if(b == 'T')
		ans = 'A';
	else if(b == 'C')
		ans = 'G';
	else if(b == 'G')
		ans = 'C';
    cout << ans << endl;
	return 0;
}


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

using namespace std;

int main(){
  long long N, P;
  cin >> N >> P;
  if (N == 1) {
    cout << P;
    return 0;
  }

  long long max_ans = pow(P, 1.0 / double(N)) + 10;
  
  for (long long d = max_ans; d > 0; d--) {
    long long num = pow(d, N);

    if (P % num == 0) {
      cout << d << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fin ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define w(t) while(t--)
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
#define what_is(x) cerr << #x << " is " << x << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
const int N = 1 * 1e5 + 5;
const ll mod = 998244353;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
const double E = 1e-9;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
vi G[N];
int H[N];
int main(){
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    fin;
    ll x;
    map<ll, ii> m;
    for(ll i = 1; i <= 120; i++){
        for(ll j = -120; j <= i; j++){
            ll li = i * i * i * i * i;
            ll lj = j * j * j * j * j;
            m[li - lj] = {i, j};
        }
    }
    cin >> x;
    if(m.count(x))
        cout << m[x].F << " " << m[x].S << '\n';  
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}   

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

const int MAXM = 8;
const int SIZE = 10001;

int m;
int a[MAXM], b[MAXM];
int dp[SIZE];

void rec(int sum, int i, int j) {
  if(i == m) {
    dp[sum] += 1;
    return;
  }
  rec(sum, i+1, 0);
  if(j < b[i]) rec(sum+a[i], i, j+1);
}

int main() {
  while(cin >> m && m) {
    for(int i = 0; i < m; ++i) {
      cin >> a[i] >> b[i];
    }
    fill(dp, dp+SIZE, 0);
    rec(0,0,0);

    int g;
    cin >> g;
    while(g--) {
      int n;
      cin >> n;
      cout << dp[n] << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1200
def choose2(n):
    return n*(n-1) // 2
from collections import Counter
N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
ttl = 0
for v in cnt.values():
    ttl += choose2(v)
for a in A:
    ans = ttl
    ans -= choose2(cnt[a])
    ans += choose2(cnt[a] - 1)
    print(ans)
    cnt[a] + 1

Measured memory_bytes: 26780
#include <bits/stdc++.h>
using namespace std;
#define dg(x) cerr << #x << " = " << x <<endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define fore(i,a,b) for(int i=(int)a;i<=(int)b;++i)
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll ans=0;
ll n;
void fun(ll x,int a,int b,int c){
    if(x>n)return;
    if(a&&b&&c)ans++;
    fun(x*10+3,1,b,c);
    fun(x*10+5,a,1,c);
    fun(x*10+7,a,b,1);
}
int main(){
#ifdef LOCAL
    //freopen("h.txt", "r", stdin);
    // freopen("main.out", "w", stdout);
#else
    ios::sync_with_stdio(0), cin.tie(0);
    #define endl '\n'
#endif
    cin>>n;
    fun(0,0,0,0);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*bc)]

mydict = {}
for i in A:
    if i in mydict:
        score = mydict[i]
        mydict[i] = score + 1
    else:
        mydict[i] = 1


count = 0
for k, v in mydict.items():
    count = count + k*v
    
for i in range(Q):
    if b[i] in mydict:
        if c[i] in mydict:
            score1 = mydict[b[i]]
            score2 = mydict[c[i]]
            
            count1 = score1* b[i]
            count2 = score1* c[i]
            del mydict[b[i]]
            mydict[c[i]] = score1 + score2
            count = count - count1 + count2

            
        else:
            count = count - b[i] * mydict[b[i]] + c[i] * mydict[b[i]]
            mydict[c[i]] = mydict[b[i]]
            del mydict[b[i]]
            

    
    print(count)

Measured memory_bytes: 71776
import java.util.*;

public class Main {
    static int fib(int n) {
        int a = 1;
        int b = 1;
        for (int i=1;i<n;i++) {
            int tmp = b;
            b = a+b;
            a = tmp;
        }
        return b;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = Integer.parseInt(sc.next());
        int W = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
        int mod = 1_000_000_007;
        long[][] dp = new long[H+1][W+2];
        dp[0][1]=1;
        for (int i=1;i<H+1;i++) {
            for (int j=1;j<W+1;j++) {
                dp[i][j] = (dp[i][j]+dp[i-1][j-1]*fib(j-2)*fib(W-j))%mod;
                dp[i][j] = (dp[i][j]+dp[i-1][j]*fib(j-1)*fib(W-j))%mod;
                dp[i][j] = (dp[i][j]+dp[i-1][j+1]*fib(j-1)*fib(W-j-1))%mod;
            }
        }
        System.out.println(dp[H][K]);
    }
}

Measured memory_bytes: 21972
import math

A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
list1 = [A,B,C,D,E]
list2 = [i%10 for i in list1]
min_item=max(list2)
for i in range(1,10):
    if i in list2:
        min_item = min(min_item,i)
min_index = list2.index(min_item)
total_time = 0
time_seq =[]

for i in range(5):
    if i == min_index:
        continue
    time1 = math.ceil(list1[i]/10) * 10
    total_time += time1
    time_seq.append(time1)
    
total_time += list1[min_index]
print(int(total_time))

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

bool solve() {
  string g;
  int y, m, d;
  cin >> g;
  if (g == "#") return (false);
  cin >> y >> m >> d;
  if (y >= 32 || y == 31 && m >= 5) {
    cout << "? " << y-30 << " " << m << " " << d << endl;
  } else {
    cout << "HEISEI " << y << " " << m << " " << d << endl;
  }
  return (true);
}

int main() {
  while (solve());
}


Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<int> x(5);
  for(int i=0;i<5;i++){
    cin>>x.at(i);
    if(x.at(i)==0){
      cout<<i+1<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

int main(void)
{
    while(1) {
	int e;
	cin >> e;
	if (!e) break;

	int m = e;
	for (int z = 0; z*z*z <= e; z++) {
	    for (int y = 0; y*y + z*z*z <= e; y++) {
		int x = e - z*z*z - y*y;
		int temp = x + y + z;
		if (m > temp) m = temp;
	    }
	}
	cout << m << endl;
    }
    return 0;
}



Measured memory_bytes: 3108
S = input()

if S == "SUN":
    print(7)
if S == "MON":
    print(6)
if S == "TUE":
    print(5)
if S == "WED":
    print(4)
if S == "THU":
    print(3)
if S == "FRI":
    print(2)
if S == "SAT":
    print(1)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
 
#define mod 1000000007
#define inf 1000000000
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
 
int main(){
  ll n;
  cin >> n;
  vector<ll> a(n, 0);
  for(ll i = 0; i < n; i++) cin >> a[i];

  ll all = 0;
  for(ll i = 0; i < n; i++){
    all += a[i];
  }

  ll ans = all, sum = 0;
  for(ll i = 0; i < n; i++){
    sum += a[i];
    ans = min(ans, abs(sum - (all - sum)));
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;
int turn[15],pi[15],num[15],vis[15];
int k,ans=0,n,m;
set<int>se[15];
void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=1; i<=n; i++)
        {
            if(turn[i]==1)
            {
                for(int j=1; j<=m; j++)
                {
                    if(se[j].find(i)!=se[j].end())
                        num[j]++;
                }
            }
        }
        int flag=0;
        for(int i=1; i<=m; i++)
        {
            if(pi[i]==0&&num[i]%2)
            {
                flag=1;
                break;
            }
            if(pi[i]==1&&num[i]%2==0)
            {
                flag=1;
                break;
            }

        }
        if(flag==0)
        {
            ans++;
        }
        memset(num,0,sizeof(num));
        return ;
    }
    turn[x]=1;
    dfs(x+1);
    turn[x]=0;
    dfs(x+1);

}
int main()
{
    int i,x,k;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x;
        for(int j=1; j<=x; j++)
        {
            cin>>k;
            se[i].insert(k);
        }
    }
    memset(turn,0,sizeof(turn));
    memset(pi,0,sizeof(pi));
    memset(vis,0,sizeof(vis));
    for(i=1; i<=m; i++)
        cin>>pi[i];
    dfs(1);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <stack>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <iomanip>
#include <string>
#include <limits>
using namespace std;
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
int mod = 1000000000 + 7;
vector<int> v;
class Calc
{
    // 宣言
    long long a;

    public:
        // 素因数分解
        void decompositPrime(long long a);
};

/*
 * 素因数分解
 */
void Calc::decompositPrime(long long n)
{
    // 割る数の初期値
    a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            //printf("%d * ", a);
             v.push_back(a);
            n /= a;
        } else {
            a++;
        }
    }
    // 最後に残った n は素因数
    v.push_back(n);
    //printf("%d\n", n);
}

int main(){
    //std::stack<int> stack;
    int x,n;
    cin >> x >> n;
    
    if(n == 0){
        cout << x << endl;
        return 0;
    }
    int ans = 0;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    vector<bool> cnt(100, true);
    for(int i = 0; i < n; i++){
        cnt[p[i]] = false;
    }
    int j = 0;
    while(1){
        if(cnt[x-j]){
            ans = x-j;
            break;
        }else if(cnt[x+j]){
            ans = x+j;
            break;
        }
        j ++;
    }
    cout << ans << endl;
    return 0;
}





Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>
   
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef node* Node;
#define NIL NULL
  
node array[500000];
int size=0;
  
Node root = NIL;
   
Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
}
   
Node treeSearch(Node u, int k){
  Node i=u;
  while(i!=NIL){
    if(i->key==k)return i;
    else if(i->key<k)i=i->right;
    else i=i->left;    
  }
  return NIL;
}
   
Node treeSuccessor(Node x){
  if(x->right!=NIL)return treeMinimum(x->right);
  Node y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}
   
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL||z->right==NIL)y=z;
  else y=treeSuccessor(z);
     
  if(y->left!=NIL)x=y->left;
  else x=y->right;
   
  if(x!=NIL)x->parent=y->parent;
     
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent->left=x;
  else y->parent->right=x;
   
  if(y!=z)z->key=y->key;
     
  //free(y);
}
   
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
   
  z = &array[size++];
  z->key = k;
  z->left = NIL;
  z->right = NIL;
   
  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;  
}
  
  
void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
  
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
  
  
int main(){
  int n,x;
  char str[20];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s", str);
    if(str[0]=='f'){
      scanf("%d",&x);
      Node t=treeSearch(root,x);
      if (t!=NIL) printf("yes\n");
      else printf("no\n");
    }else if(str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }else if(str[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(str[0]=='d'){
      scanf("%d",&x);
      treeDelete(treeSearch(root,x));
    }
  }
  
  return 0;
}


Measured memory_bytes: 15204
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k,i;
    cin>>n;
    string str;
    cin>>str;
    cin>>k;
    char s=str[k-1];
    for(i=0;i<str.length();i++){
        if(str[i]==s)
            cout<<str[i];
        else
            cout<<"*";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>

using namespace std;

int main() {
	int N;
	cin >> N;
	if (N % 2 == 0) cout << N << endl;
	else cout << N * 2 << endl;
	return 0;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
#define title "title"
#define ll long long
#define ull unsigned ll
#define fix(x) fixed<<setprecision(x)
#define pii pair<int,int>
#define vint vector<int>
#define pb push_back
using namespace std;
void Freopen(){
	freopen(title".in","r",stdin);
	freopen(title".out","w",stdout);
}
const int mod=998244353;
map<string,int>g,f;
string s;
int F(string s);
int G(string s);
int read(){
	int g=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){g=g*10+ch-'0';ch=getchar();}
	return g*f;
}
int G(string s){
	if(s.size()==1)return (s[0]=='1'?2:1);
	if(g.find(s)!=g.end())return g[s];
	for(int i=1;i<s.size();i++)if(!(s.size()%i)){
		string re;
		for(int j=0;j<i;j++){
			int flag=1;
			for(int k=0;k<s.size()/i;k++)if(s[k*i+j]=='0'){flag=0;break;}
			re+=(char)(flag+'0');
		}g[s]=(g[s]+F(re))%mod;
	}return g[s];
}
int F(string s){
	if(f.find(s)!=f.end())return f[s];
	for(int i=1;i<=s.size();i++)f[s]=(f[s]+1ll*F(s.substr(0,s.size()-i))*G(s.substr(s.size()-i,i))%mod)%mod;
	return f[s];
}
signed main(){
	cin>>s;f[""]=1;
	return cout<<F(s),signed();
}

Measured memory_bytes: 14104
#include<map>
#include<queue>
#include<string>
#include<cstdio>

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

using namespace std;

typedef pair<int,int> pii;

const int INF=1<<29;

struct edge{ int v,d; };

int main(){
	for(int m,ng,cap;scanf("%d%d%d",&m,&ng,&cap),m;){
		cap*=10;

		int n=0; // number of cities
		vector<edge> adj[7000];
		bool gas[7000]={};

		map<string,int> id;
		char ss[16],tt[16]; scanf("%s%s",&ss,&tt);
		if(id.count(ss)==0) id[ss]=n++;
		if(id.count(tt)==0) id[tt]=n++;
		int s=id[ss],t=id[tt];

		rep(i,m){
			char a[16],b[16];
			int d; scanf("%s%s%d",a,b,&d);
			if(id.count(a)==0) id[a]=n++;
			if(id.count(b)==0) id[b]=n++;

			int u=id[a],v=id[b];
			adj[u].push_back((edge){v,d});
			adj[v].push_back((edge){u,d});
		}
		rep(i,ng){
			char a[16]; scanf("%s",a);
			if(id.count(a)) gas[id[a]]=true;
		}

		static int d[7000][2001];
		rep(u,n) rep(c,cap+1) d[u][c]=INF;
		d[s][cap]=0;

		int ans=-1;
		priority_queue< pair<int,pii> > pq;
		pq.push(make_pair(0,make_pair(s,cap)));
		while(!pq.empty()){
			int d_now=-pq.top().first;
			int u=pq.top().second.first;
			int c_now=pq.top().second.second;
			pq.pop();

			if(d[u][c_now]<d_now) continue;

			if(u==t){ ans=d_now; break; }

			rep(i,adj[u].size()){
				edge e=adj[u][i];
				if(c_now<e.d) continue;

				int d_next=d_now+e.d;
				int c_next=(gas[e.v]?cap:c_now-e.d);
				if(d_next<d[e.v][c_next]){
					d[e.v][c_next]=d_next;
					pq.push(make_pair(-d_next,make_pair(e.v,c_next)));
				}
			}
		}

		printf("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 59000
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <fstream>
#include <queue>
#include <math.h>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <list>

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

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define chk(a) rep(i, a.size()) cout << a[i] << " "
#define SORT(c) sort((c).begin(),(c).end())
#define ll long long
#define vi(m,a) vector<int> m(a)
#define vti(m,a,i) vector<vector<int>> m(a,vector<int>(i))
#define ALL(it,a) for(auto it = a.begin(); it!=a.end(); it++)
#define Fe(it,a) for(auto &it : a)
#define all(a) begin(a),end(a)


using namespace std;
typedef pair<int, int> pii;
#define WARU 1000000007;

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

int main(void) {
	//int w, h;
	//cin >> w >> h;

	//vector<int> p(w);
	//rep(i, w)
	//	cin >> p[i];
	//vector<int> q(h);
	//rep(i, h)
	//	cin >> q[i];

	int n;
	cin >> n;
	vector<int> v(n);
	rep(i, n)
		cin >> v[i];
	long long int res = 0;
	int piv = 1;
	int localmin = 1;
	res = v[0] - 1;
	v[0] = 1;
	while (piv < n) {
		int price = localmin + 1;
		//cout << piv << ":" << res << "," << price << endl;
		//rep(i, n)
		//	cout << v[i] << " ";
		//cout << endl;
		if (v[piv] <= price) {
			localmin = max(localmin, v[piv]);
			piv++;
			continue;
		}
		if (v[piv] > price * 2) {
			if (v[piv] % price == 0) {
				res += (v[piv] / price - 1);
				v[piv] = 1;
			}
			else {
				res += v[piv] / price;
				v[piv] = 1;
			}
		}
		else {
			v[piv] = 1;
			res++;
		}
		piv++;
	}
	cout << res << endl;

	return 0;
}


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


/* int N;      //数の個数
int A[210]; //数を入れる変数、最大200

int main(){
    cin>>N;
    for(int i=0;i<N;i++)cin>>A[i];
    int res=0;


    //操作が行える限り操作を繰り返す
    while(true){
        bool exist_odd=false;   //A[i]がすべて偶数か判定するフラグ
        for(int i=0;i<N;i++){
            if(A[i]%2!=0)exist_odd=true;
        }
        if(exist_odd)break; //奇数があったらbreakする

        for (int i=0;i<N;i++){
            A[i]/=2;
        }
        res++;
    }
    cout<<res<<endl;
}
 */

int N;
int A[210];

int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    int res=0;

    while(true){
        bool exist_odd=false;
        for(int i=0;i<N;i++){
            if(A[i]%2!=0)exist_odd=true;
        }
        if(exist_odd)break;

        for(int i=0;i<N;i++){
            A[i]/=2;
        }
        res++;
    }
    cout<<res<<endl;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void){
  int a,b,c,d;
  
  while(1){
  scanf("%d %d %d",&a,&b,&c);
  if(a==-1&&b==-1&&c==-1)break;
  d=a+b;
  if(a==-1||b==-1){
    puts("F");
  }else if(d>=80){
    puts("A");
      }
  else if(d<85&&d>=65){
    puts("B");
  }else if(d<65&&d>=50){
    puts("C");
  }else if(d<50&&d>=30){
    if(c>=50){
      puts("C");
    } else{
      puts("D");
  }
  }
  else{
    puts("F");
  }
  }

  return 0;
}



Measured memory_bytes: 2032
#include <stdio.h>
#include <string.h>

int main()
{
    while(1){
        int n = 0,m = 0;
        char a[100000] = "",b[100000] = "";
        scanf("%d", &n);
        if(n == 0)return 0;
        for(int i=0;i<n;i++)scanf(" %c %c", &a[i], &b[i]);
        scanf("%d", &m);
        for(int i=0;i<m;i++){
            char chr,out = '\0';
            scanf(" %c",&chr);
            for(int j=0;j<n;j++){
                if(chr == a[j]){
                    out = b[j];
                    break;
                }else{
                    out = chr;
                }
            }
            printf("%c", out);
        }
        puts("");
    }
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
//#define int long long

void solve() {
	string s;
	map<char, int> hash;
	cin >> s;
	
	for(char c: s) {
		hash[c]++;
	}
	
	for(auto x: hash) {
		if(x.second%2 != 0) {
			cout << "No";
			return;
		}
	}
	
	cout << "Yes";
}
		
			
		

int32_t main() {
	IOS;
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    if(s == "ABC") {
        out("ARC");
    }
    else {
        out("ABC");
    }

    re0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100
#define INF 1<<30

int main(void){
  int n, p[MAX+1], m[MAX][MAX];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> p[i] >> p[i+1];
  }

  for(int i=1; i<=n; i++){
    m[i][i] = 0;
  }

  for(int l=1; l<n; l++){ // iとjの差を1からn-1まで変化させる
    for(int i=1; i<=n-l; i++){
      int j = i + l; // l-1がiとjの差
      m[i][j] = INF;
      for(int k=i; k<j; k++){
        m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]);
      }
    }
  }
  cout << m[1][n] << endl;
  return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#include <unordered_map>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;
ll f(ll n){
    return (n*n + 4) / 8;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,K;
    ll L[55];
    cin >> N >> K;
    rep(i,0,N) cin >> L[i];
    sort(L,L+N, greater<ll>());
    ll ans = 0;
    rep(i,0,K) ans += L[i];
    print(ans);
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    string S, T;
    cin >> S >> T;
    vector<vector<ll>> DP(S.size() + 1, vector<ll>(T.size() + 1, 0));
    for (int i = 1; i <= S.size(); i++) {
        for (int j = 1; j <= T.size(); j++) {
            if (S[i - 1] == T[j - 1]) {
                DP[i][j] = DP[i - 1][j - 1] + 1;
            }
            else {
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            }
        }
    }
    string ans;
    int count = DP[S.size()][T.size()];
    int i = S.size(), j = T.size();
    while (count > 0) {
        while(DP[i - 1][j] == DP[i][j]) i--;
        while(DP[i][j - 1] == DP[i][j]) j--;
        ans += S[i - 1];
        i--; j--;
        count--;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 70784
#include <cstdio>
#include <iostream>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;


int main(void) {
  ll n, k, x, y;
  scanf("%lld%lld%lld%lld", &n, &k, &x, &y);
  ll res = 0;
  for(int i = 1; i <= n; ++i) {
    res += i <= k ? x : y;
  }
  printf("%lld\n", res);
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
int main(){
    int n;
    long long x,a = 1,b = 1,c = 0,d = 0;
    cin >> n >> x;
    rep(i,n){
        a = 2*a + 3;
        b = 2*b + 1;
    }
    rep(i,n + 2){
        if(x == a){
            x = x - a;
            c = c + b;
        }else if(x > a){
            x = x - (a + 1);
            c = c + b + 1; 
        }
        x = x - 1;
        a = (a - 3)/2;
        b = (b - 1)/2;
    }
    cout << c << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

vector<vector<long long> > G(200000);
vector<long long> counter(200000 ,0);
void dfs(long long i , long long p){
    for(long long v = 0; v < G[i].size(); v++){
        if(p == G[i][v]){
            continue;
        }
        counter[G[i][v]] += counter[i];
        dfs(G[i][v], i);
    }
    return;
}
int main(){
    long long n ,q;
    cin >> n >> q;

    vector<vector<long long> > children(n);
    
    for(long long i = 0; i < n-1; i++){
        long long a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        
        children[a].push_back(b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    
    for(long long i = 0; i < q; i++){
        long long p, x;
        cin >> p >> x;
        p -= 1;
        counter[p] += x;

    }

    /*for(long long i = 0; i < n; i++){
        for(long long j = 0; j < children[i].size(); j++){
            counter[children[i][j]] += counter[i];
        }
    }*/

    dfs(0, -1);

    for(long long i = 0; i < n; i++){
        printf("%lld ", counter[i]);
    }
    printf("\n");

    return 0;
}

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

int main() {
  int n;
  cin >> n;
  ll a[100010][3]={};
  ll dp[100010][3]={};
  for(int i = 0; i < n; i++) for(int j = 0; j < 3; j++) cin >> a[i][j];

  for(int i = 0; i < n; i++){
    for(int j = 0; j < 3; j++){
      for(int k = 0; k < 3; k++){
        if(j == k) continue;
        dp[i+1][k] = max(dp[i+1][k],dp[i][j] + a[i][k]);
      }
    }
  }
  ll ans = 0;
  for(int i = 0; i < 3; i++) ans = max(ans, dp[n][i]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>

int main() {
    int n, b, f, r, v;
    int i, j, k;
    int nums[4][3][10] = {{{}}};

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d", &b, &f, &r, &v);
        nums[b-1][f-1][r-1] += v;
    }

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 3; j++) {
            for (k = 0; k < 10; k++) {
                printf(" %d", nums[i][j][k]);
            }
            printf("\n");
        }
        if (i < 3) printf("####################\n");
    }

    return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                                                       \
    for(long long hoge = 0; (hoge) < (n); ++(hoge))                            \
    cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long cnt[112345];
    fill(cnt, cnt + 112345, 0);
    long long sum = 0;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        int A;
        cin >> A;
        cnt[A]++;
        sum += A;
    }
    int Q;
    cin >> Q;
    while(Q--) {
        long long B, C;
        cin >> B >> C;
        sum += (C - B) * cnt[B];
        cnt[C] += cnt[B];
        cnt[B] = 0;
        cout << sum << endl;
    }
    return 0;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}

typedef long long ll;
typedef pair<ll, ll> P;

int N;
char mp[310][310];
char tmp[310][310];
bool check(int k)
{
  REP(i, N) {
    REP(j, N) {
      tmp[i][j] = mp[i][(j + k) % N];
    }
  }

  REP(i, N) {
    REP(j, N) {
      if (tmp[i][j] != tmp[j][i]) return false;
    }
  }
  return true;
}

int main()
{
  cin >> N;
  REP(i, N) REP(j, N) cin >> mp[i][j];
  int ans = 0;
  REP(i, N) {
    if (check(i)) ans += N;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

class t_sort{
public:
	int n;
	vector<int> ans, deg;
	vector<vector<int> > G;
	void init(int N){
		n = N;
		deg.resize(n);G.resize(n);
	}
	void add_edge(int from, int to){	//DAG
		G[from].pb(to);deg[to]++;
	}
	void sort(){
		stack<int> st;
		rep(i,n)if(deg[i] == 0)st.push(i);
		while(!st.empty()){
			int v = st.top();st.pop();ans.pb(v);
			rep(i,G[v].size())if(--deg[G[v][i]] == 0)st.push(G[v][i]);
		}
	}
};

map<P, int> mp;
signed main(){
	int n,m;
	scanf("%lld%lld", &n, &m);
	t_sort t;
	t.init(n);
	rep(i,m){
		int x, y;
		scanf("%lld%lld", &x, &y);x--;y--;
		t.add_edge(x, y);
		mp[P(x, y)] = 1;
	}
	
	t.sort();
	vector<int> ans = t.ans;
	rep(i,n)printf("%lld\n", ans[i]+1);
	int res = 1;
	rep(i,n-1){
		if(mp[P(ans[i], ans[i+1])] == 0)res = 0;
	}
	printf("%lld\n", res == 1 ? 0 : 1);
	return 0;
}







Measured memory_bytes: 11040
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Aoj_Learning2
{
    class Program
    {
        static void Main(string[] args)
        {
            Aoj_Learning15();
        }

        static long getChar(char c)
        {
            if (c == 'A') return 1;
            else if (c == 'C') return 2;
            else if (c == 'G') return 3;
            else if (c == 'T') return 4;
            else return 0;
        }

        static long getKey(string s)
        {
            long sum = 0, p = 1;
            for (int i = 0; i < s.Length; i++)
            {
                sum += p * (getChar(s[i]));
                p *= 5;
            }
            return sum;
        }

        private static void Aoj_Learning15()
        {
            string[] strCommand = new string[2];
            string[] strDictionary = new string[250000000];
            int n;          // 命令数
            //int count = 0;  // 文字列登録数

            // 命令数取得
            n = int.Parse(Console.ReadLine());

            // 命令を取得して辞書への登録or検索を実行する
            for(int i = 0; i < n; i++)
            {
                strCommand = Console.ReadLine().Split(' ');
                if('i' == strCommand[0][0])
                {
                    strDictionary[getKey(strCommand[1])] = "yes";
                    //strDictionary[count] = strCommand[1];
                    //count++;
                }
                else
                {
                    if("yes" == strDictionary[getKey(strCommand[1])])
                    {
                        Console.WriteLine("yes");
                    }
                    else
                    {
                        Console.WriteLine("no");
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 97084
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 100000000
#define INFLL 100000000000
#define MOD 1000000007
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};

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

int main () {
  cin >> r;
  cout << r * r << "\n";
}

Measured memory_bytes: 256
n = int(input())
slist = [sorted(list(input())) for _ in range(n)]

slist.sort()
slist += ['x']
a = slist[0]
ans = 0
count = 1
for s in slist[1:]:
  if a == s:
    count += 1
  else:
    if count > 1:
      ans += int(count*(count-1)/2)
    count = 1
    a = s
print(ans)

Measured memory_bytes: 25028
#include<bits/stdc++.h>
#define fios ios_base::sync_with_stdio(false); cin.tie(0);
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
#define pf(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define ll long long
#define nl "\n"
using namespace std;


int main()
{
    ll a,b;

    cin>>a>>b;

    ll lcm=(a*b)/__gcd(a,b);

    cout<<lcm<<nl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

const lld N = 200043;
const lld MOD = 1000000007;

lld add(lld x, lld y)
{
    x =((x%MOD)+(y%MOD))%MOD;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

lld mul(lld x, lld y)
{
    return ((x%MOD)*(y%MOD))% MOD;
}

lld binpow(lld x, lld y)
{
    lld z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

lld inv(lld x)
{
    return binpow(x, MOD - 2);
}

lld divide(lld x, lld y)
{
    return mul(x, inv(y));
}

// Combinations

/*
lld fact[N];

void precalc()
{
    fact[0] = 1;
    for(lld i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

lld C(lld n, lld k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}
*/
vector<pair<lld,lld>>v[5005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t,i,j;
    //cin>>t;
    t=1;
    while(t--)
    {
        lld n,k;
        cin>>n>>k;
        lld ar[n+1];
        lld br[n+1];
        for(i=1;i<=n;i++)
            cin>>ar[i];
        for(i=1;i<=n;i++)
            cin>>br[i];
        lld ans=LLONG_MIN;
        lld b;
        for(i=1;i<=n;i++)
        {
            lld visited[n+1]={0};
            lld a=i;
            b=k;
            lld ctr=0;
            lld c=0;
            lld gtr=0;
            lld d=0;
            while(!visited[a] && b)
            {
                visited[a]=1;
                a=ar[a];
                ctr+=br[a];
                b--;
                c++;
                ans=max(ans,ctr);
            }
            memset(visited,0,sizeof(visited));
            lld x=max(0ll,(b-c)/c);
            ctr+=x*(ctr);
            b=b-x*c;
            a=i;
            ans=max(ans,ctr);
            while(b--)
            {a=ar[a];
                ctr+=br[a];
                ans=max(ans,ctr);
            }

        }
        cout<<ans<<endl;

    }
}





Measured memory_bytes: 3868
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n);
    Cins(int, n, a);

    vc<int> ans(n+1);
    
    for(int i = n; i > 0; i --){
        int c = a[i-1];
        for(int j = 2*i; j <= n; j += i){
            c += ans[j];
        }
        ans[i] = c % 2;
    }
    int c = 0;
    For(i, n) c += ans[i+1];
    Cout(c);
    For(i, n) if(ans[i+1]) cout << i+1 << " ";
    cout << endl;
}





Measured memory_bytes: 2432