akhauriyash/Code-Regression huggingface dataset:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    if a[i] >= b[i]:
        ans += b[i]
    else:
        ans += a[i]
        b[i] -= a[i]
        if a[i+1] > b[i]:
            ans += b[i]
            a[i+1] -= b[i]
        else:
            ans += a[i+1]
            a[i+1] = 0
print(ans)

Measured memory_bytes: 20504
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		sc.close();

		System.out.println(N*N*N);
	}
}


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

int main() {
  long long X, Y;
  cin >> X >> Y;
  
  // Xからはじめて2倍ずつして、Yを超えない範囲の数列を考える
  int count = 0;
  while (X <= Y) {
    X *= 2;
    count++;
  }
  
  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
char s[N], rs[N];
vector<int> sl[N];
int a[N];
int main() {
	scanf("%s", s);
	int m = (int) strlen(s);
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		int l, r;
		scanf("%d%d", &l, &r); -- l, -- r;
		if (l <= (m - 1) / 2 && r >= m / 2) {
			int dl = (m - 1) / 2 - l;
			int dr = r - m / 2;
			if (dl == dr) continue;
			if (dl < dr) {
				l = m / 2 + dl + 1;
			}
			else {
				r = (m - 1) / 2 - dr - 1;
			}
			assert(l <= r && (r <= (m - 1) / 2 || l >= m / 2));
		}
		if (r <= (m - 1) / 2) {
			sl[l].push_back(r);
		}
		else {
			sl[m - 1 - r].push_back(m - 1 - l);
		}
	}
	for (int i = 0; i <= (m - 1) / 2; ++ i) {
		sort(sl[i].begin(), sl[i].end());
		int las = -1;
		for (int x : sl[i]) {
			if (las != -1 && las + 1 <= x) {
				sl[las + 1].push_back(x);
			}
			las = x;
		}
		while ((int) sl[i].size() > 1) sl[i].pop_back();
	}
	for (int i = 0; i < m; ++ i) rs[m - i - 1] = s[i];
	int res = 0, gg = 0;
	for (int i = 0; i <= (m - 1) / 2; ++ i) {
		res += a[i];
		s[i] = (s[i] - 'a' + res) % 26 + 'a';
		if (sl[i].size()) {
			int delta = (26 + (rs[i] - 'a') - (s[i] - 'a')) % 26;
			s[i] = (s[i] - 'a' + delta) % 26 + 'a';
			assert(s[i] == rs[i]);
			res += delta;
			a[sl[i][0] + 1] -= delta;
		}
		if (s[i] != rs[i]) { gg = 1; break; }
	}
	puts(gg ? "NO" : "YES");
}


Measured memory_bytes: 7552
/*
   TASK: nocows
   LANG: C++14
 */

#include "bits/stdc++.h"
typedef long long ll;
typedef long double ld;

using namespace std;
#define finish(x) return cout << x, 0;

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }

const string USCAO_TAG = "nocows";
void usaco() { setIn(USCAO_TAG + ".in"); setOut(USCAO_TAG + ".out"); }
/*
template<typename... Args>
void print(Args... args) {
	((std::cout << args << " "), ...);
}
*/
ll a[100001];
ll dp[100001][101];

int main() {
	//usaco();
	#ifndef ONLINE_JUDGE
	//setIn("in.txt");
	#endif

	int n, k;
	cin >> n;

	k = 2;
	memset(dp, 0x3f3f3f3f, sizeof dp);
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	a[0] = a[1];

	for(int i = k; i >= 1; i--){
		dp[n][i] = abs(a[n] - a[n - i]);
	}

	for(int i = n - 1; i >= 1; i--){
		for(int j = 1; i - j >= 0 && j <= 2; j++){
			for(int q = 1; q <= n - i && q <= 2; q++)
					dp[i][j] = min(dp[i][j], dp[i + q][q] + abs(a[i] - a[i - j]));
		}
	}

	ll mn = 1e9;
	for(int i = 1; i <= k; i++){
		mn = min(mn, dp[1][i]);
	}
	cout << mn;
}

Measured memory_bytes: 79872
#include <cstdio>
#include <algorithm>

const int MAX_N = 50000;

int n, m, c[20], dp[MAX_N + 1];

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

	std::fill(dp, dp + MAX_N + 1, 20);

	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; ++i)
	{
		int min = dp[i - 1] + 1;
		for (int j = 0; j < m; ++j)
		{
			if (i - c[j] < 0)
			{
				continue;
			}
			min = std::min(min, dp[i - c[j]] + 1);
		}
		dp[i] = min;
	}

	printf("%d\n", dp[n]);
}


Measured memory_bytes: 2960
#include <stdio.h>
int main()
{
	int n,a[100];
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=n-1;i>=0;i--){
		printf("%d",a[i]);
		if(i>0)
			printf(" ");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1032
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 c=scan.nextInt();
		if(b<c) {
			if(c-b<=a) {
				System.out.println("safe");
			}
			else {
				System.out.println("dangerous");
			}
		}
		else {
			System.out.println("delicious");
		}
	}
}

Measured memory_bytes: 22612
def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

def under(prime, n):
    for i in range(n - 1, -1, -1):
        if prime[i]:
            return i
def over(prime, n):
    for i in range(n + 1, len(prime)):
        if prime[i]:
            return i
import sys
n = [int(line) for line in sys.stdin]

prime = create_prime(max(n) + 100)

for ni in n:
    print(under(prime, ni), over(prime, ni))

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

int main(){
	int x,n;
	cin>>x>>n;
	int a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int ans,mi=1000;
	for(int i=-2;i<=105;i++){
		if(binary_search(a+1,a+n+1,i)==0){
			if(mi>(abs(x-i))){
				mi=abs(x-i);
				ans=i;
			}
		}
	}
	cout<<ans<<endl;
}


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

int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){
        int gx, gy;
        cin >> gx >> gy;
        
        int movable[16][16]={};
        for(int i=0; i<=gx; ++i){
            movable[i][0] += 1;
        }
        for(int j=0; j<=gy; ++j){
            movable[0][j] += 2;
        }
        
        int M;
        cin >> M;
        for(int i=0; i<M; ++i){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if(x1 == x2){
                movable[x1][max(y1,y2)] += 1;
            } else {
                movable[max(x1,x2)][y1] += 2;
            }
        }
        
        int route[16][16] = {};
        for(int i=0; i<=gx; ++i){
            for(int j=0; j<=gy; ++j){
                switch(movable[i][j]){
                    case 0:
                        route[i][j] = route[i-1][j] + route[i][j-1];
                        break;
                    case 1:
                        route[i][j] = route[i-1][j];
                        break;
                    case 2:
                        route[i][j] = route[i][j-1];
                        break;
                    case 3:
                        if(i == 0 && j == 0){
                            route[0][0] = 1;
                        } else {
                            route[i][j] = 0;
                        }
                        break;
                }
            }
        }
        if(route[gx][gy] != 0){
            cout << route[gx][gy] << endl;
        } else {
            cout << "Miserable Hokusai!" << endl;
        }
    }
}

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    a,b,c=MI()
    f=0
    if b-a==c-b:
        f=1
        
    if f==1:
        print("YES")
    else:
        print("NO")

main()


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

typedef long long int ll;

int N, Q;
vector<int> A;

ll solve(ll x){
    ll s = 0;
    ll res = 0;
    for(int l=0, r=0; l<N;){
        while(r<N && s<=x){
            s += A[r++];
        }
        if(s > x)
            res += (r - l) - 1;
        else
            res += (r - l);
        s -= A[l++];
    }
    return res;
}

int main(){
    cin >> N >> Q;
    A.resize(N);
    for(auto &v: A)
        cin >> v;
    
    for(int i=0; i<Q; i++){
        ll x; cin >> x;
        cout << solve(x) << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <iomanip>
#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()
#define chmax(a,b) (a<(b)?(a=b,1):0)
#define chmin(a,b) (a>(b)?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
const int INF = 1<<29;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef pair<int,int> pii;
typedef long long ll;

typedef short Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int s, int d, Weight w){
  g[s].push_back(Edge(s,d,w));
  g[d].push_back(Edge(d,s,0));
}

Matrix flow[200];
Matrix capacity[200];
Weight total[200];

#define RESIDUE(r,s,t) (capacity[r][s][t]-flow[r][s][t])
Weight maximumFlow(const Graph &g, int s, int t) {
   if (s == t) return 2;
  int n = g.size();
  // Matrix flow(n, Array(n)), capacity(n, Array(n));
  // REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;

  while (1) {
    queue<int> Q; Q.push(s);
    vector<int> prev(n, -1); prev[s] = s;
    while (!Q.empty() && prev[t] < 0) { // s から t へ流せる路をBFSで見つける。
      int u = Q.front(); Q.pop();
      FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(t, u, e->dst) > 0) {
        prev[e->dst] = u;
        Q.push(e->dst);
      }
    }
    
    if (prev[t] < 0) return total[t]; // prev[x] == -1 <=> t-side
    Weight inc = 10000;
    for (int j = t; prev[j] != j; j = prev[j]) {
      inc = min(inc, (Weight)RESIDUE(t, prev[j], j));
    }
    for (int j = t; prev[j] != j; j = prev[j])
      flow[t][prev[j]][j] += inc, flow[t][j][prev[j]] -= inc;
    total[t] += inc;
  }
}

int main() {
  int n,m;
  while(cin>>n>>m) {
    REP(i,2*n) {
      flow[i] = Matrix(2*n,Array(2*n));
      capacity[i] = Matrix(2*n,Array(2*n));
      total[i] = 0;
    }
    Graph g(n*2);
    REP(i,n) {
      add_edge(g,2*i,2*i+1,1);
      REP(j,2*n) {
        capacity[j][2*i][2*i+1]++;
      }
    }
    REP(i,m) {
      int a,b;
      cin >> a >> b;
      a--;b--;
      add_edge(g,2*a+1,2*b,1);
      add_edge(g,2*b+1,2*a,1);
      REP(j,2*n) {
        capacity[j][2*a+1][2*b]++;
        capacity[j][2*b+1][2*a]++;
      }
//      cout << a << " "<< maximumFlow(g,1,0) << endl;
      if (maximumFlow(g,1,2*a) >= 2 && maximumFlow(g,1,2*b) >= 2) {
        puts("Yes");
      } else {
        puts("No");
      }
    }

  }
}

Measured memory_bytes: 35896
using System;
class Sample
{
	static void Main()
	{
      string str = Console.ReadLine();
      string[] arr =  str.Split(' ');
      int x = int.Parse(arr[0]);
      int y = int.Parse(arr[1]);
      if(x%y == 0)
      {
      	Console.WriteLine(0);
      }
      else
      {
      	Console.WriteLine(1);
      }
	}
}

Measured memory_bytes: 11092
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    int n = s.size();
    string ans;
    if (n <= k) ans = s;
    else ans = s.substr(0, k) + "...";
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3592
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int red[][] = new int[N][2];
		int blue[][] = new int[N][2];
		for(int i = 0; i < N; i++) {
			red[i][0] = sc.nextInt();
			red[i][1] = sc.nextInt();
		}
		for(int i = 0; i < N; i++) {
			blue[i][0] = sc.nextInt();
			blue[i][1] = sc.nextInt();
		}
		
		Arrays.sort(blue, Comparator.comparingInt(o -> o[0]));
		int ans = 0;
		int used[] = new int[N];
		Arrays.fill(used, 0);
		for(int i = 0; i < N; i++) {
			int max_red_y = -1;
			int red_num = -1;
			in : for(int j = 0; j < N; j++) {
				if(used[j] == 1) continue in;
				if(blue[i][0] > red[j][0] && blue[i][1] > red[j][1]) {
					if(max_red_y < red[j][1]) {
						max_red_y = red[j][1];
						red_num = j;
					}
				}
			}
			if(red_num != -1) {
				used[red_num] = 1;
				ans++;
			}
		}
		
		System.out.println(ans);
	}
}


Measured memory_bytes: 27092
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


res = K
def dfs(last, cur):
    global res

    if last == -1:
        for i, np in enumerate(edges[0]):
            res *= (K-i-1)
            res %= mod
            dfs(0, np)

    else:
        num_edges_cur = len(edges[cur]) - 1
        if num_edges_cur == 0:
            return

        for i in range(K-2, K-num_edges_cur-2, -1):
            res *= i
            res %= mod
        for np in edges[cur]:
            if np == last:
                continue
            dfs(cur, np)
        
dfs(-1, 0)

print(res)


Measured memory_bytes: 158044
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[100001];
int solve(int arr[],int idx)
{
    if(idx>=n) return INT_MAX;
    if(idx==n-1) return 0;
    if(dp[idx]!= -1) return dp[idx];
    int mi=INT_MAX;
    int left=INT_MAX,right=INT_MAX;
    if(idx+1 <= n-1)
    {
        left=abs(arr[idx+1]-arr[idx])+solve(arr,idx+1);
    }
    if(idx+2 <= n-1)
    {
        right=abs(arr[idx+2]-arr[idx])+solve(arr,idx+2);
    }
    mi=min(left,right);
    return dp[idx]=mi;
    
}

int main() {
    memset(dp,-1,sizeof(dp));
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)
	{
	    cin>>arr[i];
	}
	cout<<solve(arr,0)<<endl;
}


Measured memory_bytes: 5760
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	A, err := strconv.Atoi(strings.Split(scanner.Text(), " ")[0])
	if err != nil {
		fmt.Println(err)
		return
	}
	B, err := strconv.Atoi(strings.Split(scanner.Text(), " ")[1])
	if err != nil {
		fmt.Println(err)
		return
	}

	if A < 0|| A > 9|| B < 0|| B > 9 {
		fmt.Println(-1)
		return
	}
	fmt.Println(A*B)
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int a,b,c,d,e,m,n,x,y,z;
	scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
	if(a<0){
		m=a*-1;
		x=c*m;
		y=e*b;
		z=x+y+d;
		printf("%d\n",z);
	}
	else if(a>0){
		x=b-a;
		y=x*e;
		printf("%d\n",y);
	}
	else{
		x=b*e;
		y=x+d;
		printf("%d\n",y);
	}
	return 0;
}


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

int main(){
  string s;
  cin >> s;
  int a = s.length();
  char b = s.at(a-1);
  if(b=='s'){
    cout << s << "es" << endl;
  }else{
    cout << s << "s" <<endl;
  }
}


Measured memory_bytes: 3624
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n; ll k; cin>>n>>k;
	ll a[200020];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	ll l=0, r=1e9+7;
	while(r-l>1){
		ll m=(l+r)/2;
		ll s=0;
		for(int i=0; i<n; i++){
			(s+=(a[i]+m-1)/m-1);
		}
		if(s<=k) r=m;
		else l=m;
	}
	cout<<r<<endl;
	return 0;
}

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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1LL<<62)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int dx[8] = {0, 1, 0, -1, 1, -1, 1, -1};
int dy[8] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int W, H, N;
  cin >> W >> H >> N;

  int lx = 0, rx = W;
  int by = 0, uy = H;

  rep(i, N) {
    int x, y, a;
    cin >> x >> y >> a;
    if (a == 1)
      lx = max(lx, x);
    if (a == 2)
      rx = min(rx, x);
    if (a == 3)
      by = max(by, y);
    if (a == 4)
      uy = min(uy, y);
  }

  if (rx - lx <= 0 || uy - by <= 0) {
    cout << 0 << endl;
    return 0;
  }

  cout << (rx - lx) * (uy - by) << endl;

  return 0; 
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
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 long long INF = 1000000000000000;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n, m,k,l; string s;
char maze[60][60];
int dis[101][101];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	cin >> n >> m;
	vector<pair<ll, ll>> ab(n);
	vector<pair<ll, ll>> cd(m);
	rep(i, n) {
		cin >> ab[i].first >> ab[i].second;
	}
	rep(i, m) {
		cin >> cd[i].first >> cd[i].second;
	}
	rep(i, n) {
		ll flg = 0;
		ll d = INF;
		rep(j, m) {
			ll dis = abs(ab[i].first - cd[j].first) + abs(ab[i].second - cd[j].second);
			if (d > dis) {
				d = dis;
				flg = j;
			}
		}
		cout << flg + 1 << endl;
	}
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int sz=2e5+9;
ll n,k;
ll a[sz],cs[sz];
ll add(ll a,ll b){return ((a%k+b%k)%k+k)%k;}
map<ll,ll> m;
ll ans;
ll val[sz];

int main(){
    scanf("%lld %lld",&n,&k);
    for(int i=0;i<n;i++){
    	scanf("%I64d",&a[i]);
    	if(!i) cs[i]=a[i]%k;
    	else cs[i]=add(cs[i-1],a[i]);
    }
    m[0]++;
    val[0]=0;
    for(int i=0;i<n;i++){
    	val[i+1]=add(cs[i],-i-1);
    	if(i-k+1>=0) m[val[i-k+1]]--;
    	if(m.count(val[i+1])) ans+=m[val[i+1]];
    	m[val[i+1]]++;
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 17408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0; i<n; i++)
int main()
{
	int X;
	cin >> X;

	if(X>=30)
		cout << "Yes";
	else
		cout << "No";

	cin >> X;
	
	return 0;	
}


Measured memory_bytes: 3592
/*
    NEVER GIVE UP!
    THE EXPERT IN ANYTHING WAS ONCE A BEGINNER
*/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define f(i,a,b) for(ll i=a; i<=b; i++)
#define fi(i,a,b) for(ll i=a; i>=b; i--)
#define fa(x,b) for(auto x:b)
#define TC ll test_case; cin>>test_case; for(ll number=1 ; number <= test_case ; number ++ )
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define sz(a) (ll)(a).size()
#define sp(x) cout << fixed << setprecision(x);
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
#define endl "\n"

const ld pi = acos(-1);
const ll M=1e9+7,N=1e5+5,INF=1e18;

vector<bool> prime(N,true);
void Sieve()
{  
    f(p,2,N)
    {
        if(prime[p])
        {
            for( ll i=p+p; i<N; i+=p)
                prime[i]=false;
        }
    }
}

void solve()
{
    Sieve();
    ll x;
    cin >> x;
    while(!prime[x])
    {
        x++;
    }
    cout << x << endl;
}

int32_t main()
{
    FIO
    solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{

	public static void main(String args[]){
		FastReader sc = new FastReader();
		int n,i;
		n=sc.nextInt();
		int a[]=new int[n-1];
		for(i=0;i<n-1;i++)
			a[i]=sc.nextInt();
		if(n==1){
			System.out.println(a[0]*2);
			System.exit(0);
		}
		int sum=0;
		for(i=n-3;i>=0;i--)
			sum+=Math.min(a[i],a[i+1]);
		sum+=a[0]+a[n-2];
		out.println(sum);
		out.flush();
	}

	static PrintWriter out;
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
			out=new PrintWriter(System.out);
		}
		String next(){
			while(st==null || !st.hasMoreElements()){
				try{
					st= new StringTokenizer(br.readLine());
				}
				catch (IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt(){
			return Integer.parseInt(next());
		}
		long nextLong(){
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine(){
			String str = "";
			try{
				str=br.readLine();
			}
			catch(IOException e){
				e.printStackTrace();
			}
			return str;
		}
	}

	static class pair{
		int first,second;
		pair(int f,int s){
			first=f;
			second=s;
		}
	}

	public static long fastexpo(long x, long y, long p){
		long res=1;
		while(y > 0){
			if((y & 1)==1)
				res= ((res%p)*(x%p))%p;
			y= y >> 1;			
			x = ((x%p)*(x%p))%p;
		}
		return res;
	}

	public static boolean[] sieve (int n) {
		boolean primes[]=new boolean[n+1];
		Arrays.fill(primes,true);
		primes[0]=primes[1]=false;
		for(int i=2;i*i<=n;i++){
			if(primes[i]){
				for(int j=i*i;j<=n;j+=i)
					primes[j]=false;
			}
		}
		return primes;
	}

	public static long gcd(long a,long b){
        return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).longValue();
    }

    public static void merge(int a[],int l,int m,int r){
        int n1,n2,i,j,k;
        n1=m-l+1;
        n2=r-m;

        int L[]=new int[n1];
        int R[]=new int[n2];

        for(i=0;i<n1;i++)
            L[i]=a[l+i];
        for(j=0;j<n2;j++)
            R[j]=a[m+1+j];

        i=0;j=0;

        k=l;
        while(i<n1&&j<n2){
            if(L[i]<=R[j]){
                a[k]=L[i];
                i++;
            }
            else{
                a[k]=R[j];
                j++;
            }
            k++;
        }

        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            j++;
            k++;
        }
    }
    public static void sort(int a[],int l,int r){
        int m;
        if(l<r){
            m=(l+r)/2;
            sort(a,l,m);
            sort(a,m+1,r);
            merge(a,l,m,r);
        }
    }
}



Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
auto modmul = [](auto... modx) {
  ll res = 1;
  for (auto modx_ : {modx...})
  {
    res *= modx_;
    res %= mo;
    res += mo;
    res %= mo;
  }
  return res;
};
ll mypow(ll a, ll b)
{
  ll res = 1;
  a %= mo;
  while (b)
  {
    if (b & 1)
      res = res * a % mo;
    a = a * a % mo;
    b >>= 1;
  }
  return res;
}
const ll MAX = 510000;
const ll MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (ll i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
long long COM(ll n, ll k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
vector<ll> factorial(ll n)
{
  vector<ll> fac;
  fac.push_back(1);
  for (ll i = 1; i < n + 10; i++)
  {
    fac.push_back((fac[i - 1] * i) % mo);
  }
  return fac;
}
int main()
{
ll n , k ;
cin >> n >> k ;
auto mod = [](ll modx) {modx%=mo;modx+=mo;modx%=mo;return modx; };
COMinit();
vector<ll> fac = factorial(100000);

ll t=0;
rep(i,k+1)t=mod(t+mypow(-1,k-i)*COM(k,i)*mypow(i,n));

vector<ll> b={1};
rep(i,k)b.push_back(mod(b.back()+(i%2?1:-1)*mypow(fac[i+1],mo-2)));
ll bb=0;
rep(i,k+1){
  bb=mod(bb+modmul(mypow(i,n),mypow(fac[i],mo-2),b[k-i]));
}
/* 
https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5
ボール      箱	      入れ方に制限なし 箱の中身は1つ以下 箱の中身は1つ以上
区別できる   区別できる  1            2             3
区別できない  区別できる  4            5             6
区別できる   区別できない 7            8             9
区別できない  区別できない 10          11            12
*/
//1
//cout << mypow(k,n) << endl;
//2
//cout << (COM(k,n)*fac[n])%mo << endl;
//3
//cout << t << endl;
//4
//cout << COM(n+k-1,n) << endl;
//5
//cout << COM(k,n) << endl;
//6
//cout << COM(n-1,k-1) << endl;
//7
cout << bb << endl;
//8,11
//cout << (n>k?0:1) << endl;
//9 漸化式でもできる
//cout << mod(t*mypow(fac[k],mo-2)) << endl;
//10
//12
return 0;
}


Measured memory_bytes: 15884
#include<bits/stdc++.h>
using namespace std;
bool check(string s) {
	int sz = (int)s.size();
	for(int i=0;i+2<sz;i++)
		if(s[i] != s[i+2])
			return false;
	return true;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	if(check(s) || (s.front() == s.back() && ((int)s.size()&1)) || (s.front() != s.back() && (~(int)s.size()&1)))
		cout << "Second" << endl;
	else
		cout << "First" << endl;
	return 0;
}


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

#define rep(i, n) for(int i = 0; i < n; ++i)
typedef long long ll;
using namespace std;

int main() {
    int a, b, c, d, n;
    cin >> n >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;
    string s;
    cin >> s;
    if(d > c){
        for (int i = b; i < d; ++i) {
            if(i == b) continue;
            if(s[i - 1] == '#' && s[i] == '#'){
                cout << "No" << endl;
                return 0;
            }
        }
        for (int i = a; i < c; ++i) {
            if(i == a) continue;
            if(s[i - 1] == '#' && s[i] == '#'){
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    }else{
        int f = 0;
        for (int i = b; i < d; ++i) {
            if(i == b) continue;
            if(i > a - 2){
                if(s[i - 2] == '.' && s[i - 1] == '.' && s[i] == '.'){
                    f = 1;
                }
            }
            if(s[i - 1] == '#' && s[i] == '#'){
                cout << "No" << endl;
                return 0;
            }
        }
        if(s[d - 2] == '.' && s[d - 1] == '.') f = 1;
        if(f == 0) s[d] = '#';
        for (int i = a; i < c; ++i) {
            if(i == a) continue;
            if(s[i - 1] == '#' && s[i] == '#'){
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 640
s = input()

left = 0
right = len(s) - 1

cnt = 0
while left < right:
    if s[left] == s[right]:
        left += 1
        right -= 1
    elif s[left] == 'x':
        cnt += 1
        left += 1
    elif s[right] == 'x':
        cnt += 1
        right -= 1
    else:
        print(-1)
        break
else:
    print(cnt)


Measured memory_bytes: 39664
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	cout << (n * a <= b ? n * a : b) << endl;
	return 0;
}

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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 3e3 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-8;

ll dp[MAXN][MAXN];
pll par[MAXN][MAXN];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(dp, 31, sizeof dp);
	
	str s;
	str t;
	cin >> s >> t;
	ll n = s.size();
	ll m = t.size();
	s = '!' + s;
	t = '!' + t;
	
	for(int i = 0;i<=n;i++) dp[i][0] = 0;
	for(int j = 0;j<=m;j++) dp[0][j] = 0;
	
	for(int i = 1; i<=n; i++){
		for(int j = 1;j<=m;j++){
			par[i][j] = make_pair(i-1,j);
			dp[i][j] = dp[i-1][j];
			if(dp[i][j-1] > dp[i][j]){
				par[i][j] = make_pair(i,j-1);
				dp[i][j] = dp[i][j-1];
			}
			if(dp[i-1][j-1] + 1 > dp[i][j] and s[i] == t[j]){
				par[i][j] = make_pair(i-1,j-1);
				dp[i][j] = dp[i-1][j-1] + 1;
			}
		}
	}
	//debug(dp[n][m]);
	ll x = n;
	ll y = m;
	ll nx, ny;
	str ans = "";
	while(min(x,y) > 0){
		nx = par[x][y].F;
		ny = par[x][y].S;
		if(nx + ny < x + y - 1) ans = s[x] + ans ;
		x = nx;
		y = ny;
	}
	cout << ans;
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/


Measured memory_bytes: 212608
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}
func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0
	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}
	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	s := getNextString(scanner)
	if isYYMM(s) && isMMYY(s) {
		fmt.Fprintln(writer, "AMBIGUOUS")
		return
	}
	if isYYMM(s) {
		fmt.Fprintln(writer, "YYMM")
		return
	}
	if isMMYY(s) {
		fmt.Fprintln(writer, "MMYY")
		return
	}
	fmt.Fprintln(writer, "NA")
}

func isYYMM(s string) bool {
	return isYY(s[0:2]) && isMM(s[2:4])
}
func isMMYY(s string) bool {
	return isMM(s[0:2]) && isYY(s[2:4])
}

func isYY(s string) bool {
	for i := 0; i < 100; i++ {
		if s == fmt.Sprintf("%02d", i) {
			return true
		}
	}

	return false
}
func isMM(s string) bool {
	for i := 0; i < 12; i++ {
		if s == fmt.Sprintf("%02d", i+1) {
			return true
		}
	}

	return false
}


Measured memory_bytes: 640
import sys
import math
import bisect

def main():
    s = input()
    max_val = 0
    val = 0
    for i in range(3):
        if s[i] == 'S':
            val = 0
        else:
            val += 1
        max_val = max(max_val, val)
    print(max_val)

if __name__ == "__main__":
    main()


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

int main() {
    int x;
    cin >> x;
  	int fifth = x / 500;
  	int happy = 0;
  	int rest = 0;
  	if (fifth > 0) {
	  happy += 1000 * fifth;
    }
	rest = x - 500 * fifth;
  	int go = rest /5;
    if (go > 0) {
	  happy += 5 * go;
    }
	cout << happy << endl;
  
	return 0;
}

Measured memory_bytes: 256
def dfs(bit):
    if len(bit)==N:
        c=0
        s=[0 for _ in range(M)]
        for i in range(N):
            c+=A[i][0]*bit[i]
            if bit[i]==1:
                for j in range(M):
                    s[j]+=A[i][j+1]
                cond=True
                for k in range(M):
                    if s[k]<X:
                        cond=False
                        break
                if cond:
                    ans.append(c)
        return

    else:
        for i in range(2):
            bit.append(i)
            dfs(bit)
            bit.pop()
    
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]

ans=[]

dfs([])

if len(ans)==0:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 9756
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

public static partial class Program
{
    public static void Main()
    {
        var input = CRL().ArrayInts();
        var a = input[0];
        var b = input[1];
        var c = input[2];
        var x = input[3];
        var y = input[4];

        var ans = int.MaxValue;
        for (int i = 0; i <= 100000; i++)
        {
            var price = c * 2 * i + Math.Max(0, x - i) * a + Math.Max(0, y - i) * b;
            ans = Math.Min(ans, price);
        }
        
        CWL(ans);
    }
}

public static partial class Program
{
    //テンプレここから
    public static long GCD(long a, long b) => b == 0 ? a : GCD(b, a % b);
    public static int GCD(int a, int b) => b == 0 ? a : GCD(b, a % b);
    public static long LCM(long a, long b) => a * b / GCD(a, b);
    public static int LCM(int a, int b) => a * b / GCD(a, b);
    public static int ToInt(this double d) => (int) d;
    public static long ToLong(this double d) => (long) d;
    public static int ToInt(this string str) => int.Parse(str);
    public static long ToLong(this string str) => long.Parse(str);
    public static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
    public static int[] ToInt(this IEnumerable<string> strs) => strs.Select(x => x.ToInt()).ToArray();
    public static long[] ArrayLongs(this string str, char opr = ' ') => str.Split(opr).ToLong();
    public static int[] ArrayInts(this string str, char opr = ' ') => str.Split(opr).ToInt();
    public static string CRL() => Console.ReadLine();
    public static string RL() => ReadLine();
    public static void CWL(object obj) => Console.WriteLine(obj);
    public static void WL(object obj) => WriteLine(obj);
    public static long Diff(long a, long b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static int Diff(int a, int b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static long Sign(this long i) => Math.Sign(i);
    public static bool IsEven(this long i) => i % 2 == 0;
    public static bool IsEven(this int i) => i % 2 == 0;
    public static int[] dx = new [] {0, -1, 0, 1};
    public static int[] dy = new [] {-1, 0, 1, 0};
    public static long mod = 1000000007;
    public static string alphabet = "abcdefghijklmnopqrstuvwxyz";
    public static long ToLong(this char c) => c.ToString().ToInt();
    public static long[] Sort(this long[] array) => array.OrderBy(x => x).ToArray();
    public static int[] Sort(this int[] array) => array.OrderBy(x => x).ToArray();
    public static long[] DSort(this long[] array) => array.OrderByDescending(x => x).ToArray();
    public static int[] DSort(this int[] array) => array.OrderByDescending(x => x).ToArray();
    public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
    public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);
    //テンプレここまで
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int k;
	cin >> k;
	k--;
	vector<string> v(5);
	REP(i, 5) {
		v[i] = string(5001, 'z');
	}
	REP(i, s.size()) {

		REP(j, s.size() - i) {
			string tmp = s.substr(i, j + 1);
			int c = lower_bound(ALL(v), tmp) - v.begin();
			if (c == 5 || v[c] == tmp)continue;
			RFOR(i, c, 4) {
				v[i + 1] = v[i];
			}
			v[c] = tmp;
		}
	}
	cout << v[k] << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

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

    ll a, b; cin >> a >> b;

    ll ans = 0;
    if(a < b){
        rep(i, b){
            ans = 10*ans + a;
        }
    }
    else{
        rep(i, a){
            ans = 10*ans + b;
        }
    }

    cout << ans << endl;

    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

vi divs[MAXN];

int ans[MAXN], col[MAXN];

int add_seg[MAXN];

void solve(){
	int n, l, r, m, cc;
	scanf("%d%d", &n, &m);
	//cc = 500;
	cc = (int)sqrt(m + 0.5);
	REPN(i, 1, m){
		for(int j = i; j <= m; j += i){
			divs[j].pb(i);
		}
	}
	REPN(i, 1, n){
		scanf("%d%d", &l, &r);
		if (r - l <= cc){
			REPN(j, l, r){
				REP(k, 0, SZ(divs[j])){
					if (col[divs[j][k]] != i){
						col[divs[j][k]] = i;
						ans[divs[j][k]]++;
					}
				}
			}
		} else {
			int lim = r - l + 1;
			int last = INF;
			for(int j = 1; ; j++){
				int l1 = (l + j - 1) / j;
				int r1 = r / j;
				r1 = min(r1, last - 1);
				if (l1 <= lim){
					l1 = lim + 1;
				}
				if (l1 <= r1){
					add_seg[l1]++;
					add_seg[r1 + 1]--;
				}
				if (l1 == lim + 1){
					break;
				}
				last = r1;
			}
			add_seg[1]++;
			add_seg[lim + 1]--;
		}
	}
	
	REPN(i, 1, m){
		add_seg[i] += add_seg[i - 1];
		ans[i] += add_seg[i];
		
		printf("%d\n", ans[i]);
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


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

using namespace std;

int main()
{
    int A,B,C,X;
    scanf("%d %d %d %d",&A,&B,&C,&X);
    int cnt=0;
    for(int i=0;i<=A;i++)
    {
        for(int j=0;j<=B;j++)
        {
            for(int k=0;k<=C;k++)
            {
                if((500*i+100*j+50*k)==X)
                    cnt++;
            }
        }
    }
    printf("%d",cnt);
    return 0;
}


Measured memory_bytes: 256
# ABC 066 C
N = int(input())
A = input().split()
from collections import deque

tmp = deque([])
for i,a in enumerate(A):
    if i %2!=0:
        tmp.appendleft(a)
    else:
        tmp.append(a)
if N%2!=0:
    tmp.reverse()
print(' '.join(tmp))

Measured memory_bytes: 26564
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N,K;
  cin>>N>>K;
  int A[N];
  REP(i,N)cin>>A[i];
  int NG=0,OK=1e9+1;
  while(OK-NG>1){
    int C=(OK+NG)/2;
    int k=0;
    REP(i,N){
      k+=max(0,(A[i]+C-1)/C-1);
    }
    if(k<=K)OK=C;
    else NG=C;
  }
  cout<<OK<<endl;
  return 0;
}


Measured memory_bytes: 4336
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
const int MAX = 1000005;
int c[MAX];

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

    int G = 0;
    rep(i, n) {
        int a;
        cin >> a;
        G = __gcd(G, a);
        c[a]++;
    }

    if (G > 1) {
        cout << "not coprime" << endl;
        return 0;
    }

    for (int i = 2; i < MAX; i++) {
        int cnt = 0;
        for (int j = i; j < MAX; j += i) cnt += c[j];
        if (cnt > 1) {
            cout << "setwise coprime" << endl;
            return 0;
        }
    }

    cout << "pairwise coprime" << endl;
    return 0;
}


Measured memory_bytes: 7532
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    ll N;
    cin >> N;

    map<ll, int> ps;
    auto decompositPrime = [&](ll n, map<ll, int> &mp) {
        ll a = 2;
        while (n >= a * a) {
            if (n % a == 0) {
                mp[a]++;
                n /= a;
            } else {
                a++;
            }
        }
        if (n != 1) mp[n]++;
    };

    decompositPrime(N, ps);
 
    int ans = 0;
    for (auto [e0,e1] : ps) {
        int now = e1;
        for(int i =1;i<=e1;++i){
            if(now<0) break;
            if(now-i>=0) ++ans;
            now-=i;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3636
#include<stdio.h>

int main(void){
    int len,an,cnt=0;
   scanf("%d",&len);
   for(int i=0;i<len;i++){
        scanf("%d",&an);
        while(1){
            if(an%2!=0)
                break;
            an/=2;
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const ll mod = 1000000007;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  for (ll i = 1; i <= n; i++) {
    string s = to_string(i);
    if (s.size()%2 == 1) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
R, C = tuple(map(int, input().split()))
grid = [list(input()) for _ in range(R)]
dp = [[0 for _ in range(C)] for _ in range(R)]
for row in range(R):
    if grid[row][0] != '#':
        dp[row][0] = 1
    else:
        break

for col in range(C):
    if grid[0][col] != '#':
        dp[0][col] = 1
    else:
        break





def gridpaths(R, C, grid, MAX=10 ** 9 + 7):
    for row in range(1, R):
        for col in range(1, C):
            if grid[row][col] != '#':
                dp[row][col] = (dp[row - 1][col] + dp[row][col - 1])%MAX
        # print(dp)
    return dp[-1][-1]


print(gridpaths(R, C, grid))


Measured memory_bytes: 52440
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class A
{
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');
        int a = int.Parse(str[0]);
        int b = int.Parse(str[1]);

        if (a > b) Console.WriteLine("a > b");
        else if (a < b) Console.WriteLine("a < b");
        else Console.WriteLine("a == b");
    }
}

Measured memory_bytes: 5296
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


int main() {
    cout << setprecision(30);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    cin >> n;
    map<int, vector<pair<int, int>>> d;
    int u, v, w;

    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v >> w;
        d[u].pb(mp(v, w % 2));
        d[v].pb(mp(u, w % 2));
    }

    int dist[n + 1];
    bool vis[n + 1];
    memset(vis, false, sizeof vis);

    queue<pair<int, int>> just;
    just.push(mp(1, 0));
    vis[1] = true;
    bool ans[n + 1];

    while (!just.empty()) {
        auto fir = just.front();
        ans[fir.first] = fir.second;
        just.pop();
        for (auto child : d[fir.first]) {
            if (!vis[child.first]) {
                just.push(mp(child.first, (fir.second + child.second) % 2));
                vis[child.first] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}

Measured memory_bytes: 12160