akhauriyash/Code-Regression huggingface dataset:
arr = []
arr.append(input())
arr.append(input())
arr.append(input())
arr.append(input())
arr.append(input())

min = 0

count = 0

num = 0
num_val = 9
for i in range(5):
    if int(arr[i]) % 10 < num_val and int(arr[i]) % 10 != 0:
        num = i
        num_val = int(arr[i]) % 10


list = []

for i in range(5):
    if i != num:
        list.append(arr[i])
list.append(arr[num])


for i in range(5):
    count += int(list[i])
    if i == 4:
        pass
    else:
        if int(list[i]) % 10 == 0:
            pass
        else:
            count += 10 - (int(list[i])%10)

print(count)


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

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

  long count =0;
  for(int i=0;i<N;i++){
    int m = min(A[i],B[i]);

    A[i] -= m;
    B[i] -= m;
    count += m;

    m = min(A[i+1],B[i]);
    A[i+1] -= m;
    B[i] -= m;
    count += m;

    }
  cout << count << endl;
  }


Measured memory_bytes: 1024
m,n=map(int,input().split())
a=b=""
if m!=n :
    for i in range(m) :
        a=a+str(n)
    for i in range(n) :
        b=b+str(m)
    if len(a)>len(b) :
        print(a)
    else :
        print(b)
else :
    for i in range(m) :
        a=a+str(n)
    for i in range(n) :
        b=b+str(m)
    print(a)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int X = scan.nextInt();
        int A = scan.nextInt();

        if (X < A) {
            System.out.println(0);
        } else {
            System.out.println(10);
        }
        scan.close();
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    long long N;
    cin >> N;
    long long ans = N-1;
    for (long long i = 1; i*i <= N; ++i) {
        if (N%i == 0) {
            ans = min(ans, N / i + i - 2);
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	Scanner sc = new Scanner(System.in);
	int a,b,c,d,e,f,k,l,m,n,x,y,z;
	String[] S;

	Main(){
		// 整数の入力
		n = sc.nextInt();
		double t=n/2;
		if(n%2==1)t+=1;

		// 出力
		System.out.println(t/n);
	}

	public static void main(String[] args){
		new Main();
	}
}

Measured memory_bytes: 21204
#include <iostream>

using namespace std;

int main(){

        int n,x;
        int counter = 0;

        while(true){
                cin >> n >> x;
                if(n == 0 && x == 0)break;
                for(int i = 1; i <= (n - 2); i++)
                        for(int j = (i + 1); j <= (n - 1); j++)
                                for(int k = (j + 1); k <= n; k++)
                                        if((i + j + k) == x) counter++;

                cout << counter << "\n";
                counter = 0;
        }

        return 0;
}

Measured memory_bytes: 1160
def getNum(x):
    sum = 0
    for i in range(len(str(x))):
        sum += int(str(x)[i])
    return sum

n,a,b = map(int, [int(i) for i in input().split()])
sum = 0
for i in range(1,n+1):
    if a <= getNum(i) <= b:
        sum += i
print(sum)


Measured memory_bytes: 3060
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public final class Main {
	public static void main(String [] args){
		Scanner s = new Scanner(System.in);
		int arraySize = Integer.parseInt(s.nextLine().trim());
		ArrayList<String> words = new ArrayList();
		for (int i = 0; i < arraySize; i++){
			words.add(s.nextLine().trim());
		}
		ArrayList<ArrayList<Character>> keeper = new ArrayList();
		for (int i = 0; i < arraySize; i++){
			ArrayList<Character> temp = new ArrayList();
			char[] tempArr = words.get(i).toCharArray();
			for (int x = 0; x < tempArr.length; x++){
				temp.add(tempArr[x]);
			}
			keeper.add(temp);
		}
		ArrayList<Character> resultWords = new ArrayList();
		for (char c : keeper.get(0)){
			boolean shouldAdd = true;
			for (int index = 1; index < keeper.size(); index++){
				ArrayList<Character> arr = keeper.get(index);
				if (arr.contains(c)){
					arr.remove((Object)c);
				} else {
					shouldAdd = false;
				}
			}
			if (shouldAdd){
				resultWords.add(c);
			}
		}
		String result = "";
		while (!resultWords.isEmpty()){
			char c = findLeast(resultWords);
			result += c;
			resultWords.remove((Object)c);
		}
		System.out.println(result);
	}
	
	public static char findLeast(ArrayList<Character> chars){
		char result = 'z';
		for (char c : chars){
			if (c < result){
				result = c;
			}
		}
		return result;
	}
}



Measured memory_bytes: 21716
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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

map<char, int> mp;

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

  string s;
  cin >> s;

  REP(i,s.size()) mp[s[i]]++;

  if(mp['N'] > 0 && mp['S'] > 0 && mp['E'] > 0 && mp['W'] > 0) cout << "Yes" << endl;
  else if(mp['N']>0 && mp['S']>0){
    if(mp['E']>0 || mp['W']>0) cout << "No" << endl;
    else cout << "Yes" << endl;
  }
  else if(mp['E']>0 && mp['W']>0){
    if(mp['N']>0 || mp['S']>0) cout << "No" << endl;
    else cout << "Yes" << endl;    
  }else{
    cout << "No" << endl;
  }
  
  /*
  for(auto e: mp){  
  }
  
  if(mp['N'] == mp['S'] && mp['W'] == mp['E']) cout << "Yes" << endl;
  else cout << "No" << endl;
  */

  
  
  return 0;
}


/*
yes 
文字n,s or e,w
文字n,s,e,w

 */


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	double h;
	int n;
	while(scanf("%lf",&h)!=EOF){
		for(n=1;;n++){
			if(2*9.8*(5*n-5)>=h*h){
				printf("%d\n",n);
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 628
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int A, B;
  cin >> A >> B;

  if (A < B) {
    if (1 < B - A) {
      cout << B + B - 1 << endl;
    } else {
      cout << B + A << endl;
    }
  } else {
    if (1 < A - B) {
      cout << A + A - 1 << endl;
    } else {
      cout << A + B << endl;
    }
  }

}

Measured memory_bytes: 256
n, y = gets.chomp.split.map(&:to_i)

(n + 1).times do |i|
  (n - i + 1).times do |j|
    k = n - i - j
    if i * 10000 + j * 5000 + k * 1000 == y
      puts "#{i} #{j} #{k}"
      exit
    end
  end
end

puts '-1 -1 -1'


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

int gcd(int x, int y) {
	return (x % y) ? gcd(y, x % y): y;
}
int main() {
	int K;
	cin >> K;
	int64_t sum = 0;
	for(int a = 1; a <= K; a++) {
		for(int b = 1; b <= K; b++) {
			for(int c = 1; c <= K; c++) {
				sum += gcd(a, gcd(b,c));
			}
		}
	}
	cout << sum << endl;
}

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

int main()
{
	string moji, a;
	int m, i, n;

	while (cin >> moji) {
		if (moji == "-")break;

		cin >> m;

		for (i = 0; i < m; i++) {
			cin >> n;
			a = moji.substr(0, n);
			moji = moji.erase(0, n) + a;
		}
		cout << moji << endl;
	}
    return 0;
}




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

int main() {
  int H;
  int num;
  
  cin>>H>>num;
  int A[num];
  
  for(int i=0; i<num; i++){
    cin>>A[i];
  }
  
  for(int j=0; j<num; j++){
    H -= A[j];
  }
  
  if(H > 0){
    cout <<"No"<<endl;
  }else{
    cout <<"Yes"<<endl;
  }
  
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

#define ll long long
#define rep(i, n) for (ll i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)



int main()
{   
    string pd;
    cin >> pd;
    int size;
    size = pd.size();
    rep(i, size) {
        if (pd[i] == '?') {
            if (i == 0) {
                pd.replace(i,1,"D");
            } else if (i > 0 && pd[i-1]!='P' && pd[i+1]=='D') {
                pd.replace(i,1,"P");
            } else {
                pd.replace(i,1,"D");
            }
        }
    }
    cout << pd << endl;
}

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

#define MAX 2000000

int H;
int A[MAX + 1] = {};

int left(int i) {
    return 2 * i;
}
int right(int i) {
    return 2 * i + 1;
}

void maxHeapify(int i) {
    int l, r, largest;
    l = left(i);
    r = right(i);
    
    if(l <= H && A[l] > A[i]) largest = l;
    else largest = i;
    if(r <= H && A[r] > A[largest]) largest = r;
    
    if(largest != i) {
        int tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        maxHeapify(largest);
    }
}

int main(void) {
    cin >> H;
    
    for(int i = 1; i <= H; ++i) cin >> A[i];
    
    for(int i = H / 2; i >= 1; --i) maxHeapify(i);
    
    for(int i = 1; i <= H; ++i) cout << ' ' << A[i];
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 5052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll N,u,v,ans=-1;
vector<vector<ll>> tree(100010);
vector<ll> distv(100010,-1);
vector<ll> distu(100010,-1);
void bfs(ll t,vector<ll> &dist){
    queue<ll> q;
    dist.at(t)=0;
    q.push(t);
    while(!q.empty()){
        ll i=q.front();
        q.pop();
        for(auto j:tree.at(i)){
            if(dist.at(j)<0){
                q.push(j);
                dist.at(j)=dist.at(i)+1;
            }
        }
    }
    return;
}
void Main(){
    cin>>N;
    For(i,0,N-1){
        ll a,b;cin>>a>>b;a--;b--;
        tree.at(a).push_back(b);
        tree.at(b).push_back(a);
    }
    bfs(0,distv);
    bfs(N-1,distu);
    int u=0,v=0;
    For(i,0,N) (distv.at(i)<=distu.at(i) ? v : u)++;
    cout<<(v>u?"Fennec":"Snuke")<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 8108
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;
const int LOG_N = 17;

vector<int> G[MAX_N];

int par[LOG_N][MAX_N];
int depth[MAX_N];

void dfs(int u,int p,int d)
{
    par[0][u] = p;
    depth[u] = d;
    rep(i,G[u].size()){
        if(G[u][i] != p){
            dfs(G[u][i],u,d+1);
        }
    }
}

int lca(int u,int v)
{
    if(depth[u] > depth[v]){
        swap(u,v);
    }
    rep(i,LOG_N){
        if((depth[v] - depth[u]) >> i & 1){
            v = par[i][v];
        }
    }
    if(u == v){
        return u;
    }
    for(int i=LOG_N-1;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

int main()
{
    int n;
    cin >> n;
    rep(i,n){
        int m;
        scanf("%d",&m);
        rep(j,m){
            int x;
            scanf("%d",&x);
            G[i].pb(x);
        }
    }
    dfs(0,-1,0);
    rep(i,LOG_N-1){
        rep(j,n){
            if(par[i][j] < 0){
                par[i+1][j] = -1;
            }else{
                par[i+1][j] = par[i][par[i][j]];
            }
        }
    }
    int q;
    cin >> q;
    rep(i,q){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

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

using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;

int main() {
	int R, G, B, N;
	cin >> R >> G >> B >> N;

	long long ans = 0;
	for (int r = 0; r <= N / R; r++)
		for (int g = 0; g <= (N - R * r) / G; g++)
			if ((N - R * r - G * g) % B == 0)
				ans++;

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


Measured memory_bytes: 256
if __name__ == "__main__":
    n, m = map(int, input().split())
    sc = list()
    for i in range(m):
        sc.append(list(map(int, input().split())))

    for i in range(1000):
        s = str(i).zfill(3)
        if n == 3 and s[0] == '0':
            continue
        if n == 2 and s[1] == '0':
            continue
        flag = 0
        for j in range(m):
            if str(sc[j][1]) != s[sc[j][0]-1 + (3-n)]:
                flag = 1
        if flag == 0:
            print(i)
            exit()

    print('-1')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 100000005
#define MAX 5001
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);
 
int a[1002][1002];
int dp[1002][1002];
int main(){
    int h, w, n;
    while(1){
    scanf("%d%d%d", &h, &w, &n);
    if(!h)break;
    fill((int*)a, (int*)(a+1002), 0);
    fill((int*)dp, (int*)(dp+1002), 0);
    for(int i = 1;i <= h;i++)
    for(int j = 1;j <= w;j++)scanf("%d", &a[i][j]);
    n--;dp[1][1] = n;
    for(int i = 1;i <= h;i++){
        for(int j = 1;j <= w;j++){
            dp[i][j] += dp[i][j-1]/2;
            if(a[i][j-1] == 1)dp[i][j] += dp[i][j-1]%2;
            dp[i][j] += dp[i-1][j]/2;
            if(a[i-1][j] == 0)dp[i][j] += dp[i-1][j]%2;
        }
    }
     
    int y = 1, x = 1, t, f;
    while(y <= h && x <= w){
        f = a[y][x];
        if(dp[y][x]%2)f = !f;
        if(f == 0)y++;
        else x++;
    }
    printf("%d %d\n", y, x);
    }
    return 0;
}

Measured memory_bytes: 11044
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
int ud[100001];
int vd[100001];
// 深さ優先探索
vector<bool> seen;
void udfs(const Graph &G, int v , int l) {
  //cout << v << endl;
    seen[v] = true; // v を訪問済にする
    ud[v] = l;
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        udfs(G, next_v , l+1); // 再帰的に探索
    }
}
void vdfs(const Graph &G, int v , int l) {
  //cout << v << endl;
    seen[v] = true; // v を訪問済にする
    vd[v] = l;
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        vdfs(G, next_v , l+1); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数
    int N; cin >> N;
  int u,v;
  cin >> u >> v;
  if(u==v){cout << 0 << endl;return 0;}
//cout << N << endl;
    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N+1);
  //cout << N << endl;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
  

    // 頂点 0 をスタートとした探索
    seen.assign(N+1, false); // 全頂点を「未訪問」に初期化
    udfs(G,u,0);
  seen.assign(N+1,false);
  vdfs(G,v,0);
 int  ans = 0;
  for(int i=0; i<N; i++){
    if(ud[i+1]<vd[i+1]){
    ans = max(ans,vd[i+1]);
    }
  }
  cout << ans-1 << endl;
 
                           
                           
                        
  
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

ll n;
map<pair<ll,ll>,vector<pair<ll,ll>>> mp;
map<pair<ll,ll>,ll> vdist;
map<pair<ll,ll>,ll> seen;

ll dfs(ll pi, ll pj)
{
    if(seen[make_pair(pi,pj)] == 2) return vdist[make_pair(pi,pj)];
    ll dist = vdist[make_pair(pi,pj)];
    seen[make_pair(pi,pj)] = 1;
    if(!mp.count(make_pair(pi,pj))){
        seen[make_pair(pi,pj)] = 2;
        return 0;
    }
    ll tmp = 0;
    for(auto x:mp[make_pair(pi,pj)]){
        ll ni = x.first;
        ll nj = x.second;
        if(seen[make_pair(ni,nj)] == 1){
            cout << -1 << endl;
            exit(0);
        }
        tmp = max(tmp,dfs(ni,nj) + 1);
    }
    seen[make_pair(pi,pj)] = 2;
    return vdist[make_pair(pi,pj)] = tmp;
}

int main()
{
    ll i,j;
    cin >> n;
    for(i = 0;i < n;++i){
        ll pi = 0, pj = 0;
        rep(j,n-1){
            ll k;
            cin >> k;
            --k;
            ll ni = min(i,k);
            ll nj = max(i,k);
            mp[make_pair(pi,pj)].emplace_back(ni,nj);
            pi = ni;    pj = nj;
        }
    }
    vdist[make_pair(0,0)] = 0;
    cout << dfs(0,0) << endl;
    return 0;
}


Measured memory_bytes: 133120
#include<stdio.h>
#define N 100000

int main(void){
  int i,num,j,k;
  char r[5],a[5];
  char hoge;
  int hit[N],blow[N];

  for(i=0;;i++){
    scanf("%s",&r);
    scanf("%s",&a);
    if(r[0]=='0' && a[0]=='0')
      break;
    hit[i]=0;
    blow[i]=0;

    for(j=0;j<4;j++)
      if(r[j]-'0'==a[j]-'0')
        hit[i]++;

    for(j=0;j<4;j++)
      for(k=0;k<4;k++)
        if(j!=k && r[j]==a[k])
          blow[i]++;
  }
  num=i;
  for(i=0;i<num;i++){
    printf("%d ",hit[i]);
    printf("%d\n",blow[i]);
  }
  return 0;
}

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

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

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

    ll sum=0;
    rep(i,n){
        rep(j,n){
            rep(h,n){
                sum += gcd(i,gcd(j,h));
            }
        }
    }

    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 3596
fn input() -> i32 {
    let s = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    };
    let mut integers = s.split_whitespace();
    let integer: i32 = integers.next().unwrap().parse().unwrap();
    integer
}
fn input_char() -> char {
    let s = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    };
    let ch: char = {
        let mut tmp: char = 'a';
        for c in s.chars() {
            tmp = c
        }
        tmp
    };
    ch
}

fn main() {
    let b: char = input_char();
    if b == 'A' {
        println!("T");
    }
    else if b == 'T' {
        println!("A");
    }
    else if b == 'G' {
        println!("C");
    }
    else {
        println!("G");
    }
}


Measured memory_bytes: 4352
n,x = map(int,input().split())
a = list(map(int,input().split()))
a_abs = []
for i in range(n):
    a_abs.append(abs(a[i]-x))

def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a

cnt = a_abs[0]
for i in range(1,n):
    cnt = gcd(cnt, a_abs[i])
print(cnt)



Measured memory_bytes: 14252
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node{
  int parent;
  int left;
  int right;
};

struct Node T[MAX];
int n, dep[MAX], hei[MAX];

void setDepth(int u,int d){
  if(u == NIL) return;
  dep[u] = d;
  setDepth(T[u].left, d+1);
  setDepth(T[u].right, d+1);
}

int setHeight(int u){
  int h1 = 0, h2 = 0;
  if(T[u].left != NIL) h1 = setHeight(T[u].left) + 1;
  if(T[u].right != NIL) h2 = setHeight(T[u].right) + 1;
  return hei[u] = (h1 > h2 ? h1 : h2); 
}

int getSibling(int u){
  if(T[u].parent == NIL) return NIL;
  if(T[T[u].parent].left != u && T[T[u].parent].right != NIL) return T[T[u].parent].left;
  if(T[T[u].parent].right != u && T[T[u].parent].left != NIL) return T[T[u].parent].right;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",getSibling(u));
  int deg = 0;
  if(T[u].left != NIL) deg++;
  if(T[u].right != NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",dep[u]);
  printf("height = %d, ",hei[u]);

  if(T[u].parent == NIL){
    printf("root\n");
  }else if(T[u].left == NIL && T[u].right == NIL){
    printf("leaf\n");
  }else{
    printf("internal node\n");
  }
}

int main(){
  int i, v, l, r, root = 0;

  scanf("%d",&n);

  for(i = 0; i < n; i++) T[i].parent = NIL;

  for(i = 0; i < n; i++){
    scanf("%d %d %d", &v,&l,&r);
    T[v].left = l;
    T[v].right = r;
    if(l != NIL) T[l].parent = v;
    if(r != NIL) T[r].parent = v;
  }

  for(i = 0; i < n; i++) if(T[i].parent == NIL) root = i;

  setDepth(root,0);
  setHeight(root);
  for(i = 0; i < n; i++) print(i);

  return 0;
}



Measured memory_bytes: 2148
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll n;
    cin >>n;
    vector<ll> a(n);
    rep(i,0,n) cin >> a[i];

    ll cnt (0);
    while (true)
    {
        ll shf(1);

        rep(i,0,n)
            if (a[i]%2 != 0)
                shf = shf && 0;

        //for (auto i: a)
        //    cout << ' ' << i;
        //cout << endl;


        if (!shf)
            break;
 
        if (shf)   
            rep(i,0,n)
                a[i] >>= 1;

        cnt++;
    }

    cout << cnt <<endl;

    return 0;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int n; cin >> n;
    cout << "ABC" << to_string(n) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359
//Union-Find木
struct UnionFind{
private:
	vector<int> parent;
public:
	UnionFind(int N) : parent(N){ //初期化する O(N)
		for(int i=0; i<N; i++) parent[i] = i;
	}
	int root(int a){ //親を返す O(log N)
		if(parent[a] == a) return a;
		return parent[a] = root(parent[a]);
	}
	void unite(int a, int b){ //木を併合する O(log N)
		int rootA = root(a);
		int rootB = root(b);
		if(rootA != rootB) parent[rootA] = rootB;
	}
	bool same(int a, int b){ //属する木が同じかを返す O(log N)
		return root(a) == root(b);
	}
};

int A[100000],B[100000];
LL ans[100000];
LL c[100000];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	LL N,M;
	cin >> N >> M;
	
	for(int i=0; i<M; i++){
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}
	UnionFind uf(N);
	for(int i=0; i<N; i++) c[i] = 1;
	ans[M-1] = N * (N-1) / 2;
	for(int i=M-1; i>=1; i--){
		if(uf.root(A[i]) == uf.root(B[i])){
			ans[i-1] = ans[i];
			continue;
		}
		ans[i-1]  = ans[i] - c[uf.root(A[i])] * c[uf.root(B[i])];
		int tmp = c[uf.root(A[i])] + c[uf.root(B[i])];
		uf.unite(A[i],B[i]);
		c[uf.root(A[i])] = tmp;
	}
	for(int i=0; i<M; i++) cout << ans[i] << endl;

	return 0;
}


Measured memory_bytes: 4096
use proconio::{input, marker::Usize1};

const V: usize = 26;

struct State {
    cc: Vec<i32>,
    ss: Vec<Vec<i32>>,
    tt: Vec<usize>,
}

impl State {
    fn new(cc: Vec<i32>, ss: Vec<Vec<i32>>, tt: Vec<usize>) -> State {
        State { cc, ss, tt }
    }

    fn calc_score(&self) -> i32 {
        let mut score = 0;
        let mut last = vec![0; V];
        for (d, &t) in self.tt.iter().enumerate() {
            let day = d as i32 + 1;
            last[t] = day;
            score += self.ss[d][t];
            score -= last
                .iter()
                .zip(self.cc.iter())
                .map(|(&l, &c)| c * (day - l))
                .sum::<i32>();
        }
        score
    }

    fn find_before(&self, day: usize, target: usize) -> usize {
        for (i, &t) in self.tt[..day].iter().enumerate().rev() {
            if t == target {
                return day - i - 1;
            }
        }
        day
    }

    fn find_after(&self, day: usize, target: usize) -> usize {
        for (i, &t) in self.tt[day + 1..].iter().enumerate() {
            if t == target {
                return i + 1;
            }
        }
        self.tt.len() - day
    }

    fn diff(&self, day: usize, new: usize) -> i32 {
        let now = self.tt[day];
        if new == now {
            return 0;
        }
        let mut diff = self.ss[day][new] - self.ss[day][now];
        diff -= {
            let b = self.find_before(day, now) as i32;
            let a = self.find_after(day, now) as i32;
            self.cc[now] * (a * b + a)
        };
        diff += {
            let b = self.find_before(day, new) as i32;
            let a = self.find_after(day, new) as i32;
            self.cc[new] * (a * b + a)
        };
        diff
    }
}

fn main() {
    input! {
        d: usize,
        cc: [i32; V],
        ss: [[i32; V]; d],
        tt: [Usize1; d],
        m: usize,
        dq: [(Usize1, Usize1); m],
    }
    let mut state = State::new(cc, ss, tt);
    let mut score = state.calc_score();
    for (d, q) in dq {
        score += state.diff(d, q);
        state.tt[d] = q;
        println!("{}", score);
    }
}


Measured memory_bytes: 4108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define call(var) cout<<#var<<"="<<var<<endl;
#define dup(x,y) (((x)+(y)-1)/(y))
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)998244353;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
template<class t,class u> inline bool chmax(t&a,u b){if(a<b){a=b;return true;}return false;}
template<class t,class u> inline bool chmin(t&a,u b){if(b<a){a=b;return true;}return false;}

bool check(vector<P> s){
    int h = 0;
    for(P p : s){
        int b = p.first + h;
        if(b < 0) return false;
        h += p.second;
    }
    return true;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<P> ls, rs;
    int total = 0;
    rep(i,n){
        string s;cin >> s;
        int h = 0, b = 0;
        for(char c : s){
            if(c == '(') ++h;
            else --h;
            b = min(b, h);
        }
        if(h > 0) ls.emplace_back(b, h);
        else rs.emplace_back(b-h, -h);
        total += h;
    }

    sort(ls.rbegin(), ls.rend());
    sort(rs.rbegin(), rs.rend());
    if(check(ls) && check(rs) && total == 0){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
}

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

const int mod = 1000*1000*1000+7;

int po(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL*ret*x%mod;
        x = 1LL*x*x%mod;
        n /= 2;
    }
    return ret;
}
int inv(int x) { return po(x, mod - 2); }

vector<vector<int> > comb;
vector<int> fact, invf;

int N, A, B, C, D;

int cc[1010][1010];
int dp(int a, int rem) {
    int &ret = cc[a][rem];
    if(ret != -1) return ret;

    if(a == B + 1) return ret = rem == 0;

    ret = dp(a + 1, rem);
    int tmp = rem;
    int mul = 1;

    for(int i = 1; a*i <= rem; i++) {
        mul = 1LL*mul*comb[tmp][a]%mod;
        if(C <= i && i <= D) {
            ret += 1LL*mul*invf[i]%mod*dp(a + 1, tmp - a)%mod;
            ret %= mod;
        }
        tmp -= a;
    }
    return ret;
}

int main() {
    cin>>N>>A>>B>>C>>D;

    comb = vector<vector<int> >(N+1, vector<int>(N+1, 0));
    comb[0][0] = 1;
    for(int i = 1; i <= N; i++) {
        comb[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
        }
    }
    fact.resize(N + 1);
    fact[0] = 1;
    for(int i = 1; i <= N; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    invf.resize(N + 1);
    for(int i = 0; i <= N; i++) {
        invf[i] = inv(fact[i]);
    }

    memset(cc, -1, sizeof(cc));
    printf("%d", dp(A, N));
}


Measured memory_bytes: 8320
#
# File    : C.rb
# Author  : Kazune Takahashi
# Created : 2018-6-16 21:04:56
# Powered by Visual Studio Code
#

n = gets.to_i
a = gets.chomp.split(" ").map{|u| u.to_i}

ans = 0

a.each{|n|
  while n % 2 == 0
    n /= 2
    ans += 1
  end
}

puts ans

Measured memory_bytes: 2428
N,X=map(int,input().split())
x=list(map(int,input().split()))
x.append(X)
mx=min(x)
x=list(map(lambda t:t-mx,x))
def gcd(a,b):
    while b:
        a,b=b,a%b
    return(a)
a=10**10
for i,j in zip(x,x[1:]):
    a=min(a,gcd(i,j))
print(a)

Measured memory_bytes: 63896
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MaxN = 1e5;

int a, b;
int main()
{
	while(scanf("%d %d", &a, &b) != EOF)
	{
		if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) printf("Possible\n");
		else printf("Impossible\n");
	}
	return 0;
}

Measured memory_bytes: 128
n, m = map(int, input().split())
ans = [0, 0]
ac = [0 for _ in range(n)]
for _ in range(m):
  p, s = input().split()
  p = int(p) - 1
  if ac[p] == -1:
    continue
  elif s == "AC":
    ans[0] += 1
    ans[1] += ac[p]
    ac[p] = -1
  else:
    ac[p] += 1
print(*ans)

Measured memory_bytes: 10008
//#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
// using namespace __gnu_pbds;
// template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;



#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define in insert
#define ld long double


#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define int ll
const ll mod =1e9+7;
const ll MAX_NODES =200001;
const ll MAX_LOG =50;
const ll maxn = 400000+10;


int32_t main()
{

  string s;
  cin>>s;
  if(s[2]==s[3]&&s[4]==s[5])
  {
    cout<<"Yes"<<endl;
  }
  else
  {
    cout<<"No"<<endl;
  }
  
  








}


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

def sieve(n):
    is_prime = [1]*(n + 1)
    is_prime[0], is_prime[1] = 0, 0

    # for is_prime[24]. Initially it is 0. when num (outer loop) is 2. is_prime[24] = 0+1
    # when num is 3. is_prime[24] = 1+1. when num is 4 and 6 it is again incremented by 1.
    # Thus in the end is_prime[A] contains all divisors of A excpet 1, A. (special case A=1)

    for num in range(2, n+1//2):
        for mult in range(2*num, n+1, num):
            is_prime[mult] += 1
        
    ans = 1

    # i is N. elem is f(N)
    for i, elem in enumerate(is_prime[2:]):
        ans += (elem + 1)*(i + 2)

    print(ans)

sieve(n)




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

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    long long ans = 0;
    int t = n-1;
    rep(i, n){
        int cnt = 2;
        if(0 == i) cnt = 1;
        rep(j, cnt){
            if(t > 0){
                ans += a[i];
                --t;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4048
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define read freopen("in.in","r",stdin)
#define write freopen("out.out","w",stdout)
#define FastIO ios::sync_with_stdio(0)
typedef long long ll;
int n,maxw;
int weight[102];
int value[102];
ll memo[102][100005];
ll dp(int idx, int w) {
	if (w> maxw)
		return -1e9;
	if (idx == n)
		return 0;
	ll &ret = memo[idx][w];
	if (ret != -1)return ret;
	ret = max(dp(idx+1,w),dp(idx + 1, w + weight[idx]) + value[idx]);
	return ret;
}
int main() {
	FastIO;
#ifndef ONLINE_JUDGE
	//write; read;
#endif 
	memset(memo, -1, sizeof memo);
	cin >> n >> maxw;
	for (int i = 0; i < n; i++)
		cin >> weight[i] >> value[i];
	cout << dp(0, 0) << endl;
	return 0;
}

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

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a)  (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vi b(n); rep(i, n) {cin >> b[i]; b[i]--;}

  vi ans;
  for (int i = n-1; i >= 0; i--) {
    for (int j = b.size()-1; j >= 0; j--) {
      if(j == b[j]){
        b.erase(j+b.begin());
        ans.push_back(j);
        break;
      }
    }

  }
  reverse(all(ans));
  if(ans.size() != n){
    std::cout << -1 << '\n';
    return 0;
  }
  rep(i, n) std::cout << ans[i]+1 << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[5][5];
bool vis[5][5];
int main() {
	//freopen("in.txt","r",stdin);
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			scanf("%d",&a[i][j]);
		}
	}
	int n;
	scanf("%d",&n);
	for(int i=0,x;i<n;i++) {
		scanf("%d",&x);
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				if(a[i][j]==x) vis[i][j]=true;
			}
		}
	}
	bool f=false;
	for(int i=0;i<n;i++) {
		if(vis[i][0]&&vis[i][1]&&vis[i][2]) f=true;
		if(vis[0][i]&&vis[1][i]&&vis[2][i]) f=true;
	}
	if(vis[0][0]&&vis[1][1]&&vis[2][2]) f=true;
	if(vis[0][2]&&vis[1][1]&&vis[2][0]) f=true;
	printf("%s\n",f?"Yes":"No");
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int numStations = Integer.parseInt(scanner.nextLine());
		int[] time2Next = new int[numStations];
		int[] startTime = new int[numStations];
		int[] frequency = new int[numStations];
		int[] time2Last = new int[numStations];

		for (int sIdx = 0; sIdx < numStations - 1; sIdx++) {
			String[] inputs = scanner.nextLine().split(" ");
			time2Next[sIdx] = Integer.parseInt(inputs[0]);
			time2Last[sIdx] = startTime[sIdx] = Integer.parseInt(inputs[1]);
			frequency[sIdx] = Integer.parseInt(inputs[2]);

			for (int fsIdx = 0; fsIdx <= sIdx; fsIdx++) {
				time2Last[fsIdx] = ((time2Last[fsIdx] - 1) / frequency[sIdx] + 1) * frequency[sIdx] + time2Next[sIdx];
				if (time2Last[fsIdx] < startTime[sIdx] + time2Next[sIdx]) time2Last[fsIdx] = startTime[sIdx] + time2Next[sIdx];
			}
		}

		for (int sIdx = 0; sIdx < numStations; sIdx++) {
			System.out.println(time2Last[sIdx]);
		}
	}
}


Measured memory_bytes: 26708
n = int(input())
lis = [list(map(int,input().split())) for i in range(n)]
ans = 0
for i in range(n):
  if lis[i][0] == lis[i][1]:
    ans += 1
  else:
    ans = 0
  if ans == 3:
    print("Yes")
    exit()
print("No")


Measured memory_bytes: 9192
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(a: int, b: int, c: int, d: int):
    if abs(c-a) <= d or (abs(b-a) <= d and abs(c-b) <= d):
        print(YES)
    else:
        print(NO) 
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    c = int(next(tokens))  # type: int
    d = int(next(tokens))  # type: int
    solve(a, b, c, d)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const int mod=998244353;
int par[100010];
int depth[100010];
void init(int n){
  for(int i=0;i<=n;i++){
      par[i]=i;
      depth[i]=0;
  }
}
int root(int x){
  return par[x]==x?x:par[x]=root(par[x]);
}
bool same(int x,int y){
  return root(x)==root(y);
}
void unite(int x,int y){
  x=root(x);
  y=root(y);
  if(x==y)return;
  if(depth[x]<depth[y]){
      par[x]=y;
  }else{
      par[y]=x;
      if(depth[x]==depth[y])depth[x]++;
  }
}
int main(){
    ll n,m;cin>>n>>m;
    init(n);
    priority_queue<pll,vector<pll>,greater<pll> >pq;
    vector<ll>a(n);
    rep(i,n){
        cin>>a[i];
        pq.push(mp(a[i],i));
    }
    rep(i,m){
        ll x,y;cin>>x>>y;
        unite(x,y);
    }
    if(n>2*(m+1)){
        cout<<"Impossible"<<endl;
        return 0;
    }
    vector<bool>used(n);
    priority_queue<pll,vector<pll>,greater<pll> >pq2;
    ll ans=0;
    ll cnt=0;
    while(!pq.empty()){
        pll k=pq.top();
        pq.pop();
        //cout<<k.first<<' '<<k.second<<endl;
        if(used[root(k.second)]){
            pq2.push(k);
        }else{
            ans+=k.first;
            used[root(k.second)]=1;
            cnt++;
        }
    }
    //cout<<ans<<' '<<cnt<<endl;
    while(cnt<2*(n-1-m)){
        pll k=pq2.top();
        pq2.pop();
        ans+=k.first;
        cnt++;
    }
    if(n==m+1)ans=0;
    cout<<ans<<endl;
}

Measured memory_bytes: 7920
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

#ifndef INCLUDED_ROLLING_HASH_HPP
#define INCLUDED_ROLLING_HASH_HPP

#include <vector>
#include <string>

using u64 = std::uint_fast64_t;

class rolling_hash {
public:
	using u64 = std::uint_fast64_t;
	using size_type = std::uint_fast32_t;

	static constexpr u64 MOD = (1uL << 61) - 1;
	static constexpr u64 base = 20200213;

	std::string str;
	std::vector<u64> hash_, pow;

private:
	static constexpr u64 mask30 = (1ul << 30) - 1;
	static constexpr u64 mask31 = (1ul << 31) - 1;

	u64 mul(u64 a, u64 b) const {
		u64 au = a >> 31;
		u64 ad = a & mask31;
		u64 bu = b >> 31;
		u64 bd = b & mask31;
		u64 mid = ad * bu + au * bd;
		u64 midu = mid >> 30;
		u64 midd = mid & mask30;
		return apply(au * bu * 2 + midu + (midd << 31) + ad * bd);
	}
	u64 apply(u64 val) const {
		val = (val & MOD) + (val >> 61);
		if(val >= MOD) val -= MOD;
		return val;
	}
	size_type xorshift(size_type x) const {
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		return x;
	}

public:
	rolling_hash(const rolling_hash &) = default;
	rolling_hash(rolling_hash&&) = default;

	rolling_hash() : str() {};
	rolling_hash(const std::string & str) : str(str) {
		hash_.resize(str.size() + 1, 0);
		pow.resize(str.size() + 1, 1);
		for(size_type i = 0; i < str.size(); i++) {
			hash_[i + 1] = mul(hash_[i], base) + xorshift(str[i] + 1);
			pow[i + 1] = mul(pow[i], base);
			if(hash_[i + 1] >= MOD) hash_[i + 1] -= MOD;
		}
	}

	u64 hash() const { return hash_.back(); }
	u64 hash(size_type l, size_type r) const {
		u64 ret = MOD + hash_[r] - mul(hash_[l], pow[r - l]);
		return ret < MOD ? ret : ret - MOD;
	}
	
	size_type size() const { return str.size(); }
};

#endif

int main() {
	int n; scanf("%d", &n);
	std::vector<std::string> s(n);
	for(int i = 0; i < n; i++) cin >> s[i];

	std::vector<int> one(26);
	std::map<u64, std::vector<int>> cnt;
	for(auto t: s) {
		auto th = rolling_hash(t);

		std::vector<int> tmp(26);
		for(int i = 0; i < t.size(); i++) {
			u64 h = th.hash(i, t.size());
			for(int k = 0; k < 26; k++) {
				if(!cnt.count(h)) cnt[h].resize(26);
				cnt[h][k] += tmp[k];
			}

			tmp[t[i] - 'a'] = 1;
		}

		for(int i = 0; i < 26; i++) one[i] += tmp[i];
	}

	i64 ans = 0;
	for(auto t: s) {
		if(t.size() == 1) {
			ans += one[t[0] - 'a'] - 1;
			continue;
		}
		
		auto th = rolling_hash(t.substr(1, t.size() - 1));
		u64 h = th.hash();

		if(cnt.count(h)) ans += cnt[h][t[0] - 'a'] - 1;
	}
	printf("%lld\n", ans);
	return 0;
}


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

int x,y;

int euclid(int x, int y){
  if (y == 0){
    return x;
	}
  else return euclid(y, x % y);
  }


int main(){
 cin >> x >> y;
 cout << euclid(x,y) << endl;
}

int euclude(int x, int y){
  if (y == 0){
    return x;
	}
  else return euclid(y, x % y);
  }

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
const ll INF = 1LL<<60;

int main(){
  ll N;
  cin>>N;
  string W[N];
  ll ans=0;
  rep(i,N){
   cin>>W[i];
  }
  rep(i,N-1){
   if(W[i][(int)W[i].size()-1]!=W[i+1][0]){ans=1;}
  }
  rep(i,N-1){
    for(int j=i+1;j<N;j++){
    if(W[i]==W[j]){ans=1;}
    }
  }
  if(ans==1){
cout<<"No"<<endl;}
  else{cout<<"Yes"<<endl;}
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <string.h>
#include <iostream>

 
 
using namespace std;
 

int main(){
	int p1,p2;
	string s;
	cin>>s;
	s.insert(s.begin(),'\0');
	p1=1;
	p2=s.size()-1;
	while(p2>p1){
		while(s[p1]=='x'){
			p1++;
		}
		while(s[p2]=='x'){
			p2--;
		}
		if(s[p1]!=s[p2]){
			cout<<-1<<endl;
			return 0;
		}
		p1++;
		p2--;
	}
	swap(p1,p2);
	int cnt=0;
	while(p1>0 || p2<s.size()){
		if (s[p1]=='x' && s[p2]!='x'){
			cnt++;
			p1--;
		}
		else if(s[p1]!='x' && s[p2]=='x'){
			cnt++;
			p2++;
		}
		else{
			p1--;
			p2++;
		}
	}

	cout<<cnt<<endl;
			
		
 
return 0;
}





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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

template<typename T>
struct BIT {
    vector<T> data;
    BIT(size_t n) {
        data.resize(n + 1, 0);
    }
    //sum of [1, i]
    T sum(int i){
        assert(0 <= i);
        T s = 0;
        for(; i > 0; i -= i & -i) s += data[i];
        return s;
    }
    // sum of [i, j]
    T sum(int i,int j){
        assert(0 < i and i <= j);
        return sum(j) - sum(i - 1);
    }
    //add x to index i
    void add(int i, T x){
        assert(0 < i);
        for(; i < data.size(); i += i & -i) data[i] += x;
    }
    // seach min i such that sum(i) >= x
    int lower_bound(T x){
        int r = data.size() - 1, l = 0; // (l, r]
        while(r - l > 1){
            int m = (r + l) / 2;
            (sum(m) >= x ? r : l) = m;
        }
        return r;
    }
};


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

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

    vector<BIT<int>> counts(27, BIT<int>(N));
    rep(i, N) {
        counts[S[i] - 'a'].add(i+1, 1);
    }

    int Q; cin >> Q;
    rep(q, Q) {
        int t; cin >> t;

        if(t == 1) {
            int iq; char cq; cin >> iq >> cq;
            iq--;
            if(S[iq] == cq) continue;
            counts[S[iq] - 'a'].add(iq+1, -1);
            S[iq] = cq;
            counts[S[iq] - 'a'].add(iq+1, 1);
        } else {
            int l, r; cin >> l >> r;
            l--; r--;
            int ans = 0;
            rep(i, 27) ans += counts[i].sum(l+1, r+1) > 0;
            cout << ans << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 55708
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll sum=0;
    rep(i,0,n-1){
        sum+=a[i]%2;
    }
    if(sum%2==0){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    
    
    return 0;
}






Measured memory_bytes: 1024
N=int(input())
if N>105:
    ans=1
    for i in range(107,N+1,2):
        g=0
        for j in range(1,i+1):
            if i%j==0:
                g+=1
        if g==8:
            ans+=1
    print(ans)
elif N==105:
    print(1)
else:
    print(0)




Measured memory_bytes: 2940
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n,k=parseMap(split(readline()))
    println(max(n-k+1,0))
end
main()

Measured memory_bytes: 166380