akhauriyash/Code-Regression huggingface dataset:
import math
# isprime, prime_division
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z): # z : output of prime_division
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n = inn()
p = []
for i in range(11,55555,5):
    if isprime(i):
        p.append(i)
        if len(p)==n:
            break

pad = ''
for x in p:
    printn(pad + str(x))
    pad = ' '
print("")


Measured memory_bytes: 38512
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n, w = list(map(int, input().strip().split()))
    dp = [[0] * (w+5) for _ in range(n+5)]
    items = [[] for _ in range(n)]
    for i in range(n):
        items[i] = list(map(int, input().strip().split()))
    for i in range(1, n+1):
        for j in range(1, w+1):
            if j-items[i-1][1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-items[i-1][1]]+items[i-1][0])
    print(dp[n][w])

if __name__ == '__main__':
    main()



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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

int main() {
  cout << setprecision(18);
  i32 K, N;
  cin >> K >> N;
  vector<i32> A(N), Diff(N, 0);
  ArrayInput(A);
  for (u32 i = 0; i < N - 1; ++i) {
    Diff[i] = A[i + 1] - A[i];
  }
  Diff[N - 1] = (K + A[0]) - A[N - 1];
  u64 res = 0;
  for (u32 i = 0; i < N; ++i) {
    res += Diff[i];
  }
  cout << res - *max_element(Diff.begin(), Diff.end()) << endl;
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    (a *= a) %= MOD;
    n >>= 1;
  }
  return res;
}

const ll maxf = 10000000;
ll fact[maxf+5];

void fact_init(){
  fact[0] = 1;
  for(ll i=1; i<=maxf; i++){
    fact[i] = (fact[i-1] * i) % MOD;
  }
}

ll comb(ll a, ll b){
  if(a<b || a<0 || b<0) return 0;
  if(fact[0] == 0) fact_init();
  return (fact[a] * modpow((fact[a-b]*fact[b])%MOD, MOD-2)) % MOD;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,k; cin>>n>>k;
  vll a(n);
  rep(i,n) cin>>a[i];
  sort(a.rbegin(),a.rend());
  ll max=0;
  rep(i,n-k+1){
    max+=(a[i]*comb(n-i-1,k-1))%MOD;
    max%=MOD;
  }
  vsort(a);
  ll min=0;
  rep(i,n-k+1){
    min+=(a[i]*comb(n-i-1,k-1))%MOD;
    min%=MOD;
  }
  
  ll ans=max-min;
  while(ans<0) ans+=MOD;
  ans%=MOD;
  cout<<ans<<endl;
}

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

using namespace std;
int main(){
  int n, m, ans, i, maxl = 0, minr;
  cin >> n >> m;
  int li[m];
  int ri[m];
  minr = n;
  for(i = 0;i < m;i++){
    cin >> li[i] >> ri[i];
  }
  for(i = 0;i < m;i++){
    maxl = max(maxl,li[i]);
  }
  for(i = 0;i < m;i++){
    minr = min(minr,ri[i]);
  }
  ans = minr - maxl + 1;
  if(ans < 0){
    ans = 0;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <iomanip>

int main(){
  double L = 0;
  std::cin >> L;
  double a = L / 3;
  std::cout << std::setprecision(15) << (double)a * a * a << std::endl;
  return 0;
}


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

#define Int register int

const int MAXN = 50, MOD = 1e9 + 7;
int n, m, a[MAXN * 2 + 5], F[MAXN + 5][MAXN * 2 + 5][MAXN * 2 + 5];

inline void Add ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }

inline void Work () {
	scanf ( "%d", &n ), m = ( n << 1 ) - 1;
	for ( Int i = 1; i <= m; ++ i ) scanf ( "%d", &a[i] );
	std :: sort ( a + 1, a + m + 1 );
	F[n][0][0] = 1;
	for ( Int i = n; i ^ 1; -- i ) {
		bool ul = a[i] ^ a[i - 1], ur = a[m - i + 1] ^ a[m - i + 2];
		for ( Int j = 0; j <= m; ++ j ) {
			for ( Int k = 0, now; k <= m; ++ k ) {
				if ( ! ( now = F[i][j][k] ) ) continue;
				Add ( F[i - 1][j + ul][k + ur], now );
				for ( Int t = 0; t < j + ul; ++ t ) Add ( F[i - 1][t][k + ur + 1], now );
				for ( Int t = 0; t < k + ur; ++ t ) Add ( F[i - 1][j + ul + 1][t], now );
			}
		}
	}
	int Ans = 0;
	for ( Int i = 0; i <= m; ++ i ) {
		for ( Int j = 0; j <= m; ++ j ) {
			Add ( Ans, F[1][i][j] );
		}
	}
	printf ( "%d\n", Ans );
}

int main () {
//	freopen ( "hardest.in", "r", stdin );
//	freopen ( "hardest.out", "w", stdout );
	Work ();
	return 0;
}

Measured memory_bytes: 1408
package main

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

var Reader *bufio.Reader = bufio.NewReader(os.Stdin)
var Writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func Printf (f string, a ...interface{}) { fmt.Fprintf(Writer, f, a...) }
func Scanf (f string, a ...interface{}) { fmt.Fscanf(Reader, f, a...) }
func Println (a ...interface{}) { fmt.Fprintln(Writer, a...)}
func Scanln (a ...interface{}) { fmt.Fscanln(Reader, a...)}

func main() {
    defer Writer.Flush()
    var t int = 1
    Scanln(&t)
    var s string
    m := make(map[string]int)
    for t > 0 {
         Scanln(&s)
        m[s] += 1
        t -= 1
    }
    cnt := 0
    for _, _ = range m {
        cnt += 1
    }
    Println(cnt)
}


Measured memory_bytes: 17856
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
x = list(map(int,input().split()))

x.sort()

#p : 同じやつの組が何ペア
p = [0]*m
# mod M 何個
q = [0]*m

cnt = 1
for i in range(n):
    q[x[i]%m] += 1
    if i == n-1 or x[i] != x[i+1]:
        p[x[i]%m] += cnt//2
        cnt = 1
    else:
        cnt += 1

res = 0

for i in range(m):
    if i==0:
        res += q[0]//2
        continue
    if i > m-i:
        break
    if i == m-i:
        res += q[i]//2
        continue

    if q[i] >= q[m-i]:
        res += q[m-i]
        q[i] -= q[m-i]
        res += min(q[i]//2,p[i])
    else:
        res += q[i]
        q[m-i] -= q[i]
        res += min(q[m-i]//2,p[m-i])
print(res)


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

int main(){
  int N;
  cin >> N;
  int recorder=0;
  int sum=0;
  vector<vector<int>> D(N, vector<int>(2));
  for(int i=0;i<N;i++){
    for(int k= 0; k<2;k++){
      cin >> D.at(i).at(k);
    }
    if(D.at(i).at(0)==D.at(i).at(1)){
      recorder = recorder+1;
      if(recorder>=3){
        sum = 1;
      }
    }
    else{
      recorder=0;
    }
  }
  if(sum==1){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

using namespace std;

#define endl '\n'
#define ll long long
#define mod 1000000007

// class combinatorics{
//     public:
//         static const int mx = 1e6+1;
//         ll factorial[mx+1];
//         //pre-calculation factorial under mod;
//         combinatorics(){
//             factorial[0] = 1;
//             factorial[1] = 1;
//             for(int i = 2;i<=mx;i++){
//                 factorial[i] = (i * factorial[i-1]) % mod;
//             }
//         }
//         ll power(ll b,ll p){
//             ll ans = 1;
//             while(p > 0){
//                 if(p & 1)ans = (ans * b) % mod;
//                 p = p>>1;
//                 b = (b*b) % mod;
//             }
//             return ans;
//         }
//         //remember mod must be prime number
//         ll inverse(int n){
//             return power(n,mod-2);
//         }
//         // ll nCr(ll n,ll r){
//         //     return (factorial[n] * inverse((factorial[n-r] * factorial[r]) % mod)) % mod;
//         // }
//         // ll nPr(ll n,ll r){
//         //     return (factorial[n] * inverse(factorial[n-r]))%mod;
//         // }
// };

int main() {
    int n;
    cin>>n;
    ll arr[2010] = {0};
    arr[3] = 1;
    for(int i = 4;i<=n;i++){
        for(int j = 3;j<=i;j++){
            int k = i - j;
            if(k >= 3){
                arr[i] += arr[k];
                arr[i] %= mod;
            }else{
                break;
            }
        }
        arr[i] += 1;
        arr[i] %= mod;
    }
    cout<<arr[n];
    return 0;
}

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

	int dice[6];
	int i,t;
	
void nmov(){
	int buf;
	 buf = dice[0];
	dice[0] = dice[1];
	dice[1] = dice[5];
	dice[5] = dice[4];
	dice[4] = buf;
}
void emov(){
	int buf;
	buf = dice[0];
	dice[0] = dice[3];
	dice[3] = dice[5];
	dice[5] = dice[2];
	dice[2] = buf;
}
void wmov(){
	int buf;
	buf = dice[0];
	dice[0] = dice[2];
	dice[2] = dice[5];
	dice[5] = dice[3];
	dice[3] = buf;
}
void smov(){
int buf;
	buf = dice[0];
	dice[0] = dice[4];
	dice[4] = dice[5];
	dice[5] = dice[1];
	dice[1] = buf;
}

int main(){
	for(i=0;i<6;i++){
	scanf("%d",&dice[i]);
	}
	char c[105];
	scanf("%s",c);
	for(i=0; i<strlen(c); i++){
		if(c[i]=='N'){nmov();}
		else if(c[i]=='E'){emov();}
		else if(c[i]=='W'){wmov();}
		else if(c[i]=='S'){smov();}
	}
	printf("%d\n",dice[0]);
         
    return 0;
}



Measured memory_bytes: 2112
def findSumOfDigits(x):
	sum=0
	while x>0:
		sum+=int(x%10)
		#sum+=x%10
		x=int(x/10)
	return sum
	#sum+=x%10の場合、return int(sum)



n,a,b=map(int,input().split())
total=0
total_2=0
for i in range(1,n+1):
	total=findSumOfDigits(i)
	if a<=total<=b:
		total_2+=i

print(total_2)









Measured memory_bytes: 3060
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;
import std.bitmanip;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readC(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=rdsp;foreach(ref v;t)pick(r,v[i]);}}

void main()
{
  int n, ma, mb; readV(n, ma, mb);
  int[] a, b, c; readC(n, a, b, c);

  auto as = a.sum, bs = b.sum;
  auto dp = new int[][][](n+1, as+1, bs+1), inf = 10^^9;
  foreach (ref dpi; dp)
    foreach (ref dpij; dpi)
      dpij[] = inf;

  dp[0][0][0] = 0;

  foreach (i; 0..n)
    foreach (j; 0..as+1)
      foreach (k; 0..bs+1) {
        dp[i+1][j][k] = dp[i][j][k];
        if (j >= a[i] && k >= b[i])
          dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j-a[i]][k-b[i]]+c[i]);
      }

  auto ans = inf;
  foreach (j; 1..as+1)
    foreach (k; 1..bs+1)
      if (j*mb == k*ma)
        ans = min(ans, dp[n][j][k]);

  writeln(ans == inf ? -1 : ans);
}


Measured memory_bytes: 13180
n,c = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(c)]
lic = [list(map(int,input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        lic[i][j] -= 1

dict0 = {}
dict1 = {}
dict2 = {}
li0 = []
li1 = []
li2 = []

for i in range(n):
    for j in range(n):
        color = lic[i][j]
        if (i+j) % 3 == 0:
            if color in dict0:
                dict0[color] += 1
            else:
                dict0[color] = 1
                li0.append(color)
        elif (i+j) % 3 == 1:
            if color in dict1:
                dict1[color] += 1
            else:
                dict1[color] = 1
                li1.append(color)
        else:
            if color in dict2:
                dict2[color] += 1
            else:
                dict2[color] = 1
                li2.append(color)


ans = 10 ** 10

for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                ans_tmp = 0
                for ii in li0:
                    if ii != i:
                        ans_tmp += d[ii][i] * dict0[ii]
                for jj in li1:
                    if jj != j:
                        ans_tmp += d[jj][j] * dict1[jj]
                for kk in li2:
                    if kk != k:
                        ans_tmp += d[kk][k] * dict2[kk]
                ans = min(ans, ans_tmp)

print(ans)


Measured memory_bytes: 47452
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
#define ck(a,b) (0<=(a)&&(a)<(b))
using namespace std;

bool bb[7400000];
void bb_hurui(int m,int n){
	int a=0;
	for(int i=m;a<n;i++){
		if(bb[i]) {
			continue;
		}
		for(int j=i;j<7400000;j+=i){
			bb[j]=true;
		}
		a++;
	}

}
int main(){
	int m,n;
	while(cin>>m>>n,n){
		memset(bb,false,sizeof(bb));
		bb_hurui(m,n);
		REP(i,m,7400000){
			if(!bb[i]){
				p(i);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 10304
#include <stdio.h>
#define read(x) scanf("%d",&x)
#define write(x) printf("%d",x)
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;

int main(){
 
	int n;
	read(n);
	write(n*n);	
	return 0;
}


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

int main()
{
    int a, b;
    cin >> a >> b;
    if (a % 3 == 0) {
        cout << "Possible" << endl;
    } else if (b % 3 == 0) {
        cout << "Possible" << endl;
    } else if ((a + b) % 3 == 0) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}


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

int main() {
  
  int X;
  cin >> X;
  
  int a = X / 500;
  int b = X % 500;
  
  if (b == 0) {
    cout << a * 1000 << endl;
  }
  
  else {
    int c = b / 5;
    cout << a * 1000 + c * 5 << endl;
  } 
    
}

Measured memory_bytes: 256
while True:
    n = int(input())
    if n==0:
        break
    w = [len(input()) for i in range(n)]
    a = [5,7,5,7,7]
    ans = n+1
    for i in range(n):
        k,s = 0,0
        for j in range(i,n):
            s += w[j]
            if s==a[k]:
                s,k=0,k+1
            elif s>a[k]:
                break
            if k==5:
                ans = min(ans,i+1)
                break
    print(ans)


Measured memory_bytes: 5616
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n), f(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> q[i];
    for (int i = 1; i <= n; i++) f[i - 1] = i;
    int a = 0, b = 0, cnt = 1;
    do {
        bool f1 = true, f2 = true;
        for (int i = 0; i < n; i++) {
            if (f[i] != p[i]) f1 = false;
            if (f[i] != q[i]) f2 = false;
        }
        if (f1) a = cnt;
        if (f2) b = cnt;
        cnt++;
    } while (next_permutation(f.begin(), f.end()));
    cout << abs(a - b) << endl;
    return 0;
}


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

int main() {
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
  double A,B;
  cin>>A>>B;
  int x;
  double y,z,w;
  y=(A-0.001)/0.08;
  z=(B-0.001)/0.1;
  w=max(y,z)+1;
  x=w;
  if(0.08*x<A+1&&0.1*x<B+1)
    cout<<x;
  else
    cout<<-1;
}

Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0].split(" ")[0]);
  var M = parseInt(input[0].split(" ")[1]);
  C=new Array(M);
  P=new Array(0);
  for(i=0;i<M;i++){
    tmp=input[i+1].split(" ");
    Csub=[parseInt(tmp[0]),parseInt(tmp[1]),i];
    C[i]=Csub;
  }
  C.sort((a, b)=>(a[0]-b[0]||a[1]-b[1]));
  for(i=0;i<M;i++){
    var y="";
    c=`00000${C[i][0]}`.slice(-6);
    if(i==0){
      var cnt=1;
    }else if(C[i][0]!=C[i-1][0]){
      cnt=1;
    }else{
      cnt++;
    }
    y=`00000${cnt}`.slice(-6);
    P.push([`${c}${y}`,C[i][2]]);
  }
  P.sort((a,b)=>a[1]-b[1]);
  var ans="";
  for(i=0;i<M;i++){
    if(i!=M-1){
      ans=ans+P[i][0]+"\n";
    }else{
      ans=ans+P[i][0];
    }
  }


  console.log('%s', ans);
}
  
// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(){
  var input = document.getElementById("input").value;
  Main(input);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 72196
'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const K = parseInt(args[0][0], 10)
	const X = parseInt(args[0][1], 10)
	const ans = []

	for (let i = -1000000; i <= 10000000; i++) {
		if ((X - (K - 1) <= i) && (i <= X + (K - 1))) ans.push(i)
	}

	console.log(ans.join(' '))
}

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


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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randi(int a, int b) { return uniform_int_distribution(a, b)(rng); }

struct rolling_hash {
  static constexpr uint64_t mod = 2e9 + 33;
  static inline array<long long, 2> base{randi(1e9, 2e9), randi(1e9, 2e9)};
  static inline array<vector<int>, 2> powb{vector{1}, vector{1}};
  int n;
  array<vector<int>, 2> h{vector{0}, vector{0}};
  template <class S = string> rolling_hash(const S& s = "") : n(size(s)) {
    for (int k : {0, 1}) {
      for (auto c : s) h[k].push_back((h[k].back() * base[k] + c) % mod);
      while ((int)size(powb[k]) <= n)
        powb[k].push_back(powb[k].back() * base[k] % mod);
    }
  }
  int get(int l, int r, int k) const {
    return (h[k][r] + (mod - h[k][l]) * powb[k][r - l]) % mod;
  }
  auto get(int l, int r) const { return make_pair(get(l, r, 0), get(l, r, 1)); }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<rolling_hash> rh(n);
  vector<vector<pair<int, int>>> v(26);
  for (auto&& e : rh) {
    string s;
    cin >> s;
    reverse(begin(s), end(s));
    e = s;
    int bt = 0;
    for (int i = e.n; i--; ) {
      bt |= 1 << (s[i] - 'a');
      auto p = e.get(0, i);
      for (int x = 0; x < 26; ++x) {
        if (~bt >> x & 1) continue;
        v[x].push_back(p);
      }
    }
  }
  for (auto&& e : v) {
    sort(begin(e), end(e));
  }
  auto res = 0LL;
  for (auto&& e : rh) {
    auto&& vx = v[e.get(e.n - 1, e.n, 0) - 'a'];
    auto p = e.get(0, e.n - 1);
    res += upper_bound(begin(vx), end(vx), p) - lower_bound(begin(vx), end(vx), p);
  }
  cout << res - n << '\n';
}


Measured memory_bytes: 214092
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		boolean b = false;
		for (int i = 0; i < nums.length; i++) {
			if (N % nums[i] == 0 && N / nums[i] <= 9) {
				System.out.println("Yes");
				b = true;
				break;
			}
		}
		if (!b) {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
static const int INFTY = (1 << 21);
static const int BLACK = 1;
static const int Maxn = 110;

int n, M[Maxn][Maxn], p[Maxn], d[Maxn], color[Maxn];
void dijkstra(){
	for(int i = 0; i < n; i++){
		d[i] = INFTY;
		p[i] = -1;
	}
	d[0] = 0;
	while(1){
		int minv = INFTY, u = -1;
		for(int i = 0; i < n; i++){
			if(d[i] < minv && color[i] != BLACK){
				minv = d[i];
				u = i;
			}
		}
		if(u == -1) break;
		color[u] = BLACK;
		for(int v = 0; v < n; v++){
			if(color[v] != BLACK && M[u][v] + d[u] < d[v]){
				d[v] = M[u][v] + d[u];
				p[v] = u;
			}
		}
	}
	for(int i = 0; i < n; i++) cout << i << " " << d[i] << endl;
}
int main()
{
	memset(M, -1, sizeof(M));
	int u, k, t, c;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> u >> k;
		while(k--){
			cin >> t >> c;
			M[u][t] = c;
		}
		for(int j = 0; j < n; j++) 
			if(M[u][j] == -1)  M[i][j] = INFTY;
	}	
	/*for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) cout << M[i][j] << " ";
		cout << "\n";
	}*/
	dijkstra();
	return 0;
}


Measured memory_bytes: 3140
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string s;
	cin >> n >> s;
	if(n&1) {
		cout << "No";
		return 0;
	}
	n/=2;
	for(int i = 0; i + n < s.size(); i++)
		if(s[i]!=s[i+n]) return cout << "No", 0;
	cout << "Yes";
}


Measured memory_bytes: 256
//Name: Perfect Number
//Level: 2
//Category: 数学,Math,素数,素因数分解
//Note:

/**
 * n = Πp_i^a_i と素因数分解したとき、約数の和は Π_{i <φ(n)} Σ_{0≦j≦a_i} p_i^j となる。
 * オーダーは O(log N)。
 */
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>

using namespace std;

const long long SQMAX = 10000;
array<bool,SQMAX+1> is_prime;
vector<long long> primes;

bool solve() {
    int N;
    cin >> N;
    if(!N) return false;

    int tmp = N;
    long long ans = 1;
    for(long long p : primes) {
        if(p > tmp) break;
        long long s = 1;
        long long fac = 1;
        while(tmp % p == 0) {
            tmp /= p;
            fac *= p;
            s += fac;
        }
        ans *= s;
    }
    if(tmp > 1) {
        ans *= (1 + tmp);
    }
    ans -= N;
    if(ans == N) {
        cout << "perfect number" << endl;
    } else if(ans < N) {
        cout << "deficient number" << endl;
    } else {
        cout << "abundant number" << endl;
    }
    return true;
}

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

    fill(begin(is_prime), end(is_prime), true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= SQMAX; ++i) {
        if(is_prime[i]) {
            primes.push_back(i);
            for(long long j = (long long)i*i; j <= SQMAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define X first
#define Y second
#define PB push_back
#define SORT(a) sort(a.begin(), a.end())
#define CLR(a) memset(a, 0, sizeof(a))
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FOE(i,a,b) for (int i=(a);i<=(b);i++)
//#define FIT(i,a) for (__typeof__((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define FOREACH(i,a) for (auto i = (a).begin(); i != (a).end(); i++)
#define TRA(i,a,b) for (int i = (a); i != -1; i = (b)[i])
#define INF (1 << 30)
#define EPS (1e-9)
#define REP(i,n) FOR(i,0,n)
#define LL long long
#define MOD 1000000007
 
int n, m;
string s;
int main(){
//    ios::sync_with_stdio(false);
    cin >> s >> m;
    n = s.size();
    FOR(i,0,n) {
        //printf("%c %d %d\n", s[i], 'z' + 1 - s[i], m);
        if (s[i] == 'a')
             continue;
        if (m >= 'z' + 1 - s[i]){
            m -= 'z' + 1 - s[i];
            s[i] = 'a';
        }
    }
    if (m){
        m %= 26;
        s.back() += m;
    }
    cout << s << '\n';
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  int s=0;
  if(a>=b)
  {
    s+=a;
    a--;
  }
  else
  {
    s+=b;
    b--;
  }
  if(a>=b)
  {
    s+=a;
    a--;
  }
  else
  {
    s+=b;
    b--;
  }
  cout<<s;
}

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

typedef long long ll;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YesNo(x)      cout << ((x) ? "Yes" : "No") << endl
#define YESNO(x)      cout << ((x) ? "YES" : "NO") << endl
#define absi(x)       ( ((x) >= 0) ? (x) : (-(x)) )

bool yy(string s) {
	return ('0' <= s[0]) && (s[0] <= '9') && ('0' <= s[1]) && (s[1] <= '9');
}

bool mm(string s) {
	ll n = atoi(s.c_str());
	return (0 < n && n < 13);
}

bool yymm(string s) {
	return yy(s.substr(0, 2)) && mm(s.substr(2, 2));
}

bool mmyy(string s) {
	return mm(s.substr(0, 2)) && yy(s.substr(2, 2));
}

int main(int argc, const char* argv[]) {
	string s; cin >> s;

	string ret;
	if(yymm(s)) {
		if(mmyy(s)) {
			ret = "AMBIGUOUS";
		} else {
			ret = "YYMM";
		}
	} else {
		if(mmyy(s)) {
			ret = "MMYY";
		} else {
			ret = "NA";
		}
	}

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<list>
#include<algorithm>
#define endl "\n"
#define eb emplace_back
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define FORR(n) for(int i = n - 1; i >= 0; --i)
#define FORE(n) for(const auto &i : n)
typedef long long ll;
using namespace std;

bool desc(int a, int b)
{
    return a > b;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m, k;
    cin >> n >> m >> k;
    int arr_a[n + 1], arr_b[m + 1];
    vector<ll> a, b;
    a.emplace_back(0);
    b.emplace_back(0);
    FOR(i, 0, n)
    {
        cin >> arr_a[i];
        a.emplace_back(a[i] + arr_a[i]);
    }
    FOR(i, 0, m)
    {
        cin >> arr_b[i];
        b.emplace_back(b[i] + arr_b[i]);
    }
    /*
    FORE(a)
        cout << i << " ";
    cout << endl;
    FORE(b)
        cout << i << " ";
    */
    ll high = 0;
    ll i = 0;
    ll j = b.size() - 1;
    for(i = 0; i < n + 1; i++)
    {
        if(a[i] > k)
            break;
        //cout << a[i] << b[j] << endl;
        while(a[i] + b[j] > k)
        {
            //cout << b[j] << endl;
            --j;
        }
        high = max(i + j, high);
    }
    cout << high << endl;
}

Measured memory_bytes: 9256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }

        // 主処理
        Arrays.sort(a, Collections.reverseOrder());
        long side1 = 0;
        long side2 = 0;
        for (int i = 0; i < n - 1; i++) {
            if (a[i].intValue() == a[i + 1].intValue()) {
                if (side1 == 0) {
                    side1 = a[i];
                    i++;
                } else {
                    side2 = a[i];
                    break;
                }
            }
        }

        long result = side1 * side2;

        // 出力
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 47856
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.Unboxed            as AU
import qualified Data.Array.ST                 as ST
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.Foldable                  ( toList )
import           Data.Int
import qualified Data.IntMap                   as IM
import           Data.List
import qualified Data.Map                      as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import qualified Data.Sequence                 as SQ
import           Data.Time
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
readInts n = replicateM n readInt
readString = map BS.unpack . BS.words <$> BS.getLine
readStrings n = replicateM n readString
toPair [x, y] = (x, y)

main = do
  s     <- getLine
  [q]   <- readInt
  query <- readStrings q
  putStrLn $ solve s query

solve s = f (SQ.singleton s) True

f :: SQ.Seq String -> Bool -> [[String]] -> String
f s b [] | b         = concat $ toList s
         | otherwise = reverse $ concat $ toList s
f s b (q : qs) = case head q of
  "1" -> f s (not b) qs
  "2" -> f (g s b (tail q)) b qs

g :: SQ.Seq String -> Bool -> [String] -> SQ.Seq String
g s b q | (head q == "1" && b) || (head q == "2" && not b) = q !! 1 SQ.<| s
        | otherwise = s SQ.|> q !! 1


Measured memory_bytes: 113404
import java.util.Scanner;

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

        int r = scan.nextInt();
        int c = scan.nextInt();

        int[][] det = new int[r + 1][c + 1];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                det[i][j] = scan.nextInt();
                det[i][c] += det[i][j];
                det[r][j] += det[i][j];
            }
            det[r][c] += det[i][c];
        }

        for (int i = 0; i < r + 1; i++) {
            for (int j = 0; j < c + 1; j++) {
                System.out.print(det[i][j]);
                if(j==c) continue;
                System.out.print(" ");
            }
            System.out.println();
        }

    }
}

Measured memory_bytes: 39576
N = int(input())
mod = 10**9 + 7
u = 1
a = 1
b = 1
for i in range(N):
    u = u * 10
    a = a * 9
    b = b * 8
    u = u%mod
    a = a%mod
    b = b%mod
print((u-2*a+b)%mod)

Measured memory_bytes: 9180
#include<stdio.h>
int main(){
  int N,a[100],i,j,t,k;
  int c=0,min;

  scanf("%d\n",&N);
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
  }
  //scaned----------
  
  for(i=0;i<N-1;i++){
    t=0;
    min=i;
    for(j=i;j<=N-1;j++){
      if(a[j]<a[min]){
	min=j;
	t=1; 
      }
    }
    if(t==1)c++;
    k=a[i];
    a[i]=a[min];
    a[min]=k;

  }
        
  for(i=0;i<N;i++){
    printf("%d",a[i]);
    if(i<N-1)printf(" ");
  }
  printf("\n%d\n",c);

  return 0;
}



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

using namespace std;
typedef long long LL;
LL a[1000000];
int main(){
	LL n;
	cin>>n;
	LL S=0;
	for(LL i=1;i<=n;i++){
		cin>>a[i];
		S+=a[i];
	} 
	bool allpos,allneg;
	allpos=allneg=1;
	for(LL i=1;i<=n;i++){
		if(a[i]<0) allpos=0;
		if(a[i]>0) allneg=0;
	}
	if(allpos){
		sort(a+1,a+n+1);
		cout<<S-2*a[1]<<endl;
		LL now=a[1];
		for(LL i=1;i<=n-2;i++){
			cout<<now<<' '<<a[i+1]<<endl;
			now=now-a[i+1];
		}
		cout<<a[n]<<' '<<now<<endl;
		return 0;
	}
	if(allneg){
		sort(a+1,a+n+1);
		S=0;
		for(LL i=1;i<=n;i++) S+=abs(a[i]);
		cout<<S-2*abs(a[n])<<endl;
		LL now=a[n];
		for(LL i=n;i>=2;i--){
			cout<<now<<' '<<a[i-1]<<endl;
			now=now-a[i-1];
		}
		return 0;
	}
	S=0;
	for(LL i=1;i<=n;i++) S+=abs(a[i]);
	cout<<S<<endl;
	vector<LL> X,Y;
	sort(a+1,a+n+1);
	X.push_back(a[n]);
	Y.push_back(a[1]);
	for(LL i=2;i<n;i++){
		if(a[i]>=0) X.push_back(a[i]);
		else Y.push_back(a[i]);
	} 
	LL now=X[0];
	LL now1;
	for(LL i=0;i<(LL)Y.size()-1;i++){
		 cout<<now<<' '<<Y[i]<<endl;
		 now=now-Y[i];
	}
	now1=Y.back();
	for(LL i=1;i<(LL)X.size();i++){
		cout<<now1<<' '<<X[i]<<endl;
		now1=now1-X[i];
	}
	cout<<now<<' '<<now1<<endl;
	return 0;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

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

    int N; cin >> N;
    string s; cin >> s;

    rep(i, s.size()){
        int id = s[i] - 'A';
        id += N;
        id %= 26;
        id += 'A';
        s[i] = id;
    }

    cout << s << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
}; 

int main(){
    Stream io;
    
    int N;
    io.read(N);
    int S = 0;
    int x = N;
    while(x > 0){
        S += x % 10;
        x /= 10;
    }
    if(N % S == 0) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100000

int A[MAX], n;

int partition(int p, int r) {
	
	int x = A[r];
	int i = p - 1;
	for (int j = p; j < r; j++) {
		if (A[j] <= x) {
			i++;
			swap(A[j], A[i]);
		}
	}
	swap(A[i + 1], A[r]);
	return i + 1;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &A[i]);
	int q = partition(0, n-1);
	for (int i = 0; i < n; i++) {
		if (i) printf(" ");
		if (i == q) printf("[");
		printf("%d",A[i]);
		if (i == q) printf("]");
	}
	printf("\n");

    return 0;
}

Measured memory_bytes: 3580
N = int(input())
a = [int(input()) for i in range(N)]
now = a[0]
count = 1
c = 0
for i in range(10**6):
    if now != 2:
        count += 1
        now = a[now - 1]
    else:
        print(count)
        c = 1
        break
if c == 0:
    print(-1)


Measured memory_bytes: 7084
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    int ans=0;
    int a,b;
    cin >> N;
    while(N--)
    {
       cin >> a >> b;
       ans+=b-a+1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define vi vector<int>
#define ppi pair<int,pi>
#define ld long double
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << end
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define f(i, begin, end) for (__typeof(end) i = (begin); i != (end) ; i += 1 - 2 * ((begin) > (end)))
#define nl cout<<"\n";
#define par(a,n) f(i,0,n) cout<<a[i]<<" "; nl
//void prt(int x) {cerr << x;}
#define vv(n,m) vector <vector <int> > v(n, vector <int> (m));

#define er(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... brgs>
void err(istream_iterator<string> it, T a, brgs... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);	
}
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef pair<int,int> pii;
typedef vector<pii> vpii;
const int mod = 1000000007;
const int N = 3e5;

int kadane(int*a, int n);
bool isPrime(int n);
int mpow(int a, int b);


void solve(){
    int n,k;
    cin>>n>>k;
    int a[n];
    f(i,0,n) cin>>a[i];
    sort(a,a+n);
    int ans=0;
    f(i,0,k) ans+=a[i];
    cout<<ans<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
        
}

int mpow(int a, int b){ /* pow(a, b) % m */
  int m=mod;
  int x=1;
  while (b>0){
    if (b&1){
      x=(x * a) % m;
    }
    a=(a*a) % m; /* compute the next power of 2 */
    b>>=1; /* this is equivalent to b = floor(b / 2) */
  }
  return x;
}
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
    return true; 
} 

int kadane(int*a, int n){
    int max_so_far = INT_MIN, max_ending_here = 0;
    f(i,0,n){
        max_ending_here+=a[i];
        max_so_far = max(max_so_far, max_ending_here);
        if(max_ending_here<0) max_ending_here=0;
    }
    return max_so_far;
}

Measured memory_bytes: 3648
S = input()
T = input()
ans = []

lt = len(T)
for i in range(len(S)-lt+1):
    s = S[i:i+lt]
    for t in range(lt):
        if s[t]=='?':
            if t != lt-1:
                pass
            else:
                ans.append((S[:i]+T+S[i+lt:]).replace('?', 'a'))
        else:
            if s[t]!=T[t]:
                break
            elif t==lt-1:
                ans.append((S[:i]+T+S[i+lt:]).replace('?', 'a'))
                break

print(min(ans) if len(ans)>0 else "UNRESTORABLE")

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int N;
LL A[100010];

int main(){
	cin >> N;
	repp(i,0,N) cin >> A[i];
	sort(A,A+N);
	if(N == 2) return cout << A[1] - A[0] << endl,0;
	if(N == 3){
		cout << max(A[1]+A[2]-A[0]*2,A[2]*2-A[1]-A[0]) << endl;
		return 0;
	}
	LL ans = 0;
	if(N&1){
		repp(i,0,N/2) ans -= A[i] * 2;
		ans += A[N/2] + A[N/2+1];
		repp(i,N/2+2,N) ans += A[i] * 2;
		LL z = 0;
		repp(i,0,N/2-1) z -= A[i] * 2;
		z -= A[N/2] + A[N/2-1];
		repp(i,N/2+1,N) z += A[i] * 2;
		ans = max(ans,z);
	} else {
		repp(i,0,N/2-1) ans -= A[i]*2;
		ans += -A[N/2-1] + A[N/2];
		repp(i,N/2+1,N) ans += A[i] * 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  string s, t;
  cin >> s >> t;

  auto comp = [](char a, char b) {
    return (a == '?' or b == '?') or (a == b);
  };

  ll n = s.size();
  ll m = t.size();

  for (ll i = n-m; i >= 0; i--) {
    bool f = 1;
    rep(j, m) {
      if (!comp(t[j], s[i+j])) {
        f = 0;
      }
    }
    if (!f) continue;
    rep(j, n) {
      if (i <= j and j < i+m) {
        cout << t[j-i];
      } else if (s[j] == '?') {
        cout << 'a';
      } else {
        cout << s[j];
      }
    }
    return 0;
  }

  cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 256
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

def main():
    num = int(input())
    data = list(map(int, input().split()))

    bunbo = 0
    bunshi = 1
    for i in range(num):
        data[i] = 1 / data[i]
    ans = 1 / sum(data)

    # ans = bunshi / bunshibo
    print(ans)



if __name__ == '__main__':
    main()



Measured memory_bytes: 38480
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

import sys, os
def ac_input(*args):
    return map(int, input().split())


def main():
    k, x = ac_input()
    for i in range(k*2-1):
        print(str(x-k+i+1)+" ", end="")
    print("")
if __name__ == "__main__" :
    main()


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

using namespace std;

int a[510][510],c[250250][4];
int h,w;


int main()
{
    
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<w;j++)
        {
            if(a[i][j]%2==1)
            { ans++;
                c[ans][0]=i;
                c[ans][1]=j;
                c[ans][2]=i;
                c[ans][3]=j+1;
               
                a[i][j+1]++;a[i][j]--;
            }
        }
    }
    for(int i=1;i<=h-1;i++)
    {
        if(a[i][w]%2==1)
        {ans++;
            c[ans][0]=i;
            c[ans][1]=w;
            c[ans][2]=i+1;
            c[ans][3]=w;
            
            a[i+1][w]++; a[i][w]--;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)
    {
        cout << c[i][0]  << " " << c[i][1] << " " << c[i][2] << " " << c[i][3] << endl;
    }
    return 0;
}

Measured memory_bytes: 6912
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

int main(){
  int n,q; 
  string s;
  cin >> n >> q >> s;
  vector<int> v(n+1);
  v[0] = 0; v[1] = 0;
  for(int i = 2; i < n+1;i++){
    if(s[i-1] == 'C' && s[i-2] == 'A'){
      v[i] = v[i-1] + 1;
    }else{
      v[i] = v[i-1];
    }
  }
  
  //for(auto v1:v){
  //  cout << v1 << " ";
  //}
  //cout << endl;
  rep(i,q){
    int l,r; cin >> l >> r;
    cout << v[r] - v[l] << endl;
  }
  return 0;
}


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

int main(){
    int t,M=0,m=1000000000,n; cin>>n;
    for(int i=0;i<n;i++){
        cin>>t;
        M=max(M,t);
        m=min(m,t);
        }
    cout<<M-m<<endl;
    }

Measured memory_bytes: 256
import queue

n = int(input())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1for i in input().split()]
    ab[a].append(b)
    ab[b].append(a)

stack = [0]
visited = [False for _ in range(n)]
white = 0
black = 0
wQueue = queue.Queue()
wQueue.put(0)
bQueue = queue.Queue()
bQueue.put(n-1)
# print(ab)
while 1:
    wSize = wQueue.qsize()
    if wSize != 0:
        for i in range(wSize):
            now = wQueue.get()
            if not visited[now]:
                white += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        wQueue.put(ab[now][j])
    bSize = bQueue.qsize()
    if bSize != 0:
        for i in range(bSize):
            now = bQueue.get()
            if not visited[now]:
                black += 1
                visited[now] = True
                for j in range(len(ab[now])):
                        bQueue.put(ab[now][j])
    if wSize == 0 and bSize == 0:
        if white > black:
            print("Fennec")
        else:
            print("Snuke")
        # print("w:{} b:{}".format(white, black))
        exit()

Measured memory_bytes: 22956
P = 10**9+7
N, K = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
ans = 0
c = 1
for i in range(N-K+1):
    ans += (S[K-1+i]*c)%P
    ans -= (S[N-K-i]*c)%P
    ans %= P
    c = c*(K+i)*pow(i+1, P-2, P)%P
print(ans)

Measured memory_bytes: 63344
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<tuple>
#include<utility>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<iomanip>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF = 1e9 + 7;
int dx[8] = { 1,0,-1,0,1,1,-1,-1 };
int dy[8] = { 0,1,0,-1,1,-1,1,-1 };



int main() {

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int start = max(a, c);
	int finish = min(b, d);

	cout << max(0, finish - start) << endl;

	return 0;
}


Measured memory_bytes: 256