int q2(int x){
    int power = 0;
    while(1<<power)<=(x>>1){
        power++;
    }
    return power;
}

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
struct node{
  int idx;
  int s,e;
}line[2*N];
int n, m, power;
vector<vector<int>> st;
vector<int> ans;
// 将环状展开为线性
int lgp(int n){
  int ans = 0;
  while((1<<ans)<=(n>>1)){
    ans++;
  }
  return ans;
}
void build(){
  /*如C(6,1),m=8
  * 有1 2 3 4 5 6 7 8 9 10 11 ...
                      1  2  3...
    故转化后的C是(6,9)
  */
  for (int i = 1;i<=n;i++){
    if (line[i].s>line[i].e){
      line[i].e+=m;
    }
  }
  // 按起始点排序
  sort(line+1,line+1+n,[&](const node a, const node b){return a.s<b.s;});
  // 对点在线性上进行复制即 A B C D A' B' C' D'
  for(int i =1;i<=n;i++){
    line[i+n].idx = line[i].idx;
    line[i+n].s = line[i].s+m;
    line[i+n].e = line[i].e+m;
  }
  // 新线段数量
  int e = n<<1;
  // 寻找跳一步的最大值, 应满足下一条线段开头<=当前线段结尾
  /*如线段开头如下
  3
    34 
      56
        89
          102
  到102就超过了结尾，故选择到89
  */
  for (int i =1, j = 1;i<=e;i++){
    while(j+1<=e&&line[j+1].s<=line[i].e){
      j++;
    }
    st[i][0]=j;
  }
  // 倍增
  for (int p = 1; p<=power; p++){
    for (int i = 1;i<=e;i++){
      st[i][p]=st[st[i][p-1]][p-1];
    }
  }
}
int jump(int i){
  // i号线段的目标点是line[i].s+m
  int tar = line[i].s+m,cur = i, next, ans = 1;
  for(int p = power; p>=0;p--){
    next = st[cur][p];
    if (next!=0&&line[next].e<tar){
      ans+=1<<p;
      cur = next;
    }
  }
  return ans+1; // 计算的是小于目标点，+1即为到达 

}
void solve() {
  
  cin >> n >> m;
  
  for(int i =1;i<=n;i++){
    line[i].idx = i; 
    cin >> line[i].s >> line[i].e;
  }
  power = lgp(n);
  st = vector<vector<int>>(2*n+1, vector<int>(power+1,0));
  ans = vector<int>(n+1,0);
  build();
  for (int i = 1;i<=n;i++){
    ans[line[i].idx] = jump(i);
  }
  for (int i = 1;i<=n;i++) cout << ans[i]<<' ';

}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,m;
vector<vector<int>> dp1;
vector<vector<int>> dp2;
int query1(int l, int r){
  int j = (int)log2(r-l+1);
  return max(dp1[l][j],dp1[r-(1<<j)+1][j]);
}
int query2(int l, int r){
  int j = (int)log2(r-l+1);
  return min(dp2[l][j],dp2[r-(1<<j)+1][j]);
}
int main()
{
  ios
  cin >> n >> m;
  dp1 = vector<vector<int>> (n,vector<int>(log2(n)+5,0));
  dp2 = vector<vector<int>> (n,vector<int>(log2(n)+5,0));
  vector<int> arr(n);
  for (int i = 0;i<n;i++) cin >> arr[i];
  for (int i = 0;i<n;i++) {
    dp1[i][0] = arr[i];
    dp2[i][0] = arr[i];
  } 
  for (int j = 1;j<=log2(n);j++){
    for (int i = 0; i+(1<<j)-1<n;i++){
      dp1[i][j] = max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
      dp2[i][j] = min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);

    }
  }
  int l,r ;
  while (m--){
    cin >> l >> r;
    cout << query1(l-1,r-1)-query2(l-1,r-1)<<endl;
  }
  return 0;
}