akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
 
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)
vector<pair<int,int> > edge;
vector<int> to[100100];
map<pair<int,int>, int> ans;
bool visited[100100];
int ma;
void dfs(int v,int color){
    if(visited[v])return;
    visited[v]=true;
    ma=max(ma,(int)to[v].size());
    int p=1;
    REP(i,to[v].size()){
        int t=to[v][i];
        if(visited[t])continue;
        if(color==p)p++;
        ans[MP(v,t)]=ans[MP(t,v)]=p;
        dfs(t,p);
        p++;
    }
}
int main() {
    int n;
    int a[100100],b[100100];
    cin>>n;
    vector<int>v[n];
    REP(i,n-1){
        cin>>a[i]>>b[i];
        a[i]--;
        b[i]--;
        edge.PB(MP(a[i],b[i]));
        to[a[i]].PB(b[i]);
        to[b[i]].PB(a[i]);
    }
    ma=0;
    REP(i,n)visited[i]=false;
    dfs(0,-1);
    cout<<ma<<endl;
    REP(i,edge.size()){
        cout<<ans[edge[i]]<<endl;
    }

}


Measured memory_bytes: 23288
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

A,B = inpl()
ans = 0
for n in range(A,B+1):
	s = list(str(n))
	if s == s[::-1]:
		ans += 1

print(ans)	


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

int main(){
  int A,B,K;
  cin >> A >> B >> K;
  for(int i=A;i<=min(B,A+K-1);++i){
    cout << i << endl;
  }
  for(int i=max(B-K+1,A+K);i<=B;++i){
    cout << i << endl;
  }
}


Measured memory_bytes: 256
import sys

N, Y = map(int,input().split())

for x in range(N+1):
    if x*10000 > Y:
        break
    if Y - x*10000 > (N-x)*5000:
        continue
    for y in range(N+1-x):
        if x*10000 + y*5000 > Y:
            break
        z = N - (x + y)
        if (x*10000 + y*5000 + z*1000) == Y:
            print(x,y,z)
            sys.exit()

print(-1,-1,-1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define gpf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int n, t;
int a[110000];
int mx, ans, mn;

int main(){
	scanf("%d%d", &n, &t);
	rep(i, 1, n) scanf("%d", a + i);
	mx = 0;
	mn = 1e9;
	rep(i, 1, n){
		if (a[i] - mn == mx) ans++;
		else if (a[i] - mn > mx){
			mx = a[i] - mn;
			ans = 1;
		}
		mn = min(mn, a[i]);
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

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

    string s;
    cin >> s;
    cout << (s[2] == s[3] && s[4] == s[5] ? "Yes\n" : "No\n");

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define endl "\n"
  #define all(v) v.begin(),v.end()
#define int long long 
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<< ": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
const int mod = 1000000007;
const double PI = 3.1415926535898;

#define N 100005

const int INF = (1LL << 62) - 1;




int n,m;

vector<pair<int,int>> adj[N];
void dijkstra(vector<pair<int, int>> g[], int source)
{
    vector<int> arrival(N, INF), departure(N, INF);
    vector<int> vis(N), parent(N), ans;
    arrival[source] = 0;
    set<pair<int, int>> s;
    s.insert({0, source});
    while(!s.empty())
    {
        pair<int,int> x = *s.begin();
        int u = x.second;
        s.erase(s.begin());
        vis[u] = 1;
        departure[u] = arrival[u];
        for(auto y: g[u])
        {
              int v = y.first;
              int w = y.second;

            if(arrival[v] > departure[u] + w)
            {
                s.erase({arrival[v], v});
                arrival[v] = departure[u] + w;
                s.insert({arrival[v], v});
                parent[v] = u;
            }
        }
    }




      cout << "Yes" << endl;

      for(int i = 2; i <= n; i++)
      {
        cout << parent[i] << endl;
      }

}




int32_t main()
{



      cin >> n >> m;

      for(int i = 1; i <= m; i++)
      {
        int x,y;
        cin >> x >> y;
        adj[x].push_back(make_pair(y,1));
        adj[y].push_back(make_pair(x,1));
      }


      dijkstra(adj,1);


     







    return 0;
}



Measured memory_bytes: 24048
def main():
    K = int(input())
    A = [int(a) for a in input().split()]

    if not A[K - 1] == 2:
        print(-1)
        return

    nmin, nmax = 2, 2
    ii = list(range(K))
    ii.reverse()
    for i in ii:
        Ai = A[i]
        if Ai > nmax:
            print(-1)
            return
        if Ai < nmin and Ai * 2 > nmax:
            print(-1)
            return
        if Ai < nmin:
            if nmin % Ai == 0:
                pass
            else:
                nmin = Ai * (nmin // Ai + 1)
        else:
            nmin = Ai

        if nmax > Ai:
            # if nmax % Ai == 0:
            #     pass
            # else:
            #     pass
            nmax = Ai * (nmax // Ai + 1) - 1
        else:
            nmax = Ai * 2 - 1
        # print(Ai, nmin, nmax)
        if nmin > nmax:
            print(-1)
            return
    print(nmin, nmax)


main()

Measured memory_bytes: 14400
#include <bits/stdc++.h>
#define rep(i, n) for (ll(i) = 0; (i) < (n); (i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
int main()
{
    int n, m;
    ll x;
    cin >> n >> m >> x;
    vl c(n);
    vector<vl> a(n, vl(m));
    rep(i, n)
    {
        cin >> c[i];
        rep(j, m)
        {
            cin >> a[i][j];
        }
    }
    ll mi = 12e6;
    ll temp = 0;
    ll price = 0;
    for (int bit = 0; bit < (1 << n); ++bit)
    {
        vl s(m, 0);
        price = 0;
        for (int i = 0; i < n; ++i)
        {
            if (bit & (1 << i))
            {
                price += c[i];
                rep(j, m)
                {
                    s[j] += a[i][j];
                }
            }
        }
        temp = 0;
        rep(i, m)
        {
            if (s[i] >= x)
            {
                temp++;
            }
            else
            {
                break;
            }
        }
        if (temp == m)
        {
            mi = min(mi, price);
        }
    }
    if (mi != 12e6)
    {
        cout << mi << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
 
 
int main()
{
    int n;
    cin>>n;
    set<string>s;
    while(n--){
        string str;
        cin>>str;
        s.insert(str);
    }
    cout<<s.size()<<endl;
   return 0;
}

Measured memory_bytes: 19188
#include<stdio.h>
#include<math.h>

int main()
{
	int i, j, root, div, count=0,  n;
	scanf("%d", &n);
	for(i=1;i<=n;i+=2)
	{
		div=0;
		root=sqrt(i);
		for(j=1;j<=root;j+=2)
		{
			if(i%j==0)
				div+=2;
		}
		if(root*root==i)
			div--;
		if(div==8)
			count++;
	}
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 128
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heapify,heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,k = LI()
    g = LIR(n)
    g.sort(key = lambda x:-x[1])
    f = [0 for i in range(n+1)]
    x = 0
    ans = 0
    c = []
    for i in range(k):
        ans += g[i][1]
        if not f[g[i][0]]:x+=1
        else:c.append(g[i][1])
        f[g[i][0]] += 1
    ans += x**2
    c.sort()
    c = deque(c)
    d = ans
    for i in range(k,n):
        if not c:
            break
        if f[g[i][0]]:continue
        d += g[i][1]-c.popleft()+2*x+1
        f[g[i][0]] = 1
        x += 1
        if d > ans:
            ans = d
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 62000
#include <stdio.h>
int main(){
        int m,n,o;
        while(scanf("%d %d",&m,&n) != EOF){
        if( m < n){
                o = m;
                m = n;
                n = o;
        }
        while(1){
                if(n == 0){
                        printf("%d\n",m);
                        break;
                }
                o = m % n;
                m = n;
                n = o;
        }
        }
return 0;
}

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int n;
    cin>>n;
    map<string,int> m;
    string s;
    rep(i,n){
      cin>>s;
      m[s]++;
    }
    cout<<"AC x "<<m["AC"]<<endl;
    cout<<"WA x "<<m["WA"]<<endl;
    cout<<"TLE x "<<m["TLE"]<<endl;
    cout<<"RE x "<<m["RE"]<<endl;
    return 0;
}

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

int main() {
  int p, q, r;
  cin >> p >> q >> r;
  int max = p;
  if (max < q) max = q;
  if (max < r) max = r;
  int result = p+q+r-max;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))


max_h = [0]*n
max_h[0]=h[0]
for i in range(1,n):
  max_h[i] = max(max_h[i-1],h[i])

count=1
for i in range(1,n):
  if max_h[i-1]<=h[i]:
    count+=1
    

print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 20000005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N;
int P[105],A,B;
int cnt[3];
void Solve() {
	read(N);read(A);read(B);
	for(int i = 1 ; i <= N ; ++i) {
		read(P[i]);
		if(P[i] <= A) ++cnt[0];
		else if(P[i] <= B) ++cnt[1];
		else cnt[2]++;
	}
	out(min(min(cnt[0],cnt[1]),cnt[2]));enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
long int a,b,c,k,max,d;
  scanf("%ld %ld %ld %ld",&a,&b,&c,&k);
max=a;
  if(max<b) max=b; 
  if(max<c) max=c;
d=a+b+c-max;
max=max*pow(2,k);
printf("%ld",d+max);
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;


int main(){
	ll a,b,t;
	cin >> a >> b >> t;
	ll ans = 0;
	FOR(i,1,t+1){
		if(i%a==0)ans+=b;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    int[] v = new int[N];

    for (int i = 0; i < N; i++) {
      v[i] = sc.nextInt();
    }

    sc.close();

    Arrays.sort(v);

    double max = ((double) v[0] + (double) v[1]) / 2;

    for (int i = 2; i < N; i++) {
      max = (max + (double) v[i]) / 2;
    }

    System.out.println(max);

  }

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
    using namespace std;
    #define PAIN___ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define ll long long int
    #define fi first
    #define se second
    #define pb push_back
    #define pii pair < int , int >
    #define mp make_pair
    #define vec vector < ll >
    #define vecp vector < pii  >
    #define forl(i,q1,n,q2) for(ll i=q1;i<q2;i++)
    #define null NULL
    #define mm 1000005

    int main()
    {
        PAIN___;
        ll t;
        t=1;
        while(t--)
        {
            ll n;
            cin>>n;
            ll a[n];
            vec v;
            ll cnt=0;
            forl(i,0,n,n)
            {
                cin>>a[i];

            }
            forl(i,0,n,n-2)
            {
                v.pb(a[i]);
                v.pb(a[i+1]);
                ll ans=a[i+1];
                v.pb(a[i+2]);
                sort(v.begin(),v.end());
                if(v[1]==ans)
                {
                    cnt++;
                }
                v.clear();

            }
            cout<<cnt<<endl;


    }
    }



Measured memory_bytes: 256
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		//コマンドライン引数取得部分
		Scanner scanner = new Scanner(System.in);
		ArrayList<Integer> valList = new ArrayList<>();
		ArrayList<Integer> roundUpList = new ArrayList<>();

		for (int i = 0; i < 5; i++) {
			valList.add(scanner.nextInt());
			BigDecimal bd = new BigDecimal(valList.get(i));
			//１の位を切り上げる
			roundUpList.add(bd.setScale(-1, BigDecimal.ROUND_UP).intValue());
		}
		scanner.close();

		//最大差分値
		int maxVal = 0;
		//最大差分値となる配列番号
		int maxSeqNo = 0;
		//最小提供時間
		int time = 0;

		//配列同士の差分が一番大きい配列番号を取得する
		for (int i = 0; i < valList.size(); i++) {
			if (maxVal < roundUpList.get(i) - valList.get(i)) {
				maxVal = roundUpList.get(i) - valList.get(i);
				maxSeqNo = i;
			}
		}

		//最小提供時間を計算する
		for (int i = 0; i < valList.size(); i++) {
			if (i == maxSeqNo) {
				time += valList.get(maxSeqNo);
			} else {
				time += roundUpList.get(i);
			}
		}

		System.out.println(time);
	}

}


Measured memory_bytes: 23380
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);
    private static int MAX = 2500;

    public static void main(String[] args) {
	int N = Integer.parseInt(scan.next());
	int A = Integer.parseInt(scan.next());
	int[] x = new int[N];
	for (int i = 0; i < N; i++) {
	    x[i] = Integer.parseInt(scan.next());
	}

	long[][][] dp = new long[N+1][N+1][MAX+1];
	dp[0][0][0] = 1;
	for (int i = 1; i <= N; i++) {
	    int v = x[i-1];
	    for (int j = 0; j <= N; j++) {
		for (int k = 0; k <= MAX; k++) {
		    if(j-1 >= 0 && k-v >= 0) {
			dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-v];
		    } else {
			dp[i][j][k] = dp[i-1][j][k];
		    }
		}
	    }
	}

	long ans = 0;
	for (int i = 1; i <= N; i++) {
	    for (int j = 0; j <= MAX; j++) {
		if(i*A == j) ans += dp[N][i][j];
	    }
	}

	System.out.println(ans);
	scan.close();
    }
}


Measured memory_bytes: 87800
import sys
input = sys.stdin.readline
from collections import Counter


def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def solve(N, A):
    C = Counter(A)
    first = 0
    second = 0
    for k in C.keys():
        if k > first and C[k] >= 2:
            first = k
    C[first] -= 2
    for k in C.keys():
        if k > second and C[k] >= 2:
            second = k
    return first * second


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 27932
#include<iostream>
using namespace std;
int n,m,a[1<<17],used[1<<18];
main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<m;i++)cin>>a[i];
	for(int i=m;i--;)
	{
		if(!used[a[i]])
		{
			cout<<a[i]<<endl;
			used[a[i]]++;
		}
	}
	for(int i=1;i<=n;i++)if(!used[i])cout<<i<<endl;
}



Measured memory_bytes: 4284
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

long long n, a, b;

int main() { 

  cin >> n >> a >> b;

  long long ans = n / (a + b);
  ans *= a;

  long long rem = n % (a + b);
  if (rem >= a) {
    ans += a;
  } else {
    ans += rem;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=200233;
const int D=924844033,G=5,iG=554906420;
int n,ans[MAXN];
vector<int> ver[MAXN];

int fac[MAXN],inv[MAXN];
int rev[MAXN<<2];
int A[MAXN<<2],B[MAXN<<2];

int qpow(int x,int y) {
	int ret=1;
	while(y) {
		if(y&1) ret=1ll*ret*x%D;
		x=1ll*x*x%D;
		y>>=1;
	}
	return ret;
}

void NTT(int f[],int op,int lim) {
	for(int i=1;i<lim;i++)
		if(rev[i]>i) swap(f[rev[i]],f[i]);
	for(int i=1;i<lim;i<<=1) {
		int sta=qpow(~op?G:iG,(D-1)/(i<<1));
		for(int j=0;j<lim;j+=(i<<1)) {
			int w=1;
			for(int k=0;k<i;k++,w=1ll*w*sta%D) {
				int t1=f[j+k],t2=1ll*w*f[i+j+k]%D;
				f[j+k]=(t1+t2)%D;
				f[i+j+k]=(t1-t2+D)%D;
			} 
		}
	}
	if(~op) return ;
	int ilim=qpow(lim,D-2);
	for(int i=0;i<lim;i++)
		f[i]=1ll*f[i]*ilim%D;
}

int siz[MAXN];
void dfs(int u,int fa) {
	siz[u]=1;
	for(int v:ver[u])
		if(v!=fa) dfs(v,u),siz[u]+=siz[v];
}

void first() {
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*i*fac[i-1]%D;
	inv[n]=qpow(fac[n],D-2);
	for(int i=n-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%D;
}
int C(int x,int y) {
	return 1ll*fac[x]*inv[y]%D*inv[x-y]%D;
}

int main() {
	scanf("%d",&n);
	first();
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		ver[x].push_back(y);
		ver[y].push_back(x);
	}
	dfs(1,0);
	siz[0]=1;
	for(int i=2;i<=n;i++)
		++A[siz[i]],++A[n-siz[i]];
	for(int i=0;i<=n;i++)
		A[i]=1ll*A[i]*fac[i]%D;
	for(int i=0;i<=n;i++)
		B[i]=inv[i];
	reverse(B,B+n+1);

	int lim; for(lim=1;lim<=(n<<1);lim<<=1);
	for(int i=1;i<lim;i++)
		rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
	NTT(A,1,lim),NTT(B,1,lim);
	for(int i=0;i<lim;i++)
		A[i]=1ll*A[i]*B[i]%D;
	NTT(A,-1,lim);

	for(int i=1;i<=n;i++)
		ans[i]=((1ll*C(n,i)*n-1ll*inv[i]*A[n+i])%D+D)%D;

	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 37196
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 1e5 + 5, Mod = 1e9 + 7;
int n, m;
ll fact[N];

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  int offset = abs(n - m);
  fact[0] = 1;
  for (int i = 1; i < N; ++i)
    fact[i] = fact[i - 1] * i % Mod;
  if (offset > 1)
    cout << 0 << endl;
  else if (offset == 1) {
    cout << fact[m] * fact[n] % Mod << endl;
  } else
    cout << fact[m] * fact[n] * 2LL % Mod << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  for (int i=0;i<3;i++){
    if (s[i] == s[i+1]){
      cout << "Bad" <<endl;
      return 0;
    }
  }
  cout << "Good" << endl; 
}

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

#define ONLINE_JUDGE
#define pb(a) push_back(a)
#define ALL(a) a.begin(), a.end()
#define FOR(x,to) for(x=0;x<(to);x++)

using ll = long long;

const int E5 = 1e5;

//////////// Solution /////////////////////////////////
	
int N,x[E5],y[E5],t[E5];

void solve() {	
	cin >> N;
	int r=0,c=0,ct=0;
	for (int i = 0; i < N; ++i) {
		cin >> t[i] >> x[i] >> y[i];
	}
	for (int i = 0; i < N; ++i) {
		if (abs(r-x[i])+abs(c-y[i]) > t[i]-ct) {
			cout << "No\n";
			return;
		} else {
			int d = t[i] - ct - (abs(r-x[i])+abs(c-y[i]));
			if (d&1) {
				cout << "No\n";
				return;
			} 
		}
		r = x[i], c = y[i], ct = t[i];
	}

	cout << "Yes\n";
}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

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

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

Measured memory_bytes: 1408
#include <stdio.h>
int main(){
  
  int A, B, K, a, i, j = 0, b;
  
  scanf("%d%d%d", &A, &B, &K);
  
  if(A < B){
    a = A;
  } else {
    a = B;
  }
  
  int Num[a + 1];
  
  for(i = 1; i <= a; ++i){
    Num[i] = 0;
    if(A % i == 0 && B % i == 0){
      Num[i] = 1;
    }
  }
  
  for(i = a; i >= 1; --i){
    if(Num[i] == 1){
      ++j;
    }
    if(j == K){
      b = i;
      break;
    }
  }
  
  printf("%d\n", b);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long int N, a = 2, b = 1;
  cin >> N;
  for (int i = 0; i < N / 2; i++) {
    a += b;
    b += a;
  }
  if (N % 2 == 0) {
    cout << a << endl;
  }
  else {
    cout << b << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int k, s,count=0;
	scanf("%d", &k);
	scanf("%d", &s);
	for (int x = 0; x <= k; x++) {
		for (int y = 0; y <= k; y++) {

			int z = s - x - y;
			if (0 <= z&&z <= k) {
				count++;
			}
		}
	}

	printf("%d\n", count);
	return(0);
}

Measured memory_bytes: 128
from collections import deque


n, m, k =map(int, input().split())

g = []
# Init Graph
for _ in range(n):
    g.append(deque(list()))


bd = dict()
fd = dict()

directcount = [0] * n


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    directcount[a] += 1
    directcount[b] += 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True

visited = [[-1, -1] for i in range(n)]
q = deque(list())
# dfs
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        #print(q)
        nextnode = q.popleft() # 次の探索
        #print("next", nextnode)
        if visited[nextnode][0] != -1:
            #print("visited")
            continue
        visited[nextnode] = [color, cnt]
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1

colorcount = [-1] * n
# グループごとの色をカウント
for i in range(n):
    colorcount[visited[i][0]] = max(colorcount[visited[i][0]], visited[i][1])

#print(visited)
#print(colorcount)


res = [[visited[i][0], colorcount[visited[i][0]]] for i in range(n)]
#print(res)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if res[c][0] == res[d][0]:
        res[c][1] -= 1
        res[d][1] -= 1

output = []
for i in range(n):
    output.append(res[i][1] - directcount[i] - 1)

print(" ".join(list(map(lambda x: str(x), output))))


Measured memory_bytes: 156296
from collections import defaultdict, deque

N = int(input())
E = [[] for _ in range(N+1)]
edge_order = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    edge_order.append(b)


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

print(max(colors))
for i in edge_order:
    print(colors[i])

Measured memory_bytes: 24976
#include<iostream>
#include<cstdio>
#include<queue>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u) for(int i=hd[u],v;v=e[i].v,i;i=e[i].n)
using namespace std;
typedef pair<int,int> P;
const int N=2020;
int n,m,u,v,ans,fl;
int hd[N],b[N][N],f[N][N],g[N][N];
queue<int>q;
struct edge{int n,v;}e[N<<1];
void add(int u,int v){e[++fl]=(edge){hd[u],v};hd[u]=fl;}
void dfs1(int u,int rt){REP(u)if(v!=f[u][rt]) f[v][rt]=u,dfs1(v,rt);}
void wrk(int x,int y,vector<P>&ve){
	q.push(y);g[x][y]=y;b[x][y]=1;
	while(q.size()){
		u=q.front();q.pop();
		REP(u)if(v!=f[u][x]){
			if(b[x][v]){
				b[x][v]=b[v][x]=0;
				g[v][x]=g[x][v]=y;
				ve.push_back(P(y,v));
			}
			else g[x][v]=y,q.push(v);
		}
	}
}
void ins(int u,int v){
	if(g[u][v]==v) return;
	if(g[u][v]) return ins(g[u][v],v); 
	if(g[v][u]) return ins(g[v][u],u);
	vector<P>ve;
	wrk(u,v,ve);wrk(v,u,ve);
	for(P p:ve) ins(p.first,p.second);
}
void dfs2(int u,int t,int rt){
	if(g[t][u]==u) t=u,ans++;
	REP(u)if(v!=f[u][rt]) dfs2(v,t,rt);
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	FOR(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	FOR(i,1,n) dfs1(i,i);
	FOR(i,1,m) scanf("%d%d",&u,&v),ins(u,v);
	FOR(i,1,n) dfs2(i,i,i);
	cout<<(ans>>1)<<'\n';
}

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

int main(){
    int m,n;
    while(true){
        cin >> m >> n;
        if(m==0&&n==0)break;
        int count=0;
        bool a[7368795];
        for(int i=0;i<7368795;i++){
            a[i]=false;
        }
        for(int i=m;i<7368795;i++){
            if(a[i])continue;
            else{
                count++;
                for(int j=i;j<7368795;j+=i){
                    a[j]=true;
                }
            }
            if(count==n+1){
                cout << i << endl;
                break;
            }
        }
    }
}


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}

int main(){

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

    string s;
    cin >> s;

    string k = "keyence";

    for(int i = 0; i < 7; ++i){
        string tmp = "";
        tmp += s.substr(0,i);
        tmp += s.substr(s.size()-7+i, 7-i);
        if(tmp == "keyence"){
            YES();
            return 0;
        }
    }
    NO();


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    int n, x;
    cin >> n >> x;
    if (x == 1 || x == 2 * n - 1) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    if (n == 2) {
        cout << 1 << endl << 2 << endl << 3 << endl;
        return 0;
    }
    vector<int> res(2 * n, 0);
    if (x > 2) {
        res[n] = x, res[n - 1] = x - 2, res[n + 1] = x + 1, res[n + 2] = x - 1;
    } else {
        res[n] = x, res[n - 1] = x + 2, res[n + 1] = x - 1, res[n + 2] = x + 1;
    }
    int index = 1;
    for (int i = 1; i <= 2 * n - 1; i++) {
        int flag = 1;
        for (int j = n - 1; j <= n + 2; j++) {
            if (res[j] == i) {
                flag = 0;
                break;
            }
        }
        if (flag == 0) continue;
        while (index <= 2 * n - 1 && res[index] != 0) {
            index++;
        }
        if (index <= 2 * n - 1)
        res[index++] = i;
    }
    for (int i = 1; i <= 2 * n - 1; i++) {
        cout << res[i] << endl;
    }
}


Measured memory_bytes: 4048
/**
 * File    : C.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-9-29 20:55:36
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
int v[100010];
typedef tuple<int, int> I;
vector<I> cnt[2];

int main()
{
  cin >> N;
  for (auto i = 0; i < N; i++)
  {
    cin >> v[i];
  }
  for (auto k = 0; k < 2; k++)
  {
    cnt[k] = vector<I>(100010);
    for (auto i = 0; i < 100010; i++)
    {
      cnt[k][i] = I(0, i);
    }
  }
  for (auto i = 0; i < N; i++)
  {
    get<0>(cnt[i % 2][v[i]])++;
  }
  int ans = N;
  for (auto k = 0; k < 2; k++)
  {
    sort(cnt[k].begin(), cnt[k].end());
    reverse(cnt[k].begin(), cnt[k].end());
  }
  for (auto k = 0; k < 2; k++)
  {
    int t_ans = N;
    int l = 1 - k;
    int k_num = get<1>(cnt[k][0]);
    t_ans -= get<0>(cnt[k][0]);
    for (auto i = 0; i < 100010; i++)
    {
      if (k_num != get<1>(cnt[l][i]))
      {
        t_ans -= get<0>(cnt[l][i]);
        break;
      }
    }
    ans = min(ans, t_ans);
  }
  cout << ans << endl;
}

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

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

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N - 1));
    rep(i, N) rep(j, N - 1)
    {
        cin >> A[i][j];
        A[i][j]--;
    }

    int ndays = 0;
    vector<bool> is_used(N, false);
    set<int> set_new;
    rep(i, N) set_new.insert(i);
    vector<int> j_now(N, 0);

    while (!set_new.empty())
    {
        ndays++;
        rep(i, N) is_used[i] = false;
        set<int> set_next_new;

        for (const int i : set_new)
        {
            if (is_used[i])
                continue;

            if (j_now[i] == N - 1)
                continue;

            int i_enemy = A[i][j_now[i]];
            if (!is_used[i_enemy] and A[i_enemy][j_now[i_enemy]] == i)
            {
                j_now[i]++;
                j_now[i_enemy]++;
                is_used[i] = true;
                is_used[i_enemy] = true;
                set_next_new.insert(i);
                set_next_new.insert(i_enemy);
            }
        }

        set_new = set_next_new;
    }
    ndays--;

    bool is_possible = true;
    rep(i, N)
    {
        if (j_now[i] != N - 1)
        {
            is_possible = false;
            break;
        }
    }

    cout << (is_possible ? ndays : -1) << endl;
}

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

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

    int len = s.length();
    int end = 0;
    int first = 0;

    for(int i = 0; i < len; i++){
        if(s[i] == 'A'){
            first = i;
            break;
        }
    }

    for(int i = len - 1; i > first; i--){
        if(s[i] == 'Z'){
            end = i;
            break;
        }
    }

    cout << end - first + 1 << endl;
}

Measured memory_bytes: 640
N, M = map(int, input().split())
n = [0 for i in range(N)]
pair = [list(map(int, input().split())) for i in range(M)]

pair = sorted(pair)

old_pair = [0, 0]

ok = True

for i in range(M):
    if pair[i] == [1, 0]:
        ok = False
        break
    if pair[i][0] == old_pair[0] and pair[i][1] != old_pair[1]:
        ok = False
        break
    elif pair[i][0] != old_pair[0]:
        #print(pair[i][0])
        old_pair = pair[i]
        n[pair[i][0] - 1] = pair[i][1]

if n == [0]:
    print(0)
elif not ok:
    print(-1)
else:
    if n[0] == 0:
        print(1, end='')
    else:
        print(n[0], end='')
    for i in range(1, N):
        print(n[i], end='')
    print()

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

int main (){
    int n,l,c=1;
    cin>>n>>l;
    int aji=l;
    if(aji<0){aji=-aji;}
    for(int i=1;i<=n;i++){
        int t=l+i-1;
        if(t<0){t=-t;}
        if(aji>t){
            aji=t;
            c=i;}
            }
        int ans=(l-1)*n+(n*(n+1))/2-(l+c-1);
        cout<<ans<<endl;
        }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b, c;
  cin >> a >>b >> c;
  bool p = false;
  
  if(a + b == c) p = true;
  else if(b + c == a) p = true;
  else if (a + c == b) p = true;
  if(p) cout << "Yes" <<endl;
  else cout << "No" << endl; 
}



Measured memory_bytes: 256
// Create your own template by modifying this file!
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <deque>
#include <stack>
#include <functional>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x;  }
void _R(int &x) { scanf("%d", &x);  }
void _R(int64_t &x) { scanf("%lld", &x);  }
void _R(double &x) { scanf("%lf", &x);  }
void _R(char &x) { scanf(" %c", &x);  }
void _R(char *x) { scanf("%s", x);  }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...);  }
template<class T> void _W(const T &x) { cout << x;  }
void _W(const int &x) { printf("%d", x);  }
void _W(const int64_t &x) { printf("%lld", x);  }
void _W(const double &x) { printf("%.16f", x);  }
void _W(const char &x) { putchar(x);  }
void _W(const char *x) { printf("%s", x);  }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' ');  }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...);  }
#ifdef DEBUG
 #define debug(...) {printf("[DEBUG] ");W(__VA_ARGS__);}
#else
 #define debug(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1<<20;
char s[SIZE];

void solve() {
    R(s);
    int sum = 0;
    FORS(i, s) {
        sum += (s[i] - '0');
    }
    puts(sum % 9 ? "No" : "Yes");
}

int main() {
#define MULTITEST 0
#if MULTITEST    
    CASET{
        solve();
    }
#else
    solve();
#endif
    return 0;
}



Measured memory_bytes: 3276
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 1e6+1;

long long fac[MAX], finv[MAX], inv[MAX];

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

// 二項係数計算
long long COM(ll n, ll k){
  if(n >= MAX){
    ll tmp = 1;
    rep(i,k){
      tmp *= (n-i);
      tmp %= MOD;
    }
    return tmp*finv[k]%MOD;
  }

  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll POW(ll x, ll n){
  ll ret = 1;

  if(n < 0){// n < 0 にも対応
    n *= -1;
    x = inv[x];
  }

  while(0 < n){
    if(n%2 == 0){
      x = x*x%MOD;
      n /= 2;
    }
    else{
      ret = ret*x%MOD;
      n--;
    }
  }

  return ret;
}

vi MP(string s){
  vi A(s.size()+1);
  A[0] = -1;
  int j = -1;
  rep(i,s.size()) {
    while(j >= 0 && s[i] != s[j]) j = A[j];
    j++;
    A[i+1] = j;
  }
  return A;
}

vi Manacher(string s){
  vi R(s.size());
  int i = 0, j = 0;
  while(i < s.size()){
    while(i-j >= 0 && i+j < s.size() && s[i-j] == s[i+j]) ++j;
    R[i] = j;
    int k = 1;
    while(i-k >= 0 && i+k < s.size() && k+R[i-k] < j) R[i+k] = R[i-k], k++;
    i += k; j -= k;
  }
  return R;
}

vi Z_algorithm(string &s){
  vi Z(s.size());
  Z[0] = s.size();
  int i = 1, j = 0;
  while(i < s.size()){
    while(i+j < s.size() && s[j] == s[i+j]) j++;
    Z[i] = j;
    if(j == 0){++i; continue;}
    int k = 1;
    while(i+k < s.size() && k+Z[k] < j) Z[i+k] = Z[k], ++k;
    i += k; j -= k;
  }
  return Z;
}

int main(){
  ll n,a,b; cin >> n >> a >> b;
  ll ans = a*(n/(a+b));
  ans += min(n%(a+b),a);
  cout << ans << endl;
}


Measured memory_bytes: 256
function main(input) {
  var args = input.split(' ');
  var numOfBlackStone = parseInt(args[0], 10);;
  var center = parseInt(args[1], 10);;

  var startNum = center - numOfBlackStone + 1;
  var endNum = center + numOfBlackStone - 1;
  
  while (startNum <= endNum) {
    process.stdout.write(startNum + ' ');
    startNum = startNum + 1;
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 8404
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i,N)
  {
    cin >> a[i];
  }
  sort(ALL(a));
  cout << a[N-1]-a[0] << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    fact = Fact(2*N)
    for i in range(1, K+1):
        ans = (fact(K-1)*fact(N-K+1))//(fact(i-1)*fact(K-i)*fact(i)*fact(N-K-i+1))
        print(ans % mod)

def answer(N, K, i):
    ans = (fact(K-1)*fact(N-K+1))//(fact(i-1)*fact(K-i)*fact(i)*fact(N-K-i+1))
    return ans

class Fact:

    def __init__(self, n):
        self.l = [1] * n
        for i in range(1, n):
            self.l[i] = self.l[i-1] * i

    def __call__(self, k):
        return self.l[k]


main()


Measured memory_bytes: 13556
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=200005;
int n,Time=0;
vector <int> e[N],q0[N],q1[N];
int fa[N],depth[N],mx[N];
int I[N],O[N];
int a0[N],a1[N];
void dfs1(int x,int pre,int d,int pmx){
	if (pmx>0)
		q0[pmx].pb(x);
	if (pre&&mx[pre]>0)
		q1[mx[pre]].pb(x);
	fa[x]=pre,depth[x]=d,mx[x]=pmx,pmx=max(pmx,x);
	I[x]=++Time;
	for (auto y : e[x])
		if (y!=pre)
			dfs1(y,x,d+1,pmx);
	O[x]=Time;
}
int c[N];
void Add(int x,int d){
	if (!x)
		return;
	for (;x<=n;x+=x&-x)
		c[x]+=d;
}
int Ask(int x){
	int ans=0;
	for (;x;x-=x&-x)
		ans+=c[x];
	return ans;
}
int f[N];
int getf(int x){
	return f[x]==x?x:f[x]=getf(f[x]);
}
void Merge(int x,int y){
	x=getf(x),y=getf(y);
	if (depth[x]>depth[y])
		swap(x,y);
	int p=fa[y],s=Ask(O[y])-Ask(I[y]-1);
	Add(I[p],s);
	Add(I[fa[x]],-s);
	f[y]=x;
}
int ans[N];
void dfs2(int x,int pre,int v){
	if (x==1)
		v=0;
	else if (x>mx[pre])
		v+=1+a0[x];
	else
		v+=a0[x]-a1[x];
	ans[x]=v;
	for (auto y : e[x])
		if (y!=pre)
			dfs2(y,x,v);
}
int main(){
	n=read();
	For(i,1,n-1){
		int x=read(),y=read();
		e[x].pb(y),e[y].pb(x);
	}
	dfs1(1,0,0,0);
	For(i,1,n)
		f[i]=i;
	For(x,1,n){
		Add(I[x],1);
		Add(I[fa[x]],-1);
		for (auto y : e[x])
			if (y<x)
				Merge(x,y);
		for (auto y : q0[x])
			a0[y]=Ask(O[y])-Ask(I[y]);
		for (auto y : q1[x])
			a1[y]=Ask(O[y])-Ask(I[y]);
	}
	dfs2(1,0,0);
	For(i,2,n)
		printf("%d ",ans[i]);
	puts("");
	return 0;
}

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

#define vi vector<int>

int main() {

    int n, q;
    vi S, T;
    int tmp;

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

    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> tmp;
        T.push_back(tmp);
    }

    int count = 0;
    int left, right, middle;
    for (int i = 0; i < q; i++) {
        left = 0;
        right = n;
        while (left < right) {
            middle = (left + right) / 2;
            if (T[i] == S[middle]) {
                count++;
                break;
            }
            else if (T[i] < S[middle]) {
                right = middle;
            }
            else {
                left = middle + 1;
            }
        }
    }
    cout << count << endl;

    return 0;
}



Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll LINF = 1001002003004005006LL;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int x; cin >> x;
    if (400<=x&&x<=599) cout << '8';
    else if (600<=x&&x<=799) cout << '7';
    else if (800<=x&&x<=999) cout << '6';
    else if (1000<=x&&x<=1199) cout << '5';
    else if (1200<=x&&x<=1399) cout << '4';
    else if (1400<=x&&x<=1599) cout << '3';
    else if (1600<=x&&x<=1799) cout << '2';
    else if (1800<=x&&x<=1999) cout << '1';
    return 0;
}

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

int main(){
  int A,B,K,n;
  cin >> A >> B >> K;
  n = 0;
  vector<int> div(K);
  for(int i=min(A,B);i>0;i--){
    if(A%i==0&&B%i==0){
      div.at(n) = i;
      n++;
      if(n==K){
        break;
      }
    }
  }
  cout << div.at(K-1) << endl;
}

Measured memory_bytes: 256
for _ in[0]*int(input()):
 X,z=input(),[]
 for y in input():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   z[i]=min(t,k)
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))


Measured memory_bytes: 5612
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repin(Array,n) for(int i=0;i<n;i++){cin>>Array[i];}
using namespace std;

using ll = long long;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;
using Graph = vector<vector<int>>;

int main() {

	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i += 2)
		cout << s[i];
	cout << endl;

	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    bool ans = false;
    for(int i = 1; i < 10; i++){
        for(int j = 1; j < 10; j++){
            if(i * j == N)
            {
                ans = true;
                break;
            }
        }
    }
    if(ans) cout << " Yes" << endl;
    if(!(ans)) cout << "No" << endl;
}

Measured memory_bytes: 256
from itertools import product
e = (1,-1)
a,b,c,d = map(int, list(input()))
for i,j,k in product(e,repeat=3):
  if a+b*i+c*j+d*k == 7:
    break
dic = {1:"+",-1:"-"}
l = [a,dic[i],b,dic[j],c,dic[k],d]
print("".join(map(str,l))+"=7")

Measured memory_bytes: 3064