Let’s consider applying backward analysis to this game. As an example, let’s analyze the sample.

• Initial state: \([0,\infty)\)=Draw
• Second player \([1,2]\): \([0,0]\)=First player wins, \([1,\infty)\)=Draw
• First player \([3,4]\): \([0,2]\)=Second player wins, \([3,4]\)=First player wins, \([5,\infty)\)=Draw
• Second player \([1,2]\): \([0,0]\)=First player wins, \([1,4]\)=Second player wins, \([5,5]\)=First player wins, \([6,\infty)\)=Draw
• First player \([1,3]\): \([0,0]\)=Second player wins, \([1,3]\)=First player wins, \([4,5]\)=Second player wins, \([6,8]\)=First player wins, \([9,\infty)\)=Draw

For instance, if it’s the first player’s turn to take \([L,R]\) stones, a backward analysis of this turn reveals the following:

• If the number of stones left in the pile is within \([0,L-1]\), then the second player wins.
• A previous winning interval for the first player \([A,B]\) moves to \([A+L,B+R]\). This interval can overlap with others.
• A previous winning interval for the second player \([A,B]\) moves to \([A+R,B+L]\). If this interval collapses, it vanishes.

The same process occurs for the second player’s turn.

At any point, if we arrange these intervals, the outcomes have one of the following forms:

• …(First player wins)(Second player wins)(First player wins)(Draw)
• …(Second player wins)(First player wins)(Second player wins)(Draw)

Essentially, ignoring draws, we have a structure of alternating winners.

Let’s consider how to implement this backward analysis using data structures.

Firstly, ignoring intervals collapsing or overlapping, all winning intervals for one player expand by length \(l\), while all winning intervals for the other player shrink by length \(l\).
Naive processing takes linear time with respect to the number of intervals, but by holding offsets corresponding to the lengths of the intervals and only adjusting the base value, the processing can be completed in constant time.
Additionally, it is possible to see which intervals collapse when moving this base value. This series of operations can be performed using sets or priority queues.

Now, let’s handle cases where intervals collapse or overlap.
When collapsing an interval, we want to know which intervals are adjacent on both sides. It is convenient to manage this like a linked list. Also, from the structure of the outcomes, when an interval collapses, the adjacent intervals merge (unless draws are involved).

The rest is simply implementing this strategy. The details beyond this point are complex and omitted, but keeping track of each interval’s length and then restoring the specific number of stones before answering queries might make things a bit easier.

This solution can solve the problem in time complexity \(O(N \log N)\).

Sample Implementation (C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

typedef struct{
  long long lef;
  long long rig;
}linknode;

linknode inil={-1,-1};

void shrink(long long tg,long long &llh,vector<linknode> &llis){
  long long le=llis[tg].lef;
  long long re=llis[tg].rig;
  if(le!=-1){llis[le].rig=re;}
  if(re!=-1){llis[re].lef=le;}
  if(tg==llh){
    llh=re;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  long long n;
  cin >> n;
  string s;
  // cin >> s;
  for(int i=0;i<n;i++){
    if(i%2==0){s.push_back('A');}
    else{s.push_back('B');}
  }
  vector<long long> l(n),r(n);
  for(long long i=0;i<n;i++){
    cin >> l[i] >> r[i];
  }

  long long ofs=0;
  vector<long long> ofsv(n);
  set<pl> sta,stb;
  long long llh=-1;
  vector<linknode> llis(n,inil);

  long long ls=0,rs=0;
  for(long long i=n-1;i>=0;i--){
    ls+=l[i]; rs+=r[i];
    if(i==0 || s[i]!=s[i-1]){
      if(s[i]=='A'){
        // shrink B win
        ofs+=(rs-ls);
        while(!stb.empty()){
          auto it=stb.begin();
          if((*it).first<ofs){
            pl od=(*it);
            stb.erase(it);
            long long le=llis[od.second].lef;
            long long re=llis[od.second].rig;
            if(le!=-1 && re!=-1){
              long long newg=(ofs-ofsv[le])+(ofs-ofsv[re])+2-(ofs-(*it).first);
              sta.erase({ofsv[le],le});
              sta.erase({ofsv[re],re});
              ofsv[le]=ofs-newg;
              sta.insert({ofsv[le],le});
              shrink(re,llh,llis);
            }
            shrink(od.second,llh,llis);
          }
          else{break;}
        }

        // add B win
        if(llh!=-1 && s[i]==s[llh]){
          stb.erase({ofsv[llh],llh});
          long long newg=(ls-1)+(ofsv[llh]-ofs)+1;
          ofsv[llh]=ofs+newg;
          stb.insert({ofsv[llh],llh});
        }
        else{
          ofsv[i]=ofs+(ls-1);
          llis[i].rig=llh;
          if(llh!=-1){llis[llh].lef=i;}
          llh=i;
          stb.insert({ofsv[i],i});
        }
      }
      else{
        // shrink A win
        ofs-=(rs-ls);
        while(!sta.empty()){
          auto it=sta.end();it--;
          if((*it).first>ofs){
            pl od=(*it);
            sta.erase(it);
            long long le=llis[od.second].lef;
            long long re=llis[od.second].rig;
            if(le!=-1 && re!=-1){
              long long newg=(ofsv[le]-ofs)+(ofsv[re]-ofs)+2-((*it).first-ofs);
              stb.erase({ofsv[le],le});
              stb.erase({ofsv[re],re});
              ofsv[le]=ofs+newg;
              stb.insert({ofsv[le],le});
              shrink(re,llh,llis);
            }
            shrink(od.second,llh,llis);
          }
          else{break;}
        }

        // add A win
        if(llh!=-1 && s[i]==s[llh]){
          sta.erase({ofsv[llh],llh});
          long long newg=(ls-1)+(ofs-ofsv[llh])+1;
          ofsv[llh]=ofs-newg;
          sta.insert({ofsv[llh],llh});
        }
        else{
          ofsv[i]=ofs-(ls-1);
          llis[i].rig=llh;
          if(llh!=-1){llis[llh].lef=i;}
          llh=i;
          sta.insert({ofsv[i],i});
        }
      }

      ls=0; rs=0;
    }
  }

  long long clef=0;
  set<pl> st;
  long long v=llh;
  while(v!=-1){
    if(s[v]=='A'){
      // cout << "B win " << ofsv[v]-ofs+1 << "\n";
      st.insert({clef,-1});
      clef+=(ofsv[v]-ofs+1);
    }
    else{
      // cout << "A win " << ofs-ofsv[v]+1 << "\n";
      st.insert({clef,1});
      clef+=(ofs-ofsv[v]+1);
    }
    v=llis[v].rig;
  }
  st.insert({clef,0});
  st.insert({8e18,0});

  long long q;
  cin >> q;
  while(q>0){
    q--;
    long long c;
    cin >> c;
    auto it=st.lower_bound({c,8e18}); it--;
    if((*it).second==1){cout << "Alice\n";}
    else if((*it).second==-1){cout << "Bob\n";}
    else{cout << "Draw\n";}
  }
  return 0;
}