akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    vector<int> rgb_counter(3);
    rep(i, N) {
        if (S.at(i) == 'R') rgb_counter.at(0)++;
        else if (S.at(i) == 'G') rgb_counter.at(1)++;
        else if (S.at(i) == 'B') rgb_counter.at(2)++;
    }
    
    // coindition 1
    ll ans = 1;
    rep(i, 3) ans *= rgb_counter.at(i);
    
    // converse of condition 2
    rep(j, N) {
        rep(i, j) {
            int k = j + (j - i);
            if (k < N) {
                if (S.at(i) == S.at(j)) continue;
                else if (S.at(i) == S.at(k)) continue;
                else if (S.at(k) == S.at(j)) continue;
                ans--;
            }
        }
    }
    
    cout << ans << endl;
}


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

int main(){
string s;
  cin>>s;
  if(s[0]=='C'){
  cout<<"Rainy";
  }
  else if(s[0]=='S'){
  cout<<"Cloudy";
  }
  else{
  cout<<"Sunny";
  }
return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,a,b,*x = map(int,read().split())


d = [i-j for i,j in zip(x[1:],x)]

#print(d)

ans = 0
for i in d:
    ans += min(i*a,b)

print(ans)



Measured memory_bytes: 20048
import sys

def gcd(a, b):
  a, b = max(a, b), min(a, b)
  if b == 0:
    return a
  else:
    return gcd(b, a % b)


def main():
  input = sys.stdin.readline
  N, S = map(int, input().split())
  C = list(map(int, input().split()))
  C = list(set([abs(c - S) for c in C]))
  
  ans = C[0]
  for i in range(1, len(C)):
    ans = gcd(ans, C[i])

  print(ans)


if __name__ == '__main__':
  main()


Measured memory_bytes: 17864
#include <iostream>

using namespace std;

const int INF = 1000000010;

int w[101], v[101];
int dp[101][100010];

int main() {
	int N, W;
	cin >> N >> W;
	for (int i = 1; i <= N; ++i) {
		cin >> w[i] >> v[i];
	}
	int sum_v = 0;
	for (int i = 1; i <= N; ++i) sum_v += v[i];

	for (int i = 0; i <= sum_v; ++i) dp[0][i] = INF;
	dp[0][0] = 0;

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j <= sum_v; ++j) {
			dp[i][j] = dp[i - 1][j];
			if (j >= v[i]) dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	int ans = 0;
	for (int i = 0; i <= sum_v; ++i) {
		if (dp[N][i] <= W) ans = max(ans, i);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 39680
-- Vicfred
-- https://atcoder.jp/contests/abc178/tasks/abc178_b
-- math

a, b, c, d = io.read("*n", "*n", "*n", "*n")

maxima = c*b
maxima = math.max(maxima, d*b)
maxima = math.max(maxima, c*a)
maxima = math.max(maxima, a*d)

print(maxima)



Measured memory_bytes: 2756
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const ll MAX = 210000;
const ll MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string & S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
const ll ainf = 998244353;
string calc(string v, char in) {
	string res = v + in;
	sort(res.begin(), res.end(),greater<char>());
	return res;
}
ll calc(ll p, ll s1, ll s2, ll t1, ll t2) {
	ll dis1 = p - s1;
	ll dis2 = p - t1;
	ll dis3 = s2 - p;
	ll dis4 = t2 - p;
	ll res = min(dis1 * 2 + dis4,
		min(dis4 * 2 + dis1,
			min(dis2 * 2 + dis3, dis3 * 2 + dis2)));

	if (s1 < t1) {
		res = min(res, dis1);
	}
	else res = min(res, dis2);

	if (s2 > t2) {
		res = min(res, dis3);
	}
	else res = min(res, dis4);
	return res;
}
void solv() {
	int a, b, q;
	cin >> a >> b >> q;
	ll s[100010];
	s[0] = -(INF * 10);
	s[a + 1] = (INF * 10) * 2;
	for (size_t i = 1; i <= a; i++) cin >> s[i];
	sort(s, s + a + 2);
	ll t[100010];
	t[0] = -(INF * 10);
	t[b + 1] = (INF * 10) * 2;
	for (size_t i = 1; i <= b; i++)	cin >> t[i];
	sort(t, t + b + 2);
	ll x[100010];
	for (size_t i = 0; i < q; i++) cin >> x[i];

	for (size_t i = 0; i < q; i++)
	{
		ll *sp1 = lower_bound(s, s + a + 2, x[i]);
		ll *tp1 = lower_bound(t, t + b + 2, x[i]);
		ll sp1v = *sp1;
		sp1--;
		ll tp1v = *tp1;
		tp1--;
		cout << calc(x[i], *sp1, sp1v, *tp1, tp1v) << endl;
	}
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 3712
# 解答（@maspy）

# switchが10個以下
N,M = map(int,input().split())
sw = [[] for _ in range(M)]
# print(sw) # [[], [], ..., []]

for i in range(M):
    sw[i] = list(map(int,input().split()[1:]))
# print(sw) # [[１行目], [２行目], ..., [M行目]]

p = [int(x) for x in input().split()]
import itertools

answer = 0
for tpl in itertools.product([0,1],repeat=N):
  bl = True
  for i in range(M):
    # 電球iを計算
    s = sum([tpl[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    answer += 1
print(answer)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int maxx=1e6+10;

ll a[maxx]={0},b[maxx]={0};
int main() {
	ll n,m,k;
	cin>>n>>m>>k;
	rep(i,1,n+1){
		cin>>a[i];
		a[i]+=a[i-1];
	} 
	rep(i,1,m+1){
		cin>>b[i];
		b[i]+=b[i-1];
	}
	int ans=0;
	for(int i=0,j=m;i<=n;i++){
		while(j&&a[i]+b[j]>k)j--;
		if(a[i]+b[j]<=k)ans=max(ans,i+j);
	}
	cout<<ans;
} 

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

int main(){
  int x;
  cin >> x;
  for(int a = 1; a < 1000; a++){
    int64_t a5 = pow(a,5);
    for(int b = -1000; b < 1000;b++){
      int64_t b5 = pow(b,5);
      if(a5-b5 == x){
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 4108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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; }

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

    int N; cin >> N;
    ves S(N); rep(i,N) cin >> S[i];

    vel check(5,0);
    
    rep(i,N) {
        if(S[i][0] == 'M') check[0]++;
        if(S[i][0] == 'A') check[1]++;
        if(S[i][0] == 'R') check[2]++;
        if(S[i][0] == 'C') check[3]++;
        if(S[i][0] == 'H') check[4]++;
    }

    ll ans = 0;
    for(int i=0; i<=2; i++){
        for(int j=i+1; j<=3; j++){
            for(int k=j+1; k<=4; k++){
                ans += check[i] * check[j] * check[k];
            }
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int inf = 1e9;
 
int n, u, k;
 
vector<int> cnt(10001, 0);
 
 
int main(){
	cin>>k;
	for(int i = 1; i <= 100; ++i){
		for(int j = 1; j <= 100; ++j){
			for(int k = 1; k <= 100; ++k){
				ll ans = i * i + j * j + k * k + i * j + i * k + j * k;
				if(ans <= 10000)cnt[ans]++;
			}
		}
	}
	for(int i = 1; i <= k; ++i)cout<<cnt[i]<<endl;
	return 0;
}


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

int main(void)
{
  int k;
  char s1[100];
  char s2[100];
  scanf("%d", &k);
  scanf("%s", s1);
  int i = strlen(s1);
  if(i<=k){
    printf("%s\n", s1);
  } else {
    strncpy(s2,s1,k);
    s2[k]='\0';
    printf("%s...\n", s2);
  }
  return 0;
}


Measured memory_bytes: 1728
#include<cstdio>

using namespace std;

bool flag, ans;

char a[110];

int main() {
	scanf("%s", a);
	for (int i = 0; a[i]; i++) {
		if (a[i] == 'C') {
			flag = 1;
		}
		else if (flag && a[i] == 'F') {
			ans = 1;
		}
	}
	if (ans) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <memory.h>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> P;


int main() {
	int N = 200000;
	vi p(N, 1);
	p[0] = p[1] = 0;
	rep (i, N) if (p[i]) for(int j = i + i; j < N; j += i) p[j] = 0;
	vi ps;
	rep(i, N) if (p[i]) ps.pb(i);
	
	for(int n; cin >> n, n != 0; ) {
		int sum = 0;
		rep(i, n) sum += ps[i];
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,K;
  int i=0;
  cin >> A >> B >> C >> K;
  if(A < B && B < C)
    cout << "Yes" << endl;
  
  else{ 
    for(;i<K;i++){
    if (A < B){
      break;
    }
    if (A >= B){
      B *= 2;
    }

  }
  for(int j=0;j<K-i;j++){
    if (B < C){
      break;
    }
    if (B >= C){
      C *= 2;
    }
  }
  if(A < B && B < C)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  }
  
  
  

}

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

using namespace std;

#define int long long
#define MOD 1000000007


#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define all(i) (i).begin(),(i).end()å
#define rall(i) (i).begin(),(i).end(),greater<int>()


#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T> void print(T x) { std::cout << x << '\n'; }
 
//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long


int dp[103][4][4][4];
 
signed main(){
 
    int N;
    cin >> N;

    dp[0][3][3][3]=1;

    for(int len=0;len<N;len++){
        for(int c1=0;c1<4;c1++){
            for(int c2=0;c2<4;c2++){
                for(int c3=0;c3<4;c3++){
                    if(dp[len][c1][c2][c3]==0){
                        continue;
                    }

                    for (int a = 0; a < 4; a++)
					{
						//ダメな5つの条件をカットする
						if (a == 2 && c1 == 1 && c2 == 0) continue;
						if (a == 2 && c1 == 0 && c2 == 1) continue;
						if (a == 1 && c1 == 2 && c2 == 0) continue;
						if (a == 2 && c1 == 1 && c3 == 0) continue;
						if (a == 2 && c2 == 1 && c3 == 0) continue;
 
						//ダメな条件を抜けたら、aを足した文字列が作れる
 
						// S = ...... c3 c2 c1
						// nextS = ...... c2 c1 a
 
						dp[len + 1][a][c1][c2] += dp[len][c1][c2][c3];
						dp[len + 1][a][c1][c2] %= MOD;
					}


                }




            }

        }

    }

    int ans = 0;
 
	//長さNの全部の答えを纏める
	//最後から1文字目の文字
	for (int c1 = 0; c1 < 4; c1++)
	{
		//最後から2文字目の文字
		for (int c2 = 0; c2 < 4; c2++)
		{
			//最後から3文字目の文字
			for (int c3 = 0; c3 < 4; c3++)
			{
				ans += dp[N][c1][c2][c3];
				ans %= MOD;
			}
		}
	}
 
	cout << ans << endl;



 
    return 0;
 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;i++)
#define per(i,b,a) for(int i=(b),i##_st=(a);i>=i##_st;i--)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define debug(x) cerr<<#x" = "<<x<<endl
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge *i=G[x];i;i=i->nex)
typedef pair<int,int> pii;
typedef long long ll;
const int inf=~0u>>1,MOD=1e9+7;/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int rd() {
	int x=0,c=0,f=1;
	for(; c<'0'||c>'9'; c=getchar())f=c!='-';
	for(; c>='0'&&c<='9'; c=getchar())x=x*10+c-'0';
	return f?x:-x;
}
const int N=2100;
char G[N][N];
int t[N][N],a[N][N],b[N][N],c[N][N];
int F(int x,int y,int z,int w){
	return (a[z][w]-a[x-1][w]-a[z][y-1]+a[x-1][y-1])-(b[z][w]-b[x-1][w]-b[z][y]+b[x-1][y])-(c[z][w]-c[x][w]-c[z][y-1]+c[x][y-1]);
}
int main() {
	int n = rd(), m = rd(), T = rd();
	rep(i,1,n)scanf("%s",G[i]+1);
	rep(i,1,n)rep(j,1,m){
		t[i][j] = G[i][j] - '0';
	}
	rep(i,1,n)rep(j,1,m){
		a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+t[i][j];
	}
	rep(i,1,n)rep(j,2,m){
		b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(t[i][j-1]&t[i][j]);
	}
	rep(i,2,n)rep(j,1,m){
		c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+(t[i-1][j]&t[i][j]);
	}
	
	while(T--) {
		int a = rd(), b = rd(), c = rd(), d = rd();
		printf("%d\n",F(a,b,c,d));
	}
}

Measured memory_bytes: 74752
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
	 if(0<=y&&y<n&&0<=x&&x<m) return true;
	 return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
int arr[222222];
int main(void){
	int n;
	scanf("%d",&n);
	int ans = 0;
	for(int e=0;e<n;e++){
		scanf("%d",&arr[e]);
		ans ^= arr[e];
	}
	for(int e=0;e<n;e++){
		printf("%d ",ans^arr[e]);
	}
	return 0;
}


Measured memory_bytes: 4520
n   = gets.to_i
a1  = gets.split.map(&:to_i)
a2  = gets.split.map(&:to_i)

map     = [a1, a2]
map_max = Array.new(2).map{Array.new(n, 0)}

quque = []
quque.push([0, 0, 0])
while not quque.empty? do
  i, j, max = quque.shift

  max += map[j][i]
  if map_max[j][i] < max
    map_max[j][i] = max
  end
  quque.push([i+1, j,   max]) if i+1 < n
  quque.push([i,   j+1, max]) if j+1 < 2
end

max = map_max[1][n-1]
puts max


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#include<stdio.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;


#define ll                  long long
#define scl(n)              scanf("%lld",&n)
#define scll(n, m)              scanf("%lld%lld",&n, &m)
#define scc(c)	            scanf("%c",&c)
#define fr(i,n)             for (ll i=0;i<n;i++)
#define fr1(i,n)            for(ll i=1;i<=n;i++)
#define pfl(x)              printf("%lld\n",x)
#define pb                  push_back
#define debug               cout<<"I am here"<<endl;
#define pno                 cout<<"No"<<endl
#define pys                 cout<<"Yes"<<endl
#define tcas(i,t)           for(ll i=1;i<=t;i++)
#define all(x) 	            (x).begin(), (x).end()
#define pr                  pair<ll, ll>
#define ff                  first
#define ss                  second

#define l(s)                s.size()
#define asort(a)            sort(a,a+n)
#define dsort(a)            sort(a,a+n,greater<int>())
#define vasort(v)           sort(v.begin(), v.end());
#define vdsort(v)           sort(v.begin(), v.end(),greater<int>());
#define uniquee(x)          x.erase(unique(x.begin(), x.end()),x.end())
#define pn                  printf("\n")
#define el                  cout<<endl
#define md                  1000000007
#define inf                 9e18
#define ps                  cout<<" ";
#define Pai                  acos(-1.0)
#define mem(a,i)            memset(a, i, sizeof(a))
#define pcas(i)             cout<<"Case "<<i<<": "<<endl;
#define fast 	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

#define N 200006

char ans[5];
ll v[5];

bool pal(string s)
{
    string t = s;
    reverse(all(t));
    return s == t;
}
int main()
{
     ll i , j , n, m;
     cin>>n;
     ll ans=n%1000;

     if(ans)
     {
         m=n/1000;
         m=(m+1)*1000;
         ans=m-n;
     }
     pfl(ans);

    //cout<<t<<" "<<u<<endl;
return 0;
}

/// **************************Before submit****************************

///    ****Please check all base case output  and printing " YES or NO " ***
///    *check for integer overflow,array bounds
///    *check for n=1




Measured memory_bytes: 3760
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}


int main(void){
  fast_io
  cout<<fixed<<setprecision(15);

  ll n;cin>>n;
  vector<ll> X(n), Y(n+1);
  ll next = 1;
  Y[0] = 0;
  rep(i,n){
    cin>>X[i];
    ll x = X[i];
    if(x < next){
      Y[i+1] = Y[i] + 1;
    }else{
      Y[i+1] = Y[i];
      next += 2;
    }
  }
  ll count[(int)1e5+3] = {};
  rep(i,n){
    count[Y[i]]++;
  }
  ll ans = 1;
  ll ruiseki = 0;
  rep(i,n){
    ruiseki += count[i];
    ans *= ruiseki;
    ruiseki--;
    ans %= MOD;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2560
def call(n)
  i = 1
  ans = []
  while i <= n do
    # CHECK_NUM
    x = i
    if x % 3 == 0
      ans << i
    else
      # INCLUDE 3
      while x != 0 do
        if x % 10 == 3
          ans << i
          break
        else
          x /= 10
        end
      end
    end
    i += 1
  end
  ans
end

puts " " + call(gets.to_i).join(" ")


Measured memory_bytes: 8892
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    N,=pin()
    l=[int(input())-1 for i in range(N)]
    i=0#index
    ans=0#answer
    while(i!=1):
        i=l[i]
        ans+=1
        if ans>N*10:
            print(-1)
            return
    print(ans)
    return
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
3
1
2"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
3
4
1
2"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
3
3
4
2
4"""
        output = """3"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Measured memory_bytes: 63956
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-100
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}
ii solve(int x) {
	int n = 5e3;
	for (ll a = -n; a <= n; a++) {
		for (ll b = -n; b <= n; b++) {
			ll A = a * a * a * a * a;
			ll B = b * b * b * b * b;
			if (A - B == x)
				return { a, b };
		}
	}
	assert(0);
	return { INT_MIN, INT_MIN };
}
int main() {
	//	file();
	fast();
	int x; cin >> x;
	cout << solve(x).first << ' ' << solve(x).second << endl;
	return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {
    string date;
    cin >> date;
    if (date == "SUN") cout << 7;
    else if (date == "MON") cout << 6;
    else if (date == "TUE") cout << 5;
    else if (date == "WED") cout << 4;
    else if (date == "THU") cout << 3;
    else if (date == "FRI") cout << 2;
    else if (date == "SAT") cout << 1;

    // source code
    
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

map<pll, ll> m;

ll gcd(ll a, ll b){
  if(a==1 || b==1)return 1;
  if (a < b)swap(a,b);
  if(m[{a, b}]>0)return m[{a, b}];

  m[{a, b}] = b ? gcd(b, a % b) : a;
  return m[{a, b}];
}

ll lcm(ll a, ll b){
  return a * b / gcd(a, b);
}

ll f(ll x){
  ll res=0;
  while(x%2==0){
    x /= 2;
    res++;
  }
  return res;
}

int main(){
  ll n,m;cin>>n>>m;
  vector<ll>a(n);
  rep(i, n)cin>>a[i];
  rep(i, n)a[i]/=2;

  ll t = f(a[0]);
  rep(i, t)m/=2;

  rep(i, n){
    if(f(a[i])!=t){cout<<0<<endl; return 0;}
    rep(j, t)a[i]/=2;
  }

//cout<<t<<' '<<m<<endl;

  ll base = 1;
  rep(i, n){
    base = lcm(base, a[i]);
//cout<<base<<endl;
    if(base>m){cout<<0<<endl;return 0;}
  }

  ll result = 0;
  result = ((m/base)+1)/2;
  cout<<result<<endl;

  return 0;
}


Measured memory_bytes: 1024
import bisect

def resolve():
    S = input()
    T=input()

    indexes = dict()

    for i,v in enumerate(S):
        if v in indexes:
            indexes[v].append(i)
        else:
            indexes[v]=[i]

    point =-1
    roops = 0
    for i in T:
        if not i in indexes:
            print(-1)
            return
        
        nxt = bisect.bisect_right(indexes[i],point)

        if nxt == len(indexes[i]):
            roops += 1
            point = indexes[i][0]
        else:
            point = indexes[i][nxt]


    print(len(S)*roops+point + 1)





resolve()

Measured memory_bytes: 46704
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))
#define zero(x) ((fabs(x) < eps ? 1 : 0))
int main()
{
    double A,B;
    cin>>A>>B;
    double a=A/0.08,b=B/0.1;
    if(a>b)swap(a,b);
    int l=(int)floor(a),r=(int)ceil(b),ans=r+1;
    for(int i=l;i<=r;++i)
    {
        if(floor((double)i*0.08)==A&&floor((double)i*0.1)==B)
            ans=min(ans,i);
    }
    if(ans==r+1)cout<<-1<<endl;
    else cout<<ans<<endl;
}


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

const int maxn=4005;

int n,a,b,top;
int sta[maxn];
bool ans[maxn];

int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}

int main() {
	a=read(),b=read(),n=a+b;
	if(a<=b) {puts("Impossible");return 0;}
	for(int i=1;i<=n;i++)
		if(!top)sta[++top]=i;
		else {
			printf("? %d %d\n",sta[top]-1,i-1);
			fflush(stdout);char s[3];
			scanf("%s",s+1);
			if(s[1]=='N')top--;
			else sta[++top]=i;
		}
	int honest=sta[top];
	for(int i=1;i<=n;i++) {
		printf("? %d %d\n",honest-1,i-1);
		fflush(stdout);char s[3];
		scanf("%s",s+1);
		ans[i]=(s[1]=='Y');
	}printf("! ");
	for(int i=1;i<=n;i++)
		printf("%d",ans[i]);
	return 0;
}


Measured memory_bytes: 632
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()
    s = set()
    g = set()

    for _ in range(m):
        a,b = i_map()
        if a == 1:
            s.add(b)
        elif b == 1:
            s.add(a)
        elif a == n:
            g.add(b)
        elif b == n:
            g.add(a)

    if s&g:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__=="__main__":
    main()


Measured memory_bytes: 105292
#include<bits/stdc++.h>
#define N 2000009
#define ll long long
#define ld long double
#define ff first
#define ss second
#define inf 1000000005
#define mod 1000000007
using namespace std;
string s, t;
ll dp[3009][3009];
int main() {
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>s>>t;
    dp[0][0] = dp[0][1] = dp[1][0] = 0;
    for(int i=1;i<=s.size();i++) {
        for(int j=1;j<=t.size();j++) {
            if(s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    int i = s.size(), j = t.size();
    string ans = "";
    while(dp[i][j] != 0) {
        if(s[i - 1] == t[j - 1]) {
            ans.push_back(s[i - 1]);
            i--;
            j--;
        }
        else {
            if(dp[i - 1][j] > dp[i][j - 1])
                i--;
            else
                j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;
}


Measured memory_bytes: 74112
#include <stdio.h>

void trace(int A[], int N){
    int i;
    for (i = 0; i < N; i++){
        if(i > 0) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

void insertionSort(int A[], int N){
    int j, i, v;
    for(i = 1; i <N; i++){
        v = A[i];
        j = i-1;
        while(j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1]=v;
        trace(A,N);
    }
}

int main(){
    int N, i, j;
    int A[100];

    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d", &A[i]);

    trace(A, N);
    insertionSort(A, N);
    return 0;
    }
    

Measured memory_bytes: 1768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
#define ote(x) cout<<(x)<<endl
#define rp(i,s,e) for(int i=(s);i<(e);++i)

//GCD: 最大公約数
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//LCM: 最小公倍数
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

ll f(ll x){
	ll c;
	for(c=0; !(x&1L); c++) x>>=1;
	return c;
}

ll solve(ll N, ll M, vl &A){

	// a/2 -> a'
	rp(i, 0, N){
		if(A[i]%2) return 0;
		A[i] /= 2;
	}

	// a'>>T -> a'' (T=f(a'_0))
	ll T = f(A[0]);
	for(int i=0; i<N; ++i){
		if(f(A[i]) != T) return 0;
		A[i] >>= T;
	}

	M >>= T;

	ll L = 1;
	for(ll b:A){
		L = lcm(L, b);
		if(L > M) return 0;
	}

	M /= L;

	return (M+2-1)/2;//round up
}

int main(){
	ll N,M; cin>>N>>M;
	vl A(N); rp(i, 0, N) cin>>A[i];
	ote(solve(N,M,A));
}


Measured memory_bytes: 1024
#10_B
import math
a,b,C=map(int,input().split())
S=a*b*math.sin((C*2*math.pi)/360)/2
c=math.sqrt(a**2+b**2-2*a*b*math.cos((C*2*math.pi)/360))
L=a+b+c
h=2*float(S)/a
print(str(S)+'\n'+str(L)+'\n'+str(h)+'\n')


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

int main() {
	int a, b, c;
	cin >> a >> b >> c;

	if((a >= 0) && (a <= 100)) {
		if((b >= 0) && (b <= 100)) {
			if((c >= 0) && (c <= 100)) {
				if((a < b) && (b < c)) {
					cout << "Yes" << endl;
				} else {
					cout << "No" << endl;
				}
			}
		}
	}
}

Measured memory_bytes: 3108
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define LONG_INF 800000000000000000
int segment_tree[400000] = {};
int find(int now) {
	int hoge = segment_tree[now];
	if(now != 0)
	hoge += find(now / 2);
	return hoge;
}
void sete(int now, int now_l, int now_r, int req_l, int req_r) {
	if (now_l >= req_l&&now_r - 1 <= req_r) {
		segment_tree[now]++;
	}
	else {
		if (now_r - 1 >= req_l&&now_l <= req_r) {
			sete(now * 2, now_l, (now_l + now_r) / 2, req_l, req_r);
			sete(now * 2 + 1, (now_l + now_r) / 2, now_r, req_l, req_r);
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<tuple<int,int, int>> hoge;
	for (int i = 0;i < n;++i) {
		int a, b;
		cin >> a >> b;
		hoge.push_back(make_tuple(b-a+1,a, b));
	}
	sort(hoge.begin(), hoge.end());
	int now_cnt = 0;
	int re = 1;
	while (true) {
		if (re >= m) break;
		re *= 2;
	}
	for (int i = 1;i <= m;++i) {
		while (true) {
			if (now_cnt == n||get<0>(hoge[now_cnt]) >= i) break;
			sete(1,1, re+1, get<1>(hoge[now_cnt]), get<2>(hoge[now_cnt]));
			now_cnt++;
		}
		int ans = n - now_cnt;
		for (int q = 1;q*i <= m;++q) {
			ans += find(re + (q*i)-1);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 6640
#include<stdio.h>
int main(){
  long int n;
  scanf("%ld",&n);
  long int a[n],i;
  long int s=1000000,l=-1000000,ans=0;
  for(i=0;i<n;i++){
    scanf("%ld",&a[i]);
    if(s>a[i])s=a[i];
    if(l<a[i])l=a[i];
    ans+=a[i];
  }
  printf("%ld %ld %ld\n",s,l,ans);
  return 0;
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


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

    string A="AKIHABARA",B="KIHABARA",C="AKIHBARA",
            D="AKIHABRA",E="AKIHABAR",F="AKIHABR",
             G="AKIHBAR",H="KIHABAR",I="AKIHBRA",
              J="KIHABRA",K="KIHBARA",L="AKIHBR",
               M="KIHABR",N="KIHBAR",O="KIHBRA",P="KIHBR";

    if(s==A||s==B||s==C||s==D||s==E||s==F||s==G||s==H||
            s==I||s==J||s==K||s==L||s==M||s==N||s==O||s==P){
            cout<<"YES"<<endl;
            return 0;
    }

    cout<<"NO"<<endl;

}


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

bool Judge_Prime_Number( int x )
{
    for( int i = 2; i <= sqrt(x); i++ )
    {
        if( x % i == 0 )
            return false;
    }
    return true;
}

int main()
{
    int a;

    while( cin >> a )
    {
        int min = a - 1, max = a + 1;

        while( Judge_Prime_Number(min) == false )
            min--;
        while( Judge_Prime_Number(max) == false )
            max++;
        
        cout << min << " " << max << endl;
    }

    return 0;
}


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

using namespace std ;

const long long mod = 998244353 ;
const int MAX = 3000 + 10 ;

long long fastpow(long long base , long long power)
{
	if(power == 0)
		return 1ll ;
	long long x = fastpow(base , power / 2ll) ;
	x = (x * x) % mod ;
	if(power & 1)
		x = (x * base) % mod ;
	return x ;
}

long long ModInv(long long a , long long b)
{
	return ((a * fastpow(b , mod-2ll)) % mod) ;
}

long long add(long long x , long long y)
{
	long long z = (x + y) % mod ;
	return z ;
}

int arr[MAX] ;
int n , s ;

long long dp[MAX][MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>s ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	long long P = 1ll ;
	for(int i = 1 ; i <= n ; ++i)
		P = (P * 2ll) % mod ;
	dp[0][0] = P ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 0 ; j <= s ; ++j)
		{
			dp[i][j] = dp[i-1][j] ;
			if(j - arr[i] >= 0)
				dp[i][j] = add(dp[i][j] , ModInv(dp[i-1][j-arr[i]] , 2ll)) ;
		}
	}
	return cout<<dp[n][s]<<"\n" , 0 ;
}		

Measured memory_bytes: 74176
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 998244353
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif

const int INF = 0x7fffffff;
const int N=2e6+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}/*
struct Edge{
	int nxt,v;
//	int w;
//	int id;
}e[N<<1];
void add(int u,int v){
	e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;
	e[++tot].v=u,e[tot].nxt=head[v],head[v]=tot;
}*/
ll n,m,rt=1,tot=1,ans,c[N][26],d[N][26],e[N][26],fa[N],f[N];
char s[N];
vector<int>V[N];
void dfs(int p){
	for(int i=0;i<26;i++){
		if(!c[p][i]) continue;
		dfs(c[p][i]);
		f[p]+=f[c[p][i]];
		for(int j=0;j<26;j++){
			d[p][j]+=d[c[p][i]][j];
		}
	}
	for(auto j:V[p]){
//		bug(d[p][j]);
		ans+=d[p][j]-1;
	}
	for(int j=0;j<26;j++){
		if(e[p][j]) d[p][j]=f[p];
		else d[p][j]+=e[p][j];
	}
}
int main(){
#ifdef Devil_Gary
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endif
	n=read();
	for(int i=1;i<=n;i++){
		cin>>s+1;
		m=strlen(s+1);
		reverse(s+1,s+m+1);
		int p=rt;
//		cout<<s+1<<endl;
//		bug(i);
		for(int j=1;j<=m;j++){
			int x=s[j]-'a';
			if(!c[p][x]) c[p][x]=++tot;
			fa[c[p][x]]=p,p=c[p][x];
			e[p][x]++;
		}
		V[fa[p]].pb(s[m]-'a');
		f[p]++;
	}
	dfs(rt);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 744632
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

bool can = true;

vector<vector<bool> > bridge(700, vector<bool>(700, false));
vector<bool> non_visit(700, false);

vector<bool> black(700,false);

int paint(int idx,bool b){
  non_visit[idx] = false;
  black[idx] = b;
  int blacksum = 0;
  REP(i, bridge[idx].size())
  {
    if(bridge[idx][i]){
      if(non_visit[i]){
        blacksum+=paint(i, !b);
      }
      else
      {
        if(black[i] != !b){
          can = false;
        }
      }
    }
  }
  blacksum += b ? 1 : -1;
  return blacksum;
}

int main() {
  int N, M;
  cin >> N >> M;
  REP(i,N){
  REP(j,N){
    if(i!=j){
      bridge[i][j] = true;
    }
  }
  non_visit[i] = true;
  }
  REP(i,M){
    int a, b;
    cin >> a >> b;
    bridge[a - 1][b - 1] = false;
    bridge[b - 1][a - 1] = false;
  }

  vector<int> num(0);

  REP(i, N)
  {
    if(non_visit[i]){
      num.push_back(abs(paint(i,true)));
    }
  }

  if(can){
    vector<bool> hoge(4000, false);
    hoge[2000] = true;
    REP(i,num.size()){
    vector<bool> newhoge(4000, false);
    for (int j = 1000; j <= 3000;++j){
      if(hoge[j+num[i]]||hoge[j-num[i]]){
        newhoge[j] = true;
      }
    }
    REP(i,newhoge.size()){
      hoge[i] = newhoge[i];
    }
    }
    int min = 9999;
    REP(i,hoge.size()){
      if(hoge[i]){
        if(min>abs(i-2000)){
          min = abs(i - 2000);
        }
      }
    }
    for (int i = 0; i <= N;++i){
      int n = i;
      int m = N - i;
      if(abs(n-m)==min){
        cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
        break;
      }
    }
  }
  else
  {
    cout << -1 << endl;
  }
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
//#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
//#include <list>
#include <iomanip>
//#include <stdlib.h>
//#include <cctype>

using namespace std;

const int MAX_N = 1000000;
#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define prec std::cout << std::fixed << std::setprecision(15);
#define endl "\n"
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define ssort(z) sort(z.begin(), z.end())
#define rsort(z) sort(z.rbegin(), z.rend())
#define eerase(z) z.erase(unique(z.begin(), z.end()), z.end())
#define ccnt(z, w) count(z.begin(), z.end(), w)
template <typename T>
void printV(const std::vector<T>& v, const char * const separator = " ")
{
    if(!v.empty())
    {
        std::copy(v.begin(),
                  --v.end(),
                  std::ostream_iterator<T>(std::cout, separator));
        std::cout << v.back() << "\n";
    }
}


Int gcd(Int a, Int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

Int lcm(Int a, Int b) {
    return a / gcd(a, b) * b;
    //a*bは64bit integer overflow
}

int Max(int a, int b, int c) {
    int temp = max(a, b);
    return max(temp, c);
}

int Min(int a, int b, int c) {
    int temp = min(a, b);
    return min(temp, c);
}

bool integer(double num) {
    return floor(num) == num;
}

Int fact(int num) {
    if (num == 0)
        return 1;
    else
        return num * fact(num - 1);
}

void y() {
    cout << "Yes" << endl;
    exit(0);
}

void n() {
    cout << "No" << endl;
    exit(0);
}

void Y() {
    cout << "YES" << endl;
    exit(0);
}

void N() {
    cout << "NO" << endl;
    exit(0);
}

Int yakusu(int n) {
    int cnt = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cnt++;
            if (i * i != n) cnt++;
        }
    }
    return cnt;
}

/*   kokomade  */

int cnt = 0;
bool is_prime[ 50000 + 1 ];
vector<int> P;
void Eratosthenes( const int N )
{
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;//初期化
    }
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
}

int main() {
    IOS;
    //int n,x,t;cin>>n>>x>>t;
    // int a,b,c;cin>>a>>b>>c;
    string str,str2;cin>>str>>str2;
    //vector<int> l(n);
    vector<string> s(str.size()),t(str.size());
    for (int i = 0; i < str.size(); ++i) {
        s[i]=str[i];
        t[i]=str2[i];
    }
    int cnt=0;
    for (int i = 0; i < str.size(); ++i) {
        if(s[i]==t[i])cnt++;
    }

    cout<<cnt;


    cout<<endl;
    return 0;
}

/*
テレビも無ェ ラジオも無ェ
自動車もそれほど走って無ェ
ピアノも無ェ バーも無ェ
巡査 毎日ぐーるぐる
朝起ぎで 牛連れで
二時間ちょっとの散歩道
電話も無ェ 瓦斯も無ェ
バスは一日一度来る
俺らこんな村いやだ 俺らこんな村いやだ
東京へ出るだ 東京へ出だなら
銭コァ貯めで 東京でベコ(牛)飼うだ
*/


Measured memory_bytes: 256
/*
Author : Chandan Agrawal
College : Poornima College of Engg. jaipur, Raj
Mail : chandanagrawal23@gmail.com


" when you are not practicing someone else is ,
 and the day u meet them u will lose "

*/
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 200050

#define ll long long
#define ld long double
#define lli long long int

#define pb push_back
#define INF 1000000000000
#define mod 1000000007

// trignometric function always give value in Radians only
#define PI acos(-1) //3.1415926535897932384626433832795028
#define dsin(degree) sin(degree*(PI/180.0))
#define dcos(degree) cos(degree*(PI/180.0))
#define dtan(degree) tan(degree*(PI/180.0))

#define rsin(radian) sin(radian)
#define rcos(radian) cos(radian)
#define rtan(radian) tan(radian)

#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))

#define loop(i,n)  for (lli i = 0; i < n; i++)
#define FOR(i,a,b) for (lli i = a; i < b; i++)

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
#define sz(x) int(x.size())
#define F first
#define S second

#define mii map<lli,lli>

#define pii pair<lli,lli>

#define vi vector<lli>
#define vvi vector<vi>
#define vpi vector<pii>
#define vbool vector<bool>

#define seti set<lli>

#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)

#define endl '\n'

template <typename Head>
void print(Head&& head)
{
    cout<<head<<endl;
}
template <typename Head, typename... Tail>
void print(Head&& head, Tail... tail)
{
    cout<<head<<" ";
    print(tail...);
}

#define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
#define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}

#define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
#define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";

#define FD(N) fixed<<setprecision(N)

#define deb(x) cout<<#x<<" "<<x<<endl;

/*
1D vector -  vi dp(n,value);
2D vector -  vvi dp(n,vi(n,value));
*/

// chandan1,2
void chandan1(){int y=1;return;}
void chandan2(){
        loop(i,10){
        lli x=1;
    }
    return(chandan1());
}

ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}

ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}

ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}

lli fastexpo(lli a,lli b ,lli MOD = mod){
    a = a%MOD;
    //b = b%(mod-1); // if mod is prime then only
    lli ans=1;
    while(b){
        if(b&1)
            ans=(ans*1ll*a)%MOD;
        a=(a*1ll*a)%MOD;
        b=b/2;
        }
    return ans;
 }

int main(){
fastio
lli t=1;
//cin>>t;
chandan2();
while(t--) {
    lli n;
    cin>>n;
    if(n==1)
        print(0);
    else{
        lli ans = fastexpo(10,n);
        ans = modsub(ans,modmul(2,fastexpo(9,n)));
        ans = modadd(ans,fastexpo(8,n));
        print(ans);
    }
  }
return 0;
}



Measured memory_bytes: 3668
#include <stdio.h>

int main()
{
    int a, b, result;
    char op;

    for(;;) {
        scanf("%d %c %d", &a, &op, &b);
 
        if(op == '?') {
            break;
        }
        else if(op == '+') {
            result = a + b;
        }
        else if(op == '-') {
            result = a - b;
        }
        else if(op == '*') {
            result = a * b;
        }
        else if(op == '/') {
            result = a / b;
        }

        printf("%d\n", result);
  
    }

    return(0);
}


Measured memory_bytes: 2112