Problem:


Score : 700 points

Problem Statement

We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand.
When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.

The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second.
When the upper bulb no longer contains any sand, nothing happens.

Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X-a grams of sand (for a total of X grams).

We will turn over the sandglass at time r_1,r_2,..,r_K. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.

You are given Q queries.
Each query is in the form of (t_i,a_i).
For each query, assume that a=a_i and find the amount of sand that would be contained in bulb A at time t_i.

Constraints

1≤X≤10^9

1≤K≤10^5

1≤r_1<r_2< .. <r_K≤10^9

1≤Q≤10^5

0≤t_1<t_2< .. <t_Q≤10^9

0≤a_i≤X (1≤i≤Q)

All input values are integers.

Input

The input is given from Standard Input in the following format:

X
K
r_1 r_2 .. r_K
Q
t_1 a_1
t_2 a_2
:
t_Q a_Q

Output

For each query, print the answer in its own line.

Sample Input 1

180
3
60 120 180
3
30 90
61 1
180 180

Sample Output 1

60
1
120

In the first query, 30 out of the initial 90 grams of sand will drop from bulb A, resulting in 60 grams.
In the second query, the initial 1 gram of sand will drop from bulb A, and nothing will happen for the next 59 seconds. Then, we will turn over the sandglass, and 1 second after this, bulb A contains 1 gram of sand at the time in question.

Sample Input 2

100
1
100000
4
0 100
90 100
100 100
101 100

Sample Output 2

100
10
0
0

In every query, the upper bulb initially contains 100 grams, and the question in time comes before we turn over the sandglass.

Sample Input 3

100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10

Sample Output 3

19
52
91
10
58
42
100



Sample input:
180
3
60 120 180
3
30 90
61 1
180 180


Sample output:
60
1
120

Submission status: Runtime Error

Solution code:
def read_data_f(filename='arc082-e.dat'):
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), filename)
        with codecs.open(file_path, 'r', 'utf-8') as f:
            for each in f:
                lines.append(each.rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        lines.append(input())
        lines.append(input())
        lines.append(input())
        Q = int(lines[3])
        for i in range(Q):
            lines.append(input())

    return lines
  
def F_Sandglass():
    #
    # 180
    # 3
    # 60 120 180
    # 3
    # 30 90
    # 61 1
    # 180 180
    raw_data = read_data_f('arc082-f.dat')
    X = int(raw_data[0])
    K = int(raw_data[1])
    r = list(map(int, raw_data[2].split()))
    Q = int(raw_data[3])
    a = []
    t = []
    for i in range(Q):
        tt, aa = list(map(int, raw_data[i+4].split()))
        a.append(aa)
        t.append(tt)

    # print(r)
    # print(t)
    # print(a)

    time = 0
    i = j = 0
    U = X
    L = 0
    c = 0
    isUp = True
    time_diff = 0
    r.append(2000000000)
    t.append(1)


    while (i < K+1) and (time < t[Q-1]):
        while((time <= t[j] and t[j] < r[i])):
            time_diff_temp = t[j] - time
            if(isUp):
                c_temp = max(c - time_diff_temp, -X)
                U_temp = U
                L_temp = L
                if(L + c_temp) < 0:
                    L_temp = min(L + time_diff_temp, X)
            else:
                c_temp = min(c + time_diff_temp, X)
                U_temp = U
                if(U + c_temp) > X:
                    U_temp = max(U - time_diff_temp, 0)
                L_temp = L

            if(a[j] > U_temp):
                print(min(U_temp + c_temp, X))
            elif(a[j] < L_temp):
                print(max(L_temp + c_temp, 0))
            else:
                print(a[j] + c_temp)

            j += 1

        time_diff = r[i] - time
        if(isUp):
            c = max(c - time_diff, -X)
            if(L + c) < 0:
                L = -c
                if(L > U):
                    U = L

        else:
            c = min(c + time_diff, X)
            if(U + c) > X:
                U = X - c
                if(L > U):
                    L = U

        time = r[i]
        isUp = not isUp
        i += 1



    # result = remain(X, A[start_time], t[j] - start_time, start_status)
    # print(result)



F_Sandglass()

Submission status: Runtime Error

Solution code:
X = int(raw_input())
K = int(raw_input())
rs = map(int, raw_input().split(" "))
Q = int(raw_input())
qs = []

for q in xrange(Q):
  qs.append(map(int, raw_input().split(" ")))

memo = {}

l = len(qs)
for i in xrange(l):
  t = 0
  start = qs[i][1]
  s = start
  end = qs[i][0]
  pre = 0
  k = 0
  if start in memo:
    j = 0
    lm = len(memo) - 1
    while True:
      if j == lm or end < rs[j+1]: break
      j += 1
    k = j+1
    pre = rs[j]
    s = memo[start][j]
  while k < K:
    r = rs[k]
    if r >= end: break
    if k % 2 == 0:
      s = max(0, s - (r - pre))
    else:
      s = min(X, s + (r - pre))
    if start not in memo: memo[start] = {}
    memo[start][k] = s
    k += 1
    pre = r

  if k % 2 == 0:
    s = max(0, s - (end - pre))
  else:
    s = min(X, s + (end - pre))
  print s

Submission status: Runtime Error

Solution code:
X = int(raw_input())
K = int(raw_input())
rs = map(int, raw_input().split(" "))
Q = int(raw_input())
qs = []

for q in xrange(Q):
  qs.append(map(int, raw_input().split(" ")))

memo = {}

l = len(qs)
for i in xrange(l):
  t = 0
  start = qs[i][1]
  s = start
  end = qs[i][0]
  pre = 0
  k = 0
  if start in memo:
    j = 0
    lm = len(memo) - 1
    while True:
      if j == lm or end < rs[j+1]: break
      j += 1
    k = j+1
    pre = rs[j]
    s = memo[start][j]
  else:
    memo[start] = {}
  while k < K:
    r = rs[k]
    if r >= end: break
    if k % 2 == 0:
      s = max(0, s - (r - pre))
    else:
      s = min(X, s + (r - pre))
    memo[start][k] = s
    k += 1
    pre = r

  if k % 2 == 0:
    s = max(0, s - (end - pre))
  else:
    s = min(X, s + (end - pre))
  print s

Submission status: Runtime Error

Solution code:
# coding: utf-8
def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    X = II()
    K = II()
    r = ILI()
    Q = II()
    queries = [ILI() for __ in range(Q)]
    return X, K, r, Q, queries


def solve(X, K, r, Q, queries):
    l_ans = []
    r.insert(0, 0)
    dif_r = [r[i + 1] - r[i] for i in range(K)]
    for i in range(K):
        if i % 2 == 1:
            dif_r[i] = -dif_r[i]
    print(dif_r)
    # dif_r.append(10 ** 9)
    for query in queries:
        t, a = query
        dif_r_ind = 0
        now_state = 0
        now_time = 0
        ans = a
        while True:
            if now_time + dif_r[dif_r_ind] > t:
                if now_state == 1:
                    ans += t - now_time
                    ans = min(X, ans)
                else:
                    ans -= t - now_time
                    ans = max(0, ans)
                break
            else:
                if now_state == 1:
                    ans += dif_r[dif_r_ind]
                    ans = min(X, ans)
                else:
                    ans -= dif_r[dif_r_ind]
                    ans = max(0, ans)
                now_time += dif_r[dif_r_ind]
                now_state = (now_state + 1) % 2
                dif_r_ind += 1
                continue
        l_ans.append(ans)
    ans = "\n".join(map(str, l_ans))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()