akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y ;
  int num,a;
  int b[100]={0};
  for(int i=0 ; i<x ; i++ ){
    num=0;
    for(int j=0 ; j<y ; j++ ){
      cin >> a;
      num+=a;
      cout << a <<" ";
      b[j]+=a;
     }
     b[y]+=num;
     cout<<num<<endl;
  }
  for(int i=0 ; i<y+1 ; i++ ){
    if( i!=y )
      cout << b[i] <<" ";
    else
      cout<<b[i] << endl;
  }
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))

#define y0 y12345
#define y1 y54321
typedef unsigned long ul;
typedef long long ll;
//typedef pair<int, int> mpair;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
using namespace std;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
   	int n,m;
	string s;cin>>s;
	int a = (s[0]-48)*10+(s[1]-48);
	int b = (s[2]-48)*10+(s[3]-48);
	//cout << a << endl;
	//cout << b << endl;
	if(1<=a&&a<=12){
		if(1<=b&&b<=12){
			cout << "AMBIGUOUS" <<  endl;
		}else{
			cout << "MMYY" <<endl;
		}
	}else{
		if(1<=b&&b<=12){
			cout << "YYMM"<< endl;
		}else{
			cout << "NA" <<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i < 10; i++)
		for(int j = 1; j < 10; j++)
			if(i*j == n)
			{
				cout << "Yes" << endl;
				return 0;
			}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

typedef tuple< ul, ul, ul > edge;
typedef tuple< ul, ul > state;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  ul n, m, s, t;
  cin >> n >> m >> s >> t;
  s--; t--;
  vector< vector< edge > > path(n);
  for (ul i=0; i<m; ++i) {
    ul u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    path[u].push_back(make_tuple(v, a, b));
    path[v].push_back(make_tuple(u, a, b));
  }
  vector< ul > yen(n), snuke(n);
  vector< bool > v_y(n, false), v_s(n, false);
  priority_queue< state, vector< state >, greater< state > > q;
  q.push(make_tuple(0, s));
  while (!q.empty()) {
    auto tp = q.top();
    q.pop();
    ul idx = get<1>(tp), cost = get<0>(tp);
    if (v_y[idx]) continue;
    yen[idx] = cost;
    v_y[idx] = true;
    for (auto c : path[idx]) {
      q.push(make_tuple(cost + get<1>(c), get<0>(c)));
    }
  }
  priority_queue< state, vector< state >, greater< state > > q2;
  q2.push(make_tuple(0, t));
  while (!q2.empty()) {
    auto tp = q2.top();
    q2.pop();
    ul idx = get<1>(tp), cost = get<0>(tp);
    if (v_s[idx]) continue;
    snuke[idx] = cost;
    v_s[idx] = true;
    for (auto c : path[idx]) {
      q2.push(make_tuple(cost + get<2>(c), get<0>(c)));
    }
  }
  vector< ul > ans(n);
  ans[n-1] = yen[n-1] + snuke[n-1];
  for (ul i=n-1; i!=0; --i) {
    ans[i-1] = min(ans[i], yen[i-1]+snuke[i-1]);
  }
  ul initial = 1000000000000000;
  for (ul i=0; i<n; ++i) {
    cout << initial - ans[i] << endl;
  }
  return 0;
}


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

N = int(input())
dic = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
for i in range(N):
    dic[input().rstrip('\n')] += 1
for k, v in dic.items():
    print(k, 'x', v)


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

class SegTreeLazy {
    using T = long long int;
    static const T op(const T& lhs, const T& rhs) { // binary operator***
        return lhs + rhs;
    }
    constexpr static T unit = 0; // unit***
    const int N;
    T *data, *delay;
    int calc_size(int n) { int ret = 1; while (n > ret) ret *= 2; return ret; }
    void force(int i, int l, int r) {
        if (delay[i]) {
            data[i] += delay[i] * (r - l); // force***
            if (r - l > 1) {
                delay[2*i+1] += delay[i];
                delay[2*i+2] += delay[i];
            }
            delay[i] = 0;
        }
    }
public:
    explicit SegTreeLazy(int n) : N(calc_size(n)) {   // [0, n-1]
        data = new T[2*N-1]();
        delay = new T[2*N-1]();
    }
    ~SegTreeLazy() { delete[] data; delete[] delay; }
    T query(int a, int b, int i = -1, int l = -1, int r = -1) {
        if (i == -1) { i = 0; l = 0; r = N; }
        if (r <= a || b <= l) return unit;
        force(i, l, r);
        if (a <= l && r <= b) return data[i];
        const int m = (l+r)/2;
        if (r - l == 1) return data[i];
        if (b <= m) return query(a, b, 2*i+1, l, m);
        if (m <= a) return query(a, b, 2*i+2, m, r);
        T v1 = query(a, b, 2*i+1, l, m),
            v2 = query(a, b, 2*i+2, m, r);
        return op(v1, v2);
    }
    void add(int a, int b, T v, int i = -1, int l = -1, int r = -1) {
        if (i == -1) { i = 0; l = 0; r = N; }
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) { delay[i] += v; force(i, l, r); return; }
        add(a, b, v, 2*i+1, l, (l+r)/2); force(2*i+1, l, (l+r)/2);
        add(a, b, v, 2*i+2, (l+r)/2, r); force(2*i+2, (l+r)/2, r);
        data[i] = op(data[2*i+1], data[2*i+2]);
    }
    T get(int i) { return query(i, i+1); }
    void init(int *a, int n) {
        for (int i = 0; i < n; i++) data[i+N-1] = a[i];
        for (int i = N-2; i >= 0; i--) data[i] = op(data[2*i+1], data[2*i+2]);
    }
    // void update(int i, T v) {
    //     int ov = get(i);
    //     add(i, i+1, v-ov); // BEWARE: assumes add is `+'
    // }
};

int main() {
    int n, q; cin >> n >> q;
    int c[n]; for (int i = 0; i < n; i++) cin >> c[i], c[i]--;
    vector<pair<int, int> > query[n];
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        l--; r--;
        query[r].push_back({l, i});
    }
    int ans[q], pos[n];
    fill(pos, pos+n, 0);
    SegTreeLazy st(n+1);
    for (int i = 0; i < n; i++) {
        st.add(pos[c[i]], i+1, 1);
        pos[c[i]] = i+1;
        for (auto [l, idx] : query[i]) {
            int a = st.get(l);
            ans[idx] = a;
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << endl;
}


Measured memory_bytes: 47724
import Control.Applicative
import Text.Printf

main :: IO ()
main = do
  xs <- (map read . words) <$> getLine
  if xs !! 0 == 0 && xs !! 1 == 0 then return ()
    else do {
    putStrLn $ take (xs !! 1) (repeat '#');
    putStr $ solve xs;
    putStrLn $ take (xs !! 1) (repeat '#');
    putStrLn $ "";
    main;
    }

solve :: [Int] -> String
solve xs
  | h == 2 = ""
  | otherwise = "#" ++ (take (w - 2) (repeat '.')) ++ "#\n" ++ solve ((h - 1) : w : []) 
  where h = xs !! 0
        w = xs !! 1

Measured memory_bytes: 3932
s = input()
n = len(s)
sd = s[::-1]
a = s[:int((n-1)/2)]
ad = a[::-1]
b = s[int((n+3)/2-1):]
bd = b[::-1]
if s == sd and a == ad and b == bd:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 61884
/*  -*- coding: utf-8 -*-
 *
 * 1590.cc: One-Time Path
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int INF = 1 << 30;

/* typedef */

typedef pair<int,int> pii;
typedef vector<pii> vpii;

/* global variables */

vpii nbrs[MAX_N];
int ds[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--, b--;
    //nbrs[a].push_back(pii(b, c));
    nbrs[b].push_back(pii(a, c));
  }

  int st = 0, gl = n - 1;
  int maxd = -1;
  vpii &nbrgl = nbrs[gl];

  for (vpii::iterator git = nbrgl.begin(); git != nbrgl.end(); git++) {
    int &gv = git->first, &gd = git->second;
    fill(ds, ds + n, -1);
    ds[gl] = ds[gv] = gd;

    priority_queue<pii> q;
    q.push(pii(gd, gv));

    while (! q.empty()) {
      pii u = q.top(); q.pop();
      int &ud = u.first, &ui = u.second;
      if (ud != ds[ui]) continue;
      if (ui == st) break;

      vpii &nbru = nbrs[ui];

      for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	int &vi = vit->first, &vd = vit->second;
	if (vd <= ud && ds[vi] < vd) {
	  ds[vi] = vd;
	  q.push(pii(vd, vi));
	}
      }
    }

    if (ds[st] >= 0 && maxd < gd) maxd = gd;
  }

  printf("%d\n", maxd);
  return 0;
}



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

using namespace std;

int main(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	if( a+b > c+d){
		cout << "Left" << endl;
	}
	else if( a+b == c+d){
		cout << "Balanced" << endl;
	}
	else{
		cout << "Right" << endl;
	}


	return 0;
}



Measured memory_bytes: 256
s=input()

if s=="hi" :
    print("Yes")
elif s=="hihi" :
    print("Yes")
elif s=="hihihi" :
    print("Yes")
elif s=="hihihihi" :
    print("Yes")
elif s=="hihihihihi" :
    print("Yes")
else :
    print("No")

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
using namespace std;
const int N=505;
int n,cnt[N],len;
int main(){
	scanf("%d",&n);int x;rep(i,1,n)scanf("%d",&x),cnt[x]++;
	
	rep(i,1,n)if(cnt[i])len=i;
	int mi=(len+1)>>1;
	rep(i,mi,len)cnt[i]-=2;
	if(!(len&1))cnt[mi]++;
	rep(i,1,n){
		if(cnt[i]<0 || (cnt[i] > 0 && i<=mi)){
			puts("Impossible");
			return 0;
		}
	}
	puts("Possible");
	return 0;
}

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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}



int main(void) {
    int n;
    scanf("%d\n",&n);
    int i;
    int seq[n];
    for(i=0;i<n;i++)
        scanf("%d",&seq[i]);
    qsort(seq, n, sizeof(int), compare_int);
    int sum = seq[n/2] - seq[n/2-1];

    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 892
n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)



Measured memory_bytes: 9428
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define BR cout<<endl;
#define LEN(s) s.length();
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; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const ll mod=1000000007;

int main(){
    int n;
    cin >> n;

    int d1[n], d2[n];
    rep(i,n){
        cin >> d1[i] >> d2[i];
    }

    int count = 0;

    for(int i = 0; i < n; i++){
        if(d1[i] == d2[i]){
            count++;
        }
        else {
            count = 0;
        }

        if(count == 3){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int gcd(int a, int b){
  int big,small;
  if(a>b){
    big=a;
    small=b;
  }else if(a<b){
    big=b;
    small=a;
  }else{
    return a;
  }

  int rest=1;
  while(1){
    rest=big%small;
    if(rest==0) break;
    big=small;
    small=rest;
  }

  return small;
}

int main(){
  int N,K;
  cin >> N >> K;
  int a[N];
  for(int i=0;i<N;i++) cin >> a[i];
  sort(a,a+N);
  int mx = a[N-1];
  int gc = a[0];
  for(int i=1;i<N;i++){
    gc = gcd(gc,a[i]);
  }

  if(mx - K>=0 && (mx - K)%gc == 0){
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define NIL -1
typedef long long ll;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll MOD = 1000000007;



void solve() {

    ll n, k, broken, result;
    ll a[200010];
    cin >> n;
    rep(i, n) cin >> a[i];
    k = 1;
    broken = 0;
    rep(i, n) {
        if(a[i] == k) {
            ++k;
        } else {
            ++ broken;
        }
    }
    if(broken == n) {
        result = -1;
    } else {
        result = broken;
    }

    cout << result << endl;
    return;
}

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

}

Measured memory_bytes: 1792
from bisect import*
class SquareSkipList:
    def __init__(self,values=[],square=1000,seed=42):
        INF=10**18
        self.square=square
        self.layer1=layer1=[]
        self.layer0=layer0=[]
        y=seed
        l0=[]
        for v in values:
            y^=(y&0x7ffff)<<13
            y^=y>>17
            y^=(y&0x7ffffff)<<5
            if y%square<1:
                layer0+=l0,
                l0=[]
                layer1+=v,
            else:l0+=v,
        layer1+=INF,
        layer0+=l0,
        self.rand_y=y
    def add(self,x):
        y=self.rand_y
        y^=(y&0x7ffff)<<13
        y^=y>>17
        y^=(y&0x7ffffff)<<5
        self.rand_y=y
        if y%self.square<1:
            layer1,layer0=self.layer1,self.layer0
            idx1=bisect(layer1,x)
            layer1.insert(idx1,x)
            layer0_idx1=layer0[idx1]
            idx0=bisect(layer0_idx1,x)
            layer0.insert(idx1+1,layer0_idx1[idx0:])
            del layer0_idx1[idx0:]
        else:
            idx1=bisect(self.layer1,x)
            insort(self.layer0[idx1],x)
    def remove(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        if idx0==len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1]+=layer0.pop(idx1+1)
        else:del layer0_idx1[idx0]
    def search_higher(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect(layer0_idx1,x)
        return layer1[idx1]if idx0==len(layer0_idx1)else layer0_idx1[idx0]
    def search_lower(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        return layer1[idx1-1]if idx0<1else layer0_idx1[idx0-1]
    def pop(self,idx):
        layer1,layer0=self.layer1,self.layer0
        s=-1
        for i,l0 in enumerate(layer0):
            s+=len(l0)+1
            if s>=idx:break
        if s==idx:
            layer0[i]+=layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:return layer0[i].pop(idx-s)
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=SquareSkipList([])
    t.add(0)
    t.add(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.add(v)
    print(c)
main()

Measured memory_bytes: 25872
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

signed main(){
    ll n;
    cin >> n;
    ll a[n] = {};
    map<ll,ll> m;
    priority_queue<ll> pq;

    rep(i,0,n){
        cin >> a[i];
        if(m.count(a[i]) == 0){
            m[a[i]] = 1;
        }
        else{
            m[a[i]]++;
        }

        if(m[a[i]] == 2){
            pq.push(a[i]);
        }
    }


    if(pq.size() < 2) cout << 0 << endl;
    else{
        ll a = pq.top();
        pq.pop();
        if(m[a] >= 4){
            cout << a*a << endl;
        }
        else{
            cout << a*pq.top() << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 10628
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

ll C[2005][2005];
ll dp[100005][13];


int main(){
    ll N,M,s=0,ans=0;
    cin >> N >> M;
    vector<int> A(N+10);
    for(int i=0; i<N; i++){
        cin >> A[i];
        s += A[i];
    }
     for(int i=0; i<N; i++){
        if(A[i] >= s/(4.0*M)) ans++;
    }
    if(ans >= M){
        cout << "Yes" << endl; 
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools as it
N=one_int()
ds=many_int()

temp = list(it.combinations(ds,2))
sums=0
for i in temp:
    sums+=(i[0]*i[1])

print(sums)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;


int main(){
    ll n;cin>>n;
    ll x[200020];
    map<ll,ll> xp,xm;
    rep(i,0,n){
        cin>>x[i];
        xp[x[i]+i]++;
        xm[i-x[i]]++;
    }
    ll an=0;
    for(auto p:xp){
        an+=xp[p.first]*xm[p.first];
    }
    cout<<an<<endl;
}
    









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

int main() {
  int N,M;
  cin >> N >> M;
  vector<int>count(N+1);
  
  for(int i=0; i<M; i++){
    int a,b;
    cin >> a >> b;
    count[a]++;
    count[b]++;
  }
   
  for(int i=1; i<=N; i++){
   	cout << count[i] <<endl;
  }
}

Measured memory_bytes: 256
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if A != B and V <= W:
    print("NO")
else:
    dist = abs(A - B)
    v = V - W
    t = dist / v
    if t <= T:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 9188
N=int(input())
ans=[2]
i=7
flag=0
while(len(ans)<N):
  for j in range(2,int(i**0.5)+1):
    if i%j==0:
      flag=1
      break;
  if flag!=1:
    ans.append(i)
  i+=5
  flag=0
  
for i in range(len(ans)):
  print(ans[i],end=" ")

Measured memory_bytes: 3060
#define DBG 0 //submit 0
#if DBG
    #include <algorithm>
    #include<array>
    #include <ctime>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <iostream>
    #include <cmath>
    #include <numeric>
#else
    #include <bits/stdc++.h>
#endif

using namespace std;


int main(){
    int a,b,x,i,j,k,tmp = 0,tmpi = 0;
    double deg,l,ans;

    cin >> a >> b >> x;
	
    if(x > a*a*b / 2){
        ans = atan2((2.0*((double)b-(double)x/((double)a*(double)a))),(double)a);
    }else{
        ans = atan2((double)b,(2.0*(double)x/((double)a*b)));
    }

    ans = 180.0/M_PI*ans;

    //cout << ans << endl;
    printf("%.10f",ans);

}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define MOD 1000000007

int wa[100000] = {};

int main(){
	int N,Q;
	cin >> N >> Q;
	string S;
	cin >> S;
	
	for(int i=1; i<N; i++){
		wa[i] = wa[i-1];
		if(S[i-1] == 'A' && S[i] == 'C') wa[i]++;
	}

	for(int i=0; i<Q; i++){
		int l,r;
		cin >> l >> r;
		int ans = wa[r-1] - wa[l-1];
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 1408
// inputに入力データ全体が入る
function Main(input) {
// 1行目がinput[0], 2行目がinput[1], …に入る
　input = input.split("\n");
  k = ~~input[0]
　a = ~~input[1].split(" ")[0];
  b = ~~input[1].split(" ")[1];
  let i=k;
  while (i <= b){
    if(i >= a && i <= b ){
      console.log("OK");
      return;
    }
    i += k;
  }
  console.log("NG")
  return;
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29628
import itertools

n, m = map(int, input().split())
path = [[False] * n for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0
for i in itertools.permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n-1:
                ans += 1
                break

            if not path[i[j]][i[j+1]]:
                break
print(ans)

Measured memory_bytes: 3064
use proconio::input;

fn main() {
    input! {
        s : String,
    }
    let s: Vec<char> = s.chars().collect();
    let mut cnt = 0;
    for c in s {
        cnt += c as i32 - 48;
    }
    if cnt % 9 == 0 {
        println!("Yes");
    } else {
        println!("No");
    }
}


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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int n,m;
  cin >> n >> m;

  vector< vector<int> > job(100010);
  int a,b;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    job[a].push_back(b);
  }
  
  int totalPayment = 0;
  priority_queue<int> pays;
  for(int i=1;i<=m;i++){
    for(auto p:job[i]){
      pays.push(p);
    }
    if(pays.size()>0){
      totalPayment += pays.top(); pays.pop();
    }
  }
  cout << totalPayment << endl;
  return 0;
}



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

int main(){
    int a, b, temp;
    cin >> a >> b;
    if (a < b){
        temp = a;
        a = b;
        b = temp;
    }

    while(1){
        if(a % b == 0){
            break;
        }else{
            temp = b;
            b = a % b;
            a = temp;
        }
    }    
    cout << b << endl;
    return 0;
}



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



int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#ifndef ONLINE_JUDGE
  freopen("in", "r", stdin);
  freopen("out", "w", stdout);
#endif

  int n;
  cin >> n;
  long long d;
  cin >> d;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    long long x, y;
    cin >> x >> y;
    if (x * x + y * y <= d * d) ++ans;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 3648
#!/usr/bin/env python3
import sys


def solve(a: int, b: int):
    print(a if a <= b else a - 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(a, b)


if __name__ == '__main__':
    main()


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

int main() {
  int n, counter = 0;
  cin >> n;
  vector<int> vec(n);
  for(int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }

  bool stop = false;
  while(true){
    for(int j = 0; j < n; j++) {
      if(vec.at(j) % 2 == 0) {
        vec.at(j) /= 2;
      } else {
        stop = true;
        break;
      }
    }
    if(stop) break;
    counter++;
  }

  cout << counter << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<cstdlib>
#include<stack>
#include<ctime>
#include<map>
#include<list>
using namespace std;

const int x=26;

long long n;
long long a,m=0,s[105];

int main()
{
	char s[15];
	int cnt=0;
	long long n;
	scanf("%lld",&n);
	while(n>0)
	{
		n--;
		s[cnt++]=n%26+'a';
		n/=26;
	}
	for(int i=cnt-1; i>=0; i--) putchar(s[i]);
	puts("");
	return 0;
}

Measured memory_bytes: 3728
import copy

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
BB = copy.deepcopy(B)

ans = 0

for i in range(N):
  if A[i] >= B[i]:
    ans += B[i]
    A[i] -= B[i]
  else:
    ans += A[i]
    B[i] -= A[i]
    if B[i] >= A[i+1]:
      ans += A[i+1]
      A[i+1] = 0
    else:
      ans += B[i]
      A[i+1] -= B[i]

print(ans)

Measured memory_bytes: 18904
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
	int n,d;
	cin>>n>>d;
	int f = 1 + 2*d;
	int x = n%f;
	int y = n/f;
	if(x == 0) cout<<y;
	else cout<<y+1;
	return 0;
	
 } 

Measured memory_bytes: 256
fun main(args: Array<String>) {
  val N = readInt()
  val S = readString()

  val len1Set = mutableSetOf<Int>()
  val len2Set = mutableSetOf<Int>()
  val len3Set = mutableSetOf<Int>()

  S.forEach { c ->
    val n = c.toInt()
    len2Set.forEach {
      len3Set.add(it * 10 + n)
    }
    len1Set.forEach {
      len2Set.add(it * 10 + n)
    }
    len1Set.add(n)
  }
  println(len3Set.size)
}

fun readString() = readLine()!!
fun readStrings() = readString().split(' ')
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }



Measured memory_bytes: 54656
#include<stdio.h>
#define NINE 9

int main(void)
{
	int i,j;
	for(i=1;i<=NINE;i++){
		for(j=1;j<=NINE;j++){
			printf("%dx%d=%d\n",i,j,i*j);
		}
	}
	return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
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;
}
const int INF = 2e9;
const int MOD = 1e9 + 7;

int main() {
   string s, t;
   cin >> s >> t;
   sort(s.begin(), s.end());
   sort(t.begin(), t.end());
   reverse(t.begin(), t.end());
   if (s < t)
      cout << "Yes" << endl;
   else
      cout << "No" << endl;
   return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O4")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(998244353)
#define INF (1e15)
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

bool check(int n,int a,int b,vector<int> &v){
	int now=0;
	for(auto &i:v){
		int r=max(0ll,i-b*n);
		now+=(r+a-1)/a;
	}
	if(now<=n) return true;
	return false;
}

int32_t main() {
#ifdef LOCAL_TEST
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\input.in","r",stdin);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\output.out","w",stdout);
	freopen("E:\\Jimmy\\2 Coding\\1 C++\\error.out","w",stderr);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);

	//code...
	int n,m; cin>>n>>m;
	vector<string> a(n),b(m);
	for(auto &i:a)
		cin>>i;
	for(auto &i:b)
		cin>>i;
	For(i,0,n-m){
		For(j,0,n-m){
			bool ac=true;
			For(x,0,m-1) For(y,0,m-1){
				if(a[i+x][j+y]!=b[x][y]){
					ac=false;
					goto END;
				}
			}
		END:
			if(ac){
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
	return 0;
}

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


typedef long long ll;
int main(){
   // freopen("in.txt","r", stdin);
    int n;
    cin>>n;
    vector<ll> a(n+1,0);
    for(int i = 1; i<=n; i++){
        cin>>a[i];
    }
    vector<ll> dp(n+1, 0);
    dp[1]=0;
    vector<ll> prefix(n+1);
    prefix[1]=a[1];
    for(int i = 3; i<= n; i+=2){
        prefix[i]=prefix[i-2]+a[i];
    }
    for(int i = 2; i<= n; i++){
        if(i&1){
            dp[i]=max(dp[i-1],dp[i-2]+a[i]);
        }else {
            dp[i]=a[i]+dp[i-2];
            dp[i]=max(dp[i], prefix[i-1]);
        }
    }
    cout<<dp[n]<<endl;


    return 0;
}

Measured memory_bytes: 7480
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String... args) {
        List<Apple> apples = new ArrayList();
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

        String[] input = null;
        // 標準入力読み込み
        try {
            input = br.readLine().split(" ");
            br.close();
        } catch (IOException e){
            e.printStackTrace();
        }
        int n = Integer.parseInt(input[0]);
        int l = Integer.parseInt(input[1]);

        // applesリストの作成
        for(int i = 0; i < n; i++){
            apples.add(new Apple(l + i));
        }

        // tasteの絶対値を基準に、applesを昇順でソート
        apples.sort((a1, a2) -> {
            int t1 = a1.taste;
            int t2 = a2.taste;
            int t1Abs = t1 >= 0 ? t1 : t1 * -1;
            int t2Abs = t2 >= 0 ? t2 : t2 * -1;
            if(t1Abs < t2Abs){
                return -1;
            } else if(t1Abs > t2Abs){
                return 1;
            } else {
                if(t1 < 0) return -1;
                else if(t2 < 0) return 1;
                else return 0;
            }
        });

        // 合計値の計算
        Integer totalTaste = 0;
        apples.remove(0);
        for (Apple a : apples) {
            totalTaste += a.taste;
        }
        System.out.println(totalTaste);
    }
}

class Apple {
    int taste;
    Apple(String taste){
        this.taste = Integer.parseInt(taste);
    }
    Apple(int taste){
        this.taste = taste;
    }
    @Override
    public String toString() {
        return ((Integer)this.taste).toString();
    }
}

Measured memory_bytes: 26452
a,b,c,d = gets.chomp.split(' ').map(&:to_i)
h = {}
h[a] = true
h[b] = true
h[c] = true
h[d] = true
if h[1] && h[9] && h[7] && h[4]
  puts 'YES'
else
  puts 'NO'
end

Measured memory_bytes: 14304
#include <iostream>
#include <vector>
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;
static const ll MAX_V = 100000;

//Graph
struct E {
	int to;
	int from;
	int cost;
	//bool visited;
	bool use;
};

vector<E> G[MAX_V];
bool v[MAX_V];

ll VS, ES;
//dfs
ll ans = 0;
void dfs(int n) {
	rep(i, 0, G[n].size()) {
		if (G[n][i].use && !v[G[n][i].to]) {
			v[G[n][i].to] = true;
			dfs(G[n][i].to);
		}
	}
}

void output() {
	repe(i, 1, VS) {
		cout << v[i] << endl;
	}
}

int main() {
	cin >> VS >> ES;

	rep(i, 0, ES)
	{
		ll s, t; cin >> s >> t;
		E* e1 = new E();
		e1->to = t;
		e1->from = s;
		G[s].push_back(*e1);

		E* e2 = new E();
		e2->to = s;
		e2->from = t;
		G[t].push_back(*e2);
	}

	///////////////////////////////////////////////////////////

	//Edge all false
	repe(i, 1, VS) rep(j, 0, G[i].size()) {
		//Edge all visited false;
		repe(k, 1, VS) rep(l, 0, G[k].size()) G[k][l].use = true;
		repe(k, 1, VS) v[k] = false;

		G[i][j].use = false;

		//DFS
		v[1] = true;
		//if (i == 4) {
		//	cout << endl;
		//}
		dfs(1);

		//output();
		bool ok = true;
		repe(k, 1, VS)  ok &= v[k];
		if (!ok)ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;
 
public class Main {
public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);  
         
         int a = scan.nextInt();
         int b = scan.nextInt();
         int m = a * b;
         int s = 2 * a + 2 * b; 
       
          System.out.println(m + " " + s);
      }
 }

Measured memory_bytes: 25936
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
#include <stack>
#include <iomanip>
#include <map>
#include <math.h>
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const ll INF = 1LL << 60;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }


int main()
{
	int N;
	cin >> N;
	vector<int>  A(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	sort(A.begin(),A.end());
	int count = 1;
	int ans = 0;
	int num = A[0];
	for(int i = 1; i < N; i++)
	{
		if(num != A[i] && count %2 != 0) ans++,num = A[i],count = 1;
		else if(num != A[i] && count%2 == 0) num = A[i],count = 1;
		else if (num == A[i]) count++;
	}
	if(count % 2 != 0) ans++;
	cout << ans << endl;
}
      

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n; cin >> n;
  vector<vector<int>> g(n);
  for(int i = 0; i < n; i++){
    int u, k;
    cin >> u >> k;
    u--;
    for(int j = 0; j < k; j++){
      int v; cin >> v; v--;
      g[u].push_back(v);
    }
  }
  vector<int> dist(n, -1);
  queue<int> q;
  q.push(0);
  dist[0] = 0;
  while(!q.empty()){
    int now = q.front();
    q.pop();
    for(int nx: g[now]){
      if(dist[nx] == -1){
        dist[nx] = dist[now] + 1;
        q.push(nx);
      }
    }
  }
  for(int i = 0; i < n; i++) cout << i+1 << ' ' << dist[i] << endl;
  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}



Measured memory_bytes: 3156
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << "Hello World" << endl;
	}
	else {
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}
	return 0;
}

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

using namespace std;

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

	bool h = true;
	for (int i = 0; i+1 < s.size(); i++) {
		if (s[i] == s[i + 1]) {
			cout << i+1 << ' ' << i + 2 << endl;
			h = false;
			break;
		}
	}

	if (h) {
		for (int i = 0; i + 2 < s.size(); i++) {
			if (s[i] == s[i + 2]) {
				cout << i+1 << ' ' << i + 3 << endl;
				h = false;
				break;
			}
		}
		if (h) {
			cout << -1 << ' ' << -1 << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 512
/* Includes */
#include <stdio.h>

/* Prototypes */

/* Valuables */
int n, m, l;
int matrix_a[101][101];
int matrix_b[101][101];
long long matrix_c[101][101];

/* Main */

int main ()
{
    scanf("%d %d %d", &n, &m, &l);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix_a[i][j]);
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < l; j++) {
            scanf("%d", &matrix_b[i][j]);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < l; k++) {
                matrix_c[i][k] += matrix_a[i][j] * matrix_b[j][k];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) {
            printf("%lld", matrix_c[i][j]);

            if (j == (l - 1)) {
                printf("\n");
            }
            else {
                printf(" ");
            }
        }
    }
}


Measured memory_bytes: 2120
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
typedef long long ll;
const int N=1e5+5;
int n,ma,mb,la[N],lb[N];ll A,B,a[N];
struct bit{
	int c[N];
	inline void chg(R int x,R int y){for(++x;x<=n+1;x+=x&-x)upd(c[x],y);}
	inline int qwq(R int x){R int res=0;for(++x;x;x-=x&-x)upd(res,c[x]);return res;}
	inline int query(R int l,R int r){return l>r?0:dec(qwq(r),qwq(l-1));}
}f,g;
int main(){
	scanf("%d%lld%lld",&n,&A,&B);
	fp(i,1,n)scanf("%lld",&a[i]);
	for(R int i=1,ia=0,ib=0;i<=n;++i){
		while(ia<n&&a[ia+1]<=a[i]-A)++ia;
		while(ib<n&&a[ib+1]<=a[i]-B)++ib;
		la[i]=ia,lb[i]=ib;
	}
	ma=mb=0,f.chg(0,1),g.chg(0,1);
	fp(i,2,n){
		R int df=g.query(mb,la[i]),dg=f.query(ma,lb[i]);
		f.chg(i-1,df),g.chg(i-1,dg);
		if(a[i]-a[i-1]<A)ma=i-1;
		if(a[i]-a[i-1]<B)mb=i-1;
	}
	printf("%d\n",add(f.query(ma,n),g.query(mb,n)));
	return 0;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

vector<long long int> prime_factor(long long int n){
    vector<long long int> res;
    for(int i=2; i*i<=n; ++i){
        while(n%i==0){
            res.push_back(i);
            n/=i;
        }
    }
    if(n!=1) res.push_back(n);
    return res;
};

class segtree{
public:
    i64 n,size_;
    vector<vector<pair<int,int>>> segs;
    segtree()=default;
    segtree(i64 size){ init(size); }
    void init(i64 size){
        size_=size;
        n=1;
        while(n<size) n*=2;
        segs.resize(n*2-1);
    }
    void insert(int l_,int r_){ insert(0,n,0,l_,r_); }
    void insert(int a,int b,int index,int l_,int r_){
        if(b<=l_ or r_<=a) return;
        if(l_<=a and b<=r_){
            segs[index].push_back(make_pair(l_,r_));
            return;
        }
        insert(a,(a+b)/2,2*index+1,l_,r_);
        insert((a+b)/2,b,2*index+2,l_,r_);
    }
    int query(int lb,int x){ return query(0,n,0,lb,x); }
    int query(int a,int b,int index,int lb,int x){
        if(/*b<=lb or*/ x<a or b<=x) return 0;
        int res=0;
        if(lb<a and a<=x and x<b) res+=segs[index].end()-upper_bound(segs[index].begin(),segs[index].end(),make_pair(lb,inf));
        if((a+b)/2<b) res+=query(a,(a+b)/2,index*2+1,lb,x);
        if(a<(a+b)/2) res+=query((a+b)/2,b,index*2+2,lb,x);
        return res;
    }
};

void solve(){
    int N,M;
    cin >> N >> M;

    vector<pair<int,int>> LR;
    rep(i,0,N){
        int L,R;
        cin >> L >> R;
        ++R;
        LR.push_back(make_pair(L,R));
    }
    sort(LR.begin(),LR.end());
    segtree seg(M+1);
    rep(i,0,N) seg.insert(LR[i].first,LR[i].second);

    rep(i,1,M+1){
        int ans=0;
        rep(j,1,M/i+1){
            int tmp=seg.query(i*(j-1),i*j);
            ans+=seg.query(i*(j-1),i*j);
        }
        cout << ans << endl;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 79468
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = [int(i) for i in input().split()]

m = lcm(A) - 1
f = 0
for i in range(N):
    f += m % A[i]
print(f)

Measured memory_bytes: 5372
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	double v,y;
	int ans;
	while(cin >> v){
		y = 4.9*pow(v/9.8,2);
		y-=0.00001;
		ans = (y/5);
		cout << ans +2 << endl;
		
	}
	return 0;
}


Measured memory_bytes: 3164
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  string a,s,c;cin>>a>>s>>c;

  cout<<a[0]<<s[0]<<c[0]<<endl;


  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(h1: int, s1: int, h2: int, s2: int) -> bool:
    while h1 > 0 and h2 > 0:
        h1 -= s2
        h2 -= s1
        # LOG.debug(("first:", h1, s1))
        # LOG.debug(("second:", h2, s2))
    return h2 <= 0


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    # N = int(input())
    A, B, C, D = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(A, B, C, D)
    print("Yes" if result else "No")


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)


Measured memory_bytes: 18436
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    int n, k;
    cin >> t;
    for(int count = 0; count < t; count++){
        cin >> n;
        cin >> k;

        int point[n];
        int interval[n-1];
        cin >> point[0];
        for(int i = 1; i < n; i++){
            cin >> point[i];
            interval[i-1] = point[i] - point[i-1];
        }
        if(n <= k){
            cout << 0 << endl;
        } else {
            int total_length = point[n-1]-point[0];
            sort(interval, interval+(n-1));
            reverse(interval, interval+(n-1));
            
            
            for(int i = 0; i < k-1; i++){
                total_length -= interval[i];
            }
            cout << total_length << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1956
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
signed main(){
    int x,y,z;
    cin>>x>>y>>z;
    x-=z;
    y+=z;
    cout<<x/y<<endl;
}

Measured memory_bytes: 256
n = int(input())
query = [tuple(map(int, input().split())) for _ in range(n)]

x, y = 1, 1
for t, a in query:
    if t >= x and a >= y:
        x = t
        y = a
    else:
        if t < x and a < y:
            x = t * max((x + t - 1) // t, (y + a - 1) // a)
            y = a * max((x + t - 1) // t, (y + a - 1) // a)
        elif t < x:
            x = t * ((x + t - 1) // t)
            y = a * ((x + t - 1) // t)
        else:
            x = t * ((y + a - 1) // a)
            y = a * ((y + a - 1) // a)
print(x + y)

Measured memory_bytes: 9096
#include <stdio.h>

int main()
{
  int N,op;
  scanf("%d",&N);
  
  if(N>=1 && N<=1000)
  {op= 1000-N;
   printf("%d\n",op);
  }
  else if(N>1000 && N<=2000)
  {op= 2000-N;
   printf("%d\n",op);
   }
   else if(N>2000 && N<=3000)
  {op= 3000-N;
   printf("%d\n",op);
   }
   else if(N>3000 && N<=4000)
  {op= 4000-N;
   printf("%d\n",op);
   }
   else if(N>4000 && N<=5000)
   {op= 5000-N;
   printf("%d\n",op);
   }
   else if(N>5000 && N<=6000)
   {op= 6000-N;
    printf("%d\n",op);
    }
   else if(N>6000 && N<=7000)
  {op= 7000-N;
   printf("%d\n",op);
   }
   else if(N>7000 && N<=8000)
  {op= 8000-N;
   printf("%d\n",op);
   }
   else if(N>8000 && N<=9000)
  {op= 9000-N;
   printf("%d\n",op);
   }
   else if(N>9000 && N<=10000)
  {op= 10000-N;
   printf("%d\n",op);
   }
     
  return 0;
}

Measured memory_bytes: 1728
let N = Int(readLine()!)!
let S = readLine()!.characters
var cnt = S.reduce(0){$0+($1>"#" ?1:0)}
var ans = cnt
for c in S {
    let tmp = ans
    if c>"#" {
        cnt--
    } else {
        cnt++
    }
    ans = min(cnt, ans)
}
print(ans)

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

int d[10];

int main(){
    int n, k; cin >> n >> k;
    for(int i=0;i<k;i++){
        int di; cin >> di;
        d[di] = 1;
    }

    for(int i=n;;i++){
        int j = i; bool ok = true;
        while(j){
            if(d[j%10]) ok = false;
            j /= 10;
        }

        if(ok){
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256