local mmi, mma = math.min, math.max
local capacity = io.read("*n")
local t = {}
local k = io.read("*n")
for i = 1, k do
  t[i] = {}
  t[i][1] = i
  t[i][2] = io.read("*n")
end
local q = io.read("*n")
for i = 1, q do
  t[k + i] = {}
  t[k + i][1] = k + i
  t[k + i][2] = io.read("*n")
  t[k + i][3] = io.read("*n")
end
table.sort(t, function(a, b) return a[2] < b[2] end)
local leftidx, rightidx = 0, capacity
local leftpos, rightpos = 0, capacity
local lasttime = 0
local way = false
for i = 1, k + q do
  if t[i][1] <= k then
    local len = t[i][2] - lasttime
    if way then
      rightpos = rightpos + len
      if capacity < rightpos then
        rightidx = mma(0, rightidx - (rightpos - capacity))
        rightpos = capacity
      end
      leftpos = mmi(leftpos + len, capacity)
      leftidx = mmi(leftidx, rightidx)
    else
      leftpos = leftpos - len
      if leftpos < 0 then
        leftidx = mmi(capacity, leftidx - leftpos)
        leftpos = 0
      end
      rightpos = mma(rightpos - len, 0)
      rightidx = mma(rightidx, leftidx)
    end
    lasttime = t[i][2]
    way = not way
  else
    local len = t[i][2] - lasttime
    local ri, li = rightidx, leftidx
    local rp, lp = rightpos, leftpos
    if way then
      rp = rp + len
      if capacity < rp then
        ri = mma(0, ri - (rp - capacity))
        rp = capacity
      end
      lp = mmi(lp + len, capacity)
      li = mmi(li, ri)
    else
      lp = lp - len
      if lp < 0 then
        li = mmi(capacity, li - lp)
        lp = 0
      end
      rp = mma(rp - len, 0)
      ri = mma(ri, li)
    end
    local p = t[i][3]
    if p <= li then
      t[i][4] = lp
    elseif ri <= p then
      t[i][4] = rp
    else
      t[i][4] = lp + p - li
    end
  end
end
table.sort(t, function(a, b) return a[1] < b[1] end)
for i = k + 1, k + q do
  print(t[i][4])
end
