akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
#include <sstream>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define ios     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll mod=1000000007;
ll INF=1e18;
ll gcd (ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll fastexp(ll x ,ll n)
{
    ll result =1;
    while(n>0)
    {
        if(n%2==1)
            result*=x;
        x*=x;
        n=n/2;
    }
    return result;
}

ll modularExp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%mod;
        x=((x%mod)*(x%mod))%mod;
        n=n/2;
    }
    return (result)%mod;
}
bool isPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
bool mycomp(pll &a,pll &b)
{
    if(a.F!=b.F)
        return a.F < b.F;
    else
        return a.S < b.S;
}

void solve()
{
      string s,t;
      cin>>s>>t;
      ll n =s.length();
      ll m =t.length();
      ll ans =INF;
      ll i,j;
      for(i=0;i<n-m+1;i++)
      {
           string ns = s.substr(i,m);
           ll cnt=0;
           for(j=0;j<m;j++)
           {
                if(t[j]!=ns[j])
                    cnt+=1;
           }
           ans=min(ans,cnt);
      }
      cout<<ans;
     
     
}

     
     


int main()
{
    ios;
    ll t;
//    cin>>t;
     t=1;
     while(t--)
     {
          solve();
     }
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <set>
#include <cstdio>
#include <cctype>
using namespace std;

int w, h;
char M[60][10];
int D[60][10];
set<int> V[150];
double G[150];
int XL[150], XR[150];
int N;
const static int dx[4] = {1,0,-1,0};
const static int dy[4] = {0,1,0,-1};

int ctoi(char c) { return c - '0'; }
char itoc(int i) { return i + '0'; }

double rec(int x, int y, char num, int n) {
  M[y][x] = '0';
  D[y][x] = n;
  if(y == 0 || (isdigit(M[y-1][x]) && D[y-1][x] != n)) {
    XL[n] = min(XL[n], x);
    XR[n] = max(XR[n], x+1);
  }
  double res = x+0.5;
  for(int i = 0; i < 4; ++i) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx < 0 || nx >= w) continue;
    if(ny < 0 || ny >= h) continue;
    if(M[ny][nx] != num) continue;
    res += rec(nx, ny, num, n);
  }
  return res;
}

void make() {
  for(int i = 0; i < h; ++i) {
    fill(D[i], D[i]+w, -1);
  }
  N = 0;
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      if(M[i][j] != '.' && M[i][j] != '0') {
	XL[N] = 999999;
	XR[N] = -1;
	G[N] = rec(j, i, M[i][j], N);
	N++;
      }
    }
  }

  for(int i = 0; i < N; ++i) V[i].clear();
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      if(D[i][j] != -1) {
	int &s = D[i][j];
	int ny = i + 1;
	if(ny >= h) continue;
	if(D[ny][j] != -1 && D[ny][j] != s) {
	  V[s].insert(D[ny][j]);
	}
      }
    }
  }
}

int cnt;
double calc(int p) {
  double res = G[p];
  cnt++;
  for(set<int>::iterator it = V[p].begin(); it != V[p].end(); it++) {
    res += calc(*it);
  }
  return res;
}

void solve() {
  make();
  /*
  for(int i = 0; i < N; ++i) {
    cout << i << " : ";
    for(set<int>::iterator it = V[i].begin(); it != V[i].end(); it++)
      cout << " " << *it;
    cout << endl;
  }*/
  for(int i = 0; i < N; ++i) {
    cnt = 0;
    double tmp = calc(i);
    double M = tmp/(cnt*4.0);
    if(M > XL[i] && M < XR[i]) continue;
    cout << "UNSTABLE" << endl;
    return;
  }
  cout << "STABLE" << endl;
}

main() {
  while((cin >> w >> h) && (w || h)) {
    for(int i = h-1; i >= 0; --i) {
      for(int j = 0; j < w; ++j) {
	cin >> M[i][j];
      }
    }
    solve();
  }
}

Measured memory_bytes: 0
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

use std::cmp;

fn main() {
    let N = get!(usize);
    let A = get!(Vec<i64>);
    let B = get!(Vec<i64>);

    // 1番目の街から貪欲にモンスターを倒せばよい
    let (ans, _) = (0..N).fold(
        (0, A[0]),
        |(acc, p), i| {
            let x = cmp::min(p, B[i]);
            let y = cmp::min(A[i + 1], B[i] - x);
            (acc + x + y, A[i + 1] - y)
        }
    );

    println!("{}", ans);
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
#define MOD 1000000007LL
#define MOD2 1000000009LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

string s;
string t;

ll hash[2][300009];
ll hash2[2][300009];
ll powc[300009];
ll powc2[300009];
int n,m;

bool cl(int l,int r){
	ll va=hash[0][r]-hash[0][l];
	ll vb=hash[1][r-l]-hash[1][0];
	va+=MOD;
	va%=MOD;
	vb+=MOD;
	vb%=MOD;
	vb=vb*powc[l]%MOD;
	if(va!=vb)return false;
	va=hash2[0][r]-hash2[0][l];
	vb=hash2[1][r-l]-hash2[1][0];
	va+=MOD2;
	va%=MOD2;
	vb+=MOD2;
	vb%=MOD2;
	vb=vb*powc2[l]%MOD2;
	return va==vb;
}

bool cr(int l,int r){
	ll va=hash[0][r]-hash[0][l];
	ll vb=hash[1][m]-hash[1][m-(r-l)];
	va+=MOD;
	va%=MOD;
	vb+=MOD;
	vb%=MOD;
	vb=vb*powc[r-m]%MOD;

	if(va!=vb)return false;
	va=hash2[0][r]-hash2[0][l];
	vb=hash2[1][m]-hash2[1][m-(r-l)];
	va+=MOD2;
	va%=MOD2;
	vb+=MOD2;
	vb%=MOD2;
	vb=vb*powc2[r-m]%MOD2;
	return va==vb;
}

int main(void){
	cin >> s;
	cin >> t;
	n=s.size();
	m=t.size();
	powc[0]=1;
	powc2[0]=1;
	for(int i=0;i<n;i++){
		powc[i+1]=powc[i]*26LL%MOD;
		powc2[i+1]=powc2[i]*26LL%MOD2;
	}
	for(int i=0;i<n;i++){
		hash[0][i+1]+=hash[0][i];
		hash[0][i+1]+=(ll)(s[i]-'a')*powc[i]%MOD;
		hash[0][i+1]%=MOD;
		hash2[0][i+1]+=hash2[0][i];
		hash2[0][i+1]+=(ll)(s[i]-'a')*powc2[i]%MOD2;
		hash2[0][i+1]%=MOD2;
	}
	for(int i=0;i<m;i++){
		hash[1][i+1]=hash[1][i];
		hash[1][i+1]+=(ll)(t[i]-'a')*powc[i]%MOD;
		hash[1][i+1]%=MOD;

		hash2[1][i+1]=hash2[1][i];
		hash2[1][i+1]+=(ll)(t[i]-'a')*powc2[i]%MOD2;
		hash2[1][i+1]%=MOD2;
	}
	int ans=0;
	for(int i=0;i<=n-m;i++){
		int l=i,r=i+m+1;
		while(l+1<r){
			int mid=(l+r)/2;
			if(cl(i,mid))l=mid;
			else r=mid;
		}
		int tmp=l;
		l=i-1,r=i+m;
		while(l+1<r){
			int mid=(l+r)/2;
			if(cr(mid,i+m))r=mid;
			else l=mid;
		}
		if(tmp+1==r)ans++;
		//printf("%d %d %d\n",i,tmp,r);
	}
	printf("%d\n",ans);
	return 0;
}

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

int main() {
  int N = 0;
  cin >> N;
	
  bool flag_zero = false;
  bool flag_ideal = true;
  int min_abs_A = INT_MAX;
  long long int sum_abs_A = 0;
  vector<int> A(N, 0);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    sum_abs_A += abs(A[i]);
    if (A[i] == 0) {
      flag_zero = true;
    }
    if (abs(A[i]) < min_abs_A) {
      min_abs_A = abs(A[i]);
    }
    if (A[i] < 0) {
      flag_ideal = !flag_ideal;
    }
  }
  
  if ((flag_ideal || flag_zero) == true) {
    cout << sum_abs_A << endl;
  } else {
    cout << sum_abs_A - 2 * min_abs_A << endl;
  }
  
  return 0;
}

Measured memory_bytes: 640
a,b,c = map(int, input().split())
k = int(input())

ans = False
tmp_a = a
tmp_b = b
tmp_c = c

for i in range(0,k+1):
  for j in range(0,k+1):
    for l in range(0,k+1):
      tmp_a *= pow(2,i)
      tmp_b *= pow(2,j)
      tmp_c *= pow(2,l)
      if tmp_a < tmp_b and tmp_b < tmp_c and i + j + l <= k:
        ans = True
        break
      tmp_a = a
      tmp_b = b
      tmp_c = c

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

Measured memory_bytes: 9212
import itertools

n,k=map(int,input().split())
s=[input().split() for i in range(2*k)]
t=[]
for i in range(len(s)//2):
  t.append(s[2*i+1])
res = [ flatten for inner in t for flatten in inner ]

res = [int(i) for i in res]
res=list(set(res))

print(n-len(res))

Measured memory_bytes: 9684
#include<iostream>
using namespace std;
#define MAX 100000

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

int main() {
  int H, i, A[MAX + 1];
  
  cin >> H;
  for ( i = 1; i <= H; i++ ) cin >> A[i];
  
  for ( i = 1; i <= H; i++ ) {
    cout << "node " << i << ": key = " << A[i] << ", ";
    if ( parent(i) >= 1 ) cout << "parent key = " << A[parent(i)] << ", ";
    if ( left(i) <= H ) cout << "left key = " << A[left(i)] << ", ";
    if ( right(i) <= H ) cout << "right key = " << A[right(i)] << ", ";
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 3104
import math

n = int(input())
s = int(input())


r = 0

if n == s:
    print(n + 1)
    exit()
elif n < s:
    print(-1)
    exit()

sq = int(math.sqrt(n))


# 2 <= d <= √n
for i in range(2, sq+1):
    nt = n
    st = 0

    while nt > 0:
        st += nt % i
        nt //= i

    if st == s:
        print(i)
        exit()
    
# √n < d <= n
for i in range(sq+1, 0, -1):
    b = (n - s) // i + 1
    
    st = n % b + n // b

    if n // b != b and st == s:
        print(b)
        exit()

print(-1)

Measured memory_bytes: 9200
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <algorithm>

using ii = std::pair<int, int>;

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<int> length(2*n);

	for (int i = 0; i < 2 * n; i++)
		scanf("%d", &length[i]);

	std::sort(length.begin(), length.end());

	int sum = 0;

	for (int i = 0; i < length.size(); i += 2)
		sum += length[i];

	printf("%d", sum);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	char a[20000];
	bool flag=0;
	scanf("%s",a);
	for(int i=0;i<strlen(a);i++){
		if(a[i]=='C')
			flag=1;
		if(flag==1&&a[i]=='F'){
			printf("Yes");
			return 0;
		}
	}
	printf("No");
	return 0;
} 

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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> data(H);
  for (int i=0; i<H; i++) {
    string S;
    cin >> S;
    data.at(i) = S;
    //cout << S.at(0) << S.at(1) << S.at(2) << S.at(3) << S.at(4) << endl;
  }
  
  for (int i=0; i<H; i++) {
    string S = data.at(i);
    string str = "";
    //cout << S.at(0) << S.at(1) << S.at(2) << S.at(3) << S.at(4) << endl;
    for (int j=0; j<W; j++) {
      char c = S.at(j);
      if (c=='#') {
        //str += '#';
        cout << '#';
      } else { // c=='.'
        int n = 0;
        for (int k=0; k<3; k++) {
          for (int l=0; l<3; l++) {
            if (k==1 && l==1 || i==0 && k==0 ||i==H-1 && k==2 || j==0 && l==0 ||j==W-1 && l==2) {
              continue;
            }
            string strr = data.at(i+k-1);
            //cout << strr << endl;
            char cc = strr.at(j+l-1);
            //cout << cc;
            if(cc=='#') {
              n++;
            }
          }
        }
        cout << n;
      }
    }
    cout << endl;
  }
}


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) cin >> A[i] >> B[i];
  unordered_set<int> S1, S2;
  for (int i = 0; i < M; i++) {
    if (A[i] == 1) S1.insert(B[i]);
    if (B[i] == N) S2.insert(A[i]);
  }
  for (int s1 : S1) {
    if (S2.count(s1)) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
}

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

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  def popcount(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
              
  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = popcount(i) % 2
    ans += (-1)**cnt * 2**(n-1-popcount(s))
  print(ans)
  
if __name__ == "__main__":
  main()

Measured memory_bytes: 9320
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,l;
cin>>n>>l;
vector<string> vec(n);
for(int i=0;i<n;i++){
  cin>>vec[i];
}
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++){
  cout<<vec[i];
}
cout<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<map>

using namespace std;

int main(){
    int N,K;
    int ans = 0;
    string S;
    cin >> N >> K;
    vector<int> A(N);
    map<int,int> mp;
    vector<int> rmp;

    for(int i = 0; i < N; i++){
        cin >> A[i];
        if(mp[A[i]] == 0){
            mp[A[i]] = 1;
        }else{
            mp[A[i]]++;
        } 
    }
    if(mp.size() <= K){
        cout << ans << endl;
        return 0;
    }
    for(auto elm : mp){
        rmp.push_back(elm.second);
    }
    sort(rmp.begin(), rmp.end(), greater<int>());
    int sum = 0;
    int j = 0;
    for (int j = K; j < rmp.size(); j++){
        ans += rmp[j];
    }
    // ans = N - sum;
    cout << ans << endl;
}

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

const int mod=998244353;

long C[2001][2001];

long comb(int n){
	for(int i=0;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<i;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			C[i][j]%=mod;
		}
		C[i][i]=1;
	}
}

int main(){
	string s;
	cin >> s;
	int n=s.length();
	int red[n]={};
	red[0]=(s[0]=='0'?2:s[0]=='1'?1:0);
	for(int i=1;i<n;i++) red[i]+=red[i-1]+(s[i]=='0'?2:s[i]=='1'?1:0);
	
	long dp[n+1][2*n+1]={};
	dp[1][0]=(s[0]!='0'?1:0);
	dp[1][1]=(s[0]!='2'?1:0);
	for(int i=2;i<=n;i++){
		for(int j=max(0,red[i-1]-i);j<=min(i,red[i-1]);j++){
			dp[i][j]=(dp[i-1][j]+(j!=0?dp[i-1][j-1]:0))%mod;
		}
	}
	comb(n);
	long ans=0;
	for(int i=0;i<=min(n,red[n-1]);i++){
		if(red[n-1]-i<=n) ans+=dp[n][i]*C[n][red[n-1]-i]%mod;
		ans%=mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 92672
import java.util.Scanner;
import java.math.BigInteger;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    double[] position = new double[2];
    int x = 0;
    int theta = 90;
    while(true) {
      String str = sc.next();
      String[] strArr = str.split(",");
      x = Integer.parseInt(strArr[0]);
      position[0] += x*Math.cos(Math.toRadians(theta));
      position[1] += x*Math.sin(Math.toRadians(theta));
      theta -= Integer.parseInt(strArr[1]);
      if (x == 0 && strArr[1].equals("0")) {
        break;
      }
    }
    System.out.println((int)position[0]);
    System.out.println((int)position[1]);
  }
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using P = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
int INF = 1e9+7;

int main() {
    int N,A,B;
    ll sum = 0;
    int ab;
    cin >> N >> A >> B;
    for (int i=1; i<=N; i++) {
        ab = 0;
        int j = i;
        while(j>0) {
            ab += j%10;
            j /= 10;
        }
        if (A<=ab & ab<=B) {sum+=i;}
    }
    cout << sum << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18L + 5;
void solve(){
    int n; int W; cin >> n >> W;
    vector<int> w(n);
    vector<int> v(n);
    int total_value = 0;
    for(int i = 0; i < n; i++){
        cin >> w[i] >> v[i];
        total_value += v[i];
    }
    vector<ll> dp(total_value+1, INF);
    dp[0] = 0;
    // dp[i] = min weight for value i
    for(int item = 0; item < n; item++){
        for(int value = total_value - v[item]; value >= 0; value--){
            dp[value + v[item]] = min(dp[value + v[item]], dp[value] + w[item]);
        }
    }
    
    ll ans = 0;
    for(int i = 0; i <= total_value; i++){
        if(dp[i] <= W){
            ans = max( ans, (ll)i);
        }
    }
    cout << ans << endl;
}
            
    
    
int main(){
    //int t; t = 1;
    //int t; cin >> t;
    //while(t--){
        solve();
    //}
}


Measured memory_bytes: 1024
# input
N = int(input())
P = list(map(int, input().split()))

# check
# 考え方参考：https://note.com/tanon_cp/n/n6b51b9a57076
sorted_P = sorted(P)
change_idx_cnt = 0
for sp, p in zip(sorted_P, P):
    if sp != p:
        change_idx_cnt += 1

if change_idx_cnt <= 2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
int main() {
  int a,b;
  cin>>a>>b;
  if(b!=100){
    cout<<b*(int)pow(100,a)<<endl;
  }else{
    cout<<b*(int)pow(100,a)+1*(int)pow(100,a)<<endl;
  }
}


Measured memory_bytes: 256
while True:
   m,f,r=map(int, input().split())
   if m==-1 and f==-1 and r==-1:
      break
   elif m==-1 or f==-1:
      print('F')
   elif m+f>=80:
      print('A')
   elif m+f>=65:
      print('B')
   elif m+f>=50:
      print('C')
   elif m+f>=30:
      if r>=50:
         print('C')
      else:
         print('D')
   else:
      print('F')


Measured memory_bytes: 5596
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, less<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[&](auto f,auto... args){return f(f,args...);};

int main(){
    svec s(3);
    rep(i,3)cin>>s[i];
    rep(i,3)cout<<s[i][i];
    cout<<endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	n := readInt()
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		a[i] = readInt()
	}
	var ans int
	count := make([]int, 100001)
	for i := 1; i != 2; {
		count[i]++
		if count[i] > 1 {
			println(-1)
			return
		}
		i = a[i]
		ans++
	}
	println(ans)
}


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

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

	int ans = 0;
	for(int i=1;i<N;i++)ans += i;
	for(int i=1;i<M;i++)ans += i;

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
X, Y = gets.chomp.split(" ").map(&:to_i)

A = [1,3,5,7,8,10,12]
B = [4,6,9,11]

puts (A.include?(X) && A.include?(Y)) || (B.include?(X) && B.include?(Y)) ? 'Yes' : 'No'


Measured memory_bytes: 1788
#include <stdio.h>
int main(void){
    int x;
    scanf("%d",&x);
    x = x%7;
    switch(x){
    case 0:
        printf("thu\n");
        break;
    case 1:
        printf("fri\n");
        break;
    case 2:
        printf("sat\n");
        break;
    case 3:
        printf("sun\n");
        break;
    case 4:
        printf("mon\n");
        break;
    case 5:
        printf("tue\n");
        break;
    case 6:
        printf("wed\n");
        break;
    }
    return 0;
}


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

const int N=1e5+50, mod=1e9+7;
inline void add(int &x,int y) {x=(x+y>=mod) ? (x+y-mod) : (x+y);}

char t[N]; 
int n,ans,s[N],f[N],pre[N][3],fir[N];

int main() {
	scanf("%s",t+1); n=strlen(t+1);
	for(int i=1;i<=n;i++) s[i]=(s[i-1]+t[i]-'a'+1)%3;
	pre[0][0]=pre[0][1]=pre[0][2]=-1;
	for(int i=1;i<=n;i++) {
		pre[i][0]=pre[i-1][0];
		pre[i][1]=pre[i-1][1];
		pre[i][2]=pre[i-1][2];
		pre[i][s[i-1]]=i-1;
	}
	for(int i=1;i<=n;i++) {
		fir[i]=fir[i-1];
		if(t[i]==t[i-1]) fir[i]=i;
	}
	f[0]=1;
	for(int i=1;i<=n;i++) {
		int pos=fir[i]-1;
		f[i]=f[i-1];
		int val=(t[i]=='a') ? 2 : 1;
		if(~pos) {
			pos=pre[pos][(s[i]-val+3)%3];
			if(~pos) add(f[i],f[pos]);
		}
		if(!s[i] && i!=n) add(f[i],1);
	} 
	if(!fir[n]) for(int i=1;i<n;i++) if(!s[i]) add(f[n],mod-1);
	cout<<f[n]<<'\n';
}

Measured memory_bytes: 2688
N =int(input())
AB = []
for i in range(N):
    AB.append(list(map(int,input().split())))

end = 0
ans = 0
AB = sorted(AB,key=lambda x:x[1])
t = 0
for y in AB:
    t += y[0]
    if t > y[1]:
        print("No")
        exit()



print("Yes")


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

int main()
{
  while (1){
    int n1, n2;
    cin >> n1;
    if (n1 == 0) return 0;
    char before[n1], after[n1];
    for (int i = 0; i < n1; i++) cin >> before[i] >> after[i];

    cin >> n2;
    vector<char> vc;
    for (int i = 0; i < n2; i++) {
      char c;
      cin >> c;
      for (int i = 0; i < n1; i++) {
        if (before[i] == c) {
          c = after[i];
          vc.push_back(c);
          break;
        }
        else if (i + 1 == n1) vc.push_back(c);
      }
    }
    int len = vc.size();
    for (int i = 0; i < len; i++) cout << vc[i];
    //for (auto i: vc) cout << i;
    cout << endl;
  }
}



Measured memory_bytes: 3196
from itertools import groupby
from collections import Counter

### https://atcoder.jp/contests/abc152/submissions/15835670
def fast_prime_factorization_many(lst):
  # 素因数分解（ロー法、複数）
  from subprocess import Popen, PIPE
  res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
  return [Counter(list(map(int, r.split()[1:]))) for r in res]

def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  if N == 1:
    print(1)
    exit(0)
  
  mod = int(1e9+7)
  Factors = fast_prime_factorization_many(A)
  #print(Factors)
  ### lcmを求める
  lcm = 1
  max_factor = [0] * (1000010)
  for f in Factors:
    for k,v in f.items():
      v_prev = max_factor[k]
      if v_prev < v:
        for i in range(v-v_prev):
          lcm = lcm * k % mod
        max_factor[k] = v
        
  #print(lcm)
  ans = 0
  for a in A:
    wk =  lcm * pow(a,mod-2,mod)
    #print(wk)
    ans += wk
    ans %= mod
  print(ans)
  exit(0)
  
main()


Measured memory_bytes: 21784
#python3 
g = [[-1 for _ in range(15)] for _ in range(15)]

n = int(input())
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y

ans = 0
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1 
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {

	public static final MyScanner in = new MyScanner();

	public static void main(String[] args) {

		int N = in.nextInt();
		int K = in.nextInt();
		int Q = in.nextInt();
		int[] score = new int[N];

		int moreThan = Q - K; 

		int A = 0;
		for(int i = 0; i < Q; i++) {
			A = in.nextInt() -1;
			score[A] = score[A] + 1;
		}

		String YES = "Yes";
		String NO = "No";
		for(int i =0; i < N; i++) {
			System.out.println(moreThan < score[i] ? YES: NO);
		}
	}

	public static class MyScanner{
		Scanner sc = new Scanner(System.in);
		String nextLine() {return sc.nextLine();}
		String next() {return sc.next();}
		int nextInt() {return Integer.valueOf(sc.next());}
	}
}

Measured memory_bytes: 50020
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int t[11][11];
int main(){
  while(cin>>n){
    if(n==0)break;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
    cin>>t[i][j];
      }
    }
    for(int j=0;j<n;j++){
      t[n][j]=0;
      for(int i=0;i<n;i++){
    t[n][j]+=t[i][j];
      }
    }
    for(int i=0;i<=n;i++){
      t[i][n]=0;
      for(int j=0;j<n;j++){
    t[i][n]+=t[i][j];
      }
    }
 
    for(int i=0;i<=n;i++){
       
      for(int j=0;j<=n;j++){
 
    printf("%5d",t[i][j]);
      }
      cout<<endl;
    }
  }
  return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

vector<pair<long long, int>> factorize(long long n){
    vector<pair<long long, int>> res;
    
    if(n%2 == 0){
        res.emplace_back(2,0);
        while(n%2 == 0){
            n /= 2;
            res.back().second++;
        }
    }
    
    for(long long  i=3; i*i<=n; i+=2){
        if(n%i) continue;
        res.emplace_back(i,0);
        while(n%i == 0){
            n /= i;
            res.back().second++;
        }
    }
    if(n != 1) res.emplace_back(n,1);
    return res;
}

void Main(){
    int n; cin >> n;
    auto v = factorize(n);
    int ans = 1;
    for(auto& p : v){
        ans *= p.first-1;
        n /= p.first;
    }
    ans *= n;
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main() {
#ifdef HOME
    freopen("in", "r", stdin);
#endif

    string s;
    while (cin >> s) {
        int n = s.length();

        map<int, int> mp;
        mp[0] = 0;

        int mask = 0;
        auto upd = [&](int &x, int mask) {
            if (mp.count(mask)) {
                x = min(x, mp[mask] + 1);
            }
        };
        for (int i = 0; i < n; i++) {
            mask ^= 1 << (s[i] - 'a');

            int cur = n + 1;
            upd(cur, mask);
            for (int j = 0; j < 26; j++) {
                int cmask = mask ^ (1 << j);
                upd(cur, cmask);
            }
            if (!mp.count(mask)) {
                mp[mask] = cur;
            } else {
                mp[mask] = min(mp[mask], cur);
            }
            if (i == n - 1) cout << cur << endl;
        }

    }

#ifdef HOME
    cerr << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Measured memory_bytes: 9860
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template < typename T > using oset = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
// find_by_order(k) (k+1)th largest element
// order_of_key(k) no of elements <=k

typedef long long ll;
typedef long double ld;
#define endl '\n'
#define rep(i,n)  for(ll i = 0; i < (n); ++i)
#define repA(i, a, n)  for(ll i = a; i <= (n); ++i)
#define repD(i, a, n)  for(ll i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define ff first
#define ss second
#define pb push_back
typedef vector<ll> vll;
typedef vector<pair<ll,ll>> vpl;
const ld PI = 4*atan((ld)1);
const ll INF = LLONG_MAX;
const ll mod = 1e9+7;

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll tt=1;
        // cin >> tt;
    repA(qq,1,tt){
        string s,t; cin >>s >> t;

        ll ns = sz(s);
        ll nt = sz(t);

        ll ans =INF;
        rep(i,ns-nt+1){
            ll cnt =0;
            rep(j,nt){
                if(t[j]!=s[i+j])cnt++;
            }
            ans = min(ans,cnt);
        }
        cout << ans ;
    }
}


Measured memory_bytes: 3652
#include<iostream>
using namespace std;
const int mod=1e9+7;
int dp[1001][1001];
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char c;cin>>c;
			if(c=='#')dp[i][j]=0;
			else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
			dp[1][1]=1;
		}
	cout<<dp[n][m];
	return 0;
}

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

int main(void) {
  int A, B;
  cin >> A >> B;
  
  if(A == B)
    cout << 2*A << endl;
  else if(A > B)
    cout << 2*A - 1 << endl;
  else
    cout << 2*B - 1 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int n,h,m=0,co=0;
    int i=0;
    cin >> n;
    while(i<n){
        i++;
        cin >> h;
        if(m<=h){
            co++;
            m=h;
        }
    }
    cout << co << endl;
    return 0;
}


Measured memory_bytes: 256
p1 = [0,0]
p2 = [100,0]
R = [[0.5,-1.7320508/2],[1.7320508/2,0.5]]

def dot(A,b):
    vs = [0,0]
    for i in range(2):
        for j in range(2):
            vs[i] += A[i][j]*b[j]
    return vs

def diff(p1,p2):
    return [(p1[0]-p2[0])/3.0,(p1[1]-p2[1])/3.0]

def sumV(p1,p2):
    return [p1[0]+p2[0],p1[1]+p2[1]]

def new_koch(p1,p2):
    p = diff(p2,p1)
    p_new1 = sumV(p1,p)
    p_new2 = sumV(p_new1,dot(R,p))
    p_new3 = sumV(p1,sumV(p,p))
    return [p1,p_new1,p_new2,p_new3]

n = int(input())
ps = [p1,p2]
for i in range(n):    
    X = len(ps)
    ps_new = []
    for i in range(X-1):
        ps_new.extend(new_koch(ps[i],ps[i+1]))
    ps_new += [ps[-1]]
    ps = [p for p in ps_new]

for p in ps:
    print(*p)




Measured memory_bytes: 6300
n=int(input())
# s=[input() for i in range(n)]
s=[]
for i in range(n):
  S=input()
  S=list(S)
  S.sort()
  S=''.join(S)
  s.append(S)
from collections import defaultdict as dd
d=dd(int)
for ss in s:
  d[ss]+=1
ans=0
for k,v in d.items():
  ans+=v*(v-1)//2
print(ans)



Measured memory_bytes: 19760
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/


int main(){
int N,M;
cin>>N>>M;
vector<pair<int,int>> path(M);
rep(i,M){
    int a,b;
    cin>>a>>b;
    path[i]=make_pair(a,b);
}
int count=0;
rep(i,M){
    Graph G(N+1);
    int seen[N+1];
    rep3(j,N){
        seen[j]=-1;
    }
    rep(j,M){
        if(i!=j){
            G[path[j].first].push_back(path[j].second);
            G[path[j].second].push_back(path[j].first);
        }
    }

     queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    seen[1] = 0;
    que.push(1); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (seen[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            seen[nv] =0;
            que.push(nv);
        }
    }
    bool judge=false;
    rep3(j,N){
        if(seen[j]==-1){
            judge=true;
        }

    }
    if(judge){
        count++;
    }

}
cout<<count<<endl;
return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main()
{
    ll n, p;
    cin >> n >> p;
    ll r[200005];
    r[n - 1] = 1;
    for(int i = n - 2; i >= 0; i--) r[i] = r[i + 1] * 10 % p;
    string s;
    cin >> s;
    ll ans = 0;
    if(p == 2 || p == 5){
        for(int i = 0; i < n; i++){
            if((s[i] - '0') % p == 0) ans += i + 1;
        }
        cout << ans << endl;
        return 0;
    }
    ll b[10005]{0};
    b[0] = 1;
    ll k = 0;
    for(int i = n - 1; i >= 0; i--){
        k = (k + (s[i] - '0') * r[i]) % p;
        b[k]++;
    }
    for(int i = 0; i < p; i++){
        ans += b[i] * (b[i] - 1) / 2;
    }
    cout << ans << endl;
}

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

d, x = tuple(map(int, input().split()))

a = []

append = a.append
for i in range(n):
    append(int(input()))

total = 0

for i in range(n):

    for j in range(d):
        if j % a[i] == 0:
            total += 1

total += x
print(total)


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

const int M=52;

vector<int> operator+(const vector<int>& a,const vector<int>& b){
  vector<int> res(M);
  rep(i,M)res[i]=a[i]+b[i];
  return res;
}
bool operator<(const vector<int>& a,const vector<int>& b){
  rep(i,M){
    if(a[i]!=b[i])return a[i]<b[i];
  }
  return true;
}

struct edge{
  int to,cap;
  vector<int> cost;
  int rev;
};

int V;
int N;
vector<edge> g[202];
int h[202];
vector<int> dist[202];
int prevv[202],preve[202];
vector<int> vinf;

void init(int v){
  V=v;
  vinf=vector<int>(M,INF);
  for(int i=0;i<V;i++){
    g[i].clear();
  }
}

void add_edge(int from,int to,int cap,vector<int> cost){
  g[from].push_back((edge){to,cap,cost,(int)g[to].size()});
  vector<int> rev=cost;
  rep(i,cost.size())rev[i]=-rev[i];
  g[to].push_back((edge){from,0,rev,(int)g[from].size()-1});
}

vector<int> min_cost_flow(int s,int t,int f){
  vector<int> res=vector<int>(M,0);
  memset(h,0,sizeof(h));
  while(f>0){
    rep(i,V)dist[i]=vinf;
    dist[s]=vector<int>(M,0);
    bool update=true;
    while(update){
      update=false;
      for(int v=0;v<V;v++){
        if(dist[v]==vinf)continue;
        for(int i=0;i<g[v].size();i++){
          edge &e=g[v][i];
          if(e.cap>0&&dist[e.to]>dist[v]+e.cost){
            dist[e.to]=dist[v]+e.cost;
            prevv[e.to]=v;
            preve[e.to]=i;
            update=true;
          }
        }
      }
    }
    if(dist[t]==vinf) return vinf;

    int d=f;
    for(int v=t;v!=s;v=prevv[v]){
      d=min(d,g[prevv[v]][preve[v]].cap);
    }
    f-=d;
    rep(i,M)res[i]=res[i]+d*dist[t][i];
    for(int v=t;v!=s;v=prevv[v]){
      edge &e=g[prevv[v]][preve[v]];
      e.cap-=d;
      g[v][e.rev].cap+=d;
    }
  }
  return res;
}

string s[55];
vector<int> costs[55];

int main(){
  cin>>N;
  rep(i,N)cin>>s[i];
  int source=N*2,sink=N*2+1;
  init(2*N+2);
  rep(i,M){
    vector<int> tmp(M,1000);
    tmp[i]=999;
    costs[i]=tmp;
  }
  rep(i,N){
    add_edge(source,i,1,vector<int>(M,0));
    add_edge(i+N,sink,1,vector<int>(M,0));
  }
  rep(i,N){
    rep(j,N){
      if('A'<=s[i][j]&&s[i][j]<='Z'){
        add_edge(i,j+N,1,costs[s[i][j]-'A']);
      }else{
        add_edge(i,j+N,1,costs[s[i][j]-'a'+26]);
      }
    }
  }
  vector<int> res=min_cost_flow(source,sink,N);
  string ans;
  rep(i,M){
    rep(j,N*1000-res[i]){
      if(i>=0&&i<26){
        ans+=(char)('A'+i);
      }else{
        ans+=(char)('a'+i-26);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4560
use std::io::Read;


#[derive(Copy, Clone)]
struct Edge{
    from: usize,
    to: usize,
    weight: i64,
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    // get stdio    
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();
    
    let edges: Vec<(usize, usize)> = (0..m)
        .map(|_| {
            (
                iter.next().unwrap().parse::<usize>().unwrap() - 1,
                iter.next().unwrap().parse::<usize>().unwrap() - 1,
            )
        })
        .collect();


    // construct graph
    let mut graph: Vec<Vec<Edge>> = (0..n)
        .map(|_| {
            Vec::new()
        }).collect();

    for e in edges.iter() {
        graph[e.0].push( Edge{from:e.0, to:e.1, weight:1});
        graph[e.1].push( Edge{from:e.1, to:e.0, weight:1})
    }

    

    // dfs
    let mut stack: Vec<Edge> = Vec::new();
    stack.push(Edge{from:0, to:0, weight:0});

    let mut visited: Vec<bool> = vec![false; n];
    let mut color: Vec<i32> = vec![-1; n];
    color[0] = 2;

    let mut is_partite : bool = true;
    while let Some(e) = stack.pop()  {

        if visited[e.to] {
            continue;
        }
        visited[e.to] = true;
        color[e.to] = 3 - color[e.from];
        // match color[e.from] {
        //     1 => 2,
        //     2 => 1,
        //     _ => 0,
        // };
        for i in graph[e.to].iter() {
            if ! visited[i.to] {
                stack.push(*i);
            } else if color[i.from] == color[i.to] {
                is_partite = false; // if adjacent node's color is different, given graph is not bipartite.
            }
        }
    }
    
    let whites = color.iter().filter(|&x| *x == 1).collect::<Vec<&i32>>().len();
    if is_partite {
        println!("{}",  whites * (n-whites) - m);
    } else {
        println!("{}", n*(n-1)/2 - m);
    }

}


Measured memory_bytes: 26876
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}
int main() {
long long n,k;
cin >> n >> k;
long long kouho=n%k;
long long kouhotwo=(n%k)-k;
cout << min(kouho,abs(kouhotwo));
}


Measured memory_bytes: 256
#include <stdio.h>

int main ()
{
    int a;
	int b;
	int c;
	int d;
    
	scanf("%d", &a);
    scanf("%d %d", &b, &c);
        
	for(b;b<=c;b++)
    {
    	if(b%a==0)
        {
            d++;
        }
    }
    
    if(d!=0)
    {
        printf("OK");
    }
    
	else
    {
        printf("NG");
    }


    return 0;
}

Measured memory_bytes: 1708
// user:halahen
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int i,j,k;
int n;
int read(){
	int tot=0,fh=1;
	char c=getchar();
	while ((c<'0')||(c>'9')){ if(c=='-') fh=-1; c=getchar(); }
	while ((c>='0')&&(c<='9')){ tot=tot*10+c-'0'; c=getchar(); }
	return tot*fh;
}
int main(){
	n=read();
	if (n<=111){
		printf("111\n"); return 0;
	}
	if (n<=222){
		printf("222\n"); return 0;
	}
	if (n<=333){
		printf("333\n"); return 0;
	}
	if (n<=444){
		printf("444\n"); return 0;
	}
	if (n<=555){
		printf("555\n"); return 0;
	}
	if (n<=666){
		printf("666\n"); return 0;
	}
	if (n<=777){
		printf("777\n"); return 0;
	}
	if (n<=888){
		printf("888\n"); return 0;
	}
	if (n<=999){
		printf("999\n"); return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        d: i32,
    }

    let ans = if d == 25 {
        "Christmas"
    } else if d == 24 {
        "Christmas Eve"
    } else if d == 23 {
        "Christmas Eve Eve"
    } else if d == 22 {
        "Christmas Eve Eve Eve"
    } else {
        ""
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352