\(K\) に依存しない解法を紹介します。
まず、負荷と回復をまとめて捉えるため、 \(A_i := A_i - B_i\) と置きなおします。
また、 \(\max(-K,\min(K,A_i))\) と置き換えても問題ないため、そのようにします。このようにすることで、考えるべき値域が狭くなって楽になります。

全てのクエリについてまとめて求解する (オフラインでの求解) ことを考えます。そのため、各クエリを

• タスク \(L_i\) の開始時に始点を設置
• タスク \(R_i\) の終了時に終点を設置

というように分解しておきます。

タスクを \(1,2,\dots,N\) の順で舐めていきながら、 (現在のストレス値, そのストレス値になるクエリの集合) の集合をうまく管理することを考えます。

• オフセット \(h\) を導入し、 \(h=0\) で初期化する。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • タスク \(i\) の開始時の始点を追加する。
    • このとき、現在のオフセット \(h\) も紐づけて記録しておく。
  • \(h\) から \(A_i\) を減算する。
  • この時点で記録された当時のオフセットが \(h+K\) 以上であるデータについて、それらは限界に到達するため取り出してマージし、現在の \(h\) を記録した新たなデータとして再開する。 … ★
  • この時点で記録された当時のオフセットが \(h\) 未満であるデータについて、それらはストレス値が \(0\) に合わせられるため取り出してマージし、現在の \(h\) を記録した新たなデータとして再開する。 … ★★
  • タスク \(i\) の終了時の終点を処理する。

★ や ★★ で一度同時に取り出されたデータについて、それらがストレス値 \(0\) に合わせられるため、そこから先のタスクに関しては (限界に達した回数の差異を調整すれば) 統一的に扱えるという点がミソです。

上記のマージは、 マージテク(small-to-large) と呼ばれる方法 (具体的には小さなデータ構造の各要素を大きなデータ構造にマージする) で全体 \(O(Q \log Q)\) で処理できます。

少し実装が煩雑です(詳しい方法は実装例を参照してください)が、全体で時間計算量 \(O((N+Q) \log Q)\) で処理できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int N,K,Q;
  cin >> N >> K >> Q;
  vector<int> A(N);
  for(auto &nx : A){
    int aa,bb;
    cin >> aa >> bb;
    nx=max(-K,min(K,aa-bb));
  }
  vector<vector<int>> ql(N);
  vector<vector<int>> qr(N);
  for(int i=0;i<Q;i++){
    int l,r;
    cin >> l >> r;
    l--; r--;
    ql[l].push_back(i);
    qr[r].push_back(i);
  }

  vector<int> alive(Q,1);
  vector<int> vc;
  vector<int> vh;
  vector<vector<int>> ve;
  vector<int> inv(Q);
  vector<pi> res(Q,{0,0});
  set<pi> st;
  int h=0;
  for(int i=0;i<N;i++){
    if(!ql[i].empty()){
      for(auto &nx : ql[i]){ inv[nx]=vc.size(); }
      st.insert({h,vc.size()});
      vc.push_back(0);
      vh.push_back(h);
      ve.push_back(ql[i]);
    }

    h-=A[i];

    {
      // merge large side
      vector<int> vlis;
      while((!st.empty()) && (*st.rbegin()).first-h>=K){
        vlis.push_back((*st.rbegin()).second);
        auto it=st.end(); it--;
        st.erase(it);
      }
      if(vlis.size()>=1){
        int x=vlis[0];
        for(int j=1;j<vlis.size();j++){
          int y=vlis[j];
          if(ve[x].size()<ve[y].size()){swap(x,y);}
          int ofs=vc[y]-vc[x];
          for(auto &nx : ve[y]){
            if(alive[nx]==0){continue;}
            ve[x].push_back(nx);
            inv[nx]=x;
            res[nx].first+=ofs;
          }
          ve[y].clear();
        }
        vc[x]++;
        vh[x]=h;
        st.insert({h,x});
      }
    }
    {
      // merge small side
      vector<int> vlis;
      while((!st.empty()) && (*st.begin()).first-h<0){
        vlis.push_back((*st.begin()).second);
        st.erase(st.begin());
      }
      if(vlis.size()>=1){
        int x=vlis[0];
        for(int j=1;j<vlis.size();j++){
          int y=vlis[j];
          if(ve[x].size()<ve[y].size()){swap(x,y);}
          int ofs=vc[y]-vc[x];
          for(auto &nx : ve[y]){
            if(alive[nx]==0){continue;}
            ve[x].push_back(nx);
            inv[nx]=x;
            res[nx].first+=ofs;
          }
          ve[y].clear();
        }
        vh[x]=h;
        st.insert({h,x});
      }
    }

    for(auto &nx : qr[i]){
      int pos=inv[nx];
      res[nx].first+=vc[pos];
      res[nx].second=vh[pos]-h;
      alive[nx]=0;
    }
  }
  for(auto &nx : res){
    cout << nx.first << " " << nx.second << "\n";
  }
  return 0;
}