#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include "jumpgame.h"
#define ll long long
using namespace std;
typedef pair<ll,int> P;
typedef vector<ll> LL;
vector <P> tmp,v;ll ans;
namespace SGT
{
struct node{int ls,rs;ll num,add;}t[30000000];int tot=1;
inline void upd(int p,ll z)
{t[p].num+=z,t[p].add+=z;}
inline void push_up(int p)
{t[p].num=max(t[t[p].ls].num,t[t[p].rs].num);}
inline void push_down(int p)
{upd(t[p].ls,t[p].add),upd(t[p].rs,t[p].add),t[p].add=0;}
void add(ll l,ll r,int p,ll x,ll y,ll z)
{
if(x<=l&&y>=r){upd(p,z);return ;}
if(!t[p].ls) t[p].ls=++tot,t[p].rs=++tot;
ll mid=(l+r)>>1;push_down(p);
if(x<=mid) add(l,mid,t[p].ls,x,y,z);
if(y>mid) add(mid+1,r,t[p].rs,x,y,z);
push_up(p);return ;
}
void change(ll l,ll r,int p,ll x,ll z)
{
if(l==r){t[p].num=max(t[p].num,z);return ;}
if(!t[p].ls) t[p].ls=++tot,t[p].rs=++tot;
ll mid=(l+r)>>1;push_down(p);
if(x<=mid) change(l,mid,t[p].ls,x,z);
else change(mid+1,r,t[p].rs,x,z);
push_up(p);return ;
}
ll query(ll l,ll r,int p,ll x,ll y)
{
if((x<=l&&y>=r)||!t[p].ls) return t[p].num;
ll mid=(l+r)>>1;ll ans=0;push_down(p);
if(x<=mid) ans=max(ans,query(l,mid,t[p].ls,x,y));
if(y>mid) ans=max(ans,query(mid+1,r,t[p].rs,x,y));
return ans;
}
};using namespace SGT;
ll play_game(ll n,int m,ll k,LL l,LL r)
{
for(ll p:l) tmp.push_back({p,1});
for(ll p:r) tmp.push_back({p+1,-1});
sort(tmp.begin(),tmp.end());
for(auto now:tmp)
{
if(!v.empty()&&v.back().first==now.first)
v.back().second+=now.second;
else v.push_back(now);
}
for(int i=0,val=0;i<v.size()-1;++i)
{
ll pos=v[i].first,nxt=v[i+1].first;
ll len=nxt-pos,cur=0;val+=v[i].second;
if(len>=k)
{
ans+=(len/k-1)*val;
ll l=pos%k,r=(nxt-1)%k;
if(len%k)
{
if(l<=r)
add(0,k-1,1,l,r,val);
else
{
add(0,k-1,1,l,k-1,val);
add(0,k-1,1,0,r,val);
}
}
cur=t[1].num,add(0,k-1,1,0,k-1,val);
}
else
{
ll l=pos%k,r=(nxt-1)%k;
if(l<=r)
{
cur=query(0,k-1,1,l,r);
add(0,k-1,1,l,r,val);
}
else
{
cur=max(cur,query(0,k-1,1,l,k-1));
cur=max(cur,query(0,k-1,1,0,r));
add(0,k-1,1,l,k-1,val);
add(0,k-1,1,0,r,val);
}
}
change(0,k-1,1,nxt%k,cur);
}
return ans+t[1].num;
}