akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

bool issmall(char c) {
  if (c >= 'a' && c <= 'z') return true;
  else return false;
}

string S;
int main() {
  while (cin >> S) {
	string sub = "";
	for (int i = 2; i + 1 < S.size(); ++i) sub += S[i];

	bool ok = true;
	int numA = 0, numC = 0;
	for (int i = 0; i < S.size(); ++i) {
	  if (S[i] == 'A') ++numA;
	  else if (S[i] == 'C') ++numC;
	  else if (!issmall(S[i])) ok = false;
	}
	if (numA != 1) ok = false;
	if (numC != 1) ok = false;

	numC = 0;
	for (int i = 0; i < sub.size(); ++i) if (sub[i] == 'C') ++numC;
	if (numC != 1) ok = false;

	if (ok) puts("AC");
	else puts("WA");
  }
}



























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


int main(){

    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    
    vector<int> a(n);
    
    int minv = 101;
    int maxv = -101;
    
    rep(i,n) {
        cin >> a[i];
        minv = min(minv,a[i]);
        maxv = max(maxv,a[i]);
    }
    
    int ans = 1e9;
    for(int i = minv; i <= maxv; i++){
        int sum = 0;
        for(int j = 0; j < n; j++){
            sum += (a[j] - i) * (a[j] - i);
        }
        ans = min(ans,sum);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#1203から
import sys
N, M = map(int, input().split())
if N >= M:
    print(0)
    sys.exit()
li = list(map(int, input().split()))
li.sort()
diff_list = []
for i in range(M - 1):
    diff_list.append(li[i + 1] - li[i])

diff_list.sort(reverse=True)
ans = sum(diff_list)
for i in range(N - 1):
    ans -= diff_list[i]

print(ans)


Measured memory_bytes: 13968
x1, y1, x2, y2 = map(int, input().split())
x_diff = x2 - x1
y_diff = y2 - y1

x3 = x2 - y_diff
y3 = y2 + x_diff
x4 = x3 - x_diff
y4 = y3 - y_diff

print(x3, y3, x4, y4)

Measured memory_bytes: 2940
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')


def is_prime(n):
    if n == 1: return False

    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False

    return True


def main():
    Q = INT()
    LR = []

    lmin = INF
    rmax = 0
    for i in range(Q):
        l, r = MAP()
        lmin = l if l < lmin else lmin
        rmax = r if r > rmax else rmax
        LR.append([l, r])

    L = [0] * ((rmax - lmin)//2 + 2)
    for i, n in enumerate(range(lmin, rmax+2, 2)):
        L[i+1] = L[i] + (is_prime(n) and is_prime((n+1)//2))

    for q in range(Q):
        print(L[(LR[q][1] - lmin)//2+1] - L[(LR[q][0] - lmin)//2])


if __name__ == '__main__':
    main()

Measured memory_bytes: 61148
import java.util.*;

public class Main { //クラス名はMain
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
      	int a1=sc.nextInt();
      	int a2=sc.nextInt();
      	int a3=sc.nextInt();
      	String o;
      	if(a1+a2+a3>=22)o="bust";
      	else o="win";
     	 System.out.println(o);
    }
}

Measured memory_bytes: 23636
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;


int main() {
    int N; cin >> N;
    string S; cin >> S;
    int K; cin >> K;
    char c = S[K-1];
    for (int i = 0; i < N; ++i) {
        if (S[i] != c) cout << '*';
        else cout << S[i];
    }
    cout << endl;
}


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

int main() {
    int A, B, C, X;
    cin >> A >> B >> C >> X;

    int ans = 0;
    for (int i = 0; i <= A; i++) {
        for (int j = 0; j <= B; j++) {
            for (int k = 0; k <= C; k++) {
                int sum = 500*i + 100*j + 50*k;
                if (sum == X) ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}


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

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

	string ans = "APPROVED";
	for( int i = 0; i < N; i++ ) {
		if( A[i] % 2 == 0 ) {
			if( A[i] % 3 && A[i] % 5 ) {
				ans = "DENIED";
			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>

#include <map>
#include <string>

#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cinttypes>


using namespace std;

int solve(int k, string n)
{
	int ans = 0;

	if (k == 1)
	{
		ans += n[0] - '0';
		ans += 9 * (n.size() - 1);
	}
	else if (k == 2)
	{
		ans += (n[0] - '0' - 1) * (n.size() - 1) * 9;

		int i, j;

		for (i = 1; i < n.size(); ++i)
		{
			j = n[i] - '0';

			if (j != 0)
				break;
		}

		if (i < n.size())
		{
			ans += j;

			if (i + 1 < n.size())
			{
				ans += (n.size() - i - 1) * 9;
			}
		}

		ans += (n.size() - 1) * (n.size() - 2) / 2 * 81;
	}
	else
	{
		ans += (n[0] - '0' - 1) * (n.size() - 1) * (n.size() - 2) / 2 * 81;
		ans += (n.size() - 1) * (n.size() - 2)* (n.size() - 3) / 6 * 729;

		int i, j;

		for (i = 1; i < n.size(); ++i)
		{
			j = n[i] - '0';

			if (j != 0)
				break;
		}

		ans += solve(2, n.substr(i));
	}

	return ans;
}

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

	int k;
	cin >> k;

	cout << solve(k,n) << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll x, y;
  cin >> x >> y;
  
  if (x % y == 0)
    cout << -1 << endl;
  else
    cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, X, M = nn()

dic = dict()

ans = 0
cyc = 0
A = X
for i in range(N):
    if i != 0 and A in dic:
        cyc = i - dic[A][0]
        cyci = dic[A][0]
        r = ans - dic[A][1]
        t = dic[A][1]
        break

    dic[A] = (i, ans)
    ans += A
    A = A**2 % M

if cyc == 0:
    print(ans)
    exit(0)

#print(N//cyc)
ans = t + r * ((N-cyci)//cyc)

for i in range((N-cyci) % cyc):
    ans += A
    A = A**2 % M

print(ans)

Measured memory_bytes: 84092
#include<stdio.h>
#include<stdbool.h>
#define N 8
#define FREE -1
#define NOT_FREE 1

int a;
int row[N];
int col[N];
int dpos[2*N-1];
int dneg[2*N-1];
bool x[N][N];

void printboard(){
  int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(x[i][j]){
	if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j)printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void putqueen(int i){
  int j;
  if(i==N){
    printboard();
    return;
  }
  for(j=0;j<N;j++){
    if(NOT_FREE==col[j]||NOT_FREE==dpos[i+j]||NOT_FREE==dneg[i-j+N-1])
      continue;
    row[i]=j;
    col[j]=dpos[i+j]=dneg[i-j+N-1]=NOT_FREE;
    putqueen(i+1);
    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=FREE;
  }
}


int main(){
  int i,j,k,r,c;
  for(i=0;i<N;i++)
    row[i]=col[i]=FREE;
  for(i=0;i<2*N-1;i++)
    dpos[i]=dneg[i]=FREE;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      x[i][j]=false;
    }
  }
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    x[r][c]=true;
  }
  putqueen(0);

  return 0;
}



Measured memory_bytes: 2108
using System;
class c
{
    static void Main()
    {
        var nk = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        long n = nk[0], k = nk[1];
        long MOD = (long)1e9 + 7;
        var pre = nCkPre(2000, MOD);
        for (int i = 1; i <= k; i++)
        {
            long ans = nCk(n - k + 1, i, pre, MOD) % MOD;
            Console.WriteLine(((nCk(k - 1, i - 1, pre, MOD) % MOD) * ans) % MOD);
        }
    }
    static long nCk(long n, long k, long[][] pre, long MOD)
    {
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        if (k == 0 || n == k) return 1;
        return pre[0][n] * (pre[2][k] * pre[2][n - k] % MOD) % MOD;
    }
    static long[][] nCkPre(long MaxN, long MOD)
    {
        var ret = new long[3][];
        for (int i = 0; i < 3; i++) ret[i] = new long[MaxN + 1];
        ret[0][0] = ret[0][1] = 1;
        ret[1][0] = ret[1][1] = 1;
        ret[2][1] = 1;
        for (int i = 2; i < MaxN; i++)
        {
            ret[0][i] = ret[0][i - 1] * i % MOD;
            ret[1][i] = MOD - ret[1][MOD % i] * (MOD / i) % MOD;
            ret[2][i] = ret[2][i - 1] * ret[1][i] % MOD;
        }
        return ret;
    }
}

Measured memory_bytes: 13340
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e6 + 555;
const int MOD = 1e9 + 7;
ll xpow(ll a, ll b) {
    ll ret = 1;
    a %= MOD;
    assert(b >= 0);
    while (b) {
        if (b & 1)
            ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    cout << fixed;
    static ll inv[maxn + 555], invp[maxn + 555], p[maxn + 555];
    inv[1] = 1;
    for (int i = 2; i <= maxn; i++)
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    p[0] = 1;
    for (int i = 1; i <= maxn; i++)
        p[i] = p[i - 1] * i % MOD;
    invp[0] = 1;
    for (int i = 1; i <= maxn; i++)
        invp[i] = invp[i - 1] * inv[i] % MOD;
    auto C = [&](int a, int b) -> ll {
        if (a < b)
            return 0;
        else
            return p[a] * invp[b] % MOD * invp[a - b] % MOD;
    };
    int n;
    string s;
    cin >> n >> s;
    ll ans = 0;
    int tot = n + (int)s.size();
    for (int i = (int)s.size(); i <= tot; i++) {
        //枚举放i个a，剩下地方放b..z
        (ans += C(tot, i) * xpow(25, tot - i)) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 51140
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    string s;
    cin >> s;
    cout << (s <= "2019/04/30" ? "Heisei" : "TBD") << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(){
  int n;cin>>n;
  int h[n];
  for(int i = 0; n > i; i++)cin>>h[i];
  int cansee = 1;
  int canshe = h[0];
  for(int i = 1; n > i; i++){
    if(canshe <= h[i]){
      cansee++;
      canshe = h[i];
    }
  }
  cout << cansee << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

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

a.sort()


temp = 0
double = 0

for i in range(n):
    if temp != a[i]:
        temp = a[i]
    else:
        double += 1

if (n - double) % 2 == 0:
    print(n-double-1)
else:
    print(n-double)


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

#define fi first
#define se second

typedef long long LL;

set<pair<LL, int> >sab, sba, sac, sca, sbc, scb;
set<pair<LL, int> >::iterator i, j, k;
LL ans = 0, anss;
LL a[100010][4];
LL f[4];

void fuck_pusha(int i) {
	ans += a[i][1];
	sab.insert({a[i][1]-a[i][2], i});
	sac.insert({a[i][1]-a[i][3], i});
}

void fuck_pushb(int i) {
	ans += a[i][2];
	sba.insert({a[i][2]-a[i][1], i});
	sbc.insert({a[i][2]-a[i][3], i});
}
void fuck_pushc(int i) {
	ans += a[i][3];
	sca.insert({a[i][3]-a[i][1], i});
	scb.insert({a[i][3]-a[i][2], i});
}

void fuck_popa(int i) {
	ans -= a[i][1];
	sab.erase({a[i][1]-a[i][2], i});
	sac.erase({a[i][1]-a[i][3], i});
}
void fuck_popb(int i) {
	ans -= a[i][2];
	sba.erase({a[i][2]-a[i][1], i});
	sbc.erase({a[i][2]-a[i][3], i});
}
void fuck_popc(int i) {
	ans -= a[i][3];
	sca.erase({a[i][3]-a[i][1], i});
	scb.erase({a[i][3]-a[i][2], i});
}
int main() {
	for (int i=1; i<=3; ++i) scanf("%lld", &f[i]);

	int n = f[1] + f[2] + f[3];
	
	int na = 0, nb = 0, nc = 0;
	for (int i=1; i<=n; ++i) {
		scanf("%lld%lld%lld", &a[i][1], &a[i][2], &a[i][3]);
		if (na < f[1]) {
			fuck_pusha(i);
			na++;
		}
		else if (nb < f[2]) {
			fuck_pushb(i);
			nb++;
		}
		else if (nc < f[3]) {
			fuck_pushc(i);
			nc++;
		}
	}

	anss = ans;

	while (1) {
		i = sab.begin();
		j = sba.begin();

		bool flag = 0;

		if (i->fi + j->fi < 0) {
			flag = 1;
			int xi = i->se;
			int yi = j->se;
			fuck_popa(xi); fuck_popb(yi);
			fuck_pusha(yi); fuck_pushb(xi);
			anss = max(ans, anss);
		}

		i = sac.begin();
		j = sca.begin();

		if (i->fi + j->fi < 0) {
			flag = 1;
			int x = i->se;
			int y = j->se;
			fuck_popa(x); fuck_popc(y);
			fuck_pusha(y); fuck_pushc(x);
			anss = max(ans, anss);
		}

		i = sbc.begin();
		j = scb.begin();

		if (i->fi + j->fi < 0) {
			flag = 1;
			int x = i->se;
			int y = j->se;
			fuck_popb(x); fuck_popc(y);
			fuck_pushb(y); fuck_pushc(x);
			anss = max(anss, ans);
		}

		i = sab.begin();
		j = sbc.begin();
		k = sca.begin();
		if (i->fi + j->fi + k->fi < 0) {
			flag = 1;
			int xi = i->se;
			int yi = j->se;
			int zi = k->se;
			fuck_popa(xi); fuck_popb(yi); fuck_popc(zi);
			fuck_pusha(zi); fuck_pushb(xi); fuck_pushc(yi);
			anss = max(ans, anss);
		}

		i = sac.begin();
		j = sba.begin();
		k = scb.begin();
		if (i->fi + j->fi + k->fi < 0)
		{
			flag = 1;
			int xi = i->se;
			int yi = j->se;
			int zi = k->se;
			fuck_popa(xi); fuck_popb(yi); fuck_popc(zi);
			fuck_pusha(yi); fuck_pushb(zi); fuck_pushc(xi);
			anss = max(ans, anss);
		}

		if (!flag) break;
	}

	printf("%lld\n", anss);

	return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

struct edge {int to, cost;};
typedef pair<int, int> P; // firstは最短距離, secondは頂点の番号

const int INF=INT_MAX/2;
const int MAX_V=101010;
int V,E;
vector<edge> G[MAX_V];
int d[MAX_V];
int pre[MAX_V];

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d, d+V, INF);
  fill(pre,pre+V,-1);
  d[s]=0;
  que.push(P(0, s));

  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second; // 頂点の番号
    if (d[v] < p.first) continue;
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        pre[e.to]=v;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

int main(){
  int K; cin>>K;
  V=K+1,E=K+(K-1);
  for(int i=1;i<K;i++){
    G[i].push_back({(i+1)%K,1});
    G[i].push_back({(i*10)%K,0});
  }
  dijkstra(1);
  cout<<d[0]+1<<endl;
  return 0;
}


Measured memory_bytes: 7164
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

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

/*-------------------------------------------*/

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

    int n;
    cin >> n;
    vector<pair<int, int>> v;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, i});
        v.push_back({b, i + n});
    }
    sort(ALL(v));

    bool a = true, b = true, c[n] = {}, d = false;
    ll sum = 0;
    rep(i, n) {
        sum += v[i].first;
        (v[i].second < n ? a : b) = false;
        (c[v[i].second % n] ? d : c[v[i].second % n]) = true;
    }
    if(d || a || b)
        cout << sum << endl;
    else if(abs(v[n - 1].second - v[n].second) != n)
        cout << sum - v[n - 1].first + v[n].first << endl;
    else
        cout << min(sum - v[n - 1].first + v[n + 1].first,
                    sum - v[n - 2].first + v[n].first)
             << endl;

    return 0;
}

Measured memory_bytes: 2420
object Main extends App{
    val Array(a,b,c,k) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
    if(1 <= k && k <= a)          println(k)
    if(a < k && k <= a+b)        println(a)
    if(a+b < k && k <= a+b+c)    println(a-(k-(a+b)))
    
}


Measured memory_bytes: 54652
#!/usr/bin/env python3
def solve(a):
    for i in range(len(a)-1):
        if a[i+1] - a[i] <= -2:
            return "No"
        elif a[i+1] - a[i] == -1:
            a[i+1] += 1
    return "Yes"

def main():
    N = int(input())
    A = [0] + list(map(int,input().split()))
    print(solve(A))

if __name__ == '__main__':
    main()

Measured memory_bytes: 14396
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=998244353;

#define MAX_N 1000010
ll inv[MAX_N+10],fac[MAX_N+10],ifac[MAX_N+10];

void setComb(){
  inv[0]=1;inv[1]=1;fac[1]=1;ifac[1]=1;fac[0]=1;ifac[0]=1;
  for(int i=2;i<MAX_N;i++){
    inv[i]=(-MOD/i)*inv[MOD%i]%MOD;
    fac[i]=fac[i-1]*i%MOD;
    ifac[i]=ifac[i-1]*inv[i]%MOD;

    inv[i]=(inv[i]+MOD)%MOD;
    fac[i]=(fac[i]+MOD)%MOD;
    ifac[i]=(ifac[i]+MOD)%MOD;
  }
  return;
}

ll comb(ll n,ll k){
  if(n<k||n<0||k<0) return 0;
  else return ((fac[n]*ifac[k]%MOD*ifac[n-k]%MOD+MOD)%MOD);
}

ll hcomb(ll n,ll r){
  if(n==0&&r==0) return 1;
  else if(n<0||r<0) return 0;
  else return comb(n+r-1,r-1);
}

int N;
vector<ll> A;

ll sum[1000010];

#define MAX 1000000
ll coef[1000010];

void add(ll &a,ll b){
    a=(a+b)%MOD;
}

void mul(ll &a,ll b){
    a=a*b%MOD;
}

int main(){
  cin>>N;
  A.resize(N);
  rep(i,N) cin>>A[i];

  setComb();

  for(int i=1;i<=MAX;i++) coef[i]=inv[i];
  for(int i=1;i<=MAX;i++){
      for(int j=2;i*j<=MAX;j++){
          add(coef[i*j],MOD-coef[i]);
      }
  }

  ll ans=0;
  for(int i=0;i<N;i++){
      add(sum[A[i]],A[i]);
      add(ans,MOD-A[i]);
  }

  for(int i=1;i<=MAX;i++){
      ll res=sum[i];
      for(int j=2;i*j<=MAX;j++){
          add(res,sum[i*j]);
      }
      mul(res,res);
      mul(res,coef[i]);

      add(ans,res);
  }

  mul(ans,inv[2]);
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 40832
word = input()
dict_word = {}
for i in range(len(word)):
  try:
    count = dict_word[word[i]]
    dict_word[word[i]] += 1
  except:
    dict_word[word[i]] = 1


if len(dict_word) == 2 and list(dict_word.values()) == [2, 2]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

s=S()
l=[s[0]]
ans=0
for i in range(1,len(s)):
    if len(l)==0:
        l.append(s[i])
        continue
    if l[-1]!=s[i]:
        ans+=2
        l.pop()
    else:
        l.append(s[i])
print(ans)


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

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

public class Main{

	Scanner sc=new Scanner(System.in);

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

	void run(){
		for(;;){
			Dice dice=new Dice(1, 5, 4, 3, 2, 6);
			int n=sc.nextInt();
			if(n==0){
				break;
			}
			int sum=dice.is[0];
			for(int i=0; i<n; i++){
				String s=sc.next();
				switch(s.charAt(0)){
				case 'N':
					dice.rollX();
					break;
				case 'S':
					dice.rollX();
					dice.rollX();
					dice.rollX();
					break;
				case 'E':
					dice.rollY();
					break;
				case 'W':
					dice.rollY();
					dice.rollY();
					dice.rollY();
					break;
				case 'R':
					dice.rollZ();
					break;
				case 'L':
					dice.rollZ();
					dice.rollZ();
					dice.rollZ();
					break;
				}
				sum+=dice.is[0];
			}
			println(sum+"");
		}
	}

	class Dice{
		// top, front, left, right, back, bottom
		int[] is=new int[6];

		Dice(int... is){
			this.is=is;
		}

		void rollX(){
			roll(0, 1, 5, 4);
		}

		void rollY(){
			roll(0, 3, 5, 2);
		}

		void rollZ(){
			roll(1, 3, 4, 2);
		}

		void roll(int a, int b, int c, int d){
			int t=is[d];
			is[d]=is[c];
			is[c]=is[b];
			is[b]=is[a];
			is[a]=t;
		}

		Dice[] rollAll(){
			Dice[] dices=new Dice[24];
			for(int i=0; i<6; i++){
				for(int j=0; j<4; j++){
					dices[i*4+j]=new Dice(is.clone());
					rollZ();
				}
				if((i&1)>0)
					rollX();
				else
					rollY();
			}
			return dices;
		}
	}

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

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

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

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

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

int main() {
    int r, d, x;
    cin >> r >> d >> x;
    rep(i,10) {
      x = r*x - d;
      cout << x << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{
    int n;
    cin >> n;
    put((int)pow(2, (int)log2(n)));
    return 0;
}

Measured memory_bytes: 4056
#include<iostream>
using namespace std;
int main()
{
string s,t;
int l1,l2,i,c=0;
cin>>s;
cin>>t;
l1=s.length();
l2=t.length();
for(i=0;i<l1;i++)
{
if(s[i]==t[i])
{
c++;
}
}
if(c==l1)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;

int pcnt[100001];
bool canRoot[100001], isLeaf[100001];
vector<int> edge[100001], invedge[100001];
int parent[100001];

int countps(int i){
    if(pcnt[i]>=0) return pcnt[i];
    if(canRoot[i]){
        parent[i]=0;
        pcnt[i]=0;
        return 0;
    }
    int cnt=-1;
    int pind=i;
    for(auto x : invedge[i]){
        if(cnt<countps(x)+1){
            cnt=countps(x)+1;
            pind=x;
        }
    }
    parent[i]=pind;
    pcnt[i]=cnt;
    return cnt;
}


int main(){
    int N, M;
    cin >> N >> M;
    for(int i=1;i<=N;i++) canRoot[i]=isLeaf[i]=true;
    for(int i=0;i<N-1+M;i++){
        int A, B;
        cin >> A >> B;
        edge[A].push_back(B);
        invedge[B].push_back(A);
        canRoot[B]=false;
        isLeaf[A]=false;
    }
    int root;
    for(int i=1;i<=N;i++){
        if(canRoot[i]){
            root=i;
            break;
        }
    }

    for(int i=1;i<=N;i++) parent[i]=i;
    for(int i=1;i<=N;i++) pcnt[i]=-1;
    for(int i=1;i<=N;i++){
        if(isLeaf[i]){
            countps(i);
        }
    }
    
    for(int i=1;i<=N;i++){
        assert(parent[i]!=i);
        cout << parent[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 18944
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
import pdb

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    t = S()
    cands = []
    ans = 'z' * 50
    for st_ix in range(len(s)):
        cur_j = 0
        copy_s_list = list(s)
        is_cand = False 
        while cur_j < len(t) and st_ix + len(t) - 1< len(s):
            if s[st_ix + cur_j] == t[cur_j] or s[st_ix + cur_j] == '?':
                copy_s_list[st_ix + cur_j] = t[cur_j]
                cur_j += 1
                if cur_j == len(t):
                    is_cand = True
            else:
                break

        if is_cand: 
            for ix in range(len(copy_s_list)):
                if copy_s_list[ix] == '?':
                    copy_s_list[ix] = 'a'
            cands.append(''.join(copy_s_list))
    if cands == []:
        print("UNRESTORABLE")
    else:
        print(min(cands))

            
main()



Measured memory_bytes: 7740
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef pair<int,int> pint;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=2020000000;

int N;
int a[110];
int c[10];

int main() {
	cin>>N;
	Rep(i,N) cin>>a[i];
	Rep(i,10) c[i]=i;
	sort(a,a+N);
	if(a[0]>=3200){
		cout<<1<<" "<<N<<endl;
	}
	else{
		int min=0;
		int max=0;
		Rep(i,N){
			if(a[i]>=3200){
				max++;
			}
			else{
				Rep(j,10){
					if(a[i]/400==c[j]){
						max++;
						min++;
						c[j]=-1;
					}
				}
			}
		}
		cout<<min<<" "<<max<<endl;
	}




	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int a, b, c;
	int counter;
	int eaten = 0;
	
	scanf("%d %d %d", &a, &b, &c);
	
	if(a + b >= c) counter = b + c;
	else counter = a + b * 2 + 1;
		
	printf("%d\n", counter);
	return 0;
}

Measured memory_bytes: 128
def main():
    X = int(input())
    maxi = 1
    if X <= 2:
        print(1)
        return
    for b in range(2, X):
        for p in range(2, X):
            if b**p > X:
                break
            else:
                maxi = max(maxi, b**p)
    print(maxi)
main()

Measured memory_bytes: 62572
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ll a[200100], b[200100];


int main()
{
    int n;  cin >> n;
    for(int i = 1;i<=n;i++)  cin >> a[i],b[a[i]]++;
    ll Ans = 0;
    for(int i = 1;i<=n;i++)  Ans+=(b[i] * (b[i] - 1))/2;
    for(int i = 1;i<=n;i++){
        Ans-=(b[a[i]] * (b[a[i]] - 1))/2;
        b[a[i]]--;
        Ans+=(b[a[i]] * (b[a[i]] - 1))/2;
        cout << Ans << '\n';
        Ans-=(b[a[i]] * (b[a[i]] - 1))/2;
        b[a[i]]++;
        Ans+=(b[a[i]] * (b[a[i]] - 1))/2;
    }
    return 0;
}


Measured memory_bytes: 4736
N, *L = map(int, open(0).read().split())
MOD = 10**9+7
D = [L[i+1]-L[i] for i in range(N-1)]
f = [1]
for i in range(1,N+1):
  f.append(f[-1]*i%MOD)
C = [1]
for i in range(1,N-1):
  C.append((C[-1]+pow(i+1,MOD-2,MOD))%MOD)
ans = sum(d*c for d,c in zip(D,C))%MOD
print(ans*f[N-1]%MOD)

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



 
int main(){
    ll N; cin >> N;
    vector<ll> C(N-1), S(N-1), F(N);
    for(int i = 0; i < N-1; i++){
        cin >> C[i] >> S[i] >> F[i];
    }
    for(int i = 0; i < N; i++){
        ll t=0;
        for(int j = i; j < N-1; j++){
            if(t < S[j]) t=S[j];
            else {if(t%F[j] != 0) t += F[j]-t%F[j];}
            //if(j == i) t+= S[j];
            t+=C[j];
        }
        cout << t << endl;
    }
}



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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

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

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

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

  string s; cin >> s;
  int k; cin >> k;
  string revs = s;
  reverse(ALL(revs));
  int n = SZ(s);
  vector<vvi> dp(n+1, vvi(n+1, vi(k+1, 0)));
  REP(i, n) {
    REP(j, n) {
      REP(l, k+1) {
        if(s[i] == revs[j]) {
          chmax(dp[i+1][j+1][l], dp[i][j][l] + 1);
        } else {
          chmax(dp[i+1][j+1][l], max(dp[i+1][j][l], dp[i][j+1][l]));
          if(l != k) chmax(dp[i+1][j+1][l+1], dp[i][j][l] + 1);
        }

        if(i<n && n-1-j >= 0 && s[i] == s[n-1-j]) {
          chmax(dp[i+1][j+1][k], dp[i][j][k] + 1);
        }
      }
    }
  }
/*
  REP(l, k+1) {
    REP(i, n) {
      REP(j, n) {
        cout << dp[i][j][l] << " ";
      }
      cout << endl;
    }
    cout << endl;
  }
  */

  int ans = 0;
  REP(l, k+1) {
    REP(i, n+1) chmax(ans, dp[i][n-i][l] * 2);
    REP(i, n) chmax(ans, dp[i][n-i-1][l] * 2 + 1);
  }
  cout << ans << endl;

}
























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

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

#define max_n 100

int N,K;

int main() {

	cin >> N >> K;

	if (((N - 1)*(N - 2)) / 2 < K) { cout << -1 << endl; return 0; }

	vector<int> V[max_n];
	rep(i, N-1)V[0].push_back(i+1);

	int M = N - 1;
	int k = ((N - 1)*(N - 2)) / 2;

	for(int i=1;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(k>K&&i!=j)
			{
				V[i].push_back(j);
				M++; k--;
			}
		}
	}
	
	cout << M << endl;

	for (int i = 0; i < N; i++) {
		for(int j=0; j< V[i].size(); j++){
			cout << i+1 << " " << V[i].at(j)+1 << endl;
		}
	}
	
	return 0;
	
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    int a, b, c, n;
    string s, t;

    cin >> n >> a >> b;

    long count = 0;
    for (int i = 1; i <= n; i++) {
        int dig = i % 10 + i / 10 % 10 + i / 100 % 10 + i / 1000 % 10 + i / 10000 % 10;
        if (dig >= a && dig <= b)count+=i;
    }

    cout <<  count;

    return 0;
}






Measured memory_bytes: 256
package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    hs := make([]int, n)
    for i := 0; i < n; i++ {
        var h int
        fmt.Scan(&h)
        hs[i] = h
    }

    //fmt.Println(n, hs)

    res := calcStep(hs)
    fmt.Println(res)
}

func calcStep(hs []int) int {
    //fmt.Println("hs: ", hs)
    var ng bool
    for i := range hs {
        if hs[i] > 0 {
            ng = true
            break
        }
    }
    if !ng {
        return 0
    }
    for i, h := range hs {
        //fmt.Println("i, h: ", i, h)
        if h == 0 {
            if i == 0 {
                return calcStep(hs[i+1:])
            } else if i == len(hs) {
                return calcStep(hs[:i])
            } else {
                return calcStep(hs[:i]) + calcStep(hs[i+1:])
            }
        }
    }
    for i := range hs {
        hs[i] -= 1
    }
    //fmt.Println("hs: ", hs)
    return calcStep(hs) + 1
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define MOD (ll)(1e9+7)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int main()
{
	int n;
	cin>>n;
	vector<ll>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	ll sum = 0;
	ll ans = 0;
	for(int i=0;i<n;i++){
		ans+=sum*a[i];
		sum+=a[i];
		sum%=MOD;
		ans%=MOD;
	}
	cout<<ans;
}


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

#define ll long long int
#define LD long double

const int N = 100010;

int inf = 1e9;
int mod = 1e9 + 7;

signed main()
{
    //freopen("IN", "r", stdin);
    //freopen("OUT", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int l, r, d; cin >> l >> r >> d;
    int cnt = 0;
    for(int i = 0; i <= r; i += d) {
        if(i >= l) cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

Measured memory_bytes: 3560
# coding: utf-8
from math import sqrt

def isPrime(n):
	if n == 2:
		return True
	elif n < 2 or n % 2 == 0:
		return False
	else:
		i = 3
		while i <= sqrt(n):
			if n % i == 0:
				return False
			i += 2
		return True

def main():
	n = input()
	print sum([1 if isPrime(x) else 0 for x in [input() for _ in xrange(n)]])

if __name__ == '__main__':
	main()

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

#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int long long
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

using namespace std ;

#define N 100010
const ll mod = 1e9 + 7;

int sum[N][26], n;
ll fac[N], inv[N];
char s[N];
ll ans = 0;

int idx(char c) {
	return c - 'a';
}
ll power(ll a, ll b) { ll ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod; b >>= 1;
	} return ans;
}
int main() {
	fac[0] = 1; inv[0] = power(fac[0], mod - 2);
	scanf("%d%s", &n, s + 1);
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < 26; ++j) sum[i][j] = sum[i - 1][j];
		sum[i][idx(s[i])]++;
		fac[i] = (ll)fac[i - 1] * i % mod;
		inv[i] = power(fac[i], mod - 2);
	}
	ll ans = 1;
	for(int i = 0; i < 26; ++i) ans = ans * (1 + sum[n][i]) % mod;
	outn((ans - 1 + mod) % mod);
}

Measured memory_bytes: 12032
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,i,k,j;
    cin >> n >> k;
    ll a[n],dp[n];
    for(i=0;i<n;i++)
    cin >> a[i];
    dp[0]=0;
    //dp[1]=abs(a[1]-a[0]);
    for(i=1;i<k;i++)
    {
        if(i>=n)
        break;
        ll m=dp[i-1]+abs(a[i]-a[i-1]);
        for(j=2;j<=i;j++)
        {
            ll x=dp[i-j]+abs(a[i]-a[i-j]);
            if(x<m)
            m=x;
        }
        dp[i]=m;
    }
    for(i=k;i<n;i++)
    {
        ll m=dp[i-1]+abs(a[i]-a[i-1]);
        for(j=2;j<=k;j++)
        {
            ll x=dp[i-j]+abs(a[i]-a[i-j]);
            if(x<m)
            m=x;
        }
        dp[i]=m;
    }
    //dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct pile{
  int p,o;
  pile(){}
  pile(int v){p=v;o=-1;}
};
pile p[300];
int h(int v){
  if(p[v].o==-1) return 1;
  return h(p[v].o)+1;
}
void tf(int v){
  if(p[v].p!=v){
    int i;
    for(i=p[v].p;~i&&p[i].o!=v;i=p[i].o);
    p[i].o=-1;
  }
  p[v].p=v;
  if(p[v].o!=-1) tf(p[v].o);
  p[v].o=-1;
}
void ta(const int a,const int b){
  //cout<<a<<"-"<<b<<endl;
  //cout<<p[a].o<<"+"<<p[b].o<<endl;
  assert(a!=b);
  if(p[b].o==-1){
    p[a].p=p[b].p;
    p[b].o=a;
    return;
  }
  ta(a,p[b].o);
}
signed main(){
  int m;
  while(cin>>m,m){
    for(int i=0;i<300;i++) p[i]=pile(i);
    int a,b;
    while(cin>>a>>b,a||b){
      //cout<<a<<":"<<b<<endl;
      a--;b--;
      if(a==b) continue;
      if(b<0){
	if(p[a].p!=a) tf(a);   
      }else{
	if(p[a].p==p[b].p){
	  if(h(a)<h(b)) continue;
	  tf(a);
	  //cout<<a<<" "<<b<<":"<<p[a].p<<" "<<p[b].p<<endl;
	  ta(a,b);
	}else{
	  tf(a);
	  //cout<<a<<" "<<b<<":"<<p[a].p<<" "<<p[b].p<<endl;
	  ta(a,b);
	}
      }
    }
    //puts("OK");
    vector<int> v;
    for(int i=0;i<m;i++){
      if(p[i].p==i){
	//cout<<i<<endl;
	//cout<<h(p[i])<<endl;
	v.push_back(h(i));
      }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<(int)v.size();i++) cout<<v[i]<<endl;
    cout<<"end"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3136
#include <stdio.h>
  
void swap (int* arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

int main (void) {
  int a[3];
  scanf("%d %d %d", &a[0], &a[1], &a[2]);
  if (a[0] > a[1]) swap(a, 0, 1);
  if (a[1] > a[2]) swap(a, 1, 2);
  if (a[0] > a[1]) swap(a, 0, 1);
  printf("%d %d %d\n", a[0], a[1], a[2]);
}


Measured memory_bytes: 2132
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]
  for j in range(f):
    if j+a[i-1]<f:
      dp[i][j+a[i-1]]=min(dp[i][j+a[i-1]],dp[i][j]+b[i-1])
  for j in range(f-1,0,-1):
    dp[i][j-1]=min(dp[i][j-1],dp[i][j])
print(dp[-1][h])


Measured memory_bytes: 161752
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int64_t N;
  cin >> N;
  int64_t memo = 10000000000000000;
  for (int i = 0; i < 5; i++) {
    int64_t memo2;
    cin >> memo2;
    memo = min(memo2, memo);
  }
  cout << 5 + (N - 1)/ memo << endl;
}

Measured memory_bytes: 3600
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
constexpr int INF = 1000000000 + 8;

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

    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];

    int ans = INF;

    // 連続するK個のろうそくに火をつけるのが最適→それを全列挙

    for (int i = 0; i < n - k + 1; i++) {
        const int l = x[i], r = x[i + k - 1];

        int now = abs(l - r) + min(abs(l), abs(r));
        ans = min(ans, now);
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
constexpr bool isDebugMode = true;
int testcase = 1;
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
#endif
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
const long long dy[] = {-1, 0, 0, 1};
const long long dx[] = {0, -1, 1, 0};
string abc = "abcdefghijklmnopqrstuvwxyz";
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for (const auto &e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void pt(){cout << endl; return;}
template<class Head> void pt(Head&& head){cout << head; pt(); return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
void dpt(){if(!isDebugMode) return; cout << endl; return;}
template<class Head> void dpt(Head&& head){if(!isDebugMode) return; cout << head; pt(); return;}
template<class Head, class... Tail> void dpt(Head&& head, Tail&&... tail){if(!isDebugMode) return; cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){if(!isDebugMode) return; rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){if(!isDebugMode) return; rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> long long recgcd(T1 a, T2 b){return a % b ? recgcd(b , a % b) : b;}
bool valid(long long H, long long W, long long h, long long w) { return 0 <= h && h < H && 0 <= w && w < W; }

void solve();

int main(){
    while(testcase--) solve();
    return 0;
}
ll counter = 0;

void dfs(vector<vector<ll>> &tree, vector<ll> &list, vector<ll> &c, ll node = 0, ll par = -1){
    for(auto& e : tree[node]){
        if(e == par) continue;
        dfs(tree, list, c, e, node);
    }
    list[node] = c[counter];
    counter++;
}

void solve(){
    ll N; cin >> N;
    vector<vector<ll>> tree(N);
    rep(i, N - 1){
        ll u, v; cin >> u >> v;
        tree[--u].push_back(--v);
        tree[v].push_back(u);
    }
    vector<ll> c(N); rep(i, N) cin >> c[i];
    sort(all(c));
    vector<ll> list(N, -1);
    dfs(tree, list, c);
    pt(accumulate(all(c), 0LL) - *max_element(all(c)));
    debug(list);
    return;
}

Measured memory_bytes: 4884
#include <bits/stdc++.h>
using namespace std;
#define repr(i,k,n) for(int i = (k); i < (n); i++)
#define rep(i,n) repr(i,0,n)
#define ALL(a) begin(a),end(a)
const int MOD = 1000000007;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
  }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r;
    cin >> r;
    cout << 3*r*r <<endl;
}

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

using namespace std;
const int N = 202020;
int n,len[N],c[26];
string s[N];
long long ans;
struct Trie {
	struct Trie_Node {
		int ch[26],ct[26];
	}node[1010101]; 
	int rt,tot=1;
	
	inline void reroot() {
		rt = 1; 
		for (int i = 0;i < 26; i++) 
			if (c[i]) 
				node[rt].ct[i]++;
	}
	inline void insert(const char& chr) {
		if (node[rt].ch[chr-'a']) 
			rt = node[rt].ch[chr-'a']; 
		else 
			rt = node[rt].ch[chr-'a'] = ++tot;
		for (int i = 0;i < 26; i++) 
			if (c[i]) 
				node[rt].ct[i]++;
	}
	inline int query(const string& s,int len) {
		rt = 1; 
		for (int i = len-1;i;--i)
			if (node[rt].ch[s[i]-'a']) 
				rt = node[rt].ch[s[i]-'a'];
			else 
				return 0;
		return node[rt].ct[s[0]-'a'];
	}
}T;
int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1;i <= n; i++)
	{
		cin >> s[i];
		len[i] = s[i].size();
		for (int j = 0;j < len[i]; j++) {
			c[s[i][j]-'a']++;
		} 
		T.reroot();
		for (int j = len[i]-1;~j; j--) {
			--c[s[i][j]-'a'];
			T.insert(s[i][j]);
		}
	}
	for (int i = 1;i <=n ; i++)
		ans += T.query(s[i],len[i]); 
	cout << ans-n << endl;
	return 0;
}

Measured memory_bytes: 213716
#include<bits/stdc++.h>
 
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"

using namespace std;

int32_t main()
{
	IOS;
	int n;
	cin>>n;
	if(n >= 30)
		cout<<"Yes";
	else
		cout<<"No";
	cout<<endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
char a[100005];
int x,y,ans;
int main()
{
    cin>>a;
    for (int i=0;i<sizeof(a);i++)
    {
    	if (x==y)
		{
		   x++;
		   if (a[i]=='p')
		     ans--;
		}
		else
		{
		    y++;
			if(a[i]=='g')
			ans++;
		}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
n=int(input())
h=list(map(int,input().split()))
s=0
t=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        s+=1
    else:
        if s>=t:
            t=s
        s=0
if s>=t:
    t=s
print(t)

Measured memory_bytes: 85500