akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size()){cout << a[i];cout << (i == a.size() - 1 ? "\n":" ");}
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007LL;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> A(N),B(N),sa(N);
    ll suma = 0,sumb = 0;
    rep(i,N){
        cin >> A[i];
        suma += A[i];
    }
    rep(i,N){
        cin >> B[i];
        sumb += B[i];
    }
    if(suma < sumb){
        cout << "-1\n";
        return 0;
    }
    ll miwa = 0,mi = 0;
    rep(i,N){
        if(A[i] < B[i]){
            miwa += B[i] - A[i];
            mi++;
        }
        sa[i] = A[i] - B[i];
    }
    sort(all(sa));
    ll now = 0,ans = 0;
    for(ll i = N - 1;i >= 0;i--){
        if(now >= miwa)break;
        now += sa[i];
        ans++;
    }
    cout << ans + mi << endl;
    //cout << miwa << "\n";
    //vecout(sa);
}

Measured memory_bytes: 5544
import java.util.Scanner;

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

        int n, m, l;

        n = scanner.nextInt();
        m = scanner.nextInt();
        l = scanner.nextInt();

        int[][] a = new int[n][m];
        int[][] b = new int[m][l];
        long[][] c = new long[n][l];

        //create A matrix
        for(int arow = 0; arow < n; arow++){
            for(int acol = 0; acol < m; acol++){
                a[arow][acol] = scanner.nextInt();
            }
        }

        //create B matrix
        for(int brow = 0; brow < m; brow++){
            for(int bcol = 0; bcol < l; bcol++){
                b[brow][bcol] = scanner.nextInt();
            }
        }

        for(int ccol = 0; ccol < l; ccol++){
            for(int arow = 0; arow < n; arow++){

                for(int acol = 0; acol < m; acol++){
                    c[arow][ccol] += (long)a[arow][acol] * (long)b[acol][ccol];
                }
            }
        }


        for(int row = 0; row < n; row++){
            for(int col = 0; col < l-1; col++){
                System.out.print(c[row][col] + " ");
            }
            System.out.println(c[row][l-1]);
        }

        scanner.close();
    }
}



Measured memory_bytes: 54148
import bisect


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
        self.n = n

    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l, h):
        return self._sum(h) - self._sum(l - 1)


n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'), x1))
        vx.append((y2, float('inf'), x1))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2], 1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        i1 = bisect.bisect_left(xs, j)
        i2 = bisect.bisect(xs, x2) - 1
        ans += bit.sum(i1, i2)

print(ans)

Measured memory_bytes: 39900
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <iomanip>
using namespace std;
using ll = long long;
#define rep(i, j, n) for(int i = (j); i < (n); ++i)
#define rrep(i, j, n) for(int i = (n) - 1; (j) <= i; --i)
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<ll> a(n);
	rep(i, 0, n) cin >> a[i];
	sort(a.begin(), a.end());


	// l s l s l s l (n % 2 == 1)
	// l s l s l s (n % 2 == 0)
	// 全体の和を考えたときに
	ll ans1 = 0, ans2 = 0;
	rep(i, 0, n) {
		if (i < n / 2) 
			ans1 -= a[i] << 1;
		else 
			ans1 += a[i] << 1;

		if (i <= n / 2) 
			ans2 -= a[i] << 1;
		else 
			ans2 += a[i] << 1;
	}
	// ans1 = l s l s l
	// ans2 = s l s l s
	if (n & 1) {
		ans1 -= a[n / 2] + a[n / 2 + 1];
		ans2 += a[n / 2] + a[n / 2 - 1];
	}
	else {
		ans1 += a[n / 2 - 1] - a[n / 2];
		ans2 += a[n / 2 - 1] - a[n / 2];
	}
	cout << max(ans1, ans2);

	return 0;
}


Measured memory_bytes: 3992
#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;

ll n,m,ar[N],sum,t,mark[N],vis[N][15];

pair<ii,int> p[N];

vector<int> v[N];

void f(int ind,int maxd,int d,int col)
{
	if(vis[ind][maxd-d])
		return;
	vis[ind][maxd-d]++;
	if(!mark[ind])
	mark[ind]=col;
	if(d==maxd)
		return;
	for(int i=0;i<v[ind].size();i++)
		f(v[ind][i],maxd,d+1,col);
}

int main()
{
	fast;
	cin>>n>>m;
	fo(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	int q;

	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>p[i].fi.fi>>p[i].fi.se>>p[i].se;
	}
	for(int i=q;i>=1;i--)
		f(p[i].fi.fi,p[i].fi.se,0,p[i].se);
	for(int i=1;i<=n;i++)
	{
		cout<<mark[i]<<endl;
	}


}



/*     cd onedrive\desktop\kod
cls

Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/

Measured memory_bytes: 45176
import sys
input = sys.stdin.readline
def chmin(dp, i, j, b):
    if dp[i][j] > b:
        dp[i][j] = b
        return True
    return False
def main():
    N, W = map(int, input().split())
    goods = []
    INF = 10 ** 9 + 1
    for _ in range(N):
        goods.append(list(map(int, input().split())))
    dp = [[INF for _ in range(100001)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, v = goods[i][0], goods[i][1]
        for j in range(100001):
            chmin(dp, i+1, j, dp[i][j])
            if j-v >= 0:chmin(dp, i+1, j, dp[i][j-v]+w)
    ans = 0
    for i in range(100001):
        if dp[N][i] <= W:ans = i
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 173164
n=int(input())
a=[0] +list(map(int,input().split())) + [0]
d = []
for i in range(n+1):
    d.append(abs(a[i+1]-a[i]))
sumd = sum(d)
for i in range(n):
    print(sumd - d[i] - d[i+1] + abs(a[i+2]-a[i]))

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

int main()
{
	double EPS=1e-12;
	double *a = new double[8];
	while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7])
	{
		if(fabs(((a[2]-a[0])*(a[6]-a[4]))+((a[3]-a[1])*(a[7]-a[5]))) <= EPS)
		{
			cout<<"YES" << endl;
		}
		else 
		{
			cout<< "NO" << endl;
		}
	}
	return 0;
}

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

int main()
{
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n);

    rep(i, n) cin >> a[i];

    ll ans = 0;
    if (x < a[0])
    {
        ans += a[0] - x;
        a[0] = x;
    }
    rep(i, n - 1)
    {
        if (a[i] + a[i + 1] > x)
        {
            ans += (a[i] + a[i + 1] - x);
            a[i + 1] -= (a[i] + a[i + 1] - x);
        }
    }
    cout << ans << endl;
}

//初回の例外処理忘れがち

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

int main() {
  string S;
  cin >> S;
  int ans = 700;
  if (S[0] == 'o') ans += 100;
  if (S[1] == 'o') ans += 100;
  if (S[2] == 'o') ans += 100;
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}

int main()
{
    int N, K, max_num = -1;
    cin >> N >> K;
    //vector<int> A(N);
    int a, g;
    for (int n = 0; n < N; ++n)
    {
        cin >> a;
        if (n)
        {
            g = gcd(a, g);
        }
        else
        {
            g = a;
        }
        max_num = max_num < a ? a : max_num;
    }

    if (K <= max_num && K % g == 0)
    {
        cout << "POSSIBLE" << endl;
    }
    else
    {
        cout << "IMPOSSIBLE" << endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b;
	int r = 0;
	while(scanf("%d %d",&a,&b) != EOF){
		a += b;
		while(a >0){
			r++;
			a /= 10;
		}
		
		printf("%d\n",r);
		r = 0;
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
const ll MOD = 1e9 + 7;

struct FindUnion {
	int n;
	vector<int> parent, rank;
	
	FindUnion(int _n) : n(_n) {
		parent.resize(n + 1);
		rank.resize(n + 1);
		iota(parent.begin(), parent.end(), 0);
	}
	
	int find(int x) {
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	void union_(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		
		if (fx == fy) return;
		if (rank[fx] > rank[fy]) swap(fx, fy);
		
		parent[fx] = fy;
		if (rank[fx] == rank[fy]) rank[fy]++;
	}
	
	bool is_same(int x, int y) {
		return find(x) == find(y);
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	FindUnion fu(n);
	REP(_, q) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 0) {
			fu.union_(x, y);
		} else {
			cout << fu.is_same(x, y) << "\n";
		}
	}
	return 0;
}
 



Measured memory_bytes: 3304
var a:array[0..100]of int64;
    n,m,s,t:int64;
    i,j:longint;
    k:double;
begin
  readln(n,m);
  for i:=1 to n do
  begin
    read(a[i]);
    inc(s,a[i]);
  end;
  for i:=1 to n do
    for j:=i+1 to n do
      if a[i]<a[j] then
      begin
        t:=a[i];a[i]:=a[j];a[j]:=t;
      end;
  k:=s/4/m;
  for i:=1 to m do
    if a[i]<k then
    begin
      writeln('No');
      halt;
    end;
  writeln('Yes');
end.

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> A(N);
  vector<ll> B(N);
  vector<ll> C(N);
  rep(i, N) { cin >> A[i] >> B[i] >> C[i]; }

  vector<vector<ll>> dp(N, vector<ll>(3, 0));
  dp[0][0] = A[0];
  dp[0][1] = B[0];
  dp[0][2] = C[0];
  for (int i = 1; i < N; i++) {
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + A[i];
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + B[i];
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + C[i];
  }
  cout << max(dp[N - 1][0], max(dp[N - 1][1], dp[N - 1][2])) << endl;
  return 0;
}

Measured memory_bytes: 8064
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

string a;
vector<bool> op;
string makee(){
    string ret = "";
    ret += a[0];
    for (int i = 1; i < 4; i++)
    {
        ret += (op[i-1])? "+" : "-";
        ret += a[i];
    }
    ret += "=7";
    return ret;
    
}
bool dfs(){
    if(op.size()==a.length()-1){
        int tmp = a[0]-'0';
        for (int i = 1; i < 4; i++)
        {
            if(op[i-1])tmp+=a[i]-'0';
            else tmp-=a[i]-'0';
        }
        return tmp == 7;
    }
    for (int i = 0; i < 2; i++)
    {
        op.push_back(i);
        if(dfs()) return true;
        op.pop_back();
    }
  	return false;
    
}

int main() {
    cin >> a;
  	dfs();
    string ans = makee();

    cout << ans << endl;
}

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

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var n = vals[0];
        var k = vals[1];

        if (n >= k * 2 - 1)
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }
}

Measured memory_bytes: 13268
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    N = II()
    A = LMIIS()
    A.sort(reverse=True)
    circle = [A[0]]
    from math import log2
    ans = 0
    for i in range(ceil(log2(N))):
        new_circle = []
        len_circle = len(circle)
        for j in range(min(len_circle,N-2**i)):
            new_circle.append(circle[j])
            new_circle.append(A[2**i+j])
            ans += min(circle[j],circle[(j+1)%len_circle])
        #     # dbg('score,',A[2**i+j],min(circle[j],circle[(j+1)%len_circle]))
        # dbg(A[2**i+j],circle,new_circle)
        circle = new_circle
    
    print(ans)



        



main()

Measured memory_bytes: 121740
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000
#define pi 3.1415926535897932384626

int lis(vector<int>a) {
	int b[N];
	f(i, N)b[i] = MOD;
	int l, r, m;
	f(i, a.size()) {
		l = -1;
		r = N;
		while ((l + 1) < r) {
			m = (l + r) / 2;
			if (b[m] <= a[i])l = m;
			else r = m;
		}
		b[r] = a[i];
	}
	f(i, N)if (b[i] == MOD)return i;
}



int main() {
	vector<pair<int, int> >p;
	int aa, bb, cc, dd;
	vector<int>a;
	int n, k;
	int x, y, z;
	long double ans;
	bool v = true;
	ans = 0;
	scanf("%d %d %d %d", &aa, &bb, &cc, &dd);
	if (aa > cc) {
		swap(aa, cc);
		swap(bb, dd);
	}
	scanf("%d", &n);
	f(i, n) {
		scanf("%d %d", &x, &y);
		p.push_back(make_pair(x, y));
	}
	if (aa == cc) {
		if (bb > dd)swap(bb, dd);
		ans = (long double)(dd - bb);
		ans = ans * 100;
		f(i, n) {
			if ((p[i].first == aa) && (bb <= p[i].second) && (p[i].second <= dd))ans += ((10 * pi) - 20);
		}
		printf("%.12Lf\n", ans);
		return 0;
	}
	if (bb == dd) {
		if (aa > cc)swap(aa, cc);
		ans = (long double)(cc - aa);
		ans = ans * 100;
		f(i, n) {
			if ((p[i].second == bb) && (aa <= p[i].first) && (p[i].first <= cc))ans += ((10 * pi) - 20);
		}
		printf("%.12Lf\n", ans);
		return 0;
	}
	if (bb < dd) {
		sort(p.begin(), p.end());
		f(i, n) {
			if ((aa <= p[i].first) && (p[i].first <= cc) && (bb <= p[i].second) && (p[i].second <= dd))a.push_back(p[i].second);
		}
		x = lis(a);
		ans = (long double)((dd - bb) + (cc - aa));
		ans = ans * 100;
		ans += (5 * pi - 20)*((long double)x);
      y=min(dd-bb,cc-aa);
      if(x>y)ans+=5*pi;
	}
	else {
		sort(p.begin(), p.end(), greater<pair<int, int> >());
		f(i, n) {
			if ((aa <= p[i].first) && (p[i].first <= cc) && (dd <= p[i].second) && (p[i].second <= bb))a.push_back(p[i].second);
		}
		x = lis(a);
		ans = (long double)((bb - dd) + (cc - aa));
		ans = ans * 100;
		ans += (5 * pi - 20)*((long double)x);
      y=min(bb-dd,cc-aa);
      if(x>y)ans+=5 * pi;
	}
	printf("%.12Lf\n", ans);
	return 0;
}

Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)

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

	int ans = 0;
	rep(i, stoi(a), stoi(b)+ 1) {
		bool f = true;
		string num = to_string(i);
		rep(j, 0, num.size()/2) {
			if (num[j] != num[num.size() - j - 1]) {
				f = false;
				break;
			}
		}
		if (f) ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << 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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll n;
vector<ll> a;
vector<ll> s; // s[i] .. the sum of a in [0, i)

// return the pair of <sum, count>
pair<ll, ll> calc(ll x) {
  ll sum = 0, cnt = 0;
  rep(i, n) {
    // x-a[i] is the pair of a[i]. we want to find the boundary.
    ll j = lower_bound(all(a), x-a[i]) - a.begin();;
    cnt += n-j; // the count of [j, n)
    sum += s[n] - s[j];
    sum += a[i] * (n-j);
  }
  return mp(sum, cnt);
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll m;
  cin >> n >> m;
  a.resize(n);
  s.resize(n+1);

  rep(i, n) {
    cin >> a[i];
  }
  sort(all(a));
  // printvec(a);

  rep(i, n) {
    s[i+1] = s[i] + a[i];
  }
  // printvec(s);

  ll l = 0;
  ll r = 2e5 + 5;
  // find the boundary in [l, r).
  // The count is equal or larger than m, [t, ..., t, f, ..., f]
  while (r - l > 1) {
    ll mid = (l+r)/2;
    if (calc(mid).second >= m) { // ok
      l = mid;
    } else {
      r = mid;
    }
  }
  // Here, l is the largest true value.

  auto p = calc(l);
  ll ans = p.first;
  ans -= (p.second - m)*l; // We want to know the sum of exact m values.
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
	ll a,b,k;cin>>a>>b>>k;
	ll aa=a+k-1,bb=b-k+1;
	if(aa<bb){
	   for(int i=a;i<=aa;i++)cout<<i<<endl;
	   for(int i=bb;i<=b;i++)cout<<i<<endl;
	}
	else for(int i=a;i<=b;i++)cout<<i<<endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] bs = new int[n+1];
		for (int i = 1; i < n; i++) bs[in.nextInt()]++;
		for (int i = 1; i <= n; i++) System.out.println(bs[i]);
	}
}


Measured memory_bytes: 50464
#include<stdio.h>
#include<string.h>
int main()
{
	char s[128];
	int k;
	while(scanf("%s",s)!=EOF){
		for(int i=0;i<strlen(s);i++){
			if(s[i]=='@'){
				i++;
				k=s[i]-'0';
				i++;
				for(int j=0;j<k;j++){
					printf("%c",s[i]);
				}
			}else{
				printf("%c",s[i]);
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2508
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
    int N = 1000001; 

ll factorialNumInverse[1000002]; 
  
ll naturalNumInverse[1000002]; 
  
ll fact[1000002]; 

void InverseofNumber(ll p) 
{ 
	naturalNumInverse[0] = naturalNumInverse[1] = 1; 
	for (int i = 2; i <= N; i++) 
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p; 
} 
// Function to precompute inverse of factorials 
void InverseofFactorial(ll p) 
{ 
	factorialNumInverse[0] = factorialNumInverse[1] = 1; 

	// precompute inverse of natural numbers 
	for (int i = 2; i <= N; i++) 
		factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p; 
} 
void factorial(ll p) 
{ 
	fact[0] = 1; 

	// precompute factorials 
	for (int i = 1; i <= N; i++) { 
		fact[i] = (fact[i - 1] * i) % p; 
	} 
} 

ll Binomial(ll N, ll R, ll p) 
{ 

    ll ans = ((fact[N] * factorialNumInverse[R]) 
              % p * factorialNumInverse[N - R]) 
             % p; 
    return ans; 
} 
int main() {
	ll p = 1000000007; 
	InverseofNumber(p); 
	InverseofFactorial(p); 
	factorial(p);
		long long n,i,j,k,sum=0,count=0,ans=0,x,b,c,d,mx=0,mn=0;
	cin>>n>>k;
	long long a[n];
	for(i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
    for(i=k-1;i<n;i++)
    {
        mx=(mx%p+(a[i]*(Binomial(i,k-1,p)))%p)%p;
    }
	for(i=0;i<=(n-k);i++)
	{
	    mx=(mx%p-(a[i]*(Binomial(n-i-1,k-1,p)))%p)%p;
	    mx=(mx+p)%p;
	}
	cout<<mx-mn;
	return 0;
}


Measured memory_bytes: 24448
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>//for queue and priority_queue
#include <fstream>
#include <iomanip>
#include <stack>
#include <algorithm>
#define endl "\n"

using namespace std;
void Lancer() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

//int  frq[100007];
int main(){
	Lancer();
	//cout << fixed << setprecision(12);
	
	long long n,res=0;
	cin >> n;
	res = (n / 500) * 1000;
	res += ((n % 500) / 5)*5;
	cout << res;
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
//c++ テンプレ
#include<bits/stdc++.h>
using namespace std;

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve(){
    char c;
    cin >> c;
    if(islower(c))cout << 'a' << endl;
    else cout << 'A' << endl;

}

int main(){
    solve();
    return 0;
}




Measured memory_bytes: 3636
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
string replace(string s, string from, string to){
  //cout<<s<<" from:"<<from<<" to:"<<to;
  int p = 0;
  while(p + from.size() - 1< s.size()){
    int loc = s.find(from, p);
    if(loc == -1) break;
    s = s.replace(loc, from.size(), to);
    p = loc + to.size();
  }
  return s;
}

int dfs(string s, string& g, vector<string>& from, vector<string>& to){
  if(s == g) return 0;
  if(s.size() > g.size()) return INF;
  int res = INF;
  REP(i, from.size()){
    string t = replace(s, from[i], to[i]);
    if(s == t) continue;
    int f = dfs(t, g, from, to);
    if(f != INF) res = min(res, f + 1);
  }
  return res;
}
int main(){
  int N;
  while(cin>>N && N){
    vector<string> from(N);
    vector<string> to(N);
    REP(i,N)cin>>from[i]>>to[i];
    string start, goal;
    cin>>start>>goal;
    int ans = dfs(start, goal, from, to);
    if(ans != INF) cout<<ans<<endl;
    else cout<<-1<<endl;
  }
  return 0;
}

Measured memory_bytes: 932
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <assert.h>
#include <cmath>
#include <deque>
#include <set>
#include <unordered_map>
#include <complex>
#include <fstream>
#include <map>
using namespace std;
using ll = long long;
using ld = long double;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k; cin>>k; vector<bool> v(k, 0);
	int cnt = 1, red = 7%k; v[red] = 1; if(red==0) {cout << 1 << '\n'; return 0;}
	while(1) {
		cnt++;
		int next = (red*10+7)%k; 
		if(next==0) {cout << cnt << '\n'; return 0;}
		if(v[next]==1) {cout << -1 << '\n'; return 0;}
		v[next] = 1; red = next;
	}

	return 0;
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    set<int> s;
    cin>>n;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        s.insert(x);
    }
    if(s.size()!=n) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 9600
d = input().split(" ")
la = int(d[0])
lb = int(d[1])
lm = int(d[2])
a = input().split(" ")
mina = 100000
for i in range(la):
	a[i] = int(a[i])
	if mina > a[i]:
		mina = a[i]
b = input().split(" ")
minb = 100000
for i in range(lb):
	b[i] = int(b[i])
	if minb > b[i]:
		minb = b[i]
minab = mina + minb
for i in range(lm):
	d = input().split(" ")
	c = a[int(d[0])-1] + b[int(d[1])-1] - int(d[2])
	if c < minab:
		minab = c
print(minab)

Measured memory_bytes: 15388
#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < (n); i++)
#define rrep(i, n) for (long long i = (n)-1; i >= 0; i--)
using namespace std;

// https://github.com/beet-aizu/library/blob/master/graph/bellmanford.cpp
template <typename T>
struct BellmanFord
{
  static constexpr T INF = numeric_limits<T>::max();

  struct edge
  {
    int u, v;
    T w;
    edge() {}
    edge(int u, int v, T w) : u(u), v(v), w(w) {}
  };

  int n;
  vector<vector<int>> G;
  vector<int> used, reach;
  BellmanFord(int n) : n(n), G(n), used(n, 0), reach(n, 1) {}

  vector<edge> es;
  void add_edge(int u, int v, T c)
  {
    es.emplace_back(u, v, c);
    G[u].emplace_back(v);
  }

  vector<T> build(int from, int &neg_loop)
  {
    vector<T> ds(n, INF);
    ds[from] = 0;
    for (int j = 0; j < n; j++)
    {
      bool update = 0;
      for (auto e : es)
      {
        if (!reach[e.u] || !reach[e.v] || ds[e.u] == INF)
          continue;
        if (ds[e.v] > ds[e.u] + e.w)
        {
          ds[e.v] = ds[e.u] + e.w;
          update = 1;
        }
      }
      if (!update)
        break;
      if (j == n - 1)
      {
        neg_loop = 1;
        return ds;
      }
    }
    neg_loop = 0;
    return ds;
  }

  void dfs(int v)
  {
    if (used[v])
      return;
    used[v] = 1;
    for (int u : G[v])
      dfs(u);
  }

  T shortest_path(int from, int to, int &neg_loop)
  {
    for (int i = 0; i < n; i++)
    {
      fill(used.begin(), used.end(), 0);
      dfs(i);
      reach[i] = used[to];
    }
    return build(from, neg_loop)[to];
  }
};
template <typename T>
constexpr T BellmanFord<T>::INF;

void solve(long long N, long long M, std::vector<long long> a,
           std::vector<long long> b, std::vector<long long> c)
{
  BellmanFord<long long> st(N), gl(N), al(N);
  rep(i, M) a[i]--, b[i]--;
  rep(i, M)
  {
    st.add_edge(a[i], b[i], 1);
    gl.add_edge(b[i], a[i], 1);
  }
  int tmp = 0;
  st.build(0, tmp);
  gl.build(N - 1, tmp);
  rep(i, M)
  {
    if (st.reach[a[i]] && gl.reach[b[i]])
      al.add_edge(a[i], b[i], -c[i]);
  }
  int neg_loop = 0;
  long long t = al.shortest_path(0, N - 1, neg_loop);
  if (neg_loop)
  {
    cout << "inf" << endl;
  }
  else
  {
    cout << -t << endl;
  }
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main()
{
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> a(M);
  std::vector<long long> b(M);
  std::vector<long long> c(M);
  for (int i = 0; i < M; i++)
  {
    scanf("%lld", &a[i]);
    scanf("%lld", &b[i]);
    scanf("%lld", &c[i]);
  }
  solve(N, M, std::move(a), std::move(b), std::move(c));
  return 0;
}


Measured memory_bytes: 640
void insertion_sort2(int *a, int N){ //wikipedia
	int i,j,t;
	for(j=0;j<N;j++)printf(j<N-1?"%d ":"%d\n",a[j]);
	for(i=1;i<N;i++){
		t = a[i];
		for(j=i; j>0 && a[j-1]>t; j--){
			a[j] = a[j-1];
		}
		a[j] = t;
		for(j=0;j<N;j++)printf(j<N-1?"%d ":"%d\n",a[j]);
	}
}
a[999],i;main(n){
	for(scanf("%d",&n);i<n;i++)scanf("%d",a+i);
	insertion_sort2(a,n);
	exit(0);
}

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

// dp[i][j][k][m] :=  i: 上位 i 桁目まで決定
//                    j: started(数字を書き込んだ)か
//                    k: small(数字を自由に選べる)か
//                    m: {3,5,7} を選んだかのflag
//                    の条件を満たす数値の数
int dp[11][2][2][8];

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

  string n;
  cin >> n;

  int len = n.size();
  dp[0][0][0][0] = 1;
  for (int i = 0; i < len; ++i)
  {
    for (int j = 0; j < 2; ++j)
    {
      for (int k = 0; k < 2; ++k)
      {
        for (int m = 0; m < 8; ++m)
        {
          if (!dp[i][j][k][m]) continue;

          if (k == 1)                  // small ([0, 9] から数字を選べる)か
          {
            if (j == 0 && m == 0)      // not started (数字を書き込んでいない)か
              dp[i + 1][0][1][0] += dp[i][0][1][0];                // nothing

            dp[i + 1][1][1][m | 1] += dp[i][j][1][m];              // +3
            dp[i + 1][1][1][m | 2] += dp[i][j][1][m];              // +5
            dp[i + 1][1][1][m | 4] += dp[i][j][1][m];              // +7
          }
          else                         // not small ([0, d] から数字を選べる)か
          {
            int d = n[i] - '0';

            if (j == 0 && m == 0)      // not started (数字を書き込んでいない)か
              dp[i + 1][0][1][0] += dp[i][0][0][0];                // nothing

            if (d == 3) dp[i + 1][1][0][m | 1] += dp[i][j][0][m];  // +3
            if (3 < d)  dp[i + 1][1][1][m | 1] += dp[i][j][0][m];  // +3
            if (d == 5) dp[i + 1][1][0][m | 2] += dp[i][j][0][m];  // +5
            if (5 < d)  dp[i + 1][1][1][m | 2] += dp[i][j][0][m];  // +5
            if (d == 7) dp[i + 1][1][0][m | 4] += dp[i][j][0][m];  // +7
            if (7 < d)  dp[i + 1][1][1][m | 4] += dp[i][j][0][m];  // +7
          }
        }
      }
    }
  }

  int ans = dp[len][1][0][7] + dp[len][1][1][7];
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<db, db> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
typedef vector<vi> vii;
typedef vector<vl> vll;
typedef vector<vd> vdb;
typedef vector<vb> vbb;
typedef vector<vc> vcc;
typedef vector<vs> vss;

#define f first
#define s second	
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define part(x, n) (x).begin(), (x).begin()+n
#define rpart(x, n) (x).rbegin(), (x).rbegin()+n
#define rsz resize
#define ins insert
#define cnt count
#define fr front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define LSOne(S) ((S)&-(S))

#define F0R(i, a, b) for(int i = (a); i < (b); ++i)
#define FOR(i, a) F0R(i, 0, a)
#define R0F(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define ROF(i, a) R0F (i, 0, a)
#define trav(a, x) for (auto& a: x)

const int MOD = 1e9+7;

//input
template<class A> void read(complex<A>& c);
template<class A, class B> void read(pair<A,B>& p);
template<class A> void read(vector<A>& v);
template<class A, size_t SZ> void read(array<A,SZ>& a);

template<class T> void read(T& x) { cin >> x; }
void read(db& d) { str t; read(t); d = stod(t); }
void read(ld& d) { str t; read(t); d = stold(t); }
template<class H, class... T> void read(H& h, T&... t) { read(h); read(t...); }

template<class A> void read(complex<A>& c) { A a,b; read(a,b); c = {a,b}; }
template<class A, class B> void read(pair<A,B>& p) { read(p.f,p.s); }
template<class A> void read(vector<A>& x) { trav(a,x) read(a); }
template<class A, size_t SZ> void read(array<A,SZ>& x) { trav(a,x) read(a); }

//output
template<class A> void print(A x) { cout << (x); }
template<class H, class... T> void print(const H& h, const T&... t) {
	print(h); print(t...); }
void prints() { print("\n"); } // print w/ spaces
template<class H, class... T> void prints(const H& h, const T&... t) {
	print(h); if (sizeof...(t)) print(" "); prints(t...); }

void setIn(str s) {freopen(s.c_str(), "r", stdin);}
void setOut(str s) { freopen(s.c_str(), "w", stdout);}
void unsyncIO() { ios::sync_with_stdio(0); cin.tie(0);}
void setIO(str s= ""){
	unsyncIO();
	if(sz(s)) { setIn(s+".in"), setOut(s+".out");}
}

int main(){
	setIO();
	str a, b;
	read(a, b);
	int cur = 0, best = 1001;
	FOR(i, sz(a)-sz(b)+1){
		cur = 0;
		F0R(j, i, sz(b)+i){
			if(a[j]!=b[j-i])
				cur++;
		}
		best = min(cur, best);
	}
	prints(best);
	return 0;
}



Measured memory_bytes: 3644
def bubble_sort(card, n):
    flag = 1
    while flag:
        flag = 0
        for i in range(n-1, 0, -1):
            if card[i][1] < card[i-1][1]:
                card[i], card[i-1] = card[i-1], card[i]
                flag = 1
    print(' '.join(map(str, card)))
    return card

def selection_sort(card, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if card[j][1] <  card[minj][1]:
                minj=j
        if i != minj:              
            card[i], card[minj] = card[minj], card[i]

    print(' '.join(map(str, card)))
    return card

def isStable(stable_sorted, target):
    for i in range(len(stable_sorted)):
        if stable_sorted[i] != target[i]:
            return "Not stable"
    return "Stable"

def main():
    n = int(input())
    card = input().split()

    bubble_sorted_card = bubble_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, bubble_sorted_card))

    selection_sorted_card = selection_sort(card.copy(), n)
    print(isStable(bubble_sorted_card, selection_sorted_card))

if __name__ == "__main__":
    main()


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

template <typename T>
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T>
using Matrix = vector<vector<T>>;

template <typename G>
struct StronglyConnectedComponents {
    const G &g;
    UnWeightedGraph gg, rg;
    vector<int> comp, order, used;

    StronglyConnectedComponents(G &g)
        : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {
        for (int i = 0; i < g.size(); i++) {
            for (auto e : g[i]) {
                gg[i].emplace_back((int)e);
                rg[(int)e].emplace_back(i);
            }
        }
    }

    int operator[](int k) { return comp[k]; }

    void dfs(int idx) {
        if (used[idx]) return;
        used[idx] = true;
        for (int to : gg[idx]) dfs(to);
        order.push_back(idx);
    }

    void rdfs(int idx, int cnt) {
        if (comp[idx] != -1) return;
        comp[idx] = cnt;
        for (int to : rg[idx]) rdfs(to, cnt);
    }

    void build(UnWeightedGraph &t) {
        for (int i = 0; i < gg.size(); i++) dfs(i);
        reverse(begin(order), end(order));
        int ptr = 0;
        for (int i : order)
            if (comp[i] == -1) rdfs(i, ptr), ptr++;
        t.resize(ptr);
        for (int i = 0; i < g.size(); i++) {
            for (auto &to : g[i]) {
                int x = comp[i], y = comp[to];
                if (x == y) continue;
                t[x].push_back(y);
            }
        }
    }
};

int main() {
    int V, E;
    cin >> V >> E;
    UnWeightedGraph G(V), buf;
    for (int i = 0; i < E; i++) {
        int s, t;
        cin >> s >> t;
        G[s].emplace_back(t);
    }
    StronglyConnectedComponents<UnWeightedGraph> scc(G);
    scc.build(buf);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int u, v;
        cin >> u >> v;
        cout << (scc[u] == scc[v]) << endl;
    }
}


Measured memory_bytes: 5108
#include<stdio.h>
#include<string.h>
int main(void){
	char s[1001];
	int i=0,j=0;
	int x[4]={0,0,0,0};
	scanf("%s",s);
	i=strlen(s);

	for (j= 0; j< i; ++j)
	{
		if (s[j]=='N')
		{
			x[0]=1;
		}else if (s[j]=='S')
		{
			x[1]=1;

		}else if (s[j]=='E')
		{
			x[2]=1;
		}else if (s[j]=='W')
		{
			x[3]=1;
		}

	
	}
	if (x[0]==x[1]&&x[2]==x[3])
	{
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, Q;
string s;
int dp[101010];
void solve(){
	cin >> n >> Q;
	cin >> s;
	
	for(int i = 0; i < n; i++){
		dp[i+1] = dp[i];
		if(s[i] == 'A' && s[i+1] == 'C') dp[i+1]++;
	}
	
	for(int i = 0; i < Q; i++){
		int a,b;
		cin >> a >> b;
		cout << dp[b-1]-dp[a-1] << endl;
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


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

int main(){
  int N,A;
  string S;
  cin >> N;
  A = 0;
  for(int i = 0; i < N; i++){
    cin >> S;
    if(S == "Y"){
      A = 1;
      break;
    }
  }
  if(A == 0){
    cout << "Three" << endl;
  }
  else{
    cout << "Four" << endl;
  }
}

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

int main() {

  int n;
  cin >> n;

  int taro = 0;
  int hanako = 0;

  for (int i = 0; i < n; i++) { 
    string s1, s2;
    cin >> s1 >> s2;
    if (s1 == s2) {
      taro++;
      hanako++;
    } else if (s1 < s2) {
      hanako += 3;
    } else {
      taro += 3;
    }
  }

  cout << taro << " " << hanako << endl;

  return 0;

}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
typedef int lli;
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define eb emplace_back
/*unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);
*/
int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    lli i,j,k,n;
    cin>>n;
    float ar[n];
    for(i=0;i<n;i++)
        cin>>ar[i];
    sort(ar,ar+n);
    float x=ar[0]+ar[1];x/=2;
    for(i=2;i<n;i++)
    {
        x=(x+ar[i])/2;
    }
    cout<<fixed<<setprecision(5)<<x;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{ char s[101][101];
    int i,m,n;
    scanf("%d%d",&m,&n);
    {getchar();for(i=0;i<m;i++)
        {
        gets(s[i]);

        }
      for(i=0;i<m;i++)
      {printf("%s\n",s[i]);
       printf("%s\n",s[i]);
      }
    }
    return 0;
}


Measured memory_bytes: 1720
n = int(input())
l = list(map(int,input().split()))
res = []
s = sum(l)
ts = 0
for i,t in enumerate(l):
    if i %2==1:
        ts+=t
    # print(s,ts)
res.append(s - 2*ts)
for i in range(n-1):
    t = 2*l[i] - res[-1]
    res.append(t)
print(*res)


Measured memory_bytes: 70116
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define ll          long long
#define pii         pair<int, int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int, int>
#define mii         map<pii, int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rev(i,a,b)  for(int i=a;i>=b;i--)
#define lb          lower_bound
#define ub          upper_bound

#define bg(i)       i.begin()
#define fset(it,s)   for(auto it = s.begin(); it != s.end(); it++)
 
#define track(x)                 cerr<<#x<<": "<<x<<endl
#define track2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define track3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define track4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
 
#define ed(i)       i.end()
#define mem(a)	    memset(a, 0, sizeof(a))

#define MOD         1000000007
int mult(int a,int b, int p=MOD){return ((a%p)*(b%p))%p;}
int add(int a, int b, int p=MOD){return (a + b + p)%p;}
int fpow(int n, int k, int p = MOD) {int r = 1; for (; k; k >>= 1LL) {if (k & 1LL) r = mult(r,n,p); n = mult(n,n,p);} return r;}
int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
void self_max(int &a, int b) {a = max(a, b); }
void self_min(int &a, int b) {a = min(a, b); }
void self_add(int &a, int b, int p = MOD) { a += b; if(a >= p) a -= p;}
void self_sub(int &a, int b, int p = MOD) { a -= b; if(a < 0) a += p;}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
const int INF = 1e9 + 5;
#define N	    	4000

void solve() {
    string s;
    cin>>s;
    int d;
    cin>>d;
    int len = sz(s);
    vector<vector<int>>dp(d, vector<int>(2));
    dp[0][0] = 1;
    rep(curr, 0, len) {
        vector<vector<int>>new_dp(d, vector<int>(2));
        rep(sum, 0, d) {
            for(int eq : {0, 1}) {
                rep(digit, 0, 10) {
                    if(!eq && digit > s[curr]-'0')
                        break;
                    self_add(new_dp[(sum+digit)%d][eq || (digit < (s[curr]-'0'))], dp[sum][eq]);
                }
            }
        }
        dp = new_dp;
    }
    int ans = add(dp[0][0], dp[0][1]);
    ans--;
    if(ans < 0)
        ans += MOD;
    cout<<ans<<endl;
}
int main() {
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	cin.tie(0);  //for interactive problem comment this
	cout.tie(0);    // and this
	int t = 1;
//	cin>>t;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define fastt ios_base::sync_with_stdio(false);cin.tie(NULL);
#define enl "\n"
#define ll long long
#define pb push_back
#define fi first
#define se second
#define vvl vector<vector<ll>> 
#define vl vector<ll> 
#define vpll vector<pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define ffor(i,n) for(ll i = 0; i < n; ++i)
#define PI 3.14159265 
ll mod=1e9+7;

 int main(){
     fastt;
     ll i,j,k;
   ll n,m;
   cin>>n;
   vector<int> ar(n+1,0);
   for(i=1;i<n;i++){
       cin>>j;
       ar[j]++;
   }
   for(i=1;i<=n;i++){
       cout<<ar[i]<<enl;
   }
 }


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

int f(int n) {
  int i,j,k,ret=0;
  for (i=1;(i+1)*(i+1)+2<=n;i++) {
    for (j=1;(j+1)*(j+1)+2<=n;j++) {
      for (k=1;(i*i + j*j + k*k + i*j + j*k + k*i)<=n;k++) {
        if ((i*i + j*j + k*k + i*j + j*k + k*i) == n) ret++;
      }
    }
  }
  return ret;
}
int main() {
  int N,i;
  cin>>N;
  for (i=0;i<N;i++) {
    cout<<f(i+1)<<endl;
  }
  return 0;
}


Measured memory_bytes: 3036
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>

using namespace std;

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

ll const INF = 1000000000000000000;
int const I_MAX = 2147483647;
ll const MOD = 1e9 + 7;
int const POW_MAX = 1e5;
int const N_MAX = 200000;

// nCr
ll po[POW_MAX + 2];
ll mod_pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}
ll mod_inv (ll x) {
  return mod_pow(x, MOD - 2) % MOD;
}
ll comb(int n, int r) {
  if (!po[n]) {
    po[0] = 1;
    FOR(i, 1, n + 1) po[i] = po[i - 1] * i % MOD;
  }
  return (((po[n] * mod_inv(po[r])) % MOD) * mod_inv(po[n - r])) % MOD;
}
// greatest common divisor
ll gcd(ll a, ll b) {
  while (a % b != 0) {
    ll tmp = a;
    a = b;
    b = tmp % b;
  }
  return b;
}

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

int N;
int A[N_MAX + 1];

int main() {
  scanf("%d", &N);
  int max_value = 0;
  int second_value = 0;
  vector<int> max_index;
  rep(i, N) {
    int a;
    scanf("%d", &a);
    A[i] = a;
    if (a > max_value) {
      second_value = max_value;
      max_value = a;
      max_index.clear();
      max_index.push_back(i);
    } else if (a == max_value) {
      max_index.clear();
    } else {
      if (a > second_value) second_value = a;
    }
  }

  rep(i, N) {
    bool max_flg = false;
    for (int x : max_index) {
      if (i == x) {
        max_flg = true;
        break;
      }
    }

    if (max_flg) {
      printf("%d\n", second_value);
    } else {
      printf("%d\n", max_value);
    }
  }
}


Measured memory_bytes: 2432