akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

vector<string> candidates;
void rec(int ind, string word, string target_word){
    if(ind == 9){
        candidates.push_back(word);
        return;
    } 
    if (target_word[ind] == 'A'){
        rec(ind+1, word+'A', target_word);
        rec(ind+1, word, target_word);
    } else {
        rec(ind+1, word+target_word[ind], target_word);
    }
}

int main(){
    string s;cin>>s;
    rec(0, "", "AKIHABARA");
    if (find(candidates.begin(), candidates.end(), s) != candidates.end()){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {

			String str = br.readLine();
			String[] strArr = str.split(" ");

			int n = Integer.parseInt(strArr[0]);
			int m = Integer.parseInt(strArr[1]);
			int l = Integer.parseInt(strArr[2]);

			int[][] nm = new int[n][m];
			int[][] ml = new int[m][l];

			// create array (n * m)
			for(int i=0;i<n;i++){
				str = br.readLine();
				strArr = str.split(" ");
				for(int j=0;j<m;j++){
					// ???????????????????????????
					nm[i][j] = Integer.parseInt(strArr[j]);
				}
			}

			// create array (m * l)
			for(int i=0;i<m;i++){
				str = br.readLine();
				strArr = str.split(" ");
				for(int j=0;j<l;j++){
					// ???????????????????????????
					ml[i][j] = Integer.parseInt(strArr[j]);
				}
			}

			// calculate
			StringBuilder sb = new StringBuilder();
			for(int i=0;i<n;i++){
				for(int j=0;j<l;j++){
					long c = 0;
					for(int k=0;k<m;k++){
						c += nm[i][k] * ml[k][j];
					}
					sb.append(c);
					sb.append(j<(l-1)?' ':'\n');
				}
			}

			System.out.print(sb.toString());

		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null) {
					br.close();
				}
			} catch (IOException ioe) {
			}

		}
	}
}

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

void bubble_sort(int *data, int *num, int n)
{
	int i, j;
	
	for (i = 0; i < n - 1; i++){
		for (j = 0; j < n - i - 1; j++){
			if (data[j] < data[j + 1]){
				data[j] ^= data[j + 1];
				data[j + 1] ^= data[j];
				data[j] ^= data[j + 1];
				
				num[j] ^= num[j + 1];
				num[j + 1] ^= num[j];
				num[j] ^= num[j + 1];
			}
			else if (data[j] == data[j + 1] && num[j + 1] < num[j]){
				data[j] ^= data[j + 1];
				data[j + 1] ^= data[j];
				data[j] ^= data[j + 1];
				
				num[j] ^= num[j + 1];
				num[j + 1] ^= num[j];
				num[j] ^= num[j + 1];
			}
		}
	}
}

int main(void)
{
	int n, t, m[1001], num[1001], temp;
	int i, j;
	
	while (1){
		scanf("%d%d", &n, &t);
		
		if (n + t == 0){
			break;
		}
		
		memset(m, 0, sizeof(m));
		for (i = 1; i <= n; i++){
			for (j = 1; j <= t; j++){
				num[j] = j;
				scanf("%d", &temp);
				if (temp){
					m[j]++;
				}
			}
		}
		bubble_sort(&m[1], &num[1], t);
		for (i = 1; i <= t; i++){
			if (i != 1){
				printf(" ");
			}
			printf("%d", num[i]);
		}
		
		printf("\n");
	}
	return (0);
}

Measured memory_bytes: 424
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <string.h>
#include <bitset>
#include <map>

using namespace std;

int main()
{
    int c[3][3];
    for (int i = 0; i < 3; ++i)
    {
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }
    auto ret = (c[0][0] - c[1][0] == c[0][1] - c[1][1]) &&
               (c[0][1] - c[1][1] == c[0][2] - c[1][2]) &&
               (c[1][0] - c[2][0] == c[1][1] - c[2][1]) &&
               (c[1][1] - c[2][1] == c[1][2] - c[2][2]) &&
               (c[2][0] - c[0][0] == c[2][1] - c[0][1]) &&
               (c[2][1] - c[0][1] == c[2][2] - c[0][2]) &&
               (c[0][0] - c[0][1] == c[1][0] - c[1][1]) &&
               (c[1][0] - c[1][1] == c[2][0] - c[2][1]) &&
               (c[0][1] - c[0][2] == c[1][1] - c[1][2]) &&
               (c[1][1] - c[1][2] == c[2][1] - c[2][2]) &&
               (c[0][2] - c[0][0] == c[1][2] - c[1][0]) &&
               (c[1][2] - c[1][0] == c[2][2] - c[2][0]);
    cout << (ret ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#define MN 25
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long f[MN+5][2][2],ans;
int D,s[MN+5],num;
int main()
{
    D=read();
    for(int t=D;t;t/=10) s[++num]=t%10;
    for(int len=num;len<=20;++len)
    {
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        for(int l=1,r=len,k=1;l<r;++l,--r,++k)
            for(int b1=0;b1<2;++b1) for(int b2=0;b2<2;++b2)
                for(int i=(r==len);i<=9;++i) for(int j=0;j<=9;++j)
                {
                    int lnum=i+s[r]+b1,rnum=j+b2+s[l];
                    if(lnum%10!=j||rnum%10!=i) continue;
                    f[k][b1][rnum>=10]+=f[k-1][lnum>=10][b2];
                }
        if(len&1)
        {
            for(int b1=0;b1<2;++b1)
                for(int b2=0;b2<2;++b2)
                    for(int j=(len==1);j<=9;++j)
                    {
                        int num=j+b2+s[len+1>>1];
                        if(num/10!=b1||num%10!=j) continue;
                        ans+=f[len/2][b1][b2];
                    }
        }
        else ans+=f[len/2][0][0]+f[len/2][1][1];
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n, cnt4 = 0, cnt2 = 0;
    cin >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a.at(i);
        if(a.at(i) % 4 == 0)cnt4++;
        else if(a.at(i) % 2 == 0)cnt2++;
    }
    if(cnt2 == 0)cnt2++;
    int ml = (2*cnt4+1)+cnt2-1;
    if(ml >= n)cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    ll n;
    cin >> n;
    ll a[n];
    rep(i,n) cin >> a[i];
    ll MOD = 1000000007;
    ll ans = 0;
    ll sum = 0;
    rep(i,n){
        ans += sum * a[i];
        ans %= MOD;
        sum += a[i];
        sum %= MOD;
    }
    cout << ans << endl;
    return 0;
}




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

int main()
{
	int n;
	cin >> n;
	vector<int> d1(n), d2(n);
	for (int i = 0; i < n; i++)
	{
		cin >> d1[i] >> d2[i];
	}

	for (int i = 0; i + 2 < n; i++)
	{
		if ((d1[i] == d2[i]) && (d1[i + 1] == d2[i + 1]) && (d1[i + 2] == d2[i + 2]))
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
iiii x[1000005];
vector<ii> vec[10];
int r,c,n,cnt;
stack<int> st;
//0 là cột bên trái
//1 là hàng ở trên
//2 là cột bên phải
//3 là hàng ở dưới
void qualify(int x1,int y1,int x2,int y2,int num){
    int count1=0,count2=0;
    if(y1==0&&count1==0){
        vec[0].pb(mp(x1,num));
        count1++;
    }
    if(y1==c&&count1==0){
        count1++;
        vec[2].pb(mp(x1,num));
    }
    if(y2==0&&count2==0){
        count2++;
        vec[0].pb(mp(x2,num));
    }
    if(y2==c&&count2==0){
        count2++;
        vec[2].pb(mp(x2,num));
    }
    if(x1==0&&count1==0){
        count1++;
        vec[1].pb(mp(y1,num));
    }
    if(x1==r&&count1==0){
        count1++;
        vec[3].pb(mp(y1,num));
    }
    if(x2==0&&count2==0){
        count2++;
        vec[1].pb(mp(y2,num));
    }
    if(x2==r&&count2==0){
        count2++;
        vec[3].pb(mp(y2,num));
    }
}
bool cmp(const ii &a,const ii &b){
    return a.fi<b.fi;
}
bool cmp1(const ii &a,const ii &b){
    return a.fi>b.fi;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>r>>c>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i].fi.fi>>x[i].fi.se>>x[i].se.fi>>x[i].se.se;
    for(int i=1;i<=n;i++){
        int count1=0,count2=0;
        if(x[i].fi.fi==0||x[i].fi.fi==r)
            count1++;
        if(x[i].se.fi==0||x[i].se.fi==r)
            count2++;
        if(x[i].fi.se==0||x[i].fi.se==c)
            count1++;
        if(x[i].se.se==0||x[i].se.se==c)
            count2++;
        if(count1>=1&&count2>=1)
        qualify(x[i].fi.fi,x[i].fi.se,x[i].se.fi,x[i].se.se,i);
    }
    sort(vec[0].begin(),vec[0].end(),cmp1);
    sort(vec[1].begin(),vec[1].end(),cmp);
    sort(vec[2].begin(),vec[2].end(),cmp);
    sort(vec[3].begin(),vec[3].end(),cmp1);
    for(int i=0;i<=3;i++){
        for(int j=0;j<vec[i].size();j++){
            if(!st.empty()){
                if(vec[i][j].se==st.top())
                    st.pop();
                else
                    st.push(vec[i][j].se);
            }
            else
                st.push(vec[i][j].se);
        }
    }
    if(!st.empty())
        cout<<"NO";
    else
        cout<<"YES";
}


Measured memory_bytes: 9036
#include <iostream>

using namespace std;

int main()
{
    char X, Y;
    cin >> X >> Y;
    if (X < Y) {
        cout << "<" << endl;
    }
    else if (X > Y) {
        cout << ">" << endl;
    }
    else {
        cout << "=" << endl;
    }
}


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

lint n, k;
vector<lint> a;

int main() {
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<vector<int>> doubling(n, vector<int>(65));
    for (int i = 0; i < n; i++) {
        doubling[i][0] = a[i];
    }
    for (int i = 1; i <= 64; i++) {
        for (int j = 0; j < n; j++) {
            doubling[j][i] = doubling[doubling[j][i - 1]][i - 1];
        }
    }
    bitset<65> bit(k);
    int now = 0;
    for (int i = 0; i < 64; i++) {
        if (bit[i]) {
            now = doubling[now][i];
        }
    }
    cout << now + 1 << endl;
}

Measured memory_bytes: 62660
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int a,b,c;
  cin >> a>>b>>c;
  int buf;
  buf = min(c,b/a);
  cout << buf << endl;
}



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

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

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

ll mpower(ll a,ll b,ll c){
  int z;
  if(b==0){
    z=1;
    z%=c;
    return z;
  }
  if(b==1){
    z=a;
    z%=c;
    return z;
  }
  else{
    return (((mpower(a,b/2,c))*(mpower(a,b/2,c))%c)*mpower(a,b%2,c)%c);
  }
}
//aのｂ乗をｃで割った余り

int main(){
  int n;
  cin>>n;
  cout<<1-n<<endl;
}

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

int mod = 1000000007;
long long dp[100005];;

int main() {

  long long n,m;
 cin>>n>>m;

  long long x;

  for(int i=0;i<m;i++){
     cin>>x;
     dp[x] = -1; }

  dp[0] = 1;

  if(dp[1] != -1)
    dp[1] = 1;
  else dp[1] = 0;

  for(int i=2;i<n+1;i++)
  {
     if(dp[i] == -1) dp[i] = 0;
     else {
        dp[i] = dp[i-1]+dp[i-2];
        dp[i] %= mod; }
  }

  cout<<dp[n]<<endl;

return 0;
}


Measured memory_bytes: 1024
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (a1[-1]*bef1>=a2[-1]*bef2):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
if 0 in a:
    print(max(0,ans%mod))
else:
    print(ans%mod)


Measured memory_bytes: 31804
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=4010;
int bigger_num[2][maxn][maxn],a[maxn],pos[2][maxn];
bool c[maxn];
int dp[maxn][maxn];
int main(){
	int n;
	scanf("%d",&n);
	char ch[5];
	for(int i=1;i<=n+n;i++){
		scanf("%s%d",ch,a+i);
		c[i]=(ch[0]=='B');
		pos[c[i]][a[i]]=i;
	}
	for(int i=0;i<2;i++){
		for(int j=1;j<=n+n;j++){
			int cnt=0;
			for(int k=n;k>=0;k--){
				bigger_num[i][j][k]=cnt;
				if(pos[i][k]<=j) cnt++;
			}
		}
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0]=0;
	for(int i=1;i<=n+n;i++){
		for(int j=0;j<=n;j++){
			if(j+1<=n){
				int diff_col=bigger_num[1][pos[0][j+1]][i-1-j];
				dp[i][j+1]=min(dp[i][j+1],dp[i-1][j]+diff_col+bigger_num[0][pos[0][j+1]][j+1]);
			}
			if(i-j<=n){
				int diff_col=bigger_num[0][pos[1][i-j]][j];
				dp[i][j]=min(dp[i][j],dp[i-1][j]+diff_col+bigger_num[1][pos[1][i-j]][i-j]);
			}
		}
	}
	printf("%d\n",dp[n+n][n]);
	return 0;
}

Measured memory_bytes: 188672
N, M = map(int, input().split())
L = []
R = []
for i in range(M):
    S = input().split()
    L.append(int(S[0]))
    R.append(int(S[1]))
if min(R) >= max(L):
    print(min(R)-max(L)+1)
else:
    print(0)

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

int main()
{
  long long int a, b, c, d, ans=LLONG_MIN;	cin>>a>>b>>c>>d;
  
  vector<long long int> v1, v2;
  v1.push_back(a);
  v1.push_back(b);
  if(a+1<b)	v1.push_back(a+1);
  if(b-1>a)	v1.push_back(b-1);
  
  v2.push_back(c);
  v2.push_back(d);
  if(c+1<d)	v2.push_back(c+1);
  if(d-1>c)	v2.push_back(d-1);
  
  for(int i=0; i<v1.size(); i++)
  {
    for(int j=0; j<v2.size(); j++)
    {
      ans = max(ans, v1[i]*v2[j]);
     }           
   }
    
                cout<<ans;
}

static int fastio = []() {
    #define endl '\n'
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    return 0;
}();


Measured memory_bytes: 3680
// 見せてやるぜ、奇跡ってやつをよぉ……
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    V< V< P<ll, ll> > > a(n);
    REP(i, n) {
        ll ai; cin >> ai;
        REP(j, ai) {
            ll x, y; cin >> x >> y;
            x--;
            a[i].emplace_back(x, y);
        }
    }

    ll ans = 0;
    REP(state, 1LL << n) {
        ll is_honest = true;
        vll hon(n, -1);
        REP(i, n) {
            if ((state >> i) & 1) {
                REP(j, a[i].size()) {
                    if (a[i][j].second == 1) {
                        if (!((state >> a[i][j].first) & 1)) {
                            is_honest = false;
                            break;
                        }
                        if (hon[a[i][j].first] == 0) is_honest = false;
                        else if (hon[a[i][j].first] == -1) hon[a[i][j].first] = 1;
                    } else {
                        if ((state >> a[i][j].first) & 1) {
                            is_honest = false;
                            break;
                        }
                        if (hon[a[i][j].first] == 1) is_honest = false;
                        else if (hon[a[i][j].first] == -1) hon[a[i][j].first] = 0;
                    }
                }
            }
        }
        if (is_honest) {
            // cout << state << '\n';
            chmax(ans, (ll)__builtin_popcount(state));
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
a, b = gets.chop.split.map(&:to_i)

str = ''

if a == b
  a.times {
    str += a.to_s
  }
elsif a < b
  b.times {
    str += a.to_s
  }
else
  a.times {
    str += b.to_s
  }
end

puts str

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define int long long
using namespace std; 

int n;
int h[100005];
int dp[100005];


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	cout << dp[n - 1] << '\n';
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


bool isSquare(int a) {
    REP(i, 0, 1000) {
        if (a == i * i) return true;
    }
    return false;
}


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int D; cin >> D;
    int X[11][11];
    rep(i, N) {
        rep(j, D) {
            cin >> X[i][j];
        }
    }
    int ans = 0;
    rep(i, N) {
        REP(j, i + 1, N - 1) {
            int d = 0;
            rep(k, D) {
                int t = X[i][k] - X[j][k];
                d += t * t;
            }
            if (isSquare(d)) ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int N; cin >> N;
	vector<int>vec(N, 0);
	rep(i, 0, N - 1) {
		int a; cin >> a;
		--a;
		vec[a]++;
	}
	rep(i, 0, N)cout << vec[i] << "\n";

	return 0;
}

Measured memory_bytes: 3996
a, b, k = map(int ,input().split())
if b-a+1 <= k:
    k = b-a+1
ans = []
for i in range(k):
    print(a+i)
    ans.append(a+i)
for i in range(-k+1,1):
    if b+i not in ans:
        print(b+i)

Measured memory_bytes: 3060
'use strict';
function main(input) {
  input = input.split(" ");
  const a = parseInt(input[0], 10);
  const b = parseInt(input[1], 10);
  const c = parseInt(input[2], 10);
  
  if ((a === b && b === c) || 
  (a !== b && a !== c && b !== c)) {
    console.log('No');
  } else {
    console.log('Yes');
  }
}

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

Measured memory_bytes: 7496
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
using namespace std;

enum PLAYER{
	HIROSHI,
	KENJIRO,
};

enum FISH{
	IWANA,
	YAMAME,
};

int main(){

	int table[2][2],a,b,c,d,hiro,ken;

	scanf("%d %d",&table[HIROSHI][IWANA],&table[HIROSHI][YAMAME]);
	scanf("%d %d",&table[KENJIRO][IWANA],&table[KENJIRO][YAMAME]);
	scanf("%d %d %d %d",&a,&b,&c,&d);

	hiro = a*table[HIROSHI][IWANA] + c*(table[HIROSHI][IWANA]/10) +
		   b*table[HIROSHI][YAMAME] + d*(table[HIROSHI][YAMAME]/20);

	ken = a*table[KENJIRO][IWANA] + c*(table[KENJIRO][IWANA]/10) +
		  b*table[KENJIRO][YAMAME] + d*(table[KENJIRO][YAMAME]/20);

	if(hiro == ken){
		printf("even\n");
	}else if(hiro > ken){
		printf("hiroshi\n");
	}else{
		printf("kenjiro\n");
	}

	return 0;
}

Measured memory_bytes: 2624
#include <bits/stdc++.h>
#define rhl (1000000007)
int f[5005][5005],n,m,ans;
char s[5005];
int main(){
  std::cin>>n,scanf("%s",s),m=strlen(s),f[0][0]=ans=1;
  for (int i=0;i<n;++i)
    for (int j=0;j<n;++j)
      (f[i+1][std::max(0,j-1)]+=f[i][j])%=rhl,(f[i+1][j+1]+=2LL*f[i][j])%=rhl;
  for (int i=0;i<m;++i) ans=1LL*ans*500000004%rhl;
  std::cout<<1LL*ans*f[n][m]%rhl; return 0;
}


Measured memory_bytes: 98048
#include<iostream>
#include<cmath>
using namespace std;
#define EPS 1e-10
double x[4],y[4];
double det(){
  double x1,x2,y1,y2;
  x1 = x[0] - x[1];
  y1 = y[0] - y[1];
  x2 = x[2] - x[3];
  y2 = y[2] - y[3];
  return x1 * y2 - y1 * x2;
}

int main(void){
  int n;
  cin >> n;
  while(n--){
    for(int i = 0 ; i < 4 ; i ++)cin>>x[i]>>y[i];
    cout<<(fabs(det())<EPS?"YES":"NO")<<endl;

  }
  return 0;
}

Measured memory_bytes: 1224
use v6;

my ($n, $l) = get().chomp.split(' ');
my @str;
loop (my $i = 0; $i < $n; $i++) {
	@str[$i] = get().chomp;
}
@str = @str.sort;
for @str -> $key {
	print $key;
}
print "\n";

exit;

Measured memory_bytes: 58620
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >>n;
    string v[105];
    for(int i = 0;i<n;i++)
        cin >>v[i];
    int ac=0,uc=0;
    int count=0;
    for(int i = 0;i<n;i++)
    {
        if (v[i] == "A")
            ac++;
        else if(v[i]=="Un")
            uc++;
        if(uc>ac)
        {
            if(count==0)
            cout <<"NO"<<endl;
            count++;
        }
    }
    if(ac==uc && count==0)
        cout <<"YES"<<endl;
    else if(ac != 0 && count ==0)
        cout <<"NO"<<endl;
    return 0;
}



Measured memory_bytes: 3164
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val H = readLine()!!.split(" ").map(String::toInt)


    var pre = H[0]
    for (i in 1 until H.size) {
        val cur = H[i]
        pre = when {
            pre == cur -> cur
            pre == cur - 1 -> pre
            pre <= cur - 2 -> cur - 1
            else -> {
                println("No")
                return
            }
        }
    }
    println("Yes")
}


Measured memory_bytes: 59216
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// pair 型
template<class S,class T>
std::ostream& operator<<(std::ostream& os, const pair<T,S>& p){
  cout << "(" << p.first << "," << p.second << ")";
  return os;
}

// map 型
template<class S,class T>
std::ostream& operator<<(std::ostream& os, const map<S,T,greater<li>>& mp){
  for(const pair<S,T>& x: mp){
    cout << "[" << x.first << "]=" << x.second << " ";
  }
  return os;
}

int main(){
  int n; cin >>n;
  map<li,int,greater<li>> mp;
  rep(i,n){
    li a; cin >>a; mp[a]++;
  }
  if(df)print(mp);
  auto itr=mp.begin();
  int flag=(itr->first+itr->second)%2;
  int s=itr->second,temp=itr->first;
  mp.erase(itr);
  for(pair<li,int> p: mp){
    if(df)print("p:",p);
    if((temp^p.first^p.second)&1){
      int y=s+(1-(p.second&1));
      if(df)print("s,y:",s,y);
      if(y<=p.first) flag^=1;
      if(df)print(flag);
    }
    s+=p.second;
    temp=p.first;
  }
  
  printf("%s\n",flag?"First":"Second");
}


Measured memory_bytes: 8492
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

  int ans = 0;

  for (int i = 0; i + 1 < N; i++) {
    if (i == p[i]) {
      swap(p[i], p[i + 1]);
      ans++;
    }
  }

  if (N - 1 == p[N - 1]) {
    swap(p[N - 2], p[N - 1]);
    ans++;
  }

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

Measured memory_bytes: 1024
#include <iostream>
//#include <vector>
#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

//typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 200100
//#define NIL -1

int main() {
    string s;
    cin >> s;
    if(s=="ABC"){
        cout << "ARC" << endl;
    }else{
        cout << "ABC" << endl;
    }

    return 0;
}

Measured memory_bytes: 3628
// Anve$hi $hukla
#include <bits/stdc++.h>
using namespace std;
struct ${$(){ios_base::sync_with_stdio(false);cin.tie(NULL);}}$;

typedef long long LL;
const int Maxn = 200005;

int main() {
	int n, m;
	cin >> n >> m;
	vector <string> s(n);

	for(int i = 0; i < n; i++) {
		cin >> s[i];
	}

	bool ok = 1;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(i == n - 1 && j == m - 1)
				continue;
			int cnt = 0;
			if(i != n - 1)
				cnt += (s[i + 1][j] == '#');
			if(j != m - 1)
				cnt += (s[i][j + 1] == '#');
			ok &= ((cnt < 2));
		}
	}   
	cout << (ok == 1? "Possible": "Impossible") << endl;
	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;


public class Main {
	Scanner sc = new Scanner(System.in);
	
	void run(){
		int w = sc.nextInt();
		int p = 100000;
		for(int i = 0; i < w; i++){
			if((p*1.05)%1000 > 0){
				p = ((int)(p * 1.05)/1000+1)*1000;
			}else{
				p = (int)(p * 1.05);
			}
		}
		System.out.println(p);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 17152
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int>> piii;
typedef vector<int> vi;
typedef vector<pii> vii;

#define ri(a) scanf("%d", &a)
#define rii(a,b) scanf("%d %d", &a, &b)
#define riii(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define rl(a) scanf("%lld", &a)
#define rll(a,b) scanf("%lld %lld", &a, &b)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define ROF(i,n,m) for(int i=n; i>m; i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second

const int INF = 0x3f3f3f3f;
const ll LLINF = 1e18;
const int maxN = 20; // CAMBIAR ESTE

// GJNM
int n,m,x;
int cost[maxN];
int A[maxN][maxN];
int mxpos[maxN];
int dp[1<<12];

int f(int bitmask){
	if ( bitmask != (1<<12) && dp[bitmask] != -1 )
		return dp[bitmask];

	int mx[maxN];
	FOR(i,0,m)
		mx[i] = 0;

	FOR(i,0,n){
		if ( bitmask & (1<<i) ){
			FOR(j,0,m){
				mx[j] += A[i][j];
			}
		}
	}

	bool gotit = true;

	FOR(i,0,m){
		if ( mx[i] < x )
			gotit = false;
	}

	if ( gotit )
		return dp[bitmask] = 0;

	dp[bitmask] = INF;
	FOR(i,0,n){
		if ( bitmask & (1<<i) )
			continue;

		dp[bitmask] = min(dp[bitmask], cost[i] + f(bitmask | (1<<i)) );
	}
	return dp[bitmask];
}

int main(){
	riii(n,m,x);
	FOR(i,0,n){
		ri(cost[i]);
		FOR(j,0,m){
			ri(A[i][j]);
			mxpos[j] += A[i][j];
		}
	}
	FOR(i,0,m){
		if ( mxpos[i] < x ){
			printf("-1\n");
			return 0;
		}
	}
	memset(dp,-1,sizeof(dp));
	printf("%d\n",f(0) );
	return 0;
}

Measured memory_bytes: 3844
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using vi = vector<int>;

#define scan(x) cin >>x;
#define print(x) cout << x << endl;
#define Endl endl
#define inf 99999999
#define llinf 1LL << 32

int main() {

	string s;
	string a;
	int ans = 0;
	scan(s);

	for (int i = 0; i < s.length(); i++) {
		a = s[i];
		ans += stoi(a);
	}

	if (stoi(s) % ans == 0) {
		print("Yes");
	}
	else {
		print("No");
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {

    string s; cin >> s;
    vector<int> v(4);
    rep(i, 4) v[i] = stoi(s.substr(i, 1));

    for (int bit = 0; bit <= 1<<3; ++bit) {

        int tmp = v[0];

        rep(i, 3){
            
            if (bit & 1<<i) tmp += v[i+1];
            else tmp -= v[i+1];
        }
        if (tmp == 7) {
            rep (i, 4) {
                if (i == 3) {
                    cout << v[3] << "=7" << endl;
                    return 0;
                }
                cout << v[i];
                if (bit & 1<<i) cout << "+";
                else cout << "-";
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	a := 0
	sum := 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] == 'A' {
			a++
		} else if s[i:i+2] == "BC" {
			sum += a
			i++
		} else {
			a = 0
		}
	}
	fmt.Printf("%v\n", sum)
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, q;
    cin >> n;
    vector<int> s(n);
    for(int i=0; i<n; ++i) cin >> s[i];
    sort(s.begin(), s.end());
    cin >> q;
    int res = 0;
    for(int j=0; j<q; ++j) {
        int t;
        cin >> t;
        auto itr = lower_bound(s.begin(), s.end(), t);
        if(itr != s.end() && *itr == t) res++;
    }
    cout << res << endl;
}


Measured memory_bytes: 3164
//Dragon_warrior7(IITK)
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 1000000000000000000
#define pll pair<ll, ll> 
#define ull unsigned ll
#define vll vector<ll> 
#define rub cout << "\n------------------------------------\n"
#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) 
{
	cout << *it << " = " << a;
	nl;
	err(++it, args...);
}
//typedef  tree < int ,  null_type ,  greater<int> ,  rb_tree_tag ,  tree_order_statistics_node_update > oset;
void read(vector<ll> &v)
{
	for (int i = 0; i < v.size(); i++)
		cin >> v[i];
}
// const int mod=1e9+7;
// ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// ll modInverse(ll a){return power(a,mod-2);}
ll n,m,a,b,c,k,temp,x,y;
void solveforthiscase(const int & test)
{//deb(test);
cin>>n;
vll v(n);
read(v);
sor(v);
ll ans=v[n/2]-v[n/2-1];
cout<<ans;






return ;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test=1;
// 	cin>>test;
    for(int i=1;i<=test;i++)
    {
        solveforthiscase(i);
    }
}

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

using namespace std;

const int maxn=1e5+5,mod=1e9+5;

typedef long long ll;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int a[105],ans=1e9,kk,nm=105;
        for(int i=1; i<=n; i++)
            {scanf("%d",&a[i]);
            nm=max(nm,a[i]);}
        for(int i=1; i<=nm*2; i++)
        {
            kk=0;
            for(int j=1; j<=n; j++)
                kk+=(a[j]-i)*(a[j]-i);
            ans=min(ans,kk);
        }
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

long long pow(int x, int y) {
    if (y == 0) return 1;
    long long a = pow(x, y / 2);
    if (y % 2 == 0) return a * a;
    else return a * a * x;
}

int main() {
    int X;
    cin >> X;
    
    vector<long long> S;
    rep(i, 31) REP(j, 10) {
        long long x = pow(i + 1, j + 1);
        if (x <= X) S.push_back(x);
    }
    sort(S.rbegin(), S.rend());
    cout << S[0] << endl;
    return 0;
}


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

const int N = 5010;
const int mod = 1e9 + 7;

typedef long long LL;

struct edge {
    int to, next;
} e[N * 2];

int head[N], ecnt;

inline void adde(int from, int to) {
    e[++ecnt] = (edge){to, head[from]}, head[from] = ecnt;
    e[++ecnt] = (edge){from, head[to]}, head[to] = ecnt;
}

int f[N][N], g[N], sz[N];

void dfs(int u, int fa) {
    sz[u] = 1, f[u][1] = 1;
    for (int i = head[u]; i; i = e[i].next)
        if (e[i].to != fa) {
            dfs(e[i].to, u);
            static int tmp[N];
            for (int j = 1; j <= sz[e[i].to] + sz[u]; j++) tmp[j] = 0;
            for (int j = 0; j <= sz[e[i].to]; j++)
                for (int k = 1; k <= sz[u]; k++)
                    tmp[j + k] = (tmp[j + k] + (LL)f[e[i].to][j] * f[u][k]) % mod;
            sz[u] += sz[e[i].to];
            for (int j = 1; j <= sz[u]; j++) f[u][j] = tmp[j];
        }
    for (int j = 1; j <= sz[u]; j++)    
        f[u][0] = (f[u][0] - (LL)f[u][j] * g[j] % mod + mod) % mod;
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 1, a, b; i < n; i++) scanf("%d%d", &a, &b), adde(a, b);
    g[0] = 1;
    for (int i = 2; i <= n; i += 2) g[i] = (LL)g[i - 2] * (i - 1) % mod;
    dfs(1, 0), printf("%d\n", mod - f[1][0]);
}


Measured memory_bytes: 97280
import sys
import math
n = int(input())
lis=[]
for i in range(n):
    tmp = input()
    lis.append(tmp)
m = int(input())
lit=[]
for i in range(m):
    tmp = input()
    lit.append(tmp)
lis.sort()
lit.sort()
ans=0
for i in range(len(lis)):
    tmp=0
    for j in lis:
            if j==lis[i]:
                tmp += 1
    if(lis[i] not in lit):
        ans = max(ans, tmp)
    else:
        for j in lit:
            if lis[i] == j:
                tmp -= 1
    ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define sqr(x) (x) * (x)

using namespace std;
//using namespace __gnu_pbds;

mt19937_64 gen(time(0));

//typedef tree<
//pair <int, int>,
//null_type,
//less<pair <int, int>>,
//rb_tree_tag,
//tree_order_statistics_node_update>
//ordered_set;

//const int inf = 2e9 + 6555;
//const int mod = 1e9 + 7;
//const int maxn = 1e5 + 555;



signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif
    int n;
    cin >> n;
    ll ans = 0;
    int mx = 0;
    for(int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ans += max(0, mx - x);
        mx = max(mx, x);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
using pii = pair<int, int>;
int main() {
  char a;
  cin >> a;

  for (char s = 'A'; s <= 'Z'; s++) {
    if (s == a) {
      cout << 'A' << endl;
      return 0;
    }
  }

  for (char s = 'a'; s <= 'z'; s++) {
    if (s == a) {
      cout << 'a' << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <string>
#define LL long long 
using namespace std;
string s;
LL N;
int main() {
	cin >> N;
	cin >> s;
	char c = '1';
	N =0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != c) {
			c = s[i];
			N++;
		}
	}
	cout << N << endl;

	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

void fibonacci(int);

int main(){
  int n;
  
  scanf("%d", &n);

  fibonacci(n);

  return 0;
}

void fibonacci(int n){
  int i, F[45];

  F[0]=1;
  F[1]=1;

  for(i = 2;i <= n;i++){
    F[i] = F[i - 2] + F[i - 1];
  }

  printf("%d\n", F[n]);
}



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

#define ll long long
#define ld long double
#define F first
#define S second

#define ONLINE_JUDGE 1

using namespace std;

const int mod = 1e9+7;
const int MAX = 200020;

vector<ll> fact(MAX),ifac(MAX);
vector<ll> invs(MAX);
vector<vector<int> > g(MAX);
vector<ll> dp(MAX);
vector<ll> sz(MAX);

ll pwr(ll a, ll n){
	if(n==0) return 1;
	if(n==1) return a%mod;
	ll q = pwr(a,n >> 1);
	q = 1ll * q * q % mod;
	if(n&1) q = 1ll * q * a % mod;
	return q;
}

ll inv(ll n){
	return pwr(n,mod-2);
}

void init(){
	fact[0] = 1,invs[1] = 1,ifac[0] = 1;
	for(int i = 1; i < MAX; i++)
		fact[i] = 1ll * fact[i-1] * i % mod;
	for(int i = 2; i < MAX; i++)
		invs[i] = -invs[mod%i] * 1ll * (mod / i) % mod;
	for(int i = 1; i < MAX; i++)
		ifac[i] = 1ll * ifac[i-1] * invs[i] % mod;
}

void dfs1(int v, int p = -1){
	dp[v] = 1;
	sz[v] = 1;
	for(int u : g[v]){
		if(u==p) continue;
		dfs1(u,v);
		sz[v]+=sz[u];
		dp[v] = (1ll * dp[v] * dp[u] % mod) * ifac[sz[u]] % mod;
	}
	dp[v] = 1ll * dp[v] * fact[sz[v] - 1] % mod;
}

void dfs2(int v,int p = -1){
	for(int u : g[v]){
		if(u==p) continue;
		ll tmp = (dp[v] * fact[sz[u]] % mod) * inv(dp[u]) % mod;
		tmp = ifac[sz[1] - 1] * tmp % mod; 
		tmp = fact[sz[1] - sz[u] - 1] *  tmp % mod;
		ll tmp_n = ifac[sz[u] - 1] * dp[u]%mod;
		tmp_n = tmp_n * fact[sz[1] - 1] % mod;
		dp[u] = tmp_n * tmp % mod;
		dp[u] = dp[u] * ifac[sz[1] - sz[u]] % mod;
		dfs2(u,v);
	}
}

void solve(){
	int n;
	cin >> n;
	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1);
//	cout << dp[1] + mod << "\n";
	dfs2(1);
	for(int i = 1; i <= n; i++){
		cout << (dp[i] + mod)%mod << "\n";
	}
}
int main(){
	#ifndef ONLINE_JUDGE	
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);		
	int t = 1;
	//cin >> t;
	init();
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 21748
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
    x=bisect.bisect_left(a,b[i])
    y=bisect.bisect_right(c,b[i])
    ans+=x*(n-y)
print(ans)
    

Measured memory_bytes: 29380
#if 0



#endif // 0

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = (int) 1e5 + 10;
const int INF = (int) 0x3f3f3f3f;
typedef long long LL;
int N,W;
int dp[MAXN];

void work(){
    while(~scanf("%d%d",&N,&W)){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=N;i++){
            int v,w; scanf("%d%d",&v,&w);
            while(w<=W){
                for(int j=W;j>=w;j--){
                    dp[j]=max(dp[j],dp[j-w]+v);
                }
                w<<=1;
                v<<=1;
            }
        }
        printf("%d\n",dp[W]);
    }
}

int main(){
    work();
    return 0;
}



Measured memory_bytes: 3624
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static long[][]memo;static char[][]g;
    static long dp(int id1, int id2) {
        if (id1 == n||id2==m||g[id1][id2]=='#') return 0;
        if (id1==n-1&&id2==m-1)return 1;
        if (memo[id1][id2] != -1) {
            return memo[id1][id2];
        }
        return memo[id1][id2]=(dp(id1+1,id2)+dp(id1,id2+1))%1000000007;
    }
    public  static void main(String[]args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        n= sc.nextInt();
        m = sc.nextInt();
        memo= new long[n][m];
        g= new char[n][m];
        for (long[]x:memo){
            Arrays.fill(x,-1);
        }
        for (int i =0;i<n;i++){
            g[i]=sc.nextLine().toCharArray();
        }
        pw.println(dp(0,0)%1000000007);
       // pw.println(Arrays.deepToString(memo));

      pw.flush();
    }
    static class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException
        {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if(x.charAt(0) == '-')
            {
                neg = true;
                start++;
            }
            for(int i = start; i < x.length(); i++)
                if(x.charAt(i) == '.')
                {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                }
                else
                {
                    sb.append(x.charAt(i));
                    if(dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg?-1:1);
        }

        public boolean ready() throws IOException {return br.ready();}


    }
}

Measured memory_bytes: 41224
#include<bits/stdc++.h>
using namespace std;
int main(){
    char a[6];
    bool b=true;
    for(int i=0;i<6;i++) cin>>a[i];
    for(int i=0;i<3;i++){
        if(a[i]!=a[5-i]) b=false;
    }
    if(b) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
import math
N,H=map(int,input().split())
ab=[[int(x) for x in input().split()] for _ in range(N)]
a,_=max(ab)
B=sorted([b for _,b in ab if b > a], reverse=True)
sb=sum(B)
if sb < H:
	print(len(B)+math.ceil((H-sb)/a))
else:
	B.insert(0, 0)
	for i in range(1, len(B)):
		B[i] += B[i-1]
		if B[i] >= H:
			break
	print(i)


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


int main(){
	int h,w;
	
	scanf("%d %d", &h, &w);
	while(h != 0 && w != 0){
		for(int i = 0 ; i < h ;i++){
			for(int k = 0 ; k < w ; k++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
		
		
		
		scanf("%d %d", &h, &w);
	}
	
	return 0 ;
}


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

int main() {

    string s;
    cin >> s;


    rep(i, s.length())
    {
        if (i%2 == 0)
        {
            if (s[i] == 'L')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            if (s[i] == 'R')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

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

int main() {
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  string Sa,Sb,Sc;
  cin>>Sa>>Sb>>Sc;
  char x=*Sa.begin();
  Sa.erase(Sa.begin());
  while (true) {
    if (x=='a') {
      if (Sa.empty()) {
        cout<<'A'<<endl;
        break;
      }
      x=*Sa.begin();
      Sa.erase(Sa.begin());
    } else if (x=='b') {
      if (Sb.empty()) {
        cout<<'B'<<endl;
        break;
      }
      x=*Sb.begin();
      Sb.erase(Sb.begin());
    } else {
      if (Sc.empty()) {
        cout<<'C'<<endl;
        break;
      }
      x=*Sc.begin();
      Sc.erase(Sc.begin());
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

ll mpow(ll x, ll n) { ll y = 1; for (; n > 0; n /= 2) { y = n % 2 ? y * x % MOD : y; x = x * x % MOD; } return y; }
struct Combination {
    vector<ll> fact, ifact;
    Combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1; for (int i = 0; i < n; ++i) fact[i + 1] = fact[i] * (i + 1) % MOD;
        ifact[n] = mpow(fact[n], MOD - 2); for (int i = n; i > 0; --i) ifact[i - 1] = ifact[i] * i % MOD;
    }
    ll operator ()(int n, int k) { return k < 0 || k > n ? 0 : fact[n] * ifact[n - k] % MOD * ifact[k] % MOD; }
} C(2e6 + 5);

ll f(int r, int c) {
    ll x = ((r + 2) * C(r + c + 2, c) - c - 1 + MOD) % MOD;
    return x * mpow(c + 1, MOD - 2);
}

int main() {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    ll ans = f(r2, c2) - f(r2, c1 - 1) - f(r1 - 1, c2) + f(r1 - 1, c1 - 1);
    write((ans % MOD + MOD) % MOD);
}

Measured memory_bytes: 31488