output_description: Print your answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: import sys
  
  readline = sys.stdin.readline
  
  
  def mergeup(Av, Aw, vw):
      v, w = vw
      rv, rw = [], []
      N = len(Av)
      idx = 0
      jdx = 0
      for _ in range(2 * N):
          if idx == N or Aw[idx] > Aw[jdx] + w:
              if Aw[jdx] + w > limit:
                  break
              rw.append(Aw[jdx] + w)
              rv.append(Av[jdx] + v)
              jdx += 1
          else:
              rw.append(Aw[idx])
              rv.append(Av[idx])
              idx += 1
  
      return rv, rw
  
  
  def mergedown(Av, Aw, vw):
      v, w = vw
      resv, resw = [], []
      N = len(Av)
      idx = 0
      jdx = 0
      for _ in range(2 * N):
          if jdx == N:
              resv.append(Av[idx])
              resw.append(Aw[idx])
              idx += 1
              continue
          if Aw[idx] <= Aw[jdx] - w:
              resv.append(Av[idx])
              resw.append(Aw[idx])
              idx += 1
          else:
              if Aw[jdx] - w < 0:
                  jdx += 1
                  continue
              resv.append(Av[jdx] + v)
              resw.append(Aw[jdx] - w)
              jdx += 1
      return resv, resw
  
  
  limit = 10**5
  N = int(readline())
  VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
  BS = min(N, 1 << 10)
  Q = int(readline())
  VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]
  
  
  Rv = [[0] for _ in range(BS + 1)]
  Rw = [[0] for _ in range(BS + 1)]
  for i in range(1, BS):
      for vm, wm in zip(*mergeup(Rv[i // 2], Rw[i // 2], VW[i])):
          if Rv[i][-1] < vm:
              Rv[i].append(vm)
              Rw[i].append(wm)
  
  ans = [0] * (Q + 1)
  for i in range(1, Q + 1):
      v, l = VL[i]
      Kv, Kw = [0], [l]
      while v >= BS:
          Kv, Kw = mergedown(Kv, Kw, VW[v])
          v >>= 1
      cnt = len(Rv[v]) - 1
      ctr = 0
      for j in range(len(Kv) - 1, -1, -1):
          kv, kw = Kv[j], Kw[j]
          while kw < Rw[v][cnt]:
              cnt -= 1
          ctr = max(ctr, kv + Rv[v][cnt])
      ans[i] = ctr
  
  print("\n".join(map(str, ans[1:])))
  
problem_description: Statement
  
  When you asked some guy in your class his name, he called himself S, where S
  is a string of length between 3 and 20 (inclusive) consisting of lowercase
  English letters. You have decided to choose some three consecutive characters
  from S and make it his nickname. Print a string that is a valid nickname for
  him.
samples: [{"input": "takahashi", "output": "tak\n    \n\n* * *"}, {"input": "naohiro", "output": "nao"}]