akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF ((int)(1e9))

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N; cin >> N;
	int len[3] = {0};
	rep (i, 3) cin >> len[i];
	vector<int> l(N, 0);
	rep (i, N){
		cin >> l[i];
	} // end rep

	sort(ALL(l));

	int res = INF;
	for (int i = 1; i < (1<<N); ++i){
//	int i = (1<<N) - 1;
		vector<int> cand; cand.clear();
		rep (j, N){
			if (i & (1<<j)){
				cand.push_back(l[j]);
			} // end if
		} // end rep

		if ((int)cand.size() < 3){
			continue;
		} // end if

		if ((int)cand.size() == 3){
			do{
				int curr = 0;
				rep (j, 3){
					curr += abs(cand[j] - len[j]);
				} // end rep
				if (res > curr){
//					rep (jj, 3){
//						cerr << cand[jj] << ' ';
//					} // end rep
//					cerr << "curr: " << curr << endl;
					res = curr;
				} // end if
			}while(next_permutation(ALL(cand)));
		}else{ // if ((int)cand.size() > 3)
			do{
//				swap (cand[0], cand[4]);
//				swap (cand[1], cand[2]);
//				swap (cand[2], cand[3]); 

				rep (j, pow(3,(int)cand.size() - 3)){
					int curr2 = 0;
					int k = j;
					int m = 3;
					vector<int> cand2(3,0);
					rep (j2, 3){
						cand2[j2] = cand[j2];
					} // end rep
					rep (jj, ((int)cand.size() - 3)){
						cand2[k % 3] += cand[m];
						curr2 += 10;
						k /= 3;
						++m;
					} // end rep

					rep (jj, 3){
						curr2 += abs(cand2[jj] - len[jj]);
					} // end rep
					if (res > curr2){
//						rep (jj, (int)cand.size()){
//							cerr << cand[jj] << ' ';
//						} // end rep
//						cerr << ':';
//						rep (jj, 3){
//							cerr << cand2[jj] << ' ';
//						} // end rep
//						cerr << "curr2: " << curr2 << endl;
						res = curr2;
					} // end if
				} // end rep
			}while(next_permutation(ALL(cand)));
		} // end if
	} // end for

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main(int argc, const char * argv[]) {
 
    int ans = 700;
    
    for(int i=0;i<3;i++){
        char tmp;
        scanf("%c",&tmp);
        if(tmp=='o') ans+=100;
    }
    
    printf("%d\n",ans);
    
    
    return 0;
}

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

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define FOR(i,l,r) for(long long i=l; i<r; i++)
#define FOR_REV(i,r,l) for(long long i=r; i>=l; i--)
#define pb push_back
#define mp make_pair

int main()
{
	int n,k;
  	cin>>n>>k;
    
    int a[200009];
    FOR(i,1,n+1)
    {
        cin>>a[i];
    }

    vector <int> dp(n+3, INT_MAX);

    dp[1] = 0;

    FOR(i,1,n+1)
    {
        FOR(j,0,k+1)
        {
            if (i+j <= n)
                dp[i+j] = min(dp[i+j], dp[i]+abs(a[i]-a[i+j]));
        }
    }

    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int R, G;
    cin >> R >> G;
    cout << 2 * (G - R) + R << endl;
    return 0;
}

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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
    if(ch == 'A')      return 1;
    else if(ch == 'C') return 2;
    else if(ch == 'G') return 3;
    else if(ch == 'T') return 4;
    else               return 0;
}

long long getKey(char str[]){
    long long sum=0, p=1, i;
    for(i=0 ; i<strlen(str) ; i++){
        sum += p * (getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key){
    return key % M;
}

int h2(int key){
    return 1+(key % (M-1));
}

int find(char str[]){
    long long key, i ,h;
    key = getKey(str);
    for(i=0 ; ; i++){
        h = (h1(key)+i * h2(key)) % M;
        if(strcmp(H[h], str) == 0) return 1;
        else if(strlen(H[h]) == 0) return 0;
    }
    return 0;
}

int insert(char str[]){
    long long key, i, h;
    key = getKey(str);
    for(i=0 ; ; i++){
        h = (h1(key)+i * h2(key)) % M;
        if(strcmp(H[h], str) == 0) return 1;
        else if(strlen(H[h]) == 0){
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int n;
    char str[L], com[9];
    for (int i = 0; i < M; i++ ) H[i][0] = '\0';
    scanf("%d", &n);
    for (int i=0 ; i<n ; i++ ){
	    scanf("%s %s", com, str);
	    if(com[0] == 'i' ) insert(str); 
        else{
            if (find(str)) printf("yes\n");
            else           printf("no\n");
	    }
    }
    return 0;
}



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

int main() {
    int K, S;
    cin >> K >> S;
    int count = 0;
    for (int x = 0; x <= K; x++) {
        for (int y = 0; y <= K; y++) {
            int z = (S - x - y);
            if (0 <= z && z <= K) count++;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}
//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

int main(){
    int n,m,ans(0);
    cin >> n >> m;
    bool x[n];
    rep(i,n)    x[i]=true;
    int h[n],a[m],b[m];
    rep(i,n)    cin >> h[i];
    rep(i,m){
        cin >> a[i] >> b[i];
        if(h[a[i]-1]>h[b[i]-1]){
            x[b[i]-1] = false;
        }
        else if(h[a[i]-1]<h[b[i]-1]){
            x[a[i]-1] = false;
        }else{
            x[b[i]-1] = false;
            x[a[i]-1] = false;
        }
    }

    rep(i,n){
        if(x[i])    ans++;
    }
    put(ans);
    return 0;
}

Measured memory_bytes: 4884
def abc075_b():
    h, w = map(int, input().split())
    s = [None] * (h + 2)
    ans = [[None] * w for _ in range(h)]

    s[0] = s[-1] = ["."] * (w + 2)
    for i in range(1, h + 1):
        s[i] = ["."] + list(input()) + ["."]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == "#":
                ans[i - 1][j - 1] = "#"
            else:
                ans[i - 1][j - 1] = str([s[i - 1][j - 1], s[i - 1][j], s[i - 1][j + 1], s[i][j - 1], s[i][j + 1],
                                         s[i + 1][j - 1], s[i + 1][j], s[i + 1][j + 1]].count("#"))

    for ln in ans:
        print("".join(ln))


abc075_b()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define FOR(i, n) for(ll i = 0; i < n; i++)
#define FORR(i, n) for(ll i = n; i >= 0; i--)
#define FORS(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) accumulate(v.begin(),v.end(),0)
#define SORT(v) sort(v.begin(),v.end())
#define OUT(n) (cout << n << endl)
#define IN1(a) (cin >> a)
#define IN2(a,b) (cin >> a >> b)
#define IN3(a,b,c) (cin >> a >> b >> c)
#define IN4(a,b,c,d) (cin >> a >> b >> c >> d)
#define REV(n) reverse(n.begin(), n.end())
using namespace std;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int x,a;
    IN2(x,a);
    if (x < a) OUT("0");
    else OUT("10");
}

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

int main(){
  int n;
  cin>>n;
  int i=111;
  while(i<n){
    i+=111;
  }
  cout<<i<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  sort(all(a));
  cout << a[N-1]-a[0] << endl;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
    char n;
    rep(i,3) {
      	cin >> n;
  		cout << 10-(n-'0');
    }
  	cout << endl;
  	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))



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

using namespace std;

int main() {
	int n, k;
	string s;
	cin >> n >> s >> k;
	for (int i = 0; i < n; i++) {
		if (s[i] != s[k - 1]) cout << '*';
		else cout << s[i];
	}
	cout << "\n";
}

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

int main(){
int n,x;
cin >> n >> x;
vector<int> a(n);
for(int i=0;i<n;i++){
    cin >> a.at(i);
}
int i =0;
int ans =1;
int now =0;
while(1){
    now +=a.at(i);
    if(now<=x)ans++;
    else break;
    if(i==n-1) break;
    
    i++;
}
cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int,int> Pii;
typedef long long ll;
typedef tuple<int,int,int> Ti;

int main(){
    int n,m,l,q;
    cin>>n>>m>>l;
    vector<vector<Pii>> gr(n,vector<Pii>());
    vector<vector<Pii>> d(n,vector<Pii> (n,Pii(MOD,MOD)));
    rep(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        if(c>l) continue;
        gr[a-1].push_back(Pii(b-1,c));
        gr[b-1].push_back(Pii(a-1,c));
    }
    cin>>q;
    rep(s,n){
        vector<bool> seen(n,false);
        
        priority_queue<Ti,vector<Ti>,greater<Ti>> que;
        que.push(Ti(0,0,s));
        while(!que.empty()){
            int ex,ct,nd;

            tie(ex,ct,nd)=que.top();
            que.pop();
            if(seen[nd]) continue;
            d[s][nd]=Pii(ex,ct);
            seen[nd]=true;
            for(auto p:gr[nd]){
                ll b=p.first, c=p.second;
                if(seen[b]) continue;

                Pii x=d[s][nd];
                if(d[s][nd].second+c>l){
                    x.first+=1;
                    x.second=c;
                }
                else x.second+=c;
                if(d[s][b]>x){
                    d[s][b]=x;
                    que.push(Ti(d[s][b].first,d[s][b].second,b));
                }
            }
        }
    }
    rep(i,q){
        int s,t;
        cin>>s>>t;s--;t--;
        if(d[s][t].first==MOD) cout<<-1<<endl;
        else cout<<d[s][t].first<<endl;
    }

    return 0;
}

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

namespace contest_Csharp
{
    class Program
    {


        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var vals = Console.ReadLine().Split(' ')
                .Select(x => int.Parse(x)).ToList();

            int N = vals[0];
            int ans = 0;

            List<int> P = Console.ReadLine().Split(' ')
                .Select(x => int.Parse(x)).ToList();

            //List<int> cost = new List<int>(new int[N * N]);
            int[] cost = new int[N * N];
            //List<bool> left = new List<bool>(new bool[N * N]);
            var left = new bool[N * N];

            for (int i = 0; i < N*N; i++)
            {
                cost[i] = i / N;
                cost[i] = Math.Min(cost[i], N - 1 - i / N);
                cost[i] = Math.Min(cost[i], i % N);
                cost[i] = Math.Min(cost[i], N - 1 - i % N);
            }

            foreach (var ctm in P)
            {
                ans += cost[ctm - 1];
                Queue<int> bfsQueue = new Queue<int>();
                int point = ctm - 1;
                left[ctm - 1] = true;
                bfsQueue.Enqueue(point);
                do
                {
                    point = bfsQueue.Dequeue();
                    if (point + N < N * N && cost[point + N] >
                        cost[point] + (left[point] ? 0 : 1))
                    {
                        cost[point + N] = cost[point] + (left[point] ? 0 : 1);
                        bfsQueue.Enqueue(point + N);
                    }
                    if (point - N >= 0 && cost[point - N] >
                        cost[point] + (left[point] ? 0 : 1))
                    {
                        cost[point - N] = cost[point] + (left[point] ? 0 : 1);
                        bfsQueue.Enqueue(point - N);
                    }
                    if (point % N != N - 1 && cost[point + 1] >
                        cost[point] + (left[point] ? 0 : 1))
                    {
                        cost[point + 1] = cost[point] + (left[point] ? 0 : 1);
                        bfsQueue.Enqueue(point + 1);
                    }
                    if (point % N != 0 && cost[point - 1] >
                        cost[point] + (left[point] ? 0 : 1))
                    {
                        cost[point - 1] = cost[point] + (left[point] ? 0 : 1);
                        bfsQueue.Enqueue(point - 1);
                    }
                } while (bfsQueue.Count() != 0);



            }

            Console.WriteLine(ans);
            Console.Out.Flush();

        }



    }

}


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

int main() {
  double R; //Rは現在のレーティング
  double G; //Gは次のレーティング
  int b;	//パフォーマンス
  cin >> R >> G;
  b = 2 * G - R;
  cout << b << endl;
}


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

vector<int>vec;
int n;
long long S = 0;

int cal(int i,long long sum,long long a){
//i番目、計、前までの和
  if(i == n-1){
    S += sum + a * 10 + vec[i];
    return 0;
  }
  cal(i+1,sum,a * 10 + vec[i]);
  cal(i+1,sum + a * 10 + vec[i],0);
  return 0;
}

int main(){
  string s;
  cin >> s;
  n = s.size();
  vec.resize(n);
  for(int i = 0; i < s.size() ; i++){
    vec[i] = s[i] - '0';
  }
  cal(0,0,0);
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

d1 = T1*A1 - T1*B1
d2 = T2*A2 - T2*B2
d3 = d1+d2
if d3 == 0:
    print('infinity')
    exit()

if (d1 > 0 and d3 > 0) or (d1 < 0 and d3 < 0):
    print(0)
    exit()

d1 = abs(d1)
d3 = abs(d3)
if d1 % d3 == 0:
    print(d1 // d3 * 2)
else:
    print(d1 // d3 * 2 + 1)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
	b.append(a[i]-(i+1))
b.sort()
if n%2 == 1:
	median = b[n//2]
else:
	median = (b[n//2]+b[n//2-1])/2
ans = 0
for i in range(n):
	ans += abs(a[i]-(median+i+1))
print(int(ans))

Measured memory_bytes: 26180
package main

import (
	"fmt"
	"math"
)

func main() {
	var x float64
	fmt.Scan(&x)

	year := 0
	amount := 100.0
	for {
		if amount >= x {
			fmt.Println(year)
			return
		}
		amount = math.Trunc(amount * 1.01)
		year++
	}
}


Measured memory_bytes: 1760
st = input()
if st[0] == st[1] and st[0] == st[2] and st[0] == "R":
  print(3)
elif (st[0] == st[1] and st[0] == "R") or (st[1] == st[2] and st[1] == "R"):
  print(2)
elif "R" in st:
  print(1)
else:
  print(0)


Measured memory_bytes: 8992
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;

long long MOD = 1000000007;

vector<vector<long long> > A(100000,vector<long long>(2,-1));

long long calc(long long mask){
    long long ret=0;
    for(int i=0; i<100000; i++){
        if (A[i][0]==-1)break;
        if(A[i][0]&mask)continue;
        ret+=A[i][1];
    }
  	//cout << ' ' << ret << endl;
    return ret;
}

int main(){
    long long N,K;
    cin >> N >> K;
    long long all1=pow(2,30)-1;

    for(int i=0; i<N; i++){
        cin >> A[i][0] >> A[i][1];
    }
    long long tmp=1;
    long long ans=calc(all1-K);
    for(int i=0; i<30; i++){
      	if(tmp>K)break;
        else if(K&tmp){
            long long mask=K&(all1-tmp);
            mask|=tmp-1;
          	//cout << mask;
            mask=all1-mask;
            ans=max(ans,calc(mask));
        }
        tmp*=2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5888
n, k = [int(i) for i in input().split()]
p = [(float(i)+1)/2 for i in input().split()]
tmp = [sum(p[:k])]
for i in range(1,n-k+1):
    tmp.append(tmp[-1]-p[i-1]+p[i+k-1])
print(max(tmp))

Measured memory_bytes: 23148
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=5e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;

const int MSQ = sqrt(N) + 5;

std::vector<int> wa;
bool  y[1000005];
void sieve(){
	for(int i=2;i<=1000000;i++){
		if(y[i])continue;
		wa.pb(i);
		for(int j=i;j<=1000000;j+=i){
			y[j]=1;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();
	
	int n,k;

	scanf("%d %d",&n,&k);

	std::vector<int> a(n);

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

	sort(all(a));
	ll ans = 0;
	for(int i=0;i<n-k;i++)ans+=a[i];
	printf("%lld\n",ans );
}		



Measured memory_bytes: 1024
import java.util.Scanner;

class Main {
	//???????????????????????§???????????????????????°????????????????????°
	private static int count;

	public static void main (String[]args){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] numList = new int[n];
		for(int i = 0; i< n; i++){ 
			numList[i] = scanner.nextInt();
		}
		//?????????????????????????????????????????°???????±???????(numList)????????????????°????????´???????(0)?????????????????§???????´???????(n)?????????
		mergeSort(numList, 0, n);
		
		System.out.print(numList[0]);
		for(int i = 1; i < n; i++){
			System.out.print(" " + numList[i]);
		}
		System.out.println();
		System.out.println(count);
	}
	
	//???????????????(mid)???????????????L??¨R????????????????´?????????? L??¨R????????????????´???°???????????¨?????????
	static void merge(int[] numList, int left, int mid, int right){
		int n1 = mid - left;
		int n2 = right - mid;
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];

		for(int i = 0; i < n1; i++){
			L[i] = numList[left + i];
		}
		
		for(int i = 0; i < n2; i++){
			R[i] = numList[mid + i];
		}
		
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;
		int i = 0;
		int j = 0;
		//L??¨R??????????????????????°????????????????numList???????´??????????
		//?°?????????????????????????????????????????¬??????????????????????????????????????´????????????????????????°?????????+1?????????
		for(int k = left; k < right; k++){
			count++;
			if(L[i] <= R[j]){
				numList[k] = L[i];
				i = i + 1;
			} else {
				numList[k] = R[j];
				j = j + 1;
			}
		}
	}
	
	//????¨????merge???????????????????±??????????????°?????´???????(left)??¨?????§????´???????(right)?????????-1??????????????§??°????????????
	static void mergeSort(int[] numList, int left, int right){
		if((left + 1) < right){
			int mid = (left + right) / 2;
			
		mergeSort(numList, left, mid);
		//System.out.println("???");
		mergeSort(numList, mid, right);
		//System.out.println("???");
		merge(numList, left, mid, right);
		}
	}
}

Measured memory_bytes: 170264
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    int n, x = 0, pow = 1;
    cin >> n;
    while (n){
        if (n % 10 == 1)
        {
            x += 9 * pow;
        }
        else
          if (n % 10 == 9) x += pow;
          else x += pow * (n % 10);
        pow *= 10;
        n /= 10;
    }
    cout << x << endl;
}

Measured memory_bytes: 256
N = int(input())
arr_1 = []
arr_2 = []

arr_1 = list(map(int, input().split()))
arr_2 = list(map(int, input().split()))
ans = arr_1[0]+sum(arr_2)
for i in range(1,N):
  ans = max(ans, sum(arr_1[:i+1])+sum(arr_2)-sum(arr_2[:i]))
print(ans)

Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
int main(){
    int n;
    cin >> n;
    long long a[n];
    rep(i,n) cin >> a[i];
    set<long long> st;
    map<long long,int> mp,mp2; 
    rep(i,n){
        st.insert(-a[i]);
        mp2[a[i]]++;
        if(mp.find(a[i])==mp.end()) mp[a[i]]=i;
    }
    st.insert(0);
    mp2[0]=1;
    mp[0]=-1;
    long long now = -*st.begin();
    long long now_itr = mp[now];
    long long ans[n];
    long long cnt = mp2[now];
    //cout << now << " " << now_itr << " "<< cnt << endl;
    fill_n(ans,n,0);
    for(auto itr = st.begin();itr!=st.end();itr++){
        if(itr==st.begin()) itr++;
        long long next = *itr;
        next*=(-1);
        long long next_itr = mp[next];
        ans[now_itr]+=(cnt)*(now-next);
        cnt+=(mp2[next]);
        now = next;
        if(now_itr>next_itr){
            now_itr=next_itr;
        }
        //cout << next << " " << next_itr << endl;
    }
    rep(i,n) cout << ans[i] << endl;
}

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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  string s;
  cin >> s;
  int leng = s.size();

  string ans = s;
  if(s[leng-1] == 's'){
    ans.push_back('e');
    ans.push_back('s');
  }else
  {
    ans.push_back('s');
  }
  cout << ans << endl;
  

  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a; cin >> a;
  cout << a + a*a + a*a*a << endl;
}


Measured memory_bytes: 3636
#include<stdio.h>

int main(void) {

int i,n ;

int number ;

long long int sum = 0 ;

int min = 0 ;

int max = 0 ;

scanf("%d",&n) ;

for(i = 0;i<n ;i++) {

scanf("%d",&number) ;

if(i==0){

min = number ;

max = number ;

}

if(number<min) min = number ;

if(number>max) max = number ;

sum += number ;

}

printf("%d %d %lld\n",min,max,sum) ;

return 0 ;

}  

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

int N;
std::string s, t;

int main() {
	std::cin >> N >> s >> t;
	for (int i = N; i >= 0; --i)
		if (s.substr(N - i) == t.substr(0, i))
			return std::cout << N + N - i, 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
#define fastio cin.tie(0); cin.sync_with_stdio(0);
#define MOD 1000000007
#define MAXN 1005

int R,C,A[MAXN],B[MAXN];
ll res = 1;
set<int> fs,ss,tot;

int main(){
    fastio; cin >> R >> C;
    for(int i=1; i<=R; i++){
        cin >> A[i];
        fs.insert(A[i]);
        tot.insert(A[i]);
    }
    for(int i=1; i<=C; i++){
        cin >> B[i];
        ss.insert(B[i]);
        tot.insert(B[i]);
    }
    if(fs.size() != R || ss.size() != C){
        cout << 0 << '\n';
        return 0;
    }
    sort(A+1,A+R+1);
    sort(B+1,B+C+1);
    for(int i=R; i>=1; i--){
        if(ss.count(A[i])) continue;
        int am = B+C+1-upper_bound(B+1,B+C+1,A[i]);
        res = res*am%MOD;
    }
    for(int i=C; i>=1; i--){
        if(fs.count(B[i])) continue;
        int am = A+R+1-upper_bound(A+1,A+R+1,B[i]);
        res = res*am%MOD;
    }
    for(int i=R*C; i>=1; i--){
        if(tot.count(i)) continue;
        int f = A+R+1-upper_bound(A+1,A+R+1,i);
        int s = B+C+1-upper_bound(B+1,B+C+1,i);
        int rem = f*s-(R*C-i);
        res = res*rem%MOD;
    }
    cout << res << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <unordered_map>
#include <bitset>
#include <complex>
#include <complex>
#include <cmath>
#include <iomanip>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#define mp make_pair
#define pb push_back
const int MOD = 1e9 + 7;
const int N = 1e5;
using namespace std;
map<int , int> cnt;
vector<int> l , r;
int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    int mn = 0;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++)
    {
        if(abs(a[i]) > abs(a[mn]))
        {
            mn = i;
        }
    }
    if(abs(a[mn]) == 0)
    {
        cout << 0;
        return 0;
    }
    bool flag = 0;
    
    if(abs(a[mn]) == a[mn]) flag = 1;
    for (int i = 0; i < n; i++)
    {
        if(i != mn)
        {
            l.pb(mn + 1);
            r.pb(i + 1);
        }
    }
    if (flag)
    {
        for (int i = 1; i < n; i++)
        {
            {
                l.pb(i);
                r.pb(i + 1);
            }
        }
    }
    else
    {
        for (int i = n - 1 - 1; i >= 0; i--)
        {
            {
                l.pb(i + 2);
                r.pb(i + 1);
            }
        }
    }
    cout << l.size() << "\n";
    for(int i  = 0; i < l.size(); i++) cout << l[i] << " " << r[i] << "\n";
}

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

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

int main() {
  int n,l;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    if (i == 0) {
      l = k;
    }
    l = gcd(k,l);
  }
  cout << l << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int p, b[2999], ncr[3000][3000];
bool a[2999];

int add(int x, int y)
{
    return (x+y)%p;
}

int sub(int x, int y)
{
    return (x-y+p)%p;
}

int mul(int x, int y)
{
    return (ll(x)*ll(y))%p;
}

int main()
{
    cin >> p;
    for(int i = 0; i<p; i++)
        cin >> a[i];
    ncr[0][0] = 1;
    for(int i = 1; i<p; i++)
    {
        ncr[i][0] = 1;
        for(int j = 1; j<=i; j++)
            ncr[i][j] = add(ncr[i-1][j-1],ncr[i-1][j]);
    }
    for(int i = 0; i<p; i++)
        if(a[i])
        {
            b[p-1] = add(b[p-1],1);
            int pwr = 1;
            for(int j = 0; j<p; j++)
                b[j] = sub(b[j],mul(pwr,ncr[p-1][j])), pwr = mul(pwr,p-i);
        }
    for(int i = p-1; i>=0; i--)
        cout << b[i] << " ";
    cout << endl;
}


Measured memory_bytes: 34304
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //This code is not meant for understanding, proceed with caution
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        long n = nl(), ans = 0;
        for(long i = 1; i*i<= n; i++){
            if(n%i!=0)continue;
            long x = n/i-1;
            if(x>0 && n%x==n/x)ans+=x;
        }
        pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)998244353, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)1e5+1;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

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

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

#define MAX 100020

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

ll a,b;
cin>>a>>b;
cout<<(a*b)/gcd(a,b);
}

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

using Graph = vector<vector<int>>;

int solve(auto& N, auto& G) {
  auto bipartite = true;
  vector<vector<int>> parts;
  vector<int> color(N, -1);
  function<void(int, int)> dfs = [&](auto cur, auto c) {
    color[cur] = c;
    ++parts.back()[c];
    for(auto nex: G[cur]) {
      if(color[nex] == c) bipartite = false;
      if(!~color[nex]) dfs(nex, !c);
    }
  };
  for(auto v=0; v<N; ++v) if(!~color[v]) {
    parts.emplace_back(2);
    dfs(v, 0);
  }
  if(!bipartite) return -1;

  set<int> dp = {0};
  for(const auto& p: parts) {
    set<int> nex;
    for(auto x: p) for(auto i: dp) nex.emplace(i + x);
    swap(dp, nex);
  }

  int res = 1e9;
  for(auto i: dp) {
    auto j = N - i;
    res = min(res, i*(i-1)/2 + j*(j-1)/2);
  }
  return res;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<bool>> A(N, vector<bool>(N));
  for(auto i=0; i<M; ++i) {
    int a, b;
    cin >> a >> b; --a, --b;
    A[a][b] = A[b][a] = true;
  }

  Graph G(N);
  for(auto u=0; u<N; ++u) for(auto v=0; v<N; ++v) if(u!=v) if(!A[u][v]) G[u].emplace_back(v);

  cout << solve(N, G) << endl;
}


Measured memory_bytes: 3200
import sys

sys.setrecursionlimit(1000000)  # DFSは再帰の上限回数に注意

n = int(input())
edge = [[] for i in range(n)]
a = [0] * n  # 頂点を格納しておく配列
b = [0] * n

color_dict = {}  # 色を覚えておく
k = 0


def dfs(x, last=-1, ban_color=-1):
    # lastは、どこから来たか、逆走を防ぐ。使っちゃいけない色も引数
    global k  # グローバル変数
    color = 1
    for to in edge[x]:
        if to == last: continue
        # 来た頂点に戻ろうとしたら、何もしない
        if color == ban_color: color += 1
        # 使っちゃいけない色なら、新しい色にする
        color_dict[(x, to)] = color
        dfs(to, x, color)
        # 次の頂点toについてDFS。来たのはxから。前の頂点で使った色はダメ。
        color += 1  # 色を新しくする
    k = max(k, color - 1)  # 何色を使ったか、覚えておく


for i in range(n - 1):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1  # 0-indexにする
    b[i] -= 1
    edge[a[i]].append(b[i])  # 無向グラフ
    edge[b[i]].append(a[i])

dfs(0)  # 最初の頂点をDFSに入れてスタート
print(k)  # まず、何色必要かを出力

for i in range(n - 1):  # 辺の色を1から頂点番号-1まで出力
    if (a[i], b[i]) in color_dict:  # 辞書から答を出力
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])

Measured memory_bytes: 84520
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define poly vector<ll>
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void wri(ll a){write(a); putchar(' ');}
inline void writeln(ll a){write(a); puts("");}
const int N=200005;
const ll inf=1e18;
vector<int> v[N];
poly me(poly a,poly b){
	int n=a.size(),m=b.size(),i=0,j=0;
	poly c(n+m-1);
	while(i<n&&j<m){
		c[i+j]=a[i]+b[j];
		if((i+1<n&&(j+1==m||a[i+1]+b[j]>a[i]+b[j+1])))i++; else j++;
	}
	return c;
}
poly operator +(poly a,poly b){
	poly A[2],B[2];
	for(int i=0;i<2;i++){
		for(unsigned j=i;j<a.size();j+=2)A[i].push_back(a[j]);
		for(unsigned j=i;j<b.size();j+=2)B[i].push_back(b[j]);
	}
	poly ans(a.size()+b.size()-1);
	for(auto &i:ans)i=-inf;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			poly c=me(A[i],B[j]);
			for(unsigned k=0;k<c.size();k++){ ans[k*2+i+j]=max(ans[k*2+i+j],c[k]); }
		}
	}
	return ans;
}
poly solve(int l,int r){
	if(l==r){
		sort(v[l].begin(),v[l].end()); 
		int m=v[l].size(); poly ans(m+1);
		for(int i=1;i<=m;i++)ans[i]=ans[i-1]+v[l][m-i];
		ans[1]=-inf; //cout<<l<<" fjzzq "<<ans.size()<<endl;
		return ans;
	}
	int mid=(l+r)>>1;
	return solve(l,mid)+solve(mid+1,r);
}
signed main(){
	int n=read(),k=read();
	for(int i=1;i<=n;i++){
		int c=read(),w=read();
		v[c].push_back(w);
	}
	poly ans(n+1);
	for(auto &i:ans)i=-inf;
	for(int i=1;i<=3;i++){
		for(int i=1;i<=k;i++)swap(v[i],v[((ll)rand()<<15^rand())%i+1]);
		poly zs=solve(1,k);
		for(int i=1;i<=n;i++)ans[i]=max(ans[i],zs[i]);
	}
	for(int i=1;i<=n;i++){
		if(ans[i]<0)puts("-1");
		else writeln(ans[i]);
	}
}


Measured memory_bytes: 16628
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;
template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
// long long mod = 998244353;
#define REP(i, n) for (long long i = 0; i < (n); i++)
#define rep(i, a, n) for (long long i = a; i < (n); i++)
typedef long long ll;
typedef pair<ll, ll> P;
long long mod = 1000000007;
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t % mod;
    } else {
        return modpow(m, n - 1) * m % mod;
    }
}
long long power(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}

long long moddiv(long long a, long long b) { return (a * modpow(b, mod - 2)) % mod; }

const ll INF = 1LL << 60;

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

ll nCkmod(ll n, ll k) {
    ll denomi = 1;
    for (int i = n; i > n - k; i--) {
        denomi *= i;
        denomi %= mod;
    }
    ll numera = 1;
    REP(i, k) {
        numera *= (i + 1);
        numera %= mod;
    }
    return moddiv(denomi, numera);
}
vector<vector<ll>> graph;
vector<ll> as;
vector<ll> ans;
ll memo[101][100001];
void dfs(ll cur, ll parent) {
    ans[cur] = ans[parent] + as[cur];
    REP(i, graph[cur].size()) {
        if (graph[cur][i] != parent) {
            dfs(graph[cur][i], cur);
        }
    }
}
int main() {
    ll n, q;
    cin >> n >> q;
    graph.resize(n);
    ans.resize(n);
    REP(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    as.resize(n);
    REP(i, q) {
        int p, x;
        cin >> p >> x;
        p--;
        as[p] += x;
    }
    dfs(0, 0);
    for (auto x : ans) {
        cout << x << " ";
    }
}

Measured memory_bytes: 26652
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include <numeric>
#include<stdio.h>
#include <queue>
#include <iomanip>
#include <float.h>
#include <set>
#include<functional>
#include <stack>
#include <time.h>
#include <climits>
#include <bitset>
#include <fstream>
#include<map>
#include <cassert>
#include<sstream>
#include<fstream>
#include <cstring>
using namespace std;
typedef pair<int, string>p;
map< int64_t, int > prime_factor(int64_t n) {
	map< int64_t, int > ret;
	for (int64_t i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
long long mod = 1e9 + 7;
vector< int64_t > divisor(int64_t n) {
	vector< int64_t > ret;
	for (int64_t i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(begin(ret), end(ret));
	return (ret);
}
long long pow(long long x, long long kata) {
	if (kata == 0)return 1;
	if (kata == 1)return x;
	if (kata % 2 == 0) {
		return pow(x, kata / 2)*pow(x, kata / 2) % mod;
	}
	else {
		return pow(x, kata - 1)*x%mod;
	}
}
const int MAX = 101010;
bool is_prime[MAX];
int min_factor[MAX];
int meb[MAX];
vector<int> preprocess(int n = MAX) {
	vector<int> res;
	for (int i = 0; i < n; ++i) is_prime[i] = true, min_factor[i] = -1, meb[i] = 1;
	is_prime[0] = false; is_prime[1] = false;
	min_factor[0] = 0, min_factor[1] = 1;
	meb[0] = 0; meb[1] = 1;
	for (int i = 2; i < n; ++i) {
		if (!is_prime[i]) continue;
		res.push_back(i);
		min_factor[i] = i;
		meb[i] = -1;
		for (int j = i * 2; j < n; j += i) {
			is_prime[j] = false;
			meb[j] *= -1;
			if (min_factor[j] == -1) min_factor[j] = i;
			if ((j / i) % i == 0) meb[j] = 0;
		}
	}
	return res;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	long long n, k;
	cin >> n >> k;
	preprocess();
	long long ans = 0;
	for (long long i = 1; i <= k; i++) {
		long long tmp = 0;
		for (long long j = i; j <= k; j += i) {
			tmp += pow(k / j, n)*meb[j/i];
			tmp += mod;
			tmp %= mod;
		}
		ans += tmp*i;
		ans %= mod;
	}
	cout << ans;
}



Measured memory_bytes: 4636
/* 
	Author: ankrypt
*/

#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<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 100005
#define PI 3.141592653589793
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define mem(x, a) memset(x, a, sizeof x)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pcl pair<char, ll>
#define psl pair<string, ll>


ll N, M, A, B, C, L, R;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
unordered_map<ll, ll> mp;
set<ll> s;
string S = "";
ll cases;
ll pref[MAX_INT];

int main() {
	// go;
    cin >> N >> M;
   	cin >> S;
   	fi(i, 0, S.size() - 1, 1) {
   		if(S[i] == 'A' && S[i + 1] == 'C') {
   			pref[i + 1] = pref[i] + 1;
   			pref[i + 2] = pref[i + 1]; 
   		}
   		else {
   			pref[i + 1] = pref[i];
   		}
   	}
   	pref[S.size()] = pref[S.size() - 1];
   	// fei(i, 0, S.size(), 1) {
   	// 	trace2(i, pref[i]);
   	// }
   	fi(i, 0, M, 1) {
   		cin >> L >> R;
   		ll ans = 0;
   		if(S[R - 1] == 'A' && pref[R - 1] < pref[R]) {
   			ans = -1;
   		}
   		ans += pref[R] - pref[L - 1];
   		cout << max(0ll, ans) << "\n";
   	}
    
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 4472
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << (b % a ? b - a : a + b) << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		int N = Integer.parseInt(sc.get());
		String S = sc.get();
		var chars = S.toCharArray();
		var pos = new int[3][N];
		switch (chars[0]) {
			case 'R':
				pos[0][0]++;
				break;
			case 'G':
				pos[1][0]++;
				break;
			case 'B':
				pos[2][0]++;
				break;
		}
		for (int i = 1; i < chars.length; i++) {
			pos[0][i] = pos[0][i - 1];
			pos[1][i] = pos[1][i - 1];
			pos[2][i] = pos[2][i - 1];
			switch (chars[i]) {
				case 'R':
					pos[0][i]++;
					break;
				case 'G':
					pos[1][i]++;
					break;
				case 'B':
					pos[2][i]++;
					break;
			}
		}
		long sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i; j < N; j++) {
				if (chars[i] == chars[j]) continue;
				int right;
				int ch;
				if (chars[i] != 'R' && chars[j] != 'R') {
					right = 0;
					ch = 'R';
				} else if (chars[i] != 'G' && chars[j] != 'G') {
					right = 1;
					ch = 'G';
				} else {
					right = 2;
					ch = 'B';
				}
				var target = pos[right];
				var count = target[target.length - 1] - target[j];
				var invalid = j + j - i;
				if (invalid < N && chars[invalid] == ch) count -= 1;
				sum += count;
			}
		}

		System.out.println(sum);
	}
}

class Main {
	public static void main(String... args) {
		var reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<>() {
			private StringTokenizer line;

			public String get() {
				try {
					return (line = line != null && line.hasMoreTokens() ? line : new StringTokenizer(reader.readLine())).nextToken();
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
		});
	}
}

Measured memory_bytes: 32860
#pragma region
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = n; i > 0; i--)
#define repc(i, m, n) for (int i = m; i < n; i++)
#define reprc(i, m, n) for (int i = m; i > n; i--)
#define all(v) v.begin(), v.end
#define INF 1e9
#define EPS 1e-10
using namespace std;
typedef long long ll;
#pragma endregion

int main()
{
    int N;
    cin >> N;
    set<string> S;

    rep(i,N){
        string key;
        cin >> key;
        S.insert(key);
    }

    cout << S.size() << endl;
}

Measured memory_bytes: 19260
import Control.Monad (foldM)

main = do
    [n,s] <- (map read . words) `fmap` getLine
    if n == 0 && s == 0 then return () else do
        print $ solve n s
        main

solve :: Int -> Int -> Int
solve n s = length $ filter (==(0,0)) $ foldM mayUse (n,s) [0..9]
    where
    mayUse (0,0) _ = [(0,0)]
    mayUse (0,_) _ = [] -- no hope
    mayUse (n,s) d
        | s < d = [] -- no hope
        | otherwise = [(n,s),(n-1,s-d)]

Measured memory_bytes: 4112
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[210001],c[210001],w,k,d[210001],tmp;
int b[210001],i,j,n,m,t;
int main(){
	//freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	scanf("%d%d%d",&n,&m,&t);
	for (i=1;i<=n;i++) scanf("%lld%d",&a[i],&b[i]);
	for (i=1;i<=n;i++)
	 if (b[i]==1) c[i]=(t+a[i])%m;else c[i]=(a[i]-t%m+m)%m;
	k=c[1];
	sort(c+1,c+1+n);
	for (i=2,w=0;i<=n;i++)
	 if (b[i]!=b[1]){
	 	if (b[1]==1) tmp=a[i]-a[1];else tmp=m-(a[i]-a[1]);
	 	if (2*t<tmp) continue;
		w=(w+1+(2*t-tmp)/m)%n;
		if ((2*t-tmp)%m==0) w=(w-1+n)%n;
	 }
	if (b[1]==1) w=(w+1)%n;else w=(n-w+1)%n;
	if (!w) w=n;
	for (i=1;c[i]!=k;i++);
	if (i<n&&c[i]==c[i+1]&&b[1]==2) i++;
	for (j=0;i<=n;i++){
		d[(w+j)%n]=c[i];
		j++;
	}
	for (i=1;j<n;i++){
		d[(w+j)%n]=c[i];
		j++;
	}
	d[n]=d[0];
	for (i=1;i<=n;i++) printf("%lld\n",d[i]);
	return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i=0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int D = 1e18, wh;
    for (int i=0; i < n; i++){
        int dd = abs(v.back() - 2*v[i]);
        if (dd < D){
            D=dd;
            wh = v[i];
        }
    }
    cout << v.back() << " " << wh;
    return 0;
}





Measured memory_bytes: 1024