akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(a, b); }

template<typename T> void remove(std::vector<T>& vector, unsigned int index)
{ vector.erase(vector.begin() + index); }


int main() {
    int N; cin >> N;
    vector<int> B(N);  rep(i, N-1) cin >> B[i];

    int sum = 0;
    rep(i, N-2) {
        sum += min(B[i], B[i+1]);
    }
    sum += B[0] + B[N-2];
    print(sum);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
int main()
{
	int n, k, dis = INT_MAX;
	cin >> n;
	cin >> k;
  	vector<int> h(n);
	k--;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	sort(h.begin(),h.end());
	for (int i = 0; i < n - k; i++) {
		dis = min(dis, abs(h[i] - h[i + k]));
	}
	cout << dis << endl;

	return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        int n; cin>>n;
        vi t(n);
        int sum=0;
        rep(i,n)
        {
                cin>>t[i];
                sum+=t[i];
        }
        int m; cin>>m;
        rep(i,m)
        {
                int p,x; cin>>p>>x;
                cout<<sum-t[p-1]+x<<endl;
        }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; i--)
#define loop(i, r, n) for (int i = (r); i <= (n); i++)
#define pb push_back
#define all(in) in.begin(),in.end()

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

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main(){
    int n; cin >> n;
    vector<ll> ans(n+1,0);
    loop(x,1,400) loop(y,1,400) loop(z,1,400){
        ll d = x*x + y*y + z*z + x*y + y*z + z*x;
        if(d <= n)  ans[d]++;
    }
    loop(i,1,n) cout << ans[i] << endl;
    return 0;
}

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

int main(){
  int N,s;
  cin >> N;
  s=N%10;
  if(s==3){
    printf("bon\n");
  }
  else if(s==0 || s==1 || s==6 || s==8){
    printf("pon\n");
  }
  else  printf("hon\n");

  return 0;
}

Measured memory_bytes: 3596
#include<queue>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;

int S, T;
LL SX, SY, TX, TY;
LL X[1111], Y[1111], R[1111];

const double INF = 1e12;
double dist[1111];

LL sq(LL x) { return x * x; }

double cost(int v, int w) {
    if (sq(X[v] - X[w]) + sq(Y[v] - Y[w]) <= sq(R[v] + R[w])) {
	return 0;
    } else {
	return sqrt(sq(X[v] - X[w]) + sq(Y[v] - Y[w])) - R[v] - R[w];
    }
}

int main() {
    scanf("%lld%lld%lld%lld", &SX, &SY, &TX, &TY);
    scanf("%d", &N);
    REP (i, N) scanf("%lld%lld%lld", X+i, Y+i, R+i);

    S = N++;
    X[S] = SX;
    Y[S] = SY;

    T = N++;
    X[T] = TX;
    Y[T] = TY;

    REP (i, N) dist[i] = INF;
    dist[S] = 0;
    priority_queue<pair<double, int> > Q;
    Q.push(make_pair(0.0, S));
    while (!Q.empty()) {
	pair<double, int> p = Q.top(); Q.pop();
	int v = p.second;
	if (-p.first > dist[v]) continue;
	REP (w, N) {
	    double c = cost(v, w);
	    if (dist[w] > dist[v] + c) {
		dist[w] = dist[v] + c;
		Q.push(make_pair(-dist[w], w));
	    }
	}
    }

    printf("%.99f\n", dist[T]);

    return 0;
}



Measured memory_bytes: 4464
#include<bits/stdc++.h>
#define int			long long
#define ll 			long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define dep(i,a,b)	for(int i=a;i>=b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  200005

ll n,m;
vi a[N];
bool vis[N];

ll dfs(ll node){
	vis[node]=1;
	ll ret=1;
	for(auto i:a[node]){
		if(vis[i])continue;
		ret+=dfs(i);
	}
	return ret;
}

void solve()
{
	cin>>n>>m;
	rep(i,0,m){
		ll x,y;
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
	}
	set<ll> s;
	rep(i,1,n+1){
		if(!vis[i]){
			s.insert(dfs(i));
		}
	}
	ll ans=0;
	ll mx=0;
	for(auto i:s){
		ans+=i-mx;
		mx=i;
	}
	cout<<ans<<endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 24128
import sys, os, re
from pprint import pprint
from math import sin, cos, sqrt, radians

n, m = list(map(int, sys.stdin.readline().strip().split()))
g = [[] for x in range(n)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

if [] in g:
    print("No")
    exit(0)

ans = {0: -1}
tmp = [0]

while len(ans) < n:
    tmp_next = []
    for k in tmp:
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                tmp_next.append(node) 
                flag = True

        tmp = tmp_next
        if flag == False:
            break

    """
    flag = False    
    for k, v in list(ans.items()):
        for node in g[k]:
            if node not in ans:
                ans[node] = k
                flag = True
    if flag == False:
        break
    """

print("Yes")
for i in range(1, n):
    print(ans[i]+1)

Measured memory_bytes: 108132
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;
int n,m,c;
int w[200][200];
int b[200];

int main()
{
    int ans=0;
    cin >> n >> m >> c;
    for (int i=1; i<=m; ++i)
        cin>> b[i];
    for (int i=1; i<=n; ++i)
    {
        int now=0;
        for (int j=1; j<=m; ++j)
        {
            cin >> w[i][j];
            now+=b[j]*w[i][j];
        }
        ans+=(now>-1*c);
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#define NUM (1000)
int main()
{
  int G[NUM][NUM];
  int N;
  int i;

  scanf("%d", &N);

  for(i=0; i<N; i++){
    scanf("%d %d", &G[i][0], &G[i][1]);
  }

  for(i=0; i<N; i++){
    if(G[i][0]%G[i][1] == 0){
      printf("%d\n", G[i][1]);
    }
    else
      printf("%d\n", G[i][0]%G[i][1]);
    
  }
  return 0;
}

Measured memory_bytes: 3008
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] p = new int[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
        }
        for (int i = 0; i < n-2; i++) {
            if((p[i+1] < p[i] && p[i+2] < p[i+1]) || (p[i] < p[i+1] && p[i+1] < p[i+2])){
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21972
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    if op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a//b)
    elif op == '?':
        break


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

using namespace std;
#define int long long

int32_t main(){
	ios_base::sync_with_stdio(0);
	string frase;
	int check=0;
	cin >> frase;

	for (int i = 1; i < frase.size(); i++){
		if (frase[i] == frase[i-1] && check != 1)
			check = 1;
	}


	if (check == 0)
		cout << "Good\n";
	else
		cout << "Bad\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

const int NUM = 9;

int a[NUM], b[NUM];
double memo[NUM][1<<NUM][400];

double calc(int now, int T, int num) {
  //cout << now << " " << T << " " << num << endl;
  if (now == NUM) return num > 200;
  if (memo[now][T][num] >= 0) return memo[now][T][num];
  double res = 0;
  double p = 1.0/(NUM-now);
  REP(i,NUM) {
    if (T>>i&1) continue;
    int next = num;
    if (a[now]>b[i]) next += a[now]+b[i];
    else next -= a[now]+b[i];
    res += calc(now+1, T|1<<i, next) * p;
  }
  return memo[now][T][num] = res;
}

int main() {
  int N;
  cin >> N;
  while(N--) {
    REP(i,NUM)cin>>a[i];
    REP(i,NUM)cin>>b[i];
    REP(i,NUM)REP(j,1<<NUM)REP(k,400)memo[i][j][k]=-1;
    double ans = calc(0,0,200);
    printf("%.5f %.5f\n", ans, 1-ans);
  }
}

Measured memory_bytes: 14000
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;

struct POINT{
  int x1, y1;
  int x2, y2;
};

multimap<string, POINT> MakeButton(int);
void Click(map< string, multimap<string, POINT> >,
	   vector<string>&, int&, int, int);

int main(){
  int i, n, m, w, h, now;
  string str;
  vector<string> logdata;
  map< string, multimap<string, POINT> > webpage;

  while(1){
    cin >> n;
    if(n == 0) break;
    cin >> w >> h;

    for(i=0; i<n; ++i){
      cin >> str >> m;
      if(i == 0) logdata.push_back(str);
      webpage.insert(make_pair(str, MakeButton(m)));
    }

    cin >> m;
    for(i=0, now=0; i<m; ++i){
      cin >> str;
      if(str == "click") Click(webpage, logdata, now, w, h);
      else if(str == "back" && now > 0) --now;
      else if(str == "forward" && now < logdata.size()-1) ++now;
      else if(str == "show") cout << logdata[now] << endl;
    }

    logdata.clear();
    webpage.clear();
  }
  return 0;
}

multimap<string, POINT> MakeButton(int n){
  int i, x1, y1, x2, y2;
  string str;
  POINT p;
  multimap<string, POINT> button;

  for(i=0; i<n; ++i){
    cin >> p.x1 >> p.y1 >> p.x2 >> p.y2 >> str;
    button.insert(make_pair(str, p));
  }
  return button;
}

void Click(map< string, multimap<string, POINT> > webpage,
	   vector<string>& logdata, int& now, int w, int h){
  int x, y;
  cin >> x >> y;
  if(x < 0 || w < x || y < 0 || h < y) return;

  POINT p;
  multimap<string, POINT> button;
  multimap<string, POINT>::iterator i;
  map< string, multimap<string, POINT> >::iterator j;

  j = webpage.find(logdata[now]);
  if(j == webpage.end()) return;
  button = j->second;

  for(i=button.begin(); i!=button.end(); ++i){
    p = i->second;
    if(p.x1 <= x && x <= p.x2 && p.y1 <= y && y <= p.y2){
      ++now;
      logdata.erase(logdata.begin()+now, logdata.end());
      logdata.push_back(i->first);
      return;
    }
  }
}

Measured memory_bytes: 1276
s=input()
n=len(s)
flag=False
for i in range(n//2):
    if s[i]!=s[-i-2]:
        flag=True
if flag or s[0]=="0" or s[-1]=="1":
    print(-1)
else:
    print("2 1")
    head=2
    for i in range(3,n//2+2):
        print(str(i)+" "+str(head))
        if s[i-2]=="1":
            head=i
    i=n//2+2
    while i<=n:
        print(str(i)+" "+str(head))
        i+=1

Measured memory_bytes: 47448
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
    long long n,m,d;
    scanf("%lld%lld%lld",&n,&m,&d);
    double x,y;
    if(d!=0)x=(m-1)*2*(n-d);
    if(d==0)x=(m-1)*n;
    y=n*n;
    double ans,j;
    if(y>x){
        j=y/x;
        ans=1/j;
    }
    else{
        ans=x/y;
    }
    printf("%lf\n",ans);
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long t = sc.nextLong();
		long total = 0;
		long prev = sc.nextLong();
		
		for (int i = 1; i < n; i++) {
			long tmp = sc.nextLong();
			total += Math.min(t, tmp - prev);
			prev = tmp;
		}
		total += t;
		System.out.println(total);
	}
}


Measured memory_bytes: 62256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <stack>
#include <map>
#include <iomanip>
using namespace std;

int64_t min(int64_t a,int64_t b) {
    if (a > b)
    {
        return b ;
    }else
    {
        return a ;
    }
}


int main(){
    int a,b,h,m ;
    cin >> a >> b >> h >> m ;
    double l,s ;
    l = m * 6 ;
    s = h * 30 + m * 0.5 ;
    double angle ;
    if (l - s > 0)
    {
        angle = l-s ;
    }else
    {
        angle = s-l ;
    }
    double ans = a*a + b*b - 2*a*b*cos(angle*M_PI/180.0) ;
    ans = sqrt(ans) ;
    cout << fixed << setprecision(10) << ans << endl ;
    
}

Measured memory_bytes: 4188
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 1000001;

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    map<int,bool> mp;

    ll k;
    int n;
    cin >> n >> k;

    vector<int> v(n);
    for(int i = 0; i< n; ++i)
    {
        cin >> v[i];v[i]--;
    }

    int poz1 = 0, poz2 =0;

    int ct =0;
    while(ct != k)
    {
        ct++;
        poz1 = v[poz1];
        poz2 = v[v[poz2]];

        if(poz1 == poz2)
        {
            poz1 = 0;
            while(poz1 != poz2)
            {
                poz1 = v[poz1];
                poz2 = v[poz2];
            }
            break;
        }
    }
    if(ct == k)
    {
        cout << poz1+1;
        return 0;
    }

    int stepsToCyle = 0, pozAux = 0;
    ct = 0;
    while(pozAux != poz2)
    {
        pozAux = v[pozAux];
        ct++;
    }
    k-=ct;
    int stepsInCycle = 0;
    ct = 1;
    pozAux = v[pozAux];
    while(pozAux != poz2)
    {
        ct++;
        pozAux = v[pozAux];
    }
    int rem = k % ct;
    while(rem)
    {
        rem--;
        poz2 = v[poz2]; 
    }
    cout << poz2 + 1;

    return 0;
}

Measured memory_bytes: 4000
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
for i in range(n):
  if a[i] > b[i]:
    result += b[i]
    b[i] = 0
  else:
    result += a[i]
    b[i] -= a[i]
    if a[i + 1] > b[i]:
      result += b[i]
      a[i + 1] -= b[i]
    else:
      result += a[i + 1]
      a[i + 1] = 0
print(result)

Measured memory_bytes: 25468
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i < (int)(b);++i)
#define long long long
constexpr long inf = 1e15;
using edge = pair<long, int>;
int main() {
    while (true) {
        int N, M, L, K, A, H;
        cin >> N >> M >> L >> K >> A >> H;
        if(N == 0)return 0;
        vector<int> T(L);
        rep(i, L)cin >> T[i];
        T.push_back(A);
        T.push_back(H);

        vector<vector<long>> D(N, vector<long>(N, inf));
        rep(i, N)D[i][i] = 0;
        rep(i, K)
        {
            int x,y; long t;
            cin >> x >> y >> t;
            D[x][y] = t;
            D[y][x] = t;
        }
        rep(k, N)rep(i, N)rep(j, N)D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

        vector<long> time(N, inf);
        time[A] = 0;
        priority_queue<edge, vector<edge>, greater<edge>> Q;
        Q.push(edge(0, A));

        while(Q.size())
        {
            auto p = Q.top(); Q.pop();
            auto v = p.second;
            auto cost = p.first;
            if(time[v] < cost)continue;

            int remain = 0;
            if(cost < M)remain = M - cost;
            for(auto e : T)
            {
                if(e == v)continue;
                auto dist = D[v][e];
                if(dist > M)continue;
                auto add_time = dist;
                if(dist > remain)add_time += (dist - remain);
                auto d = cost + add_time;
                if(d < time[e])
                {
                    time[e] = d;
                    Q.push(edge(d, e));
                }
            }
        }
        
        if(time[H] == inf)cout << "Help!" << endl;
        else cout << time[H] << endl;
  
    }
}



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

int main(){
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int ans=0;
	if(a>=k){
		cout<<k<<endl;
		return 0;
	}else{
		ans+=a;
		k-=a;
	}
	if(b>=k){
		cout<<ans<<endl;
		return 0;
	}else{
		k-=b;
	}
	cout<<ans-k<<endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 300005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	vector<string>v({"Sunny","Cloudy","Rainy","Sunny"});
	for (int i = 0 ; i < 3 ; i++) {
		if (v[i] == s) {
			cout << v[i + 1] << '\n';
			break;
		}
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
namespace Flandle_Scarlet
{
    #define N 300100
    int n,m;
    class BIT
    {
        public:
            int tree[N];
            int len;
            void BuildTree(int _len)
            {
                len=_len;
            }
            void Add(int pos,int x)
            {
                while(pos<=len)
                {
                    tree[pos]+=x;
                    pos+=(pos&(-pos));
                }
            }
            void RAdd(int l,int r,int x)
            {
                Add(l,x),Add(r+1,-x);
            }
            int Query(int pos)
            {
                int ans=0;
                while(pos>0)
                {
                    ans+=tree[pos];
                    pos-=(pos&(-pos));
                }
                return ans;
            }
    }T;
    struct node
    {
        int l,r;
    }c[N];bool operator<(node a,node b){return a.r-a.l<b.r-b.l;}

    void Input()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            c[i]=(node){l,r};
        }
        sort(c+1,c+n+1);
    }

    int ans[N];
    void Soviet()
    {
        T.BuildTree(m);
        int now=0;
        for(int d=1;d<=m;++d)
        {
            int ans=n-now;
            for(int i=d;i<=m;i+=d)
            {
                ans+=T.Query(i);
            }
            printf("%d\n",ans);
            while(now<n and c[now+1].r-c[now+1].l<=d)
            {
                T.RAdd(c[now+1].l,c[now+1].r,1);
                ++now;
            }
        }
    }
    void IsMyWife()
    {
        if (0)
        {
            freopen("","r",stdin);
            freopen("","w",stdout);
        }
        Input();
        Soviet();
    }
};
int main()
{
    Flandle_Scarlet::IsMyWife();
    return 0;
}

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


void solve(long long A, long long B, long long C, long long D, long long E){
    int count10 = 0;
    long long amari = 10;
    count10 += A/10;
    count10 += B/10;
    count10 += C/10;
    count10 += D/10;
    count10 += E/10;
    if (A%10 != 0) {
        count10 += 1;
        amari = min({amari, A%10});
    }
    if (B%10 != 0) {
        count10 += 1;
        amari = min({amari, B%10});
    }
    if (C%10 != 0) {
        count10 += 1;
        amari = min({amari, C%10});
    }
    if (D%10 != 0) {
        count10 += 1;
        amari = min({amari, D%10});
    }
    if (E%10 != 0) {
        count10 += 1;
        amari = min({amari, E%10});
    }
    cout << count10 * 10 - 10 + amari << endl;
}

// Generated by 1.1.4 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 A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    long long E;
    scanf("%lld",&E);
    solve(A, B, C, D, E);
    return 0;
}


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

using namespace std;
using ll = long long;

template<class T> ostream& operator<<(ostream& os, const vector<T> arr){ for(int i = 0; i < (int)arr.size(); i++)cout << arr[i] << (i == (int)arr.size() -1 ? "" : " "); return os;}

int main()
{
    int m, k;
    cin >> m >> k;
    int n = 1<<m;
    if(k==0) {
        for(int i = 0; i < n; i++)cout << i << " " << i << " ";
        return 0;
    }
    int ac = 0;
    for(int i = 0; i < n; i++)ac ^= i;
    if(k >= n || ac) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> ans(n * 2, -1);
    int cur = 0;
    for(int i = 0; i < n; i++, cur++) {
        if(i == k)cur++;
        ans[i] = cur;
        ans[2 * n- i - 2] = cur;
    }
    ans[n - 1] = ans[2 * n - 1] = k;
    cout << ans << endl;
}

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

using namespace std;
#define INF 1000007
#define MOD 1000000007
#define maxn 101
#define maxh 1001
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
const int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
typedef std::pair<int, int> P;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *) array, (T *) (array + N), val);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

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

int lcm(int a, int b) { return a / gcd(a, b) * b; }

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

int a, b;

void f(int x) {
    while (x) {
        a++;
        b = x;
        x /= 10;
    }
}

signed main() {
    int A, B;
    bool check = true;
    cin >> A >> B;
    if (A > 9 || A <= 0 || B > 9 || B <= 0)check = false;
    if (check)cout << A * B << endl;
    else cout << "-1" << endl;

}



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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
#define Size(n) (n).size()

typedef long long ll;

using namespace std;

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

//long long int kaizyo(long long int hh){
  //  cmp=1;
    //while(hh>1){
      //  cmp=(cmp*hh)%MOD;
        //hh--;
    //}
    //return cmp;
//}
//long long int ruizyo(long long int aa, long long int bb){
  //  if(aa==0){
    //    return 1;
    //}
    //else if(aa%2==0){
      //  long long int tt=ruizyo(aa/2,bb);
        //return (tt*tt)%MOD;
    //}
    //else{
      //  return (ruizyo(aa-1,bb)*bb)%MOD;
    //}
//}フェルマ－のア


//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

//visited=vector<vector<bool>>(10,vector<bool>(10,false));アを全部falseに


long long int n,cnt=0,ans=0,a,b,c,cmp,cmpp,cmps,cmpps,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s,ss;
bool fl=true;

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

       cin >> a>>b;
     // Cout(10001/10000);
       //Cout(10001%100);
       rrep(i,a,b+1){
              s=to_string(i);
              if(s[0]==s[4]&&s[1]==s[3]){
                  ans++;
              }
       }
       Cout(ans);
       
return 0;
}


Measured memory_bytes: 256
package main

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

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

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

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

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

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

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

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

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

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

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

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	x := readInt()
	y := readInt()
	a := make([]int, 13)
	for _, v := range []int{1, 3, 5, 7, 8, 10, 12} {
		a[v] = 1
	}
	for _, v := range []int{4, 6, 9, 11} {
		a[v] = 2
	}
	for _, v := range []int{2} {
		a[v] = 3
	}
	if a[x] == a[y] {
		println("Yes")
	} else {
		println("No")
	}

}

// -----------------------------------------------------------------------------


Measured memory_bytes: 640
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int main(void){
    int H,W;
    cin>>H>>W;
    char str[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin>>str[i][j];
        }
    }
    int line[H];
    int row[W];
    for(int i=0;i<H;i++){
        line[i]=0;
    }
    for(int j=0;j<W;j++){
        row[j]=0;
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(str[i][j]=='#') {
                line[i]=1;
                row[j]=1;
                }
                }
            }
    for(int i=0;i<H;i++){int ans=0;
        for(int j=0;j<W;j++){
            if(row[j]==1&&line[i]==1) {cout<<str[i][j]; ans=1;}
            if(j==W-1&&ans==1) cout<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	
	stack<int> st;
	int n;
	while( cin >> n ){
		if( n != 0 ){
			st.push(n);
		}
		else{
			cout << st.top() << endl;
			st.pop();
			
		}

	}

	ret 0;
}


Measured memory_bytes: 2996
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
  long long int n;
  cin>>n;
  ll A[n-1];
  for(ll i=0;i<n-1;i++)
    cin>>A[i];
  ll B[n]={0};
  for(ll i=0;i<n-1;i++)
  {
    B[A[i]-1]++;
  }
  for(ll i=0;i<n;i++)
  {
    cout<<B[i]<<endl;
  }
  return 0;}

Measured memory_bytes: 6716
n=int(input())
p=list(map(int,input().split()))
ct=0
for i in range(n-2):
  if (p[i]<p[i+1] and p[i+1]<p[i+2]) or (p[i]>p[i+1] and p[i+1]>p[i+2]):
    ct+=1
print(ct)

Measured memory_bytes: 3060
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	string str;
	cin >> str;
	int size = str.size();
	int ans = 0;
	for(int i=1;i<size;++i){
		if( str[i-1] != str[i] ){
			++ans;
		}
	}
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {	
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] p = new int[n+2];
		int[] a = new int[n+2];
		int[] b = new int[n+2];
		
		for (int i=1; i<=n; i++) {
			p[i] = sc.nextInt();
			b[p[i]] += i;
		}
		
		for (int i=1; i<=n; i++) {
			a[i]      = n*i;
			b[n+1-i] += n*i;
		}
		
		for (int i=1; i<=n; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		for (int i=1; i<=n; i++) {
			System.out.print(b[i] + " ");
		}
		System.out.println();
	}
}


Measured memory_bytes: 31136
N=int(input())
s = [input() for i in range(N)]
M=int(input())
t = [input() for j in range(M)]
st=s+t
st=(list(set(st)))
cost=[]

for k in st:
    cost.append(s.count(k)-t.count(k))

if max(cost)<=0:
    print(0)
else:
    print(max(cost))


Measured memory_bytes: 3060
use std::cmp::{min, max};

fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn readn<T: std::str::FromStr>(delimiter: &str) -> Vec<T> {
    let s = read1::<String>();
    s.split(delimiter).map(|e| e.parse().ok().unwrap()).collect::<Vec<T>>()
}

fn main() {
    let nm = readn::<usize>(" ");
    let n = nm[0];
    let m = nm[1];

    let mut l = 1;
    let mut r = n;

    for _ in 0..m {
        let lr = readn::<usize>(" ");
        l = max(l, lr[0]);
        r = min(r, lr[1]);
    }

    if l > r {
        println!("0");
    } else {
        println!("{}", r - l + 1);
    }
}

Measured memory_bytes: 4352
#include <stdio.h>
int main()
{
  int H,W,i,j;
  while(1)
    { 
      scanf("%d %d",&H,&W);
      if(H==0 && W==0)break;
      
      for(i=1;i<=H;i++)
	{   
	  for(j=1;j<=W;j++)
	    {
	      printf("#");
	    }
	  printf("\n");    
	}
      printf("\n");  
    }
  return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;

int main(){
    ll n,d; cin >> n >> d;
    vector<vector<long double> > x(n,vector<long double>(d));
    for(int i=0;i<n;++i){
        for(int j=0;j<d;++j){
            cin >> x[i][j];
        }
    }
    ll ans = 0;
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            long double tmp=0;
            for(int k=0;k<d;++k){
                tmp += pow(x[i][k] - x[j][k],2);
            }
            tmp = pow(tmp,0.5);
            if(tmp - (int)tmp == 0) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

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

template <class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_mset;

#define FOR(i,a,b) for(int i = a; i < b; i++)
#define F0R(i,a) for(int i = 0; i < a; i++)
#define F0Rd(i,a) for (int i = a - 1; i >=0 ; i--)
#define FORd(i,a,b) for (int i = b - 1; i >= a; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) int((x).size())
#define newl '\n'

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define print(x) cout << x << newl;
#define finish(x) return cout << x << "\n", 0;
#define bug(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " " << 

const int MXN = 2e5 + 5;
//const int MXN = 1e6 + 5;
const ll MOD = 998244353;
const ll INF = 1e9 + 7;

int N, X, Y, dist[2005][2005], cnt[2020];

int main(){ FAST
	//ifstream cin("/Users/konwoo/input.txt");
	//ofstream cout("/Users/konwoo/output.txt");


    cin >> N >> X >> Y;
    FOR(i,1,N+1){
        FOR(j,i+1,N+1){
            if (i < X && j > Y){
                dist[i][j] = X-i + 1 + j - Y;
            }
            else if (i < X && j <= Y){
                dist[i][j] = min(j-i, X-i+Y-j+1);
            }
            else if (i >= X && j <= Y){
                if (i == X && j == Y){
                    dist[i][j] = 1;
                }
                else if (i == X){
                    dist[i][j] = min(j-i,1+Y-j);
                }
                else if (j == Y){
                    dist[i][j] = min(j-i,1+i-X);
                }
                else{
                    dist[i][j] = min(j-i,1+Y-j+i-X);
                }
            }
            else{
                if (i < Y){
                    dist[i][j] = min(i - X + 1 + j - Y, Y-i + j - Y);
                }
                else{
                    dist[i][j] = j - i;
                }
            }
            cnt[dist[i][j]]++;
        }
    }



    FOR(k,1,N){
        cout << cnt[k] << newl;


    }










	return 0;
}


Measured memory_bytes: 15360
// ACM-ICPCアジア地区予選2014 G. Flipping Parentheses

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1<<19;
int segMin[2*N-1];
int segAdd[2*N-1];
int segSum[2*N-1];

void add(int l, int r, int val, int idx = 0, int rangeL = 0, int rangeR = N){
	if(rangeR <= l || r <= rangeL) return;
	if(l <= rangeL && rangeR <= r){
		segAdd[idx] += val;
		while(idx){
			idx = (idx-1)/2;
			segMin[idx] = min(segMin[2*idx+1]+segAdd[2*idx+1], segMin[2*idx+2]+segAdd[2*idx+2]);
		}
	} else {
		int rangeM = (rangeL+rangeR)/2;
		add(l, r, val, 2*idx+1, rangeL, rangeM);
		add(l, r, val, 2*idx+2, rangeM, rangeR);
	}
}

int getMin(int l, int r, int idx = 0, int rangeL = 0, int rangeR = N){
	if(rangeR <= l || r <= rangeL) return 1000000007;
	if(l <= rangeL && rangeR <= r) return segMin[idx]+segAdd[idx];
	int rangeM = (rangeL+rangeR)/2;
	return min(getMin(l, r, 2*idx+1, rangeL, rangeM), getMin(l, r, 2*idx+2, rangeM, rangeR)) + segAdd[idx];
}

void change(int pos, int val){
	int idx = pos+N-1;
	int add = val-segSum[idx];
	segSum[idx] = val;
	while(idx){
		idx = (idx-1)/2;
		segSum[idx] += add;
	}
}

int getSum(int l, int r, int idx = 0, int rangeL = 0, int rangeR = N){
	if(rangeR <= l || r <= rangeL) return 0;
	if(l <= rangeL && rangeR <= r) return segSum[idx];
	int rangeM = (rangeL+rangeR)/2;
	return getSum(l, r, 2*idx+1, rangeL, rangeM)+getSum(l, r, 2*idx+2, rangeM, rangeR);
}

int main(){
	int n, q;
	char str[300001];
	while(~scanf("%d %d", &n, &q)){
		memset(segMin, 0, sizeof(segMin));
		memset(segAdd, 0, sizeof(segAdd));
		memset(segSum, 0, sizeof(segSum));
		scanf("%s", str);
		for(int i=0;i<n;i++){
			if(str[i] == '('){
				add(i, n, 1);
			} else {
				add(i, n, -1);
				change(i, 1);
			}
		}
		for(int i=0;i<q;i++){
			int idx; scanf("%d", &idx); --idx;
			if(idx == 0 || idx == n-1){
				printf("%d\n", idx+1);
			} else if(str[idx] == '('){
				change(idx, 1);
				add(0, idx, 2);
				str[idx] = ')';
				int L = 0, R = n-1;
				while(R-L>1){
					int mid = (L+R)/2;
					if(getSum(0, mid) > 0) R = mid;
					else                   L = mid;
				}
				change(L, 0);
				add(0, L, -2);
				str[L] = '(';
				printf("%d\n", L+1);
			} else {
				change(idx, 0);
				add(0, idx, -2);
				str[idx] = '(';
				int L = 0, R = idx+1;
				while(R-L>1){
					int mid = (L+R)/2;
					if(getMin(mid, idx+1) >= 0) R = mid;
					else                        L = mid;
				}
				change(R, 1);
				add(0, R, 2);
				str[R] = ')';
				printf("%d\n", R+1);
			}
		}
	}
}

Measured memory_bytes: 13780
// ABC158, F, Removing Robots
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 2e9;
const int MAX = 2e5;
const int divisor = 998244353;
int n;
pair<int, int> a[MAX + 1];
int dp[MAX + 1];
int tree[1 << 19];

void update(int node, int left, int right, int idx, int v) {

    if (idx < left || right < idx) {
        return;
    }

    if (left == right) {
        tree[node] = v;
        return;
    }

    int mid = (left + right) >> 1;
    update(node << 1, left, mid, idx, v);
    update(node << 1 | 1, mid + 1, right, idx, v);
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}

int query(int node, int left, int right, int l, int r) {
    if (r < left || right < l) {
        return 0;
    }

    if (l <= left && right <= r) {
        return tree[node];
    }

    int mid = (left + right) >> 1;
    return max(query(node << 1, left, mid, l, r), query(node << 1 | 1, mid + 1, right, l, r));
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a, a + n);

    dp[n] = 1;
    update(1, 1, n, n, n);
    for (int k = n - 1; k >= 0; --k) {
        int r = lower_bound(a, a + n, pair<int, int>{a[k].first + a[k].second, 0}) - a - 1;
        int p = k + 1;
        if (k + 1 <= r) {
            p = query(1, 1, n, k + 1, r);
        }
        dp[k] = (dp[k + 1] + dp[p]) % divisor;
        update(1, 1, n, k, p);
    }


    cout << dp[0];
    return 0;
}


Measured memory_bytes: 4608
S=input()
T=input()
Skey=sorted(set(S),key=S.index)
Tkey=sorted(set(T),key=T.index)

for index,i in enumerate(Skey):
  S=S.replace(i,str(index))
for index,i in enumerate(Tkey):
  T=T.replace(i,str(index))

if S==T:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3992
i = gets.to_i

i.times do
	a = gets.chomp.split(" ")
	s1 = a[0].to_i
	s2 = a[1].to_i
	s3 = a[2].to_i
	if s1*s1+s2*s2 ==s3*s3 || s1*s1+s3*s3 ==s2*s2 || s3*s3+s2*s2 ==s1*s1
		puts "YES"
	else
		puts "NO"
	end
end

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<ld> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)


ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
class warshall_floyd{
  private:
    ll N; // 頂点数
    vvll dis; // iからjまでの最短距離
    ll inf = 1e18;

  public:
    warshall_floyd(ll n){
      N = n;
      dis.resize(N,vll(N));

      for(ll i=0;i<N;i++){
        for(ll j=0;j<N;j++){
          dis[i][j] = ( i == j ? 0 : inf );
        }
      }
    }

    // 辺の入力
    void in_edge(ll to, ll from, ll cost){
      dis[to][from] = cost;
    }

    // d[i][j]を埋める
    vvll main(){
      for(ll k=0;k<N;k++){
        for(ll i=0;i<N;i++){
          for(ll j=0;j<N;j++){
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
          }
        }
      }
      return dis;
    }

    // 負の経路の検出
    bool mns_loop(){
      for(ll i=0;i<N;i++){
        if(dis[i][i] < 0) return true;
      }
      return false;
    }
};
//-----------------------------------------

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  ll n;
  cin >> n;
  warshall_floyd W(n);
  REP(i,n){
    ll v, k;
    cin >> v >> k;
    REP(j,k){
      ll a, b;
      cin >> a >> b;
      W.in_edge(v,a,b);
    }
  }
  vvll tmp = W.main();
  REP(i,n) cout << i << " " << tmp[0][i] <<endl;

  return 0;
}




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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

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

void Main()
{
    int n = in(), m = in();
    vvint g(n, vint(n, INF));
    rep(i, m)
    {
        int a = in(), b = in(), c = in();
        --a, --b;
        g[a][b] = c;
        g[b][a] = c;
    }

    vvint next(n, vint(n));
    rep(i, n) rep(j, n) next[i][j] = j;

    rep(k, n) rep(i, n) rep(j, n)
    {
        if (chmin(g[i][j], g[i][k] + g[k][j]))
        {
            next[i][j] = next[i][k];
        }
    }

    set<pint> st;

    rep(i, n) rep(j, n)
    {
        st.insert(make_pair(i, next[i][j]));
    }

    cout << m - (st.size() / 2) << endl;
}

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


Measured memory_bytes: 384