akhauriyash/Code-Regression huggingface dataset:
// header {{{
#include <bits/stdc++.h>
using namespace std;

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int h, w;
int c[10][10];
int a[200][200];

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    cin >> h >> w;
    inc(i, 0, 10) inc(j, 0, 10) cin >> c[i][j];
    inc(i, 0, h)  inc(j, 0, w)  cin >> a[i][j];
    inc(k, 0, 10) inc(i, 0, 10) inc(j, 0, 10)
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
    int ans = 0;
    inc(i, 0, h) inc(j, 0, w)
        ans += a[i][j] == -1 ? 0 : c[a[i][j]][1];
    cout << ans << endl;
}


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

using namespace std;

int main(){
    int X,N;
    cin >> X >> N;

    vector<int> A(N);
    for(int i=0; i<N; i++)cin >> A.at(i);

    // sort(A.begin(), A.end());

    // cout << "after init" << endl;
    int diff = 1;
    if(find(A.begin(), A.end(), X) == A.end()){
        cout << X << endl;
        return 0;
    }

    while(true){
        int p = X+diff; int m = X-diff;
        if(A.empty()){
            cout << m << endl;
            break;
        }
        auto m_itr = find(A.begin(), A.end(), m);
        if(m_itr == A.end()){
            cout << m << endl;
            return 0;
        }
        A.erase(m_itr);
        
        if(A.empty()){
            cout << p << endl;
            break;
        }
        auto p_itr = find(A.begin(), A.end(), p);
        if(p_itr == A.end()){
            cout << p << endl;
            return 0;
        }
        A.erase(p_itr);

        diff++;
    }


}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {
	public static void main(String[] arges) {

		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] k = line.split(" ");
		int[] v = new int[3];
		for (int i = 0; i < v.length; i++) {
			v[i] = Integer.parseInt(k[i]);
		}
		long[][] suuretu = new long[v[0]][v[2]];

		int[][] suuretua = new int[v[0]][v[1]];
		int[][] suuretub = new int[v[1]][v[2]];

		for (int i = 0; i < v[0]; i++) {
			String line2 = sc.nextLine();
			String[] k2 = line2.split(" ");

			for (int j2 = 0; j2 < v[1]; j2++) {
				suuretua[i][j2] = Integer.parseInt(k2[j2]);
			}
		}
		for (int i = 0; i < v[1]; i++) {
			String line2 = sc.nextLine();
			String[] k2 = line2.split(" ");

			for (int j2 = 0; j2 < v[2]; j2++) {
				suuretub[i][j2] = Integer.parseInt(k2[j2]);
			}
		}

		for (int i = 0; i < v[0]; i++) {
			for (int j = 0; j < v[2]; j++) {

				long sum = 0;
				for (int j2 = 0; j2 < v[1]; j2++) {
					sum += suuretua[i][j2]*suuretub[j2][j];
				}suuretu[i][j] = sum;
			}
		}
		for (int i = 0; i < v[0]; i++) {
			for (int j = 0; j < v[2]; j++) {
				System.out.print(suuretu[i][j]);
				if (j!=v[2]-1) {
					System.out.print(" ");
				}
			}
			System.out.println("");
		}
	}
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    int n,k; cin >> n >> k;
    vector<lint> p(n);
    rep(i, n) cin >> p[i];

    sort(all(p));
    lint ans = 0;
    rep(i, k) ans += p[i];
    out(ans);
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <boost/range/adaptor/indexed.hpp>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
std::ostream &operator<<(std::ostream &ostr, const std::vector<T> &v) {
  for (const auto &i : v | boost::adaptors::indexed())
    ostr << (i.index() > 0 ? " " : "") << i.value();
  return ostr;
}

inline void Main() {
  // code
  int n, x, a=0, b=0;
  bool c=false;
  cin >> n;
  rep(i, n) {
    cin >> x;
    if(x%2!=0) a++;
    if(x%4==0) b++;
    else if(x%2==0) c=true;
  }
  if(c) a++;
  cout<<((a-1)<=b?"Yes":"No")<<endl;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <array>
#include <deque>
#include <vector>
#include <utility>
#include <string>
#include <cmath>

int main()
{
    uint64_t a = 0;
    double b = 0.0;
    std::cin >> a;
    std::cin >> b;
    const uint64_t ans = ( (a - (a%100) ) / 100) * static_cast<uint64_t>(std::round(b * 100.0)); //絶対小数点以上になるマン
    const double ans_mini = std::floor(static_cast<double>(a % 100)* b);
    const uint64_t last_ans = ans + static_cast<uint64_t>(ans_mini);
    std::cout << last_ans;
    return 0;
}

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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}

#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

void err(vector<string>::iterator it) {}

template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> inline T tabs(T a) { return (a > 0) ? a : -a; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	string s;

	cin >> s;
	int n = s.size();
	int ans = 0;
	REPU(i, 1, n) if (s[i] != s[i - 1]) {
		ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 512
n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]

def dist(y,z):
	summ = 0
	for i in range(d):
		summ += (y[i]-z[i])**2
	return summ**(1/2)
	
ans_list = []
for ii in range(n):
	for jj in range(n):
		if ii < jj:
			dis = dist(x[ii],x[jj])
			if dis.is_integer():
				ans_list.append(dis)
print(len(ans_list))




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

using ll = long long;

int main() {
    int n;
    string s;
    
    cin >> n >> s;
    
    map<pair<string, string>, ll> m;
    
    for(int i = 0; i < (1 << n); i++) {
        string a, b;
        for(int j = 0; j < n; j++) {
            if(i >> j & 1) {
                a.push_back(s[j]);
            } else {
                b.push_back(s[j]);
            }    
        }
        m[make_pair(a, b)]++;
    }
    
    ll ans = 0;
    
    for(int i = 0; i < (1 << n); i++) {
        string a, b;
        for(int j = 0; j < n; j++) {
            if(i >> j & 1) {
                a.push_back(s[j + n]);
            } else {
                b.push_back(s[j + n]);
            }
        }
        
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        ans += m[make_pair(b, a)];
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 87040
#include <stdio.h>
int main(){
  int a, b, c, d, e, k;
  scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &k);

  if( ((a-b)<=k) && ((a-c)<=k) && ((a-d)<=k) && ((a-e)<=k) && ((b-a)<=k) && ((b-c)<=k) && ((b-d)<=k) && ((b-e)<=k) && ((c-a)<=k) && ((c-b<=k)) && ((c-d)<=k) && ((c-e)<=k) && ((d-a)<=k) && ((d-b)<=k) && ((d-c)<=k) && ((d-e)<=k) && ((e-a)<=k) && ((e-b)<=k) && (e-c)<=k && (e-d)<=k)
    printf("Yay!\n");
  else printf(":(\n");

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int a, b;

	cin >> a >> b;

	if (a < b) {
		rep(i, b) cout << a;
		cout << endl;
	}
	else {
		rep(i, a) cout << b;
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int p[100009];
int f[100009];
main()
{
    p[1]=1;
 
    for (int i=2; i<=100000; i++)
    {
        for (int j=2*i; j<=100000; j+=i)
            p[j]=1;
    }
    p[2]=0;
    for (int i=1; i<=100000; i++)
    {
        if(p[i]==0 && p[(i+1)/2]==0 && i!=2)
            {
                f[i]=f[i-1]+1;
            }
        else f[i]=f[i-1];
    }
    int q;
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<f[r]-f[l-1]<<endl;
    }
}

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

using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
int in() {int x; cin>>x; return x;}
string stin() {string s; cin>>s; return s;}
/***** MAIN *****/
signed main() {
  string s = stin();
  if(s[1]!=s[2]) {
    cout << "No" << endl;
    return 0;
  }
  if(s[0] == s[1] || s[2] == s[3]) cout << "Yes";
  else cout << "No";
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from itertools import groupby
## 幸福数はN-group数
def solve(N: int, K: int, S: str):
    groups = groupby(S)
    compress = []
    for key,group in groups:
        compress.append(key)

    print(min(N-1,N-(len(compress)-2*K)))

    
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4212
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str;
    int k, len_str;
    cin >> str >> k;
    
    

    for (int i = 0; i < str.length(); i++) {
        int needToa = 26 - ( int(str[i]) - int('a') );
        if (k >= needToa && needToa != 26) {
            k -= needToa;
            str[i] = 'a';
        }
        
    }

    k = k % 26;
    char ins = char(int(str[str.length()-1]) + k);
    str[str.length()-1] = ins;


    cout << str << endl;
    return 0;
}

Measured memory_bytes: 512
# coding: utf-8

import codecs
import sys

sys.stdout = codecs.getwriter("shift_jis")(sys.stdout) # ??????
sys.stdin = codecs.getreader("shift_jis")(sys.stdin) # ??\???

# ??\??¬?????????print??????????????´?????? print(u'?????????') ??¨??????
# ??\??¬?????????input??? input(u'?????????') ??§OK
# ??°?¢???????????????????????????´??????6,7???????????????????????¢??????

for i in range(1,10):
	for j in range(1,10):
		k = i * j
		print("{0}x{1}={2}".format(i , j , k))

Measured memory_bytes: 6540
from fractions import gcd

a, b, k = list(map(int, input().split()))
count = 1
for i in range(gcd(a, b), 0, -1):
    if a % i != 0 or b % i != 0:
        continue
    else:
        if count == k:
            print(i)
            break
        else:
            count += 1

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

int main() {

    string s;
    cin >> s;
    if(s.size() == 1){
            cout << 0 << endl;
            return 0;
    }
    vector<char >c0,c1;
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(i%2 == 0)c0.push_back('0');
        else c0.push_back('1');
    }
    for(int i = 0; i < n; i++){
          if(i%2 == 0)c1.push_back('1');
        else c1.push_back('0');
    }
    int one = 0, two = 0;
    for(int i = 0; i < c0.size(); i++){
        if(c0[i] != s[i])one++;
    }
    //cout << endl;
    for(int i = 0; i < c0.size(); i++){
        if(c1[i] != s[i])two++;
    }
    cout << min(one,two) << endl;
    return 0;
}




Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include <iomanip>
#include <math.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60
const double PI = 3.14159265358979323846;

int alp[52] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };

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

	int N; cin >> N;
	string S; cin >> S;
	for (int i = 0; i < S.size(); i++) S[i] = alp[S[i] - 'A' + N];
	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [int(input()) for i in range(n)]
count = 0
t = 0
b = 0

for i in range(n) :
    a[i] = a[i] - 1
for i in range(n) :
    count = count + 1
    if a[t] == 1 :
        print (count)
        b = 1
        break
    else :
        t = a[t]
if b == 0 :
    print (-1)

Measured memory_bytes: 7084
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
int main() {

	int N;
	double result=0;
	cin >> N;
	vector<double> A(N);

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

	sort(A.begin(),A.end());

	for (int i = 0; i < N-1; i++)
	{
		A[i+1] = (A[i] + A[i+1]) / 2;
		sort(A.begin()+i, A.end());
	}

	cout << A[N-1];
}


Measured memory_bytes: 256
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[100][16384];

int main(int argc, char **argv)
{
        int N, W;
        cin >> N >> W;
        vector<int> v(N), w(N);
        for (int i = 0; i < N; i++)
                cin >> v[i] >> w[i];
        for (int i = 0; i < N; i++) {
                for (int j = 0; j <= W; j++) {
                        if (!i) {
                                dp[i][j] = w[i] <= j ? v[i] : 0;
                        }
                        else if (j < w[i]) {
                                dp[i][j] = dp[i-1][j];
                        }
                        else {
                                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
                        }
                }
        }
        cout << dp[N-1][W] << endl;
        return 0;
}

Measured memory_bytes: 7044
#include <iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define INF 1e8
using namespace std;
#define ll long long

#define MAX 100020
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define INF 1e8
using namespace std;
#define ll long long

#define MAX 100020

int main(){
int a,b;
  cin>>a>>b;
  if((a>=1 && a<=9) &&(b>=1 && b<=9))
    	cout<<a*b;
  else
    cout<<-1;

}



Measured memory_bytes: 3200
#include <algorithm>
#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    int N;
    cin >> N;
    if (N / 10 == 9 || N % 10 == 9)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0;
    char c;
    bool zf=0;
    while(((c=getchar())<'0'||c>'9')&&c!= '-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
int _data[100005];
signed main(){
	int n=read();
	for(register int i=1;i<=n;i++){
		_data[i]=read();
	}
	sort(_data+1,_data+n+1);
	long long _sum=0,ans=0;
	for(register int i=1;i<=n;i++){
		_sum+=_data[i];ans++;
		if(_sum*2<_data[i+1])ans=0;
	}
	cout<<ans<<'\n'; 
	return 0;
}

Measured memory_bytes: 3960
//https://atcoder.jp/contests/abc049/tasks/arc065_b

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;

void dfs(int cur, vector<int> *g, bool *visited, int *comp, int num) {
    visited[cur] = true;
    comp[cur] = num;

    for(int i=0; i<g[cur].size(); i++) {
        int next = g[cur][i];
        if(visited[next]) continue;
        dfs(next, g, visited, comp, num);
    }
}

int *get_components(vector<int> *g, int n) {
    int *comp = new int[n+1]; comp[0]=-1;
    bool visited[n+1]={0}; visited[0]=true;
    int comp_num = 1;

    for(int i=1; i<=n; i++) {
        if(visited[i]) continue;
        dfs(i, g, visited, comp, comp_num);
        comp_num++;
    }

    return comp;
}

int main() {
    int n,k,l; cin>>n>>k>>l;
    vector<int> road[n+1], rail[n+1];
    int u, v;
    while(k--) {
        cin >> u >> v;
        road[u].pb(v);
        road[v].pb(u);
    }
    while(l--) {
        cin >> u >> v;
        rail[u].pb(v);
        rail[v].pb(u);
    }

    int *kcomp = get_components(road, n);
    int *lcomp = get_components(rail, n);
    pair<int,int> anscomp[n+1];

    map<pair<int,int>, int> ans;
    for(int i=1; i<=n; i++) {
        anscomp[i] = mp(kcomp[i],lcomp[i]);
        ans[anscomp[i]]++;
    }

    for(int i=1; i<=n; i++) {
        cout << ans[anscomp[i]] << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 29312
package main

import (
	"fmt"
	"math"
)

var f = make([]bool, 100005)
var primes = make([]int, 100005)
var acc = make([]int, 100005)

func sieveOfEratosthenes(value int) {
	for i := 2; i <= int(math.Sqrt(float64(value))); i++ {
		if f[i] == false {
			for j := i * i; j < value; j += i {
				f[j] = true
			}
		}
	}
	for i := 2; i < value; i++ {
		if f[i] == false {
			primes[i] = 1
		}
	}
}

func is2017(n int) bool {
	return primes[n] == 1 && primes[(n+1)/2] == 1
}

func main() {
	sieveOfEratosthenes(100000)
	for i := 1; i <= 100000; i++ {
		acc[i] = acc[i-1]
		if is2017(i) {
			acc[i]++
		}
	}

	var q int
	fmt.Scan(&q)

	l := make([]int, q)
	r := make([]int, q)
	for i := 0; i < q; i++ {
		fmt.Scan(&l[i], &r[i])
	}
	for i := 0; i < q; i++ {
		fmt.Println(acc[r[i]] - acc[l[i]-1])
	}
}

Measured memory_bytes: 7936
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
int main(){
     int A,B,K,counter,i;
     cin >> A >> B >> K;
     if (A > B){
          swap(A,B);
     }
     counter = 0;
     for(i = A; i > 0; i--){
          if((A%i == 0)&&(B%i == 0)){
               counter++;
          }
          if(counter == K){
               break;
          }
     }
     cout << i << endl;
     return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

#define _deb(x) cout<<x;
void _print() {cerr << "]\n";} template <typename T, typename... V>void _print(T t, V... v) {_deb(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
template <class T, class U> void print_m(const map<T,U> &m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}
template<class T, class U>void debp(const pair<T, U> &pr, bool end_line=1){cout<<"{"<<pr.first<<" "<<pr.second<<"}"; cout<<(end_line ? "\n" : ", ");}
template <class T> void print_vp(const T &vp, int sep_line=0){if(vp.empty()){cout<<"Empty"<<endl; return;}if(!sep_line) cout<<"{ ";for(auto x: vp) debp(x,sep_line);if(!sep_line) cout<<"}\n";cout<<endl;}
template <typename T>void print(const T &v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<sz(v); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<endl;}
template <typename T>void print_vv(const T &vv){if(sz(vv)==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<sz(*vv.begin()); j++)cout<<setw(w)<<j<<" ";cout<<endl;int i = 0;for(auto &v: vv){cout<<i++<<" {";for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<"},\n";}cout<<endl;}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n;
    while(cin>>n){
        vl a(n), b(n);
        forn(i,n){
            ll x,y; cin>>x>>y;
            a[i] = x+y; b[i] = x-y;
        }
        sort(all(a)); sort(all(b));
        ll ans = max(a.back()-a.front(), b.back()-b.front());
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 6248
#include<stdio.h>
int main(void){
    int a,b;
    char op;
    int answer;
    while(1){
    scanf("%d %c %d",&a,&op,&b);
    if (op == '+'){
        answer=a+b;
        } else if (op == '-'){
        answer=a-b;
    } else if (op == '*'){
        answer=a*b;
    } else if (op == '/'){
        answer=a/b;
    } else if (op == '?'){
        break;
    }
    printf("%d\n",answer);}
return 0;
}

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

int N, digit, mod, ans = 0;

int main() {
  cin >> N;
  
  for (int i = 1; i <= N; i++) {
    digit = log10(i) + 1;
    mod = digit % 2;
    if (mod != 0) ans++;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
// #define int long long
using namespace std;
using pii=pair<int,int>;
#define REPF(i,a,n) for(int i=(a);i<(int)(n);++i)
#define REP(i,n) REPF(i,0,n)
#define ALL(c) begin(c),end(c)

int sum[5100][5100];
signed main() {
    int n,m;
    cin>>n>>m;
    vector<int> x(n),y(n);
    vector<pii> p(n);
    REP(i,n) {
        cin>>p[i].first>>p[i].second;
        x[i]=p[i].first;
        y[i]=p[i].second;
    }
    sort(ALL(x));
    x.erase(unique(ALL(x)),end(x));
    sort(ALL(y));
    y.erase(unique(ALL(y)),end(y));

    auto get_x=[&](int i) {
        return distance(begin(x),lower_bound(ALL(x),i));
    };
    auto get_y=[&](int i) {
        return distance(begin(y),lower_bound(ALL(y),i));
    };

    REP(i,n) {
        int xx=get_x(p[i].first);
        int yy=get_y(p[i].second);
        sum[xx][yy]++;
    }
    REP(i,5100) REPF(j,1,5100) sum[i][j]+=sum[i][j-1];
    REP(j,5100) REPF(i,1,5100) sum[i][j]+=sum[i-1][j];

    REP(i,m) {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int xx1=get_x(x1);
        int yy1=get_y(y1);
        int xx2=get_x(x2);
        int yy2=get_y(y2);
        if(find(ALL(x),x2)==end(x)) xx2--;
        if(find(ALL(y),y2)==end(y)) yy2--;

        if(xx2<xx1 || yy2<yy1) {
            cout<<0<<endl;
            continue;
        }

        int ans=sum[xx2][yy2];
        if(xx1>0) {
            ans-=sum[xx1-1][yy2];
        }
        if(yy1>0) {
            ans-=sum[xx2][yy1-1];
        }
        if(xx1>0 && yy1>0) {
            ans+=sum[xx1-1][yy1-1];
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 104828
#include <bits/stdc++.h>
using namespace std;
#define pll pair<ll,ll>
typedef long long ll;
#define mod 1000000007
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF 1e15
const int N=5e5+5;

int main()
{
	ll n;
	cin>>n;
	map<ll,ll> m;
	for(ll i=0;i<n;i++)
	{
		ll x;
		cin>>x;
		if(m[x])
		{
			cout<<"NO";
			exit(0);
		}
		m[x]++;
	}
	cout<<"YES";
}




Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int A, B;
  cin >> A >> B;
  if(!(1 == A) && !(1 == B)) {
    cout << 1 << endl;
  }
  if(!(2 == A) && !(2 == B)) {
    cout << 2 << endl;
  }
  if(!(3 == A) && !(3 == B)) {
    cout << 3 << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <vector>
#include <stack>

using namespace std;
////////////////*My library*////////////////////////
#define rep_to(a,i,n) for(int i=a;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_r(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) cout<<x<<endl
#define s_1(x) cin>>x
#define s_2(x,y) cin>>x>>y
////////////////////////////////////////////////////

////////////////////////
/*prime()*/
/*primecount()*/
/*sort()*/
/*imos???*/
/*????????¢?´¢*/
/*??±???????????¢?´¢*/
/*???????¨???????*/
///////////////////////

int main()
{
	int N;
	int a,b,c,d;
	int sumA=0,sumB=0;

	rep(i,2)
	{
		cin>>a>>b>>c>>d;
		if(i==0)sumA=a+b+c+d;
		else sumB=a+b+c+d;
	}

	if(sumA>=sumB)cout<<sumA<<endl;
	else if(sumA<sumB)cout<<sumB<<endl;

	return 0;
}

Measured memory_bytes: 1164
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())





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

	int ma = 1000000000;

	int n, k, s;
	cin >> n >> k >> s;

	if (s == ma) {
		rep(i, n) {
			if (i)cout << ' ';
			if (i < k)cout << s;
			else cout << ma - 1;
		}
	}
	else {
		rep(i ,n) {
			if (i)cout << ' ';
			if (i < k)cout << s;
			else cout << ma;
		}
	}
	cout << endl;


	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<algorithm>
#define rep(i, n) for(i=0; i<n; i++)
using namespace std;
int main() {
    string s;
    cin >> s;
    int i, len = s.length();
    int count = 0, temp = 0;
    bool ok = false;
    rep(i, len){
        if(s[i]=='A'){
            temp = i;
            break;
        }
    }
    for(i=len-1; i>=0; i--){
        if(s[i]=='Z'){
            count = i;
            break;
        }
    }
    cout << count-temp+1 << endl;
    return 0;
}

Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(int x,int a,int b)
{
    if(x+a+b>=22)
        cout<<"bust";
    else
        cout<<"win";
}
int main()
{
    int x,a,b;
    cin>>a>>b>>x;
    solve(a,b,x);
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
bit = [int(1e18) for _ in range(1 << N)]
bit[0] = 0
F = {0}
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bas = 0
  for k in range(b):
    c[k] -= 1
    bas += (1 << c[k])
  L = [[j, bit[j]] for j in F]
  for j in L:
    tb = 0
    for k in range(N):
      tb += (((j[0] >> k) & 1) | ((bas >> k) & 1)) << k
    bit[tb] = min(bit[tb], j[1] + a)
    F.add(tb)
if bit[-1] != int(1e18):
  print(bit[-1])
else:
  print(-1)

Measured memory_bytes: 93680
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
const ll INF = LLONG_MAX;
const ll MOD = 1e9 + 7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> A(N + 2), B(N + 1);
    ll sum = 0;
    rep(i, N)
    {
        cin >> A[i + 1];
    }

    A[0] = A[N + 1] = 0;
    rep(i, N + 1)
    {
        B[i] = abs(A[i + 1] - A[i]);
    }
    for (auto& b : B) {
        sum += b;
    }
    rep(i, N)
    {
        cout << sum - (B[i] + B[i + 1]) + abs(A[i + 2] - A[i + 0]) << endl;
    }
    return 0;
}

Measured memory_bytes: 2816
import java.util.*;
import java.math.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		for(int i=0;i<n;i++){
			BigInteger bi = BigInteger.ZERO;
			bi = bi.add(new BigInteger(sc.next())).add(new BigInteger(sc.next()));
			if(bi.toString().length()>80) System.out.println("overflow");
			else System.out.println(bi);
		}
	}
}

Measured memory_bytes: 18408
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
arr=list(map(int,input().split()))
l=0
r=max(arr)+1
while r-l!=1:
    persuit=(r+l)//2
    cnt=0
    for val in arr:
        if val<=persuit:
            continue
        if val%persuit==0:
            cnt+=val//persuit-1
        else:
            cnt+=val//persuit
    if cnt<=k:
        r=persuit
    else:
        l=persuit
print(r)


Measured memory_bytes: 31092
n = int(input())
s = input()

left = 0
right = 1
ans = 0

while left < n:
    s1 = s[left:right]
    s2 = s[right:]
    if s1 in s2:
        ans = max(ans,len(s1))
        right += 1
    else:
        left += 1

print(ans)

Measured memory_bytes: 3064
n = int(input())
s = [str(input()) for i in range(n)]


m = 0
a = 0
r = 0
c = 0
h = 0


for i in range(n):
    tmp = list(s[i])
    if tmp[0] == 'M':
        m += 1
    if tmp[0] == 'A':
        a += 1
    if tmp[0] == 'R':
        r += 1
    if tmp[0] == 'C':
        c += 1
    if tmp[0] == 'H':
        h += 1


arr = [m,a,r,c,h]


from itertools import combinations
base = list(combinations(arr,3))
ans = 0
for c in base:
    ans += c[0] * c[1] * c[2]

print(ans)


Measured memory_bytes: 9772
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  string s;
  cin>>s;
  Int n=s.size();
  vector<Int> cnt(26,0);
  for(Int i=0;i<n;i++) cnt[s[i]-'a']++;
  auto calc=[](Int x){return x*(x+1)/2;};
  Int ans=calc(n)+1;
  for(Int i=0;i<26;i++) ans-=calc(cnt[i]);
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  vector<int> d(N);
  for (int i = 0; i < N; ++i)
    cin >> d.at(i);

  sort(d.begin(), d.end());

  int mid = d[N / 2 - 1];
  int next = d[N / 2];

  cout << next - mid << endl;

  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main()
{
  int a,b,d,r;
  double f;
  scanf("%d%d,",&a,&b);
  d=a/b;
  r=a%b;
  f=(double)a/(double)b;
  
  printf("%d %d %f\n",d,r,f);


 return 0;
}

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


int main() {
    int a,b,k;
    cin >> a >> b >> k;
    for (int i = 100; i > 0; i--) {
        if (a%i == 0 && b%i == 0) {
            k--;
        }
        if (k == 0) {
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 3632
/*" بِسْمِ اللهِ الرَّحْمٰنِ الرَّحِيْمِ -In the name of Allah."
   Never stop chasing!-MD.SOURAV.

   ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
   ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
   ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
   [███████████████████].░░░░░░░░░░░░░░
   ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░
*/

#include <bits/stdc++.h>


#define endl           "\n"
#define MAX            32000
#define F              first
#define S              second
#define sz(x)          x.size()
#define li             long int
#define gcd(a,b)       _gcd(a,b)
#define pb             push_back
#define asrt(a,n)      sort(a,a+n)
#define MOD 	       1000000007
#define ll             long long int
#define lcd(a,b)       (a*b)/gcd(a,b)
#define mp(x,y)        make_pair(x,y)
#define no             cout<<"NO"<<endl
#define yes            cout<<"YES"<<endl
#define f(i, a, n)     for(int i=a;i<n;i++)
#define test           int t;cin>>t;while(t--)
#define srt(v)         sort(v.begin() , v.end())
#define basrt(a,n)     sort(a,a+n, greater<int>())
#define deb(x)         cout << #x<< ": "<< x<< endl;
#define sumof(x)       accumulate(x.begin(),x.end(),0);
#define rsrt(v)        sort(v.begin(),v.end(),greater<int>())
#define enter(v,n)     for(ll i=0;i<n;i++){ll x;cin>>x;v.pb(x);}
#define unique(v)      v.erase(unique(v.begin(),v.end()),v.end())
#define start          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ignore         cin.ignore (std::numeric_limits<std::streamsize>::max(),'\n');



using namespace std;

double pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664 ;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<ll,ll> mllll;
typedef map<char,ll> mchll;
typedef map<string,ll> msll;
typedef vector<pair<ll,ll>> vpllll;
typedef vector<pair<int,int>> vpiiii;

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v)
{
    os << '{';
    for (const auto &x : v) os << " " << x;
        return os << '}';
}

void solve()
{

     string s;
    cin>>s;
    string a;
    cin>>a;
    int mn=a.size();
    if(s==a)
	{
		cout << "0";
		return;
	}
    int size_of_a=a.size();
    int size_of_s=s.size();
    for(int i=0;i<(size_of_s-size_of_a)+1;i++)
    {
        string x=s.substr(i,size_of_a);
        //deb(x);
        int cnt=0;
        for(int j=0;j<size_of_a;j++)
        {
            if(x[j]!=a[j])
            {
                cnt++;
            }
        }
        mn=min(mn,cnt);
    }
    cout << mn << endl;




}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test_case=1;
    //cin>>test_case;
    while(test_case--)
	{
		solve();
	}

	return 0;
}

Measured memory_bytes: 3608
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);
        int T = int.Parse(input[2]);
        Console.WriteLine(T / A * B);
    }
}

Measured memory_bytes: 11092
open Scanf
open Printf

let id a = a
let pair a b = a, b
let triplet a b c = a, b, c

let rec scan_list = function
  | 1 -> scanf "%d" (fun k -> [k])
  | n -> scanf "%d " (fun k -> k :: scan_list (n-1))

let scan_matrix n m = let arr = Array.make_matrix n m 0 in
  for i = 1 to n do
    for j = 1 to m do begin
      if i = n && j = m
      then scanf "%d " (fun k -> arr.(i-1).(j-1) <- k)
      else scanf "%d " (fun k -> arr.(i-1).(j-1) <- k)
    end
    done
  done; arr

let f cs = let cn = Array.length cs in
  let c0 = ref [] in
  let c1 = ref [] in
  let c2 = ref [] in
  for i = 1 to cn do
    for j = 1 to cn do
      match (i+j) mod 3 with
      | 0 -> c0 := cs.(i-1).(j-1) :: !c0
      | 1 -> c1 := cs.(i-1).(j-1) :: !c1
      | 2 -> c2 := cs.(i-1).(j-1) :: !c2
      | _ -> failwith ""
    done
  done; (!c0, !c1, !c2)

let rec seq start end_ = if start = end_
  then [end_]
  else start :: seq (start+1) end_

let rec zip3 x0 y0 z0 = match x0, y0, z0 with
  | [], _, _ -> []
  | (x::xs), (y::ys), (z::zs) -> (x,y,z) :: zip3 xs ys zs

let cost ds new_c cs = List.fold_left (+) 0 @@ List.map (fun c -> ds.(c-1).(new_c-1)) cs

let costs ds cs = List.map (fun k -> cost ds k cs) (seq 1 (Array.length ds))

let min_comb ds =
  let a0 = List.sort (fun (x,_,_) (y,_,_) -> compare x y) ds in
  let a1 = List.sort (fun (_,x,_) (_,y,_) -> compare x y) (List.tl a0) in
  let a2 = List.sort (fun (_,_,x) (_,_,y) -> compare x y) (List.tl a1) in
  match List.hd a0, List.hd a1, List.hd a2 with
  | (x,_,_), (_,y,_), (_,_,z) -> x+y+z

let fold_left1 f lst = List.fold_left f (List.hd lst) (List.tl lst)

let () = let n,c = scanf "%d %d\n" pair in
  let ds = scan_matrix c c in
  let cs = scan_matrix n n in
  let c0,c1,c2 = f cs in
  let d0,d1,d2 = costs ds c0, costs ds c1, costs ds c2 in
  let ans = fold_left1 min @@ List.map min_comb
      [zip3 d0 d1 d2;
       zip3 d0 d2 d1;
       zip3 d1 d0 d2;
       zip3 d1 d2 d0;
       zip3 d2 d0 d1;
       zip3 d2 d1 d0]
  in printf "%d\n" ans

Measured memory_bytes: 24608
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;
use std::ops::Bound::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let s = read::<String>();
    let sa = construct_sa(&s);
    let lcp = construct_lcp(&s, &sa);
    let ans =
        s.len() as i64 * (s.len() as i64 + 1) / 2 - lcp.iter().map(|&x| x as i64).sum::<i64>();
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn compare_sa(i: usize, j: usize, k: usize, n: usize, rank: &Vec<i32>) -> bool {
    if rank[i] != rank[j] {
        return rank[i] < rank[j];
    }
    let ri = if i + k <= n { rank[i + k] } else { -1 };
    let rj = if i + k <= n { rank[j + k] } else { -1 };
    ri < rj
}

fn construct_sa(s: &str) -> Vec<usize> {
    let n = s.len();
    let s = s.chars().collect::<Vec<_>>();
    let mut sa = vec![0; n + 1];

    let mut rank = vec![0; n + 1];
    for i in 0..n + 1 {
        sa[i] = i;
        rank[i] = if i < n { s[i] as u64 as i32 } else { -1 };
    }

    let mut k: usize = 1;
    while k <= n {
        let mut tmp = vec![0; n + 1];
        sa.sort_by_key(|&i| (rank[i], *rank.get(i + k).unwrap_or(&-1)));
        tmp[sa[0]] = 0;
        for i in 1..n + 1 {
            tmp[sa[i]] = tmp[sa[i - 1]];
            if compare_sa(sa[i - 1], sa[i], k, n, &rank) {
                tmp[sa[i]] += 1;
            }
        }
        rank = tmp;
        k *= 2;
    }
    sa
}

fn construct_lcp(s: &str, sa: &[usize]) -> Vec<usize> {
    let s = s.chars().collect::<Vec<_>>();
    let mut rank = vec![0; s.len() + 1];
    for i in 0..s.len() + 1 {
        rank[sa[i]] = i;
    }

    let mut h = 0;
    let mut lcp = vec![0; s.len() + 1];
    for i in 0..s.len() {
        let mut j = sa[rank[i] - 1];
        if h > 0 {
            h -= 1;
        }
        while j + h < s.len() && i + h < s.len() {
            if s[i + h] != s[j + h] {
                break;
            }
            h += 1;
        }

        lcp[rank[i] - 1] = h;
    }
    lcp
}


Measured memory_bytes: 19884
def main():
  from sys import stdin
  from bisect import bisect_left
  readline = stdin.readline
  n, m = map(int, readline().split())
  data = [list(map(int, readline().split())) for _ in range(m)]
  t = [[] for _ in range(n)]
  for p, y in data:
    t[p - 1].append(y)
  for i in range(n):
    t[i].sort()
  for p, y in data:
    nth = bisect_left(t[p - 1], y) + 1
    print("%06d%06d" % (p, nth))
main()


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

using namespace std;

int insertion_sort(vector<int>& v, int length, int step) {
    int count = 0;

    for (int i = step; i < length; ++i) {
        int tmp = v[i];
        int j = i - step;
        while (j >= 0 && v[j] > tmp) {
            v[j + step] = v[j];
            j -= step;
            ++count;
        }
        v[j + step] = tmp;
    }

    return count;
}

int shell_sort(vector<int>& v, int length, vector<int>& g, int m) {
    int count = 0;

    for (int i = 0; i < m; ++i)
        count += insertion_sort(v, length, g[i]);

    return count;
}

void make_step(vector<int>& g, int target_len) {
    g.clear();

    int h = 1;
    while (true) {
        if (h > target_len)
            break;

        g.push_back(h);
        h = 3 * h + 1;
    }

    reverse(g.begin(), g.end());
}

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

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

    vector<int> g;
    make_step(g, n);
    int count = shell_sort(v, n, g, g.size());

    cout << g.size() << '\n';
    cout << g[0];
    for (int i = 1; i < g.size(); ++i)
        cout << ' ' << g[i];
    cout << '\n';

    cout << count << '\n';

    for (int i = 0; i < n; ++i)
        cout << v[i] << '\n';
}



Measured memory_bytes: 6716
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


bool ok(const string& s)
{
	int maru = 0, sika = 0;
	stack<char> use;
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i] == '(')
			++maru;
		else if (s[i] == ')')
			--maru;
		else if (s[i] == '[')
			++sika;
		else if (s[i] == ']')
			--sika;

		if (strchr("([", s[i]))
			use.push(s[i]);
		else if (strchr(")]", s[i]))
		{
			if (use.empty())
				return false;

			char last = use.top(); use.pop();
			if (last == '(' && s[i] == ']'
				|| last == '[' && s[i] == ')')
				return false;
		}
	}
	return maru == 0 && sika == 0;
}
int main()
{
	string s;
	while (getline(cin, s), s.size() > 1 || s[0] != '.')
		puts(ok(s) ? "yes" : "no");
}

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

int main() {
    long long n,m;cin>>n>>m;
    vector<long long>a(n),sum(n+1);
    sum[0]=0;
    for(int i=0;i<n;++i){
        cin>>a[i];
        sum[i+1]=a[i]+sum[i];
    }
    map<long long,long long>b;
    set<long long>c;
    for(int i=0;i<=n;++i){
        b[sum[i]%m]++;
        c.insert(sum[i]%m);
    }
    long long ans=0;
    for(auto x : c){
        ans+=b[x]*(b[x]-1)/2;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8704
#include<bits/stdc++.h>
using namespace std;
int n,h[100010],cnt=1,ans=1;
int main(){
	cin>>n>>h[0];
	for(int i=1;i<n;i++){
		cin>>h[i];
		if(h[i]<=h[i-1]){
			cnt++;
			ans=max(ans,cnt);
		}else
			cnt=1;
	}
	cout<<ans-1;
	return 0;
}

Measured memory_bytes: 640
N = int(input())
count = 0
is_true = False
for i in range(N):
    D1, D2 = map(int, input().split())
    if D1 == D2:
        count += 1
        if count == 3:
            is_true = True
    else:
        count = 0

if is_true:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9200
#include<iostream>

using namespace std;

const int nmax = 1000001;
bool sieve[nmax];

int main() {

    sieve[0] = false;
    sieve[1] = false;
    for (int i = 2; i < nmax; ++i) sieve[i] = true;
    for (int i = 2; i < nmax; ++i) {
        if (sieve[i]) for(int k = i + i; k < nmax; k += i) sieve[k] = false;
    }

    while(1) {
        int a, d, n;
        cin >> a >> d >> n;
        if (a == 0 && d == 0) break;

        int cnt = 0;
        int ai = a;
        while (1) {
            if (sieve[ai]) cnt++;
            if (cnt == n) break;
            ai += d;
            //cout << cnt << endl;
        }

        cout << ai << endl;
    }
}

Measured memory_bytes: 3988