akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e12 + 5;


int main(){
	string text1, text2;
        cin >> text1 >> text2;
        int N = text1.size(), M = text2.size();
        vector<vector<int>> LCS(N + 1, vector<int>(M + 1, 0));
        for(int onePos = 1; onePos <= N; ++onePos){
            for(int twoPos = 1; twoPos <= M; ++twoPos){
                if(text1[onePos - 1] == text2[twoPos - 1]){
                    LCS[onePos][twoPos] = 1 + LCS[onePos - 1][twoPos - 1];
                }
                else{
                    LCS[onePos][twoPos] = max(LCS[onePos - 1][twoPos],
                    			      LCS[onePos][twoPos - 1]);
                }
            }
        }
        string maxLCS = "";
        int onePos = N, twoPos = M;
       	while(LCS[onePos][twoPos] > 0){
               if(text1[onePos - 1] == text2[twoPos - 1]){
                   maxLCS.push_back(text1[onePos - 1]);
                   onePos--;
                   twoPos--;
               }else if(LCS[onePos - 1][twoPos] == LCS[onePos][twoPos]){
                   onePos--;
               }else{
                   twoPos--;
               }
        }
        reverse(maxLCS.begin(), maxLCS.end());
        cout << maxLCS << endl;
    	return 0;
}

Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define maxn 100001
int n,k,he[maxn],ver[2*maxn],nxt[2*maxn],tot,cnt;
void add(int x,int y){
	ver[++tot]=y;nxt[tot]=he[x];he[x]=tot;
}
int dfs(int x,int fa){
	int maxx=0;
	for(int i=he[x];i;i=nxt[i]){
		if(ver[i]==fa)continue;
		maxx=max(maxx,dfs(ver[i],x));
	}if(x==1)return 0;
	if(maxx==k-1&&fa!=1){
		//cout<<x<<endl;
		cnt++;return 0;
	}else return maxx+1;
}
int main(){
	scanf("%d%d",&n,&k);
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(i!=1)add(i,x),add(x,i);
		else if(x!=1)cnt++;
	}dfs(1,0);
	printf("%d",cnt);
}

Measured memory_bytes: 6912
#include <cstdio>
#include <algorithm>

using namespace std;

int euclid(int a, int b) {
    if (b > a) {
        swap(a, b);
    }

    if (a % b == 0) return b;
    return euclid(b, a % b);
}

int main() {
    int x, y;
    int ans;
    scanf("%d %d", &x, &y);

    ans = euclid(x, y);

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



Measured memory_bytes: 2716
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from math import sqrt

def get_yakusu(n):
    i = int(sqrt(n))
    while i > 0:
        if n // i > 10 ** 9:
            return -1, -1
        if n % i == 0:
            return i, n//i
        i -= 1

def rec(left, right, n, S, a):
    if left == right:
        return left
    mid = (left + right) // 2
    if mid <= n:
        return rec(mid, right, n)
    else:
        return rec(left, mid, n)

def main():
    S = int(input().strip())
    y2 = (S+10**9-1) // 10**9
    y1 = 10**9 * y2 - S
    print("0 0 {} {} {} {}".format(10**9, y1, 1, y2))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int a,b;
    cin >> a >> b;
    cout << a + b/2 << endl;
}   


Measured memory_bytes: 764
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    char a;
    cin>>a;
    a += 1;
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
n,a,b = map(int, input().split())
c = 0
for i in range(1,n+1):
  n4 = i//10**4
  n3 = i//10**3 - n4*10
  n2 = i//10**2 - n4*100 - n3*10
  n1 = i//10**1 - n4*1000 - n3*100 -n2*10
  n0 = i - n4*10000 -n3*1000-n2*100-n1*10
  total = n4+n3+n2+n1+n0
  if total>=a and total<=b:
    c+= i
print(c)

Measured memory_bytes: 3060
--{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Debug.Trace
import Data.Bits
import Control.Monad
--import Data.List
--import Data.Char
--import qualified Data.Set.Strict as Set
--import qualified Data.Map.Strict as Map

main :: IO ()
main = do
  a <- read <$> getLine
  b <- binToInt <$> getLine
  --a `traceShow`
  forM_ (solve a b) $ \s -> do
    print s


solve :: Int -> Integer -> [Integer]
solve n x = map (\i -> func (x `complementBit` i)) $ [n-1, n-2 .. 0]

binToInt :: String -> Integer
binToInt xs = binToInt' 0 xs
  where
    binToInt' !n [] = n
    binToInt' !n (x:xs) = binToInt' (2 * n + (if x == '1' then 1 else 0)) xs

func :: Integer -> Integer
func 0 = 0
func !n = 1 + func (n `mod` fromIntegral(popCount n))


Measured memory_bytes: 13640
#include<bits/stdc++.h>
#define MAX 5002
#define pb push_back
#define For(i,s,e) for (long long i=(s); i<(e); i++)
#define Debug_array(a,n) for (long long i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (long long i=(s); i<=(e); i++)
#define Fod(i,s,e) for (long long i=(s)-1; i>=(e); i--)
#define Mod 1000000007
#define pii pair<long long,long long>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair

using namespace std;

typedef long double ll;

int main(){
	ios_base::sync_with_stdio(false);
	
	long long n;cin>>n;
	ll t,a;cin>>t>>a;
	ll h[n];
	For(i,0,n) cin>>h[i];

	ll answer = 1e9;
	ll index = 0;
	For(i,0,n){
		ll f = t-h[i]*0.006;
		if(abs(f-a)<answer){
			answer = abs(f-a);
			index = i;
		}
	}

	cout<<index+1<<endl;
}

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

int main(){
  string t;
  cin >> t;
  int w=0,s=0,e=0,n=0;
  for(int i=0;i<t.size();i++){
    if(t.at(i)=='W')
      w=1;
    else if(t.at(i)=='N')
      n=1;
    else if(t.at(i)=='E')
      e=1;
    else if(t.at(i)=='S')
      s=1;
  }
  if((n+s==2&&e+w==0)||(n+s==0&&e+w==2)||(n+s+e+w==4))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

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

using namespace std;

const int N = 1234567;

vector <int> g[N], h[N];
int x[N], color[N];
int zero[N];

int dfs(int v) {
  vector <int> children;
  for (int u : g[v]) {
    children.push_back(dfs(u));
  }
  while ((int) children.size() >= 2) {
    int a = children.back();
    children.pop_back();
    int b = children.back();
    children.pop_back();
    h[a].push_back(b);
    h[b].push_back(a);
  }
  if (children.empty()) {
    return v;
  } else {
    zero[v]++;
    return children[0];
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int it = 0; it < 2; it++) {
    for (int i = 0; i < n; i++) {
      g[i].clear();
    }
    int root = -1;
    for (int i = 0; i < n; i++) {
      int x;
      scanf("%d", &x);
      if (x == -1) {
        root = i;
      } else {
        x--;
        g[x].push_back(i);
      }
    }
    dfs(root);
  }
  for (int i = 0; i < n; i++) {
    if (zero[i] == 1) {
      puts("IMPOSSIBLE");
      return 0;
    }
  }
  for (int i = 0; i < n; i++) {
    color[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    if (color[i] == 0 && zero[i] == 0) {
      int b = 0, e = 1;
      x[0] = i;
      color[i] = 1;
      while (b < e) {
        for (int j : h[x[b]]) {
          if (color[j] == 0) {
            color[j] = -color[x[b]];
            x[e++] = j;
          }
        }
        b++;
      }
    }
  }
  puts("POSSIBLE");
  for (int i = 0; i < n; i++) {
    if (i > 0) putchar(' ');
    printf("%d", color[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 70784
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#define EPS 1e-10
using namespace std;

double add(double a,double b){
	if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))return 0.0;
	return a+b;
}

struct P{
	double x,y;
	P(){}
	P(double xx,double yy){
		x=xx;
		y=yy;
	}
	P operator +(P p){
		return P(add(x,p.x),add(y,p.y));
	}
	P operator -(P p){
		return P(add(x,-p.x),add(y,-p.y));
	}
	P operator *(double d){
		return P(x*d,y*d);
	}
	P operator /(double d){
		return P(x/d,y/d);
	}
	double dot(P p){
		return add(x*p.x,y*p.y);
	}
	double det(P p){
		return add(x*p.y,-y*p.x);
	}
	bool same(P p){
		return (add(x,-p.x)==0 && add(y,-p.y)==0);
	}
};

bool on_seg(P p1,P p2,P q){
	return (p1-q).det(p2-q)==0 && (p1-q).dot(p2-q)<=0;
}

P intersection(P p1,P p2,P q1,P q2){
	return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

int n;
P p1[101],p2[101];

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++){
			scanf("%lf %lf %lf %lf",&p1[i].x,&p1[i].y,&p2[i].x,&p2[i].y);
		}
		int cnt=0;
		for(int i=0;i<n;i++){
			vector<P> inter;
			for(int j=0;j<i;j++){
				if((p1[i]-p2[i]).det(p1[j]-p2[j])==0)continue;
				P r=intersection(p1[i],p2[i],p1[j],p2[j]);
				if(r.x>-100.0+EPS && r.x<100.0-EPS && r.y>-100.0+EPS && r.y<100.0-EPS){
					bool flag=true;
					for(int k=0;k<inter.size();k++){
						if(inter[k].same(r))flag=false;
					}
					if(flag)inter.push_back(r);
				}
			}
			cnt+=1+inter.size();
		}
		printf("%d\n",cnt+1);
	}
	return 0;
}

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

int main() {
	int flag = 0;
	string N;
	cin >> N;
	for (int i = 0; i < 3; i++) {
		if (N.at(i) == '7') {
			flag++;
			break;
		}
	}
	if (flag > 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

int main() {
  int n; cin >> n;
  int m=0;
  for(int i=1;i<1001;i++){
    n-=100;
    if(n>=0 && n<=5*i){
      m=1;
      break;
    }
  }
  
  cout << m << endl;

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    double w;
    while(cin>>w)
    {
        int res=0;
        if(w>48)res++;
        if(w>51)res++;
        if(w>54)res++;
        if(w>57)res++;
        if(w>60)res++;
        if(w>64)res++;
        if(w>69)res++;
        if(w>75)res++;
        if(w>81)res++;
        if(w>91)res++;
        switch(res){
            case 0: cout<<"light fly"<<endl;break;
            case 1: cout<<"fly"<<endl;break;
            case 2: cout<<"bantam"<<endl;break;
            case 3: cout<<"feather"<<endl;break;
            case 4: cout<<"light"<<endl;break;
            case 5: cout<<"light welter"<<endl;break;
            case 6: cout<<"welter"<<endl;break;
            case 7: cout<<"light middle"<<endl;break;
            case 8: cout<<"middle"<<endl;break;
            case 9: cout<<"light heavy"<<endl;break;
            case 10: cout<<"heavy"<<endl;break;
        }
    }
}

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

#define ld long double
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("input.txt","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(int i=a ; i<=b ; i++)
#define FORD(i,a,b) for(int i=a ; i>=b ; i--)
#define INF 1000000000
#define ll long long int
#define eps (1e-8)
#define sq(x) ( (x)*(x) )
#define all(x) x.begin(),x.end()
#define flog2(n) 64 - __builtin_clzll(n) - 1
#define popcnt(n) __builtin_popcountll(n)

using namespace std;

typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

const ll K = 1e9 + 7;
ll d[3005], gt[200005], rev[200005];

ll mu(ll a, ll n) {
	if (n == 0) return 1;
	ll q = mu(a, n / 2);

	if (n % 2 == 0) return q * q % K;
	return q * q % K * a % K;
}

ll combi(int n, int k) {
	if (n < k || k < 0) return 0;
	return gt[n] * rev[n - k] % K * rev[k] % K;
}

ll numPaths(int r1, int c1, int r2, int c2) {
	return combi(r2 - r1 + c2 - c1, r2 - r1);
}

struct Data {
	int r, c;
	Data(int __r = 0, int __c = 0): r(__r), c(__c) {}

	bool operator < (const Data & x) {
		if (r != x.r) return r < x.r;
		return c < x.c;
	}
};

vector<Data> data;

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

    gt[0] = rev[0] = 1;

    FOR (i, 1, 200000) {
    	gt[i] = gt[i - 1] * 1ll * i % K;
    	rev[i] = mu(gt[i], K - 2);
    }

    int H, W;
    cin >> H >> W;

    int n;
    cin >> n;
    FOR (i, 1, n) {
    	int r, c;
    	cin >> r >> c;
    	data.pb(Data(r, c));
    }
    sort(all(data));
    ll res = numPaths(1, 1, H, W);

    FOR (i, 0, n - 1) {
    	d[i] = numPaths(1, 1, data[i].r, data[i].c);

    	FOR (j, 0, n - 1) {
    		if (i == j) continue;
    		d[i] = (d[i] - d[j] * numPaths(data[j].r, data[j].c, data[i].r, data[i].c) % K + K) % K;
     	}
     	res = (res - d[i] * numPaths(data[i].r, data[i].c, H, W) % K + K) % K;
     	//cout << d[i] << " ";
    }

    //cout << endl;

    cout << res << endl;



    
	
    return 0;
}

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

using namespace std;

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

    int n;
    cin>>n;

    set<string> items;
    string s;

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

        if(items.find(s)==items.end()){
            items.insert(s);
        }
    }

    cout<<items.size()<<"\n";

    return 0;
}


Measured memory_bytes: 19216
#include<cstdio>
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    if(n>0&&m>0)puts("Positive");
    else if(n<0&&m<0)
    if((m-n)&1)puts("Positive");
    else puts("Negative");
    else puts("Zero");
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


long long num_geq(int thresh, vector<int>& A){
  int N = A.size();
  long long ret = 0;
  for(int i = 0; i < N; i++){
    int thresh_now = thresh - A[i];
    ret += A.end() - lower_bound(A.begin(), A.end(), thresh_now);
  }
  return ret;
}

int main(){
  int N;
  long long M;
  cin >> N >> M;

  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A.begin(), A.end());

  int ok = 0, ng = 1e6;
  while(ng - ok > 1){
    int mid = (ok + ng) / 2;
    //cout << mid << ' ' << num_geq(mid, A) << endl;
    if(num_geq(mid, A) >= M){
      ok = mid;
    }else{
      ng = mid;
    }
  }

  vector<long long> A_sum(N + 1);
  for(int i = 0; i < N; i++){
    A_sum[i + 1] = A_sum[i] + A[i];
  }

  long long ans = 0, cnt = 0;
  for(int i = 0; i < N; i++){
    int start_idx = lower_bound(A.begin(), A.end(), ok - A[i]) - A.begin();
    cnt += N - start_idx;
    ans += static_cast<long long>(A[i]) * (N - start_idx) + (A_sum[N] - A_sum[start_idx]);
  }
  ans -= (cnt - M) * ok;
    

  cout << ans << endl;
}


Measured memory_bytes: 1408
N, P = map(int, input().split())
S = input()
now = 0
hyou = [0] * P
hyou[0] = 1
cnt = 1
ans = 0

if P == 2 or P == 5:
    for i, t in enumerate(S[::-1]):
        temp = int(t)
        if temp % P == 0:

            ans += N - i
    print(ans)
    exit()

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)


Measured memory_bytes: 3500
#include <iostream>
#include <string>
#include <stack>

using namespace std;

char not_k(char a) {
	if (a == '0') {
		return '2';
	} else if(a == '2') {
		return '0';
	} else {
		return '1';
	}
}

char seki(char a, char b) {
	if (a == b) {
		return a;
	} else if (a == '0' || b == '0') {
		return '0';
	} else if (a == '1' || b == '1') {
		return '1';
	} else {
		return '2';
	}
}

char wa(char a, char b) {
	if (a == b) {
		return a;
	} else if (a == '2' || b == '2') {
		return '2';
	} else if (a == '1' || b == '1') {
		return '1';
	} else {
		return '0';
	}
}

bool kaiseki(string a) {
	stack<char> stk1, stk2;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] == '0' || a[i] == '1' || a[i] == '2') {
			char b = a[i];
			if (!stk1.empty() && stk1.top() == '-') {
				stk1.pop();
				b = not_k(b);
			}
			stk2.push(b);
		} else if (a[i] == '-') {
			if (!stk1.empty() && stk1.top() == '-') {
				stk1.pop();
			} else {
				stk1.push(a[i]);
			}
		} else if (a[i] == ')') {
			char p = stk2.top();
			stk2.pop();
			char q = stk2.top();
			stk2.pop();
			char r = stk1.top();
			stk1.pop();
			if (r == '+') {
				p = wa(p, q);
			} else {
				p = seki(p, q);
			}
			stk1.pop();
			if (!stk1.empty() && stk1.top() == '-') {
				stk1.pop();
				p = not_k(p);
			}
			stk2.push(p);
		} else {
			stk1.push(a[i]);
		}
	}
	char k = stk2.top();
	stk2.pop();
	if (!stk1.empty() && stk1.top() == '-') {
		stk1.pop();
		k = not_k(k);
	}
	return k == '2';
}

int main() {
	string a;
	string abc = "012";
	while (cin >> a) {
		if (a == ".") {
			break;
		}
		int counter = 0;
		string b;
		for (int i = 0; i < 3; i++) {
			b = a;
			while (b.find('P') != string::npos) {
				b[b.find('P')] = abc[i];
			}
			for (int j = 0; j < 3; j++) {
				while (b.find('Q') != string::npos) {
					b[b.find('Q')] = abc[j];
				}
				for (int k = 0; k < 3; k++) {
					while (b.find('R') != string::npos) {
						b[b.find('R')] = abc[k];
					}
					if (kaiseki(b)) {
						counter++;
					}
					b = a;
					while (b.find('P') != string::npos) {
						b[b.find('P')] = abc[i];
					}
					while (b.find('Q') != string::npos) {
						b[b.find('Q')] = abc[j];
					}
				}
				b = a;
				while (b.find('P') != string::npos) {
					b[b.find('P')] = abc[i];
				}
			}
			
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
const main = (inputs) => {
  var array1 = inputs[0].split(" ");
  var array2 = inputs[1].split(" ");
  var N = array1[0];
  var M = array1[1];

  var sum = 0;
  array2.forEach((elm) => {
    sum += elm - 0;
  });

  var NGValue = sum / (4 * M);

  var sortArray = array2.filter(v => {
    return Number(v) >= Number(NGValue);
  });
  if (sortArray.length >= M && N > 0 && M > 0) {
    console.log('Yes');
  } else {
    console.log('No');
  }
}
main(require('fs').readFileSync('/dev/stdin', 'UTF-8').trim().split("\n"));

Measured memory_bytes: 21064
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}

int main()
{
    ll x=in();
    cout<<x/500*1000+x%500/5*5<<endl;
}


Measured memory_bytes: 256
/**
 *   author: Shubham Srivastava
 *   created: 01 September 2019  17:30:22
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    string a,b;cin>>a>>b;
    int count = 0;
    for(int i=0;i<a.size();i++)
        if(a[i] == b[i])
            count++;
    cout<<count;
return 0;
}

Measured memory_bytes: 256
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define     loop(n,i,a)     for(int i=a;i<n;i++)
#define     loopR(n,i,a)    for(int i=n-1;i>=a;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=2e6+10,oo=0x3f3f3f3f,MOD=998244353;
const double PI = acos(-1);

void solve(){
    int n;
    cin>>n;
    int cnt[mxN]={};
    loop(101,i,1){
        loop(101,j,1){
            loop(101,k,1){
                cnt[i*i+j*j+k*k+i*j+j*k+i*k]++;
            }
        }
    }
    loop(n+1,i,1)
        cout<<cnt[i]<<Endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();
}

Measured memory_bytes: 11392
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	int n, m;
	cin >> n >> m;

	vector<priority_queue<int>> a(n);

	for (int i = 0; i < m; i++)
	{
		int q, t, x;
		cin >> q >> t;

		switch (q)
		{
			case 0:
				cin >> x;
				a[t].push(x);
				break;

			case 1:
				if (!a[t].empty())
				{
					println(a[t].top());
				}
				break;

			case 2:
				if (!a[t].empty())
				{
					a[t].pop();
				}
				break;
		}
	}
}


Measured memory_bytes: 4132
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(r, &n)
	items := make(map[string]int)
	var s string
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &s)
		items[s]++
	}

	fmt.Println(len(items))
}

// Union-Find
type unionFind struct {
	d []int
}

func newUnionFind(n int) *unionFind {
	uf := new(unionFind)
	uf.d = make([]int, n)
	for i := 0; i < n; i++ {
		uf.d[i] = -1
	}
	return uf
}

func (uf *unionFind) find(x int) int {
	if uf.d[x] < 0 {
		return x
	}
	uf.d[x] = uf.find(uf.d[x])
	return uf.d[x]
}

func (uf *unionFind) unite(x, y int) bool {
	rootX := uf.find(x)
	rootY := uf.find(y)
	if rootX == rootY {
		return false
	}

	if uf.d[rootX] < uf.d[rootY] {
		uf.d[rootX] += uf.d[rootY]
		uf.d[rootY] = rootX
	} else {
		uf.d[rootY] += uf.d[rootX]
		uf.d[rootX] = rootY
	}

	return true
}

func (uf *unionFind) same(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func (uf *unionFind) size(x int) int {
	return -uf.d[uf.find(x)]
}

// mod combination
func modpow(a, n, mod int) int {
	res := 1
	for n > 0 {
		if n%2 != 0 {
			res = res * a % mod
		}
		a = a * a % mod
		n = n / 2
	}
	return res
}

func modcomb(n, a, mod int) int {
	x := 1
	y := 1
	for i := 0; i < a; i++ {
		x = x * (n - i)
		x %= mod
		y = y * (i + 1)
		y %= mod
	}
	return x * modpow(y, mod-2, mod) % mod
}

func modfactorial(n, mod int) int {
	result := 1
	for i := 1; i <= n; i++ {
		result = (result * i) % mod
	}
	return result
}

// Utility

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func primeFactor(x int) map[int]int {
	res := make(map[int]int)
	for i := 2; i*i <= x; i++ {
		for x%i == 0 {
			res[i]++
			x = x / i
		}
	}
	if x != 1 {
		res[x] = 1
	}
	return res
}

func divisor(x int) []int {
	res := make([]int, 0)
	for i := 1; i*i <= x; i++ {
		if x%i == 0 {
			res = append(res, i)
			if i != x/i {
				res = append(res, x/i)
			}
		}
	}
	return res
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x / gcd(x, y) * y
}

func reverseString(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

// Queue ...
type Queue []int

// pop ...
func (q *Queue) empty() bool {
	return len(*q) == 0
}

// push ...
func (q *Queue) push(i int) {
	*q = append(*q, i)
}

// pop ...
func (q *Queue) pop() (int, bool) {
	if q.empty() {
		return 0, false
	} else {
		res := (*q)[0]
		*q = (*q)[1:]
		return res, true
	}
}

// Stack ...
type Stack []int

// pop ...
func (s *Stack) empty() bool {
	return len(*s) == 0
}

// push ...
func (s *Stack) push(i int) {
	*s = append(*s, i)
}

// pop ...
func (s *Stack) pop() (int, bool) {
	if s.empty() {
		return 0, false
	} else {
		index := len(*s) - 1
		res := (*s)[index]
		*s = (*s)[:index]
		return res, true
	}
}


Measured memory_bytes: 17560
package main

import(
  "fmt"
)

func main() {
  var s string
  fmt.Scan(&s)
  
  if s == "Sunny" {
    fmt.Println("Cloudy")
  }else if s == "Cloudy" {
    fmt.Println("Rainy")
  }else if s == "Rainy" {
    fmt.Println("Sunny")
  }
  
}

Measured memory_bytes: 512
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char prev = s.charAt(0);
        int count = 0;
        for(int i = 1; i < s.length(); i++) {
            if(prev == s.charAt(i)) {
                continue;
            } else {
                prev = s.charAt(i);
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 24212
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits>
int main(void){
    long N;
    std::cin >> N;
    if(N%1000!=0){
        std::cout << (N/1000+1)*1000-N << std::endl;
    }else{
        std::cout << 0 << std::endl;
    }
    return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner std = new Scanner(System.in);
        int defaultpip[] = new int[6];
 
        for(int i=0; i<6; i++){
            defaultpip[i] = Integer.parseInt(std.next());
        }
        Dice dc1 = new Dice(defaultpip);
 
        int defaultpip2[] = new int[6];
        for(int i=0; i<6; i++){
            defaultpip2[i] = Integer.parseInt(std.next());
        }
        Dice dc2 = new Dice(defaultpip2);

        String query[] = {"S", "W", "N", "E"};
 
        boolean same = false;
        for(int i = 0; i<1000; i++){
            if(dc1.issame(dc2)){
                same = true; break;
            }else{
                dc1 = dc1.newnowpips(query[(int)(Math.random()*4)]);
            }
        }
        if(same){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}
 
class Dice {
    int pips[];
    int nowpip;
    int spip;
    int epip;
    int wpip;
    int npip;
    int rpip;
 
    public Dice(int pip[]){
        this(pip, 0, 1, 2, 3, 4, 5);
    }
 
    public Dice(int pip[], int now, int s, int e, int w, int n, int r){
        pips = pip;
        nowpip = now;
        spip = s;
        epip = e;
        wpip = w;
        npip = n;
        rpip = r;
    }
 
    public Dice newnowpips(String query){
        if(query.equals("N")){
            return new Dice(pips,spip,rpip,epip,wpip,nowpip,npip);
        }else if(query.equals("E")){
            return new Dice(pips,wpip,spip,nowpip,rpip,npip,epip);
        }else if(query.equals("S")){
            return new Dice(pips,npip,nowpip,epip,wpip,rpip,spip);
        }else if(query.equals("W")){
            return new Dice(pips,epip,spip,rpip,nowpip,npip,wpip);
        }else { //clockwise
            return new Dice(pips,nowpip,epip,npip,wpip,spip,rpip);
        }
    }
 
    public String showdice(){
        return pips[nowpip] +" "+ pips[spip] +" "+ pips[epip] +" "+ pips[wpip] +" "+ pips[npip] +" "+ pips[rpip];
    }
 
    public boolean issame(Dice d2){
        return showdice().equals(d2.showdice());
    }
}


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

int main(){
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());

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

  int c;
  c = a*b;

  if (c%2==0){
    cout<<"Even"<<endl;
  }  
  else{
    cout<<"Odd"<<endl;
  }

}

Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

d,n = inpl()
res = n*100**(d)
if n == 100:
    res += 100**(d)
print(res)

Measured memory_bytes: 5196
#include <stdio.h>
int main(){
	int a,b,c=0,d=0;
	scanf("%d",&a);
	for(int i=0;i<a;i++)
	{
		scanf("%d",&b);
		if(b>=c)
		{
			c=b;
			d++;
		}
	}
	printf("%d",d);
}

Measured memory_bytes: 128
#include <stdio.h>
char dp[100][100][100];
void solve() {
	int i, j, k;
	for(i = 0; i < 100; ++ i) for(j = 0; j < 100; ++ j) for(k = 0; k < 100; ++ k) dp[i][j][k] = ' ';
	dp[0][0][0] = '#';
	dp[1][1][0] = '#';
	dp[1][0][0] = '#';
	dp[1][0][1] = '#';
	for(i = 2; i < 100; ++ i) {
		for(j = 0; j < i + 1; ++ j) {
			dp[i][j][0] = '#';
			dp[i][0][j] = '#';
		}
		dp[i][1][i] = '#';
		for(j = 0; j < i - 1; ++ j) for(k = 0; k < i - 1; ++ k) dp[i][j + 2][k + 2] = dp[i - 2][i - 2 - j][i - 2 - k];
	}
}
int main() {
	int N, I;
	int n, i, j;
	scanf("%d", &N);
	solve();
	scanf("%d", &n);
	for(i = 0; i < n; ++ i) {
		for(j = 0; j < n; ++ j) printf("%c", dp[n - 1][i][j]);
		printf("\n");
	}
	for(I = 1; I < N; ++ I) {
		scanf("%d", &n);
		printf("\n");
		for(i = 0; i < n; ++ i) {
			for(j = 0; j < n; ++ j) printf("%c", dp[n - 1][i][j]);
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1544
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	s <- getLine
	print $ ( last $ elemIndices 'Z' s ) - ( head $ elemIndices 'A' s ) + 1


Measured memory_bytes: 13820
N, K = map(int, input().split())
R = N - K

if R == 0: #赤いボールが無い時
    print (1)
    for _ in range(1, K):
        print (0)
    exit()

if K == 1: #青いボールが1つのとき
    print (R+1)
    exit()

for i in range(1, K+1): #K回答えを出力
    if i > R+1:
        print (0)
        continue
    if i >= 2:
        position = ((position * (R + 1 - (i-1))) // i)
        a = position%(7 + 10 ** 9)
        boal = ((boal * (K - (i-1)))// (i-1))
        b = boal%(7 + 10 ** 9) 
        print ((a * b)%(7 + 10 ** 9))
    elif i == 1:
        position = R + 1
        boal = 1
        print (R+1)
    

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int n;
vvint g;
priority_queue<int> q;
vint ans;

void bfs(int s) {
    queue<int> q_;
    q_.push(s);
    while (!q_.empty()) {
        int v = q_.front(); 
        q_.pop();
        ans[v] = q.top();
        q.pop();
        for (int n_v : g[v]) {
            if (ans[n_v] != -1) continue;
            q_.push(n_v);
        }
    }
}

int main() {
    cin >> n;
    g.resize(n);
    ans.assign(n,-1);
    rep(i,n-1) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    rep(i,n) {
        int x; cin >> x;
        q.push(x);
    }
    bfs(0);
    int sum = 0;
    rep(i,n) {
        if (i == 0) continue;
        sum += ans[i];
    }
    cout << sum << endl;
    rep(i,n) cout << ans[i] << " ";
}


Measured memory_bytes: 4096
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct Point {
	long long x, y;

	Point (long long x = 0, long long y = 0) : x(x), y(y) {}

	void in() {
		scanf("%lld%lld", &x, &y);
		x *= 2, y *= 2;
	}

	Point operator + (const Point &a) const {
		return Point(x + a.x, y + a.y);
	}

	Point operator - (const Point &a) const {
		return Point(x - a.x, y - a.y);
	}

	Point operator * (const long long &k) const {
		return Point(x * k, y * k);
	}

	Point operator / (const long long &k) const {
		return Point(x / k, y / k);
	}

	bool operator < (const Point &a) const {
		return x < a.x || (x == a.x && y < a.y);
	}

	long long len2() const {
		return x * x + y * y;
	}

	Point turn90() const {
		return Point(-y, x);
	}
};

long long dot(const Point &a, const Point &b) {
	return a.x * b.x + a.y * b.y;
}

long long det(const Point &a, const Point &b) {
	return a.x * b.y - a.y * b.x;
}

struct Line {
	Point a, b;

	Line(Point a, Point b) : a(a), b(b) {}
};

bool project(const Point &p, const Line &l, Point &q) {
	long long dt = dot(p - l.a, l.b - l.a);
	Point pp = (l.b - l.a) * dt;
	long long d = (l.b - l.a).len2();
	if (pp.x % d != 0 || pp.y % d != 0) {
		return false;
	}
	q = l.a + pp / d;
	return true;
}

bool reflect(const Line &l, const Point &p, Point &q) {
	if (!project(p, l, q)) {
		return false;
	}
	q = q + q - p;
	return true;
}

bool onLine(const Line &l, const Point &p) {
	return det(p - l.a, l.b - l.a) == 0;
}

const int N = 1005;

int n;

set<Point> tr;

Point p[N];

bool sameLine() {
	for (int i = 2; i < n; ++i) {
		if (det(p[i] - p[0], p[1] - p[0]) != 0) {
			return false;
		}
	}
	return true;
}

bool check(const Line &l) {
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (onLine(l, p[i])) {
			++cnt;
		} else {
			Point q;
			if (!reflect(l, p[i], q)) {
				return false;
			}
			if (!tr.count(q)) {
				return false;
			}
		}
	}
	return cnt <= 2;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		p[i].in();
		tr.insert(p[i]);
	}
	if (sameLine()) {
		puts("No");
		return 0;
	}
	bool ans = false;
	for (int i = 1; i < n; ++i) {
		Point m = (p[0] + p[i]) / 2,
			  mm = m + (p[i] - p[0]).turn90();
		ans = ans || check(Line(m, mm));
	}
	for (int i = 2; i < n; ++i) {
		Point m = (p[1] + p[i]) / 2,
			  mm = m + (p[i] - p[1]).turn90();
		ans = ans || check(Line(m, mm));
	}
	ans = ans || check(Line(p[0], p[1]));
	puts(ans ? "Yes" : "No");
	return 0;
}

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

using namespace std;

using ll = int64_t;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===




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

	int N;
	cin >> N;
	string S;
	cin >> S;

	if (N % 2 == 1) {
		cout << "No" << endl;
		return 0;
	}
	
	bool ans = true;
	for (int i = 0; i < N / 2; ++i) {
		if (S[i] != S[i + N / 2]) {
			ans = false;
			break;
		}
	}

	cout << (ans ? "Yes" : "No") << endl;

	return 0;
}

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

int main()
{
    int n, p, t, a, x;
    cin >> n >> p;

    list<int> l[n];
    list<int>::iterator it;

    while (p--)
    {
        cin >> t;
        if (t == 0)
        {
            cin >> a >> x;
            l[a].push_back(x);
        }
        if (t == 1)
        {
            cin >> a;
            for (it = l[a].begin(); it != l[a].end(); it++)
            {
                if (it != l[a].begin())
                    cout << " ";
                cout << *it;
            }
            cout << endl;
        }
        if (t == 2)
        {
            cin >> a >> x;
            it = l[x].end();
            l[x].splice(it, l[a]);
        }
    }
    return 0;
}


Measured memory_bytes: 18660
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef long long ll;

int asc(const void *arg1,const void *arg2) {return *((int *)arg2)-*((int *)arg1);}

int main(){
    int n,a[300001];
    ll sum=0;
    scanf("%lld",&n);
    for(ll i=0;i<3*n;i++) scanf("%lld",&a[i]);
    qsort(a,3*n,sizeof(int),asc);
    for(ll i=0;i<n;i++) sum+=a[2*i+1];
    printf("%lld",sum);

    return 0;
}

Measured memory_bytes: 4248
n,t = map(int,input().split())
a = [0] * (t+1)
for _ in range(n):
	l, r = map(int,input().split())
	a[l] += 1
	a[r] -= 1

ans = 0
current = 0
for i in range(t+1):
	current += a[i]
	ans = max([ans, current])

print(ans)


Measured memory_bytes: 6388
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <sstream> 
#include <cctype>
#include <stack>
#include <queue>
#include <cstring>
#include <map>
 
using namespace std;

int main(){

	int n,m,k;
	cin>>n>>m>>k;

	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			int x=i*n + j *m - 2*i*j;
			if(x==k){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}

	cout<<"No"<<endl;

	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



M = Mod(10**9 + 7)
m = 10**9 + 7
fact = [1] * (2 * (10**5) + 1)
fact_inv = [0] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact[i] = M.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], m-2, m)


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    memo = defaultdict(dict)

    def f(u, p, flag=False):
        if u in memo and p in memo[u]:
            return memo[u][p]
        r = 1
        n = 1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.mul(r, fact_inv[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.mul(r, fact_inv[na-1])
            r = M.mul(r, fact[n-1])

        memo[u][p] = n, r
        return n, r

    f(1, 0, True)

    for i in range(1, N+1):
        print(f(i, 0, False)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    slv(N, AB)

    # N = (10**5) * 2
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))


if __name__ == '__main__':
    main()


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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const double PI = 3.1415926535;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;


int main(){
    string s;
    cin >> s;
    int n = s.size();
    reverse(s.begin(),s.end());
    vector<int>cnt(2019);
    int now = 0;
    ll ans = 0;
    int digit = 1;
    cnt[0]++;
    rep(i, 0, n){
        now = (now+(s[i]-'0')*digit)%2019;
        ans += cnt[now];
        cnt[now]++;
        digit = (digit*10) % 2019;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3748
from collections import deque

S = str(input())
Q = int(input())
Query = [list(map(str, input().split())) for _ in range(Q)]

sArry = deque(S)
rFlag = False
for i in range(Q):
    if Query[i][0] == '1':
        rFlag = (rFlag == False)
        
    else:
        if rFlag:
            if Query[i][1] == '1':
                sArry.append(Query[i][2])
            else:
                sArry.appendleft(Query[i][2])
        else:
            if Query[i][1] == '1':
                sArry.appendleft(Query[i][2])
            else:
                sArry.append(Query[i][2])
            
#    print("  ", i, rFlag, "".join(sArry), Query[i])



if rFlag:
    print("".join(reversed(sArry)))
else:
    print("".join(sArry))


Measured memory_bytes: 119356
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,x,y;
  cin>>n>>m>>x>>y;
  vector<int> X(n);
  vector<int> Y(m);
  for(int i=0;i<n;i++)cin>>X[i];
  for(int i=0;i<m;i++)cin>>Y[i];
  int max_X=X[0];
  for(int i=0;i<n;i++){
    if(max_X<X[i])max_X=X[i];
  }
  int min_Y=Y[0];
  for(int i=0;i<m;i++){
    if(Y[i]<min_Y)min_Y=Y[i];
  }
  if(x<max_X&&max_X<min_Y&&min_Y<y)cout<<"No War"<<endl;
  else cout<<"War"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair
#define M 1000000007
#define all(v) (v).begin(),(v).end()
const int N = 3e5 + 5;
int main(){
	int l , r , d;
	cin >> l >> r >>d;
	cout << r/d - (l-1)/d <<endl;
	
}

Measured memory_bytes: 3632
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:#代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:#要素数の少ない方へMergeする
                self.table[s1] += self.table[s2]#子の和を増やす(-)
                self.table[s2] = s1#Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return
    def size(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return abs(self.table[x])
N,M = [int(n) for n in input().split()]
UF = UnionFind(N)
a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = [int(n)-1 for n in input().split()]
ans = [0]*M
ans[M-1] = int(N*(N-1)/2)
for i in range(M-1,0,-1):
    if(UF.find(a[i]) != UF.find(b[i])):
        ans[i-1] = ans[i] - UF.size(a[i])*UF.size(b[i])
    else:
        ans[i-1] = ans[i]
    UF.union(a[i],b[i])
for i in range(M):
    print(ans[i])


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

int main(void){
    int a;
    int b;
    int c;
    int d;
    int ans;

    cin >> a;
    cin >> b;
    cin >> c;

    d = a - b ;
    ans = c - d;

    if (ans < 0){
        ans = 0;
    }

    cout << ans << "\n";


return 0;
}

Measured memory_bytes: 256
#048-C
n,x=map(int,input().split())
a=list(map(int,input().split()))
a_sum=sum(a)
ans=0
if a[0]>x:
    a[0]=x
    ans+=a[0]-x
else:
    ans+=a[0]
for i in range(n-1):
    if a[i]+a[i+1]>x:
        a[i+1]-=a[i+1]+a[i]-x
        ans+=a[i+1]
print(a_sum-sum(a))

Measured memory_bytes: 14588
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, a, n) for (int i = (a); i < (int)(n); i++)
#define repc(i, a, n) for (int i = (a); i <= (int)(n); i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init)                                              \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
#define DBG(str) cerr << (str) << endl;
int main() {
  int n, x;
  cin >> n >> x;
  vector<int> m(n);
  ll sum = 0;
  int mi = 1e6;
  rep(i, 0, n) {
    cin >> m[i];
    sum += m[i];
    mi = min(mi, m[i]);
  }
  int num = (x - sum) / mi;
  cout << n + num;

  return 0;
}


Measured memory_bytes: 256
n = int(input())
lst = set()

for i in range(2, int(n ** (1 / 2)) + 1):
  k = i
  while k <= n * i:
    k *= i
    if n % k == k // i:
      lst.add(i)
      break

for i in range(2, int(n ** (1 / 2)) + 1):
  if n % i == 1:
    lst.add(i)
    lst.add((n - 1) // i)

if n > 2:
  lst.add(n - 1)
lst.add(n)
print(len(lst))

Measured memory_bytes: 3188
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> H >> W >> K;
	vector<string>s(H);
	for (auto &i : s)cin >> i;
	for (int i = 0; i < 1 << H; i++) {
		for (int j = 0; j < 1 << W; j++) {
			int num = 0;
			for (int k = 0; k < H; k++) {
				for (int l = 0; l < W; l++) {
					if ((i >> k) & 1)continue;
					if ((j >> l) & 1)continue;
					num += s[k][l]=='#';
				}
			}
			if (num == K)N++;
		}
	}
	cout << N << endl;
}


Measured memory_bytes: 3616