stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e9;

#define Fast    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define sz      200005



ll arr[sz];

int brr[sz];





int main(){

    Fast;

    ll n,k,i;



    cin>>n>>k;

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

        cin>>arr[i];

    }

    memset(brr,0,sizeof(brr));



    i=1;

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }



    ll cnt=0;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        cnt++;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }

    k=k%cnt;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    cout<<i<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.9616360330468483x):
#include <bits/stdc++.h>

using namespace std;



int main() 

{

int n;

long long int k;

cin>>n>>k;

vector<int>visit(n+1);

vector<int>arr(n+1);

for(int i=1;i<=n;i++)

{

      cin>>arr[i];    

}

int pos=1;

int len=0;

while(visit[pos]==0)

{     

          visit[pos]=1;

          pos=arr[pos];

          len++;

}

int pos1=arr[pos];

int cycle=1;

while(pos1!=pos)

{

          pos1=arr[pos1];

          cycle++;

}

 

int j;

if(k<=(len-cycle))

{

          j=k;

          pos=1;

}

else

{

          k=(k-(len-cycle));

          j=k%cycle;

}

 

while(j--)

{

          pos=arr[pos];

}

cout<<pos<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

vector<int> Edge[200005],vec;

int mark[200005];

void dfs(int u)

{

    vec.push_back(u);

    for(int i=0; i<Edge[u].size(); i++)

    {

        int v=Edge[u][i];

        if(mark[v]==0)

        {

            mark[v]=1;

            dfs(v);

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    ll n,k;

    cin>>n>>k;

    for(int i=1; i<=n; i++)

    {

        ll v;

        cin>>v;

        Edge[i].push_back(v);

    }

    mark[1]=1;

    dfs(1);

    ll len=vec.size();

    if(k<len)

    {

        cout<<vec[k]<<endl;

        return 0;

    }

    ll idx=Edge[vec[len-1]][0];

    memset(mark,0,sizeof(mark));

    vec.clear();

    k-=(len-1);

    mark[idx]=1;

    dfs(idx);

    len=vec.size();

    idx=k%len;

    idx--;

    if(idx==-1)

        idx=len-1;

    cout<<vec[idx]<<endl;





    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 7.308205378509092x):
#include<bits/stdc++.h>

using namespace std;

#define ll         long long

#define mod        1000000007

#define setbits(x) __builtin_popcountll(x)

#define zrobits(x) __builtin_ctzll(x)

#define inf        1e18

#define ps(x,y)    fixed<<setprecision(y)<<x



int main() {

// #ifndef ONLINE_JUDGE

// 	freopen("input.txt", "r", stdin);

// 	freopen("output.txt", "w", stdout);

// #endif



	ll n, k;

	cin >> n >> k;

	ll a[n + 1];

	a[0] = 0;

	for (ll i = 1; i <= n; ++i)

	{

		cin >> a[i];

	}

	std::vector<ll> v(n + 1, 0);



	ll start = 1;

	int l ;

	while (1)

	{

		if (v[start] == 1)

		{

			l = start;

			break;

		}



		v[start] = 1;

		start = a[start];

		k--;

		if (k == 0)

		{

			cout << start << endl;

			return 0;

		}

	}



	ll cnt = 0;

	int end = start;

	vector<int > v1;

	while (1)

	{



		v1.push_back(start);

		start = a[start];

		cnt++;

		if (start == end)

			break;

	}

	// for (auto i : v1)

	// {

	// 	cout << i << " ";

	// }

	cout << v1[k % cnt] << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e9;

#define Fast    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define sz      200005



ll arr[sz];

int brr[sz];





int main(){

    Fast;

    ll n,k,i;



    cin>>n>>k;

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

        cin>>arr[i];

    }

    memset(brr,0,sizeof(brr));



    i=1;

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }



    ll cnt=0;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        cnt++;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }

    k=k%cnt;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    cout<<i<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.9662358911955324x):
#include<bits/stdc++.h>

using namespace std;

#define ll         long long

#define mod        1000000007

#define setbits(x) __builtin_popcountll(x)

#define zrobits(x) __builtin_ctzll(x)

#define inf        1e18

#define ps(x,y)    fixed<<setprecision(y)<<x



int main() {

// #ifndef ONLINE_JUDGE

// 	freopen("input.txt", "r", stdin);

// 	freopen("output.txt", "w", stdout);

// #endif



	ll n, k;

	cin >> n >> k;

	ll a[n + 1];

	a[0] = 0;

	for (ll i = 1; i <= n; ++i)

	{

		cin >> a[i];

	}

	std::vector<ll> v(n + 1, 0);



	ll start = 1;

	int l ;

	while (1)

	{

		if (v[start] == 1)

		{

			l = start;

			break;

		}



		v[start] = 1;

		start = a[start];

		k--;

		if (k == 0)

		{

			cout << start << endl;

			return 0;

		}

	}



	ll cnt = 0;

	int end = start;

	vector<int > v1;

	while (1)

	{



		v1.push_back(start);

		start = a[start];

		cnt++;

		if (start == end)

			break;

	}

	// for (auto i : v1)

	// {

	// 	cout << i << " ";

	// }

	cout << v1[k % cnt] << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

vector<int> Edge[200005],vec;

int mark[200005];

void dfs(int u)

{

    vec.push_back(u);

    for(int i=0; i<Edge[u].size(); i++)

    {

        int v=Edge[u][i];

        if(mark[v]==0)

        {

            mark[v]=1;

            dfs(v);

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    ll n,k;

    cin>>n>>k;

    for(int i=1; i<=n; i++)

    {

        ll v;

        cin>>v;

        Edge[i].push_back(v);

    }

    mark[1]=1;

    dfs(1);

    ll len=vec.size();

    if(k<len)

    {

        cout<<vec[k]<<endl;

        return 0;

    }

    ll idx=Edge[vec[len-1]][0];

    memset(mark,0,sizeof(mark));

    vec.clear();

    k-=(len-1);

    mark[idx]=1;

    dfs(idx);

    len=vec.size();

    idx=k%len;

    idx--;

    if(idx==-1)

        idx=len-1;

    cout<<vec[idx]<<endl;





    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 7.283899387595825x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

	int n;

	ll k;

	cin>>n>>k;

	vector<int> a(n);

	for(int i=0;i<n;i++) cin>>a[i];

	vector<int> s;

	vector<int> ord(n+1,-1);

	int c=1,l=0;

	int v=1;

	while(ord[v]==-1) {

		ord[v]=s.size();

		s.push_back(v);

		v=a[v-1];

	}

	c=s.size()-ord[v];

	l=ord[v];

	if(k<l) cout<<s[k]<<endl;

	else {

		k-=l;

		k%=c;

		cout<<s[k+l]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e9;

#define Fast    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define sz      200005



ll arr[sz];

int brr[sz];





int main(){

    Fast;

    ll n,k,i;



    cin>>n>>k;

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

        cin>>arr[i];

    }

    memset(brr,0,sizeof(brr));



    i=1;

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }



    ll cnt=0;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        cnt++;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }

    k=k%cnt;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    cout<<i<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.9596964866181412x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

	int n;

	ll k;

	cin>>n>>k;

	vector<int> a(n);

	for(int i=0;i<n;i++) cin>>a[i];

	vector<int> s;

	vector<int> ord(n+1,-1);

	int c=1,l=0;

	int v=1;

	while(ord[v]==-1) {

		ord[v]=s.size();

		s.push_back(v);

		v=a[v-1];

	}

	c=s.size()-ord[v];

	l=ord[v];

	if(k<l) cout<<s[k]<<endl;

	else {

		k-=l;

		k%=c;

		cout<<s[k+l]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

vector<int> Edge[200005],vec;

int mark[200005];

void dfs(int u)

{

    vec.push_back(u);

    for(int i=0; i<Edge[u].size(); i++)

    {

        int v=Edge[u][i];

        if(mark[v]==0)

        {

            mark[v]=1;

            dfs(v);

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    ll n,k;

    cin>>n>>k;

    for(int i=1; i<=n; i++)

    {

        ll v;

        cin>>v;

        Edge[i].push_back(v);

    }

    mark[1]=1;

    dfs(1);

    ll len=vec.size();

    if(k<len)

    {

        cout<<vec[k]<<endl;

        return 0;

    }

    ll idx=Edge[vec[len-1]][0];

    memset(mark,0,sizeof(mark));

    vec.clear();

    k-=(len-1);

    mark[idx]=1;

    dfs(idx);

    len=vec.size();

    idx=k%len;

    idx--;

    if(idx==-1)

        idx=len-1;

    cout<<vec[idx]<<endl;





    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 7.239869896830797x):
#include<bits/stdc++.h>    

#define int long long int

#define pb push_back

#define endl "\n"

#define F first

#define S second 

#define mod 1000000007     

using namespace std;



main()

{    

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

    int n, k;

    cin >> n >> k;

    int arr[n + 1];

    for(int i = 1; i <= n; i++)

        cin >> arr[i];

    vector<int> visit(n + 1, -1);

    int entry = 0;

    int cur = 1;

    while(visit[cur] == -1 and k){

        if(entry == k){

            cout << cur;

            return 0;

        }

        visit[cur] = entry++;

        cur = arr[cur];

    }

    int cycle = entry - visit[cur];

    int left = (k - entry) % cycle;

    while(left--){

        cur = arr[cur];

    }

    cout << cur;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf = 1e9;

#define Fast    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define sz      200005



ll arr[sz];

int brr[sz];





int main(){

    Fast;

    ll n,k,i;



    cin>>n>>k;

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

        cin>>arr[i];

    }

    memset(brr,0,sizeof(brr));



    i=1;

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }



    ll cnt=0;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        cnt++;

        brr[i]=1;

        i=arr[i];

    }

    if(k==0){

        cout<<i<<endl;

        return 0;

    }

    k=k%cnt;

    memset(brr,0,sizeof(brr));

    while(k && brr[i]==0){

        k--;

        brr[i]=1;

        i=arr[i];

    }

    cout<<i<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.9478505736300034x):
#include<bits/stdc++.h>    

#define int long long int

#define pb push_back

#define endl "\n"

#define F first

#define S second 

#define mod 1000000007     

using namespace std;



main()

{    

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

    int n, k;

    cin >> n >> k;

    int arr[n + 1];

    for(int i = 1; i <= n; i++)

        cin >> arr[i];

    vector<int> visit(n + 1, -1);

    int entry = 0;

    int cur = 1;

    while(visit[cur] == -1 and k){

        if(entry == k){

            cout << cur;

            return 0;

        }

        visit[cur] = entry++;

        cur = arr[cur];

    }

    int cycle = entry - visit[cur];

    int left = (k - entry) % cycle;

    while(left--){

        cur = arr[cur];

    }

    cout << cur;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <cmath>

#include <utility>

#include <iostream>

#include <functional>

#include <bitset>

#include <algorithm>

#include <vector>

#include <forward_list>

#include <set>

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <tuple>

#include <numeric>

#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))

using namespace std;

using ll = long long;

using P = pair<ll, ll>;

const ll MOD = 1e9 + 7;

const ll INF = (1ll << 60);



ll c = 0;

vector<ll> a(300000), b;

set<ll> p;

ll z;



void dfs(ll x)

{

    if (p.find(x) != p.end() && c > 0)

    {

        z = x;

        return;

    }



    p.insert(x);

    b.push_back(x);

    c++;

    dfs(a[x]);

}



int main(void)

{

    ll n, k;



    cin >> n >> k;



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

    {

        cin >> a[i];

        a[i]--;

    }



    dfs(0);



    ll t = 0;



    for (int i = 0; i < c; i++)

    {

        if (b[i] == z)

        {

            t = i;

            break;

        }

    }



    if (k - t <= 0)

    {

        cout << b[k] + 1 << endl;

        return 0;

    }



    cout << b[((k - t) % (c - t)) + t] + 1 << endl;

}


// Faster C++ solution for the same problem (measured speedup: 3.3826511814047895x):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <utility>

#include <iostream>

#include <functional>

#include <bitset>

#include <algorithm>

#include <vector>

#include <forward_list>

#include <set>

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <tuple>

#include <numeric>

#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))

using namespace std;

using ll = long long;

using P = pair<ll, ll>;

const ll MOD = 1e9 + 7;

const ll INF = (1ll << 60);



int main(void)

{

    ll n, k;



    cin >> n >> k;



    vector<ll> a(n + 1);



    for (int i = 1; i <= n; i++)

    {

        cin >> a[i];

    }



    int ans = 1;



    while (k)

    {

        if (k & 1)

        {

            ans = a[ans];

        }



        vector<ll> d(n + 1);



        for (int i = 1; i <= n; i++)

        {

            d[i] = a[a[i]];

        }



        a = d;



        k >>= 1;

    }



    cout << ans << endl;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <cmath>

#include <utility>

#include <iostream>

#include <functional>

#include <bitset>

#include <algorithm>

#include <vector>

#include <forward_list>

#include <set>

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <tuple>

#include <numeric>

#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))

using namespace std;

using ll = long long;

using P = pair<ll, ll>;

const ll MOD = 1e9 + 7;

const ll INF = (1ll << 60);



ll c = 0;

vector<ll> a(300000), b;

set<ll> p;

ll z;



void dfs(ll x)

{

    if (p.find(x) != p.end() && c > 0)

    {

        z = x;

        return;

    }



    p.insert(x);

    b.push_back(x);

    c++;

    dfs(a[x]);

}



int main(void)

{

    ll n, k;



    cin >> n >> k;



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

    {

        cin >> a[i];

        a[i]--;

    }



    dfs(0);



    ll t = 0;



    for (int i = 0; i < c; i++)

    {

        if (b[i] == z)

        {

            t = i;

            break;

        }

    }



    if (k - t <= 0)

    {

        cout << b[k] + 1 << endl;

        return 0;

    }



    cout << b[((k - t) % (c - t)) + t] + 1 << endl;

}


// Faster C++ solution for the same problem (measured speedup: 3.3865568997476383x):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <utility>

#include <iostream>

#include <functional>

#include <bitset>

#include <algorithm>

#include <vector>

#include <forward_list>

#include <set>

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <tuple>

#include <numeric>

#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))

using namespace std;

using ll = long long;

using P = pair<ll, ll>;

const ll MOD = 1e9 + 7;

const ll INF = (1ll << 60);



int main(void)

{

    ll n, k;

    cin >> n >> k;



    vector<ll> a(n), p;

    map<ll, ll> m;



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

    {

        cin >> a[i];

        a[i]--;

        m[i] = INF;

    }



    ll time = 0;

    ll city = 0;

    ll start, end;



    while (true)

    {

        if (m[city] == INF)

        {

            m[city] = time;

            p.push_back(city);

            city = a[city];

        }

        else

        {

            start = m[city];

            end = time;

            break;

        }



        time++;

    }





    if (start > k)

    {

        cout << p[k] + 1 << endl;

        return 0;

    }



    cout << p[(k - start) % (start - end) + start] + 1 << endl;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

int n,m,l[310000],r[310000],tree[110000];

vector<int> vec[110000];

void add(int x,int y){

    for (;x<=m;x+=x&-x) tree[x]+=y;

}

int getsum(int x){

    int sum=0;

    for (;x;x-=x&(-x)) sum+=tree[x];

    return sum;

}

int main(){

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

    for (int i=1;i<=n;i++){

        scanf("%d%d",&l[i],&r[i]);

        vec[r[i]-l[i]+1].push_back(i);

    }

    for (int i=1;i<=m;i++){

        int ans=0;

        for (int j=0;j<(int)vec[i].size();j++)

            add(l[vec[i][j]],1),add(r[vec[i][j]]+1,-1);

        for (int j=i;j<=m;j+=i) ans+=getsum(j);

        n-=vec[i].size();

        printf("%d\n",ans+n);

    }

    return 0;

}

//

// Faster C++ solution for the same problem (measured speedup: 3.6389981563784253x):
#include <bits/stdc++.h>

#define F first

#define S second

using namespace std;

const int N=200003;

int n,m,cnt,f[N],kq[N];

pair< pair<int,int>,int> p[N*17];

void ud(int i)

{

    for (;i<=m*2;i+=(i&-i)) f[i]++;

}

int tv(int i)

{

    int res=0;

    for (;i>0;i-=(i&-i)) res+=f[i];

    return res;

}

int main()

{

   

    ios_base::sync_with_stdio(0);

    cin.tie(0);cout.tie(0);

    cin>>n>>m;

    for (int i=1;i<=n;i++)

    {

        cnt++;

        cin>>p[cnt].S>>p[cnt].F.F;

        p[cnt].F.S=-1;

    }

    for (int i=2;i<=m;i++)

    for (int j=i;j<=m*2;j+=i)

    {

        cnt++;

        p[cnt].F.F=j-1;

        p[cnt].F.S=i;

        p[cnt].S=j-i+1;

    }

    sort(p+1,p+cnt+1);

    for (int i=1;i<=cnt;i++)

    {

        int cs=p[i].F.S;

        //cout<<p[i].F.F<<" "<<p[i].S<<" "<<p[i].F.S<<"\n";

        if (cs<0) ud(p[i].S);

        else

        {

            kq[cs]+=tv(p[i].F.F)-tv(p[i].S-1);

            //cout<<cs<<" "<<p[i].F.F<<" "<<p[i].S-1<<"\n";

        }

    }

    for (int i=1;i<=m;i++) cout<<n-kq[i]<<"\n";

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cstdlib>

#include <set>

#include <stack>

#include <queue>

using namespace std;



#define X first

#define Y second

#define N 300010

#define M 400010

typedef long long ll;

typedef pair<int,int> pii;

const int Mod=1000000007;



int n,m;

int c[N];

vector<pii> g[N];



inline int Lowbit(int x){return x&(-x);}



void Add(int x,int v)

{

	while (x<=m)

	{

		c[x]+=v;

		x+=Lowbit(x);

	}

}



int Val(int x)

{

	int res=0;

	while (x)

	{

		res+=c[x];

		x-=Lowbit(x);

	}

	return res;

}



int main()

{

	//freopen("in.in","r",stdin);

	//freopen("out.out","w",stdout);

	

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

	for (int i=1;i<=n;i++)

	{

		int l,r; scanf("%d%d",&l,&r);

		g[r-l+1].push_back(make_pair(l,r));

	}

	int sz=0;

	for (int i=1;i<=m;i++)

	{

		int x=i,res=0;

		do

		{

			res+=Val(x);

			x+=i;

		}while (x<=m);

		

		for (int j=0;j<g[i].size();j++)

		{

			Add(g[i][j].X,1);

			Add(g[i][j].Y+1,-1);

		}

		printf("%d\n",res+n-sz);

		sz+=g[i].size();

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.665806127264591x):
#include<set>

#include<map>

#include<stack>

#include<queue>

#include<deque>

#include<cmath>

#include<cstdio>

#include<cctype>

#include<string>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

#define MAXN 300000

#define MAXM 100000

#define lowbit(x) (x&(-x))



using namespace std;



int n,m;

vector<int>gg[MAXM+80];

struct node{

	int a[MAXM+80];

	void add(int x,int A)

	{

		while(x<=m)

		{

			a[x]+=A;

			x+=lowbit(x);

		}

		return ;

	}

	int S(int x)

	{

		int sum=0;

		while(x)

		{

			sum+=a[x];

			x-=lowbit(x);

		}

		return sum;

	}

}tree;

int main()//You'll know it's a copy.

{

	int i,j,l,r,tmp=0,S;

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

	for(i=1;i<=n;i++)

	{

		scanf("%d%d",&l,&r);

		gg[r-l+1].push_back(l);

	}

	for(i=1;i<=m;i++)

	{

		S=0;

		for(j=i;j<=m;j+=i)

			S+=tree.S(j);

		for(j=0;j<gg[i].size();j++)

			tree.add(gg[i][j],-1),tree.add(i+gg[i][j],1);

		printf("%d\n",n-tmp-S);

		tmp+=gg[i].size();

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cstdlib>

#include <set>

#include <stack>

#include <queue>

using namespace std;



#define X first

#define Y second

#define N 300010

#define M 400010

typedef long long ll;

typedef pair<int,int> pii;

const int Mod=1000000007;



int n,m;

int c[N];

vector<pii> g[N];



inline int Lowbit(int x){return x&(-x);}



void Add(int x,int v)

{

	while (x<=m)

	{

		c[x]+=v;

		x+=Lowbit(x);

	}

}



int Val(int x)

{

	int res=0;

	while (x)

	{

		res+=c[x];

		x-=Lowbit(x);

	}

	return res;

}



int main()

{

	//freopen("in.in","r",stdin);

	//freopen("out.out","w",stdout);

	

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

	for (int i=1;i<=n;i++)

	{

		int l,r; scanf("%d%d",&l,&r);

		g[r-l+1].push_back(make_pair(l,r));

	}

	int sz=0;

	for (int i=1;i<=m;i++)

	{

		int x=i,res=0;

		do

		{

			res+=Val(x);

			x+=i;

		}while (x<=m);

		

		for (int j=0;j<g[i].size();j++)

		{

			Add(g[i][j].X,1);

			Add(g[i][j].Y+1,-1);

		}

		printf("%d\n",res+n-sz);

		sz+=g[i].size();

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 9.406089520695687x):
#include<cstdio>  

#include<iostream>  

#include<algorithm>  

#include<cstdlib>  

#include<cstring>

#include<string>

#include<climits>

#include<vector>

#include<cmath>

#include<map>

#define LL long long



using namespace std;



inline char nc(){

  static char buf[100000],*p1=buf,*p2=buf;

  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }

  return *p1++;

}



inline void read(int &x){

  char c=nc(),b=1;

  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;

  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;

}



inline void read(LL &x){

  char c=nc(),b=1;

  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;

  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;

}



int wt,ss[19];

inline void print(int x){

	if (x<0) x=-x,putchar('-'); 

	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}

}

inline void print(LL x){

	if (x<0) x=-x,putchar('-');

	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}

}



LL n,m;



int main()

{

    read(n);read(m);    

    LL x,y,z;

	vector<LL> a(m+10);

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

	{

		read(x);read(y);

        z=y-x+1;a[0]+=1;a[z]-=1;

        LL t=z+1,s;

        while(t<=m)

		{

            LL v=((x+t-1)/t);

            if((x+t-1)/t<=0) break;

            s=y/((x+t-1)/t);

            if(s>=t) a[t-1]+=1,a[s]-=1;

            if((x+t-1)/t<=1) break;

            t=max(s+1,(x+(v-1)-1)/(v-1));

        }

    }

    LL ans=0;

    for (int i=0;i<m;i++)

    	ans+=a[i],cout<<ans<<endl;

    return 0;

}