Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C)]for _ in range(R)]

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
    print(max(dp[-1][-1]))
main()

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))

    ds_list = []
    for k in range(20):
        ds = [-1] * N
        ds_list.append(ds)
        half = 2 ** k
        divider = half * 2
        last = -1
        for i in range(N):
            if half <= A[i] % divider:
                ds[i] = last = i
            else:
                ds[i] = last


    cn = 0
    for r in range(N - 1, -1, -1):
        if r == 0:
            cn += 1
            break

        l = 0
        for k in range(20):
            p = ds_list[k][r]
            if p <= 0:
                continue
            else:
                l = max(l, ds_list[k][p - 1] + 1)
        cn += r - l + 1


    print(cn)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))

    ds_list = []
    for k in range(20):
        ds = [-1] * N
        ds_list.append(ds)
        half = 2 ** k
        divider = half * 2
        last = -1
        for i in range(N):
            if half <= A[i] % divider:
                ds[i] = last = i
            else:
                ds[i] = last


    cn = 0
    for r in range(N - 1, -1, -1):
        if r == 0:
            cn += 1
            break

        lp = -1
        for k in range(20):
            p = ds_list[k][r]
            if p <= 0:
                continue
            else:
                lp = max(lp, ds_list[k][p - 1])
        cn += r - lp


    print(cn)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
  ans = S[lr[i][0]-1:lr[i][1]].count("AC")
  print(ans)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]

dp = [0]*(N+1)
for i in range(N):
  if S[i:i+2]=="AC":
    dp[i+1] = dp[i] +1
  else:
    dp[i+1] = dp[i]

for i in range(Q):
  print(dp[lr[i][1]-1]-dp[lr[i][0]-1])
### BUGGY CODE ###

h,w,m=map(int, input().split())
a=[0]*m
hc=[0]*w
wc=[0]*h
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[]
wk=[]
for i in range(len(hc)):
	if hc[i]==hcm:
		hk.extend([i])
for i in range(len(wc)):
	if wc[i]==wcm:
		wk.extend([i])
c=0
for i in range(len(a)):
	if a[i][0] in wk:
		if a[i][1] in hk:
			c+=1
if c==len(hk)*len(wk):
	print(hcm+wcm-1)		
else:
	print(hcm+wcm)

### FIXED CODE ###

h,w,m=map(int, input().split())
a=[0]*m
hc=[0]*w
wc=[0]*h
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[0]*w
wk=[0]*h
for i in range(len(hc)):
	if hc[i]==hcm:
		hk[i]=1
for i in range(len(wc)):
	if wc[i]==wcm:
		wk[i]=1
c=0
for i in range(len(a)):
	if wk[a[i][0]]==1 and hk[a[i][1]]==1:
		c+=1
if c==sum(hk)*sum(wk):
	print(hcm+wcm-1)		
else:
	print(hcm+wcm)
### BUGGY CODE ###

#おわり、むり

N,W = map(int,input().split())

X,Y,Z = [],[],[]
for i in range(N):
    x,y,z = map(int,input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)  
    
dp = [[[0,0,0] for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i][0]= 0 #X
    dp[0][i][1]= 0 #Y
    dp[0][i][2]= 0 #Z
    
ans = 0
for fgo in range(0,8):
    FGO = [fgo%2,(fgo//2)%2,(fgo//4)%2]
    for i in range(N):
        for w in range(W+1):
            if w>=1:
                x = dp[i][w-1][0]+X[i]
                y = dp[i][w-1][1]+Y[i]
                z = dp[i][w-1][2]+Z[i]
                NOW = (x*pow(-1,FGO[0]))+(y*pow(-1,FGO[1]))+(z*pow(-1,FGO[2]))
                BEFORE = sum([dp[i][w][f]*pow(-1,FGO[f]) for f in range(3)])
                if NOW > BEFORE:
                    dp[i+1][w][0] = x
                    dp[i+1][w][1] = y
                    dp[i+1][w][2] = z
                else:
                    dp[i+1][w][0] = dp[i][w][0]
                    dp[i+1][w][1] = dp[i][w][1]
                    dp[i+1][w][2] = dp[i][w][2]
            else:
                dp[i+1][w][0] = dp[i][w][0]
                dp[i+1][w][1] = dp[i][w][1]
                dp[i+1][w][2] = dp[i][w][2]
    MAX_ABS = abs(dp[N][W][0])+abs(dp[N][W][1])+abs(dp[N][W][2])
    if MAX_ABS > ans: ans = MAX_ABS
    #print(MAX_ABS,FGO,dp)

print(ans)

### FIXED CODE ###

N,W = map(int,input().split())

L = []
for i in range(N):
    L.append(list(map(int,input().split())))
    
MAX_ANS = 0
for fgo in range(0,8):
    FGO = [pow(-1,fgo%2),pow(-1,(fgo//2)%2),pow(-1,(fgo//4)%2)]
    L = sorted(L,key=lambda x:x[0]*FGO[0]+x[1]*FGO[1]+x[2]*FGO[2],reverse=True)
    ans = 0
    for m in L[:W]:
        ans += m[0]*FGO[0] + m[1]*FGO[1] + m[2]*FGO[2]
    if ans > MAX_ANS: MAX_ANS = ans

print(MAX_ANS)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0] * (tlen + 1) for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = dpi[j] + 1
      else:
        if dpi1[j] > dpi[j1]:
          dpi1[j1] = dpi1[j]
        else:
          dpi1[j1] = dpi[j1]
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N

def solve(node, point):
    
    ans[node] += point



    if es.get(node, None) != None:
        for i in es[node]:
            solve(i, point+point_root[i])
solve(0, point_root[0])
print(*ans)

### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


print(*ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

N,A,B,C,D=map(int,input().split())
S="*"+input()

M={(C,D):True}

def f(X,Y):
    if (X,Y) in M:
        return M[(X,Y)]

    if C<X or D<Y:
        return False

    F=False
    try:
        if S[X+1]=="." and Y!=X+1:
            F|=f(X+1,Y)
    except:
        pass
    
    try:
        if S[X+2]=="." and Y!=X+2:
            F|=f(X+2,Y)
    except:
        pass

    try:
        if S[Y+1]=="." and X!=Y+1:
            F|=f(X,Y+1)
    except:
        pass
    
    try:
        if S[Y+2]=="." and X!=Y+2:
            F|=f(X,Y+2)
    except:
        pass

    M[(X,Y)]=F
    return F

if f(A,B):
    print("Yes")
else:
    print("No")



### FIXED CODE ###

N,A,B,C,D=map(int,input().split())
S="*"+input()

X=[0]*(N+1)
Y=[0]*(N+1)

for k in range(1,N+1):
    if S[k]=="#":
        X[k]=X[k-1]+1
    else:
        Y[k]=Y[k-1]+1

if max(X[A:max(C,D)+1])>=2:
    print("No")
else:
    if C<D:
        print("Yes")
    elif C>D:
        F=False
        for k in range(B,min(N,D+1)):
            F|=(S[k-1:k+2]=="...")

        if F:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  b.append(a.index(i+1)+1)
print(' '.join(map(str,b)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(range(len(a)), key=lambda k: a[k])
for i in range(n):
  b[i]+=1
print(' '.join(map(str,b)))
### BUGGY CODE ###

from collections import defaultdict
def main():
    s = list(input())
    dic1 = defaultdict(int)
    dic2 = defaultdict(int)
    n = len(s)
    for i in range(n):
        s[i] = int(s[i])
    for i in range(n):
        dic3 = defaultdict(int)
        for e in dic1:
            dic3[(e*10+s[i])%2019] = dic1[e]
            dic2[e] += dic1[e]
        dic1 = dic3
        dic1[s[i]] += 1 
    print(dic1[0]+dic2[0])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,2019))%2019
        dp[x] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

def factorial(n):
  ans = 1
  for i in range(n):
    ans *= i+1
    ans %= mod
  return ans


mod = 998244353
n = int(input())
s = input()
ans = 1
r,g,b = 0,0,0
rg,rb,gb = 0,0,0
for i in s:
  if i == "R":
    if gb > 0:
      ans *= gb
      gb -= 1
    elif g > 0:
      ans *= g
      g -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      rb += 1
    else:
      r += 1
  elif i == "G":
    if rb > 0:
      ans *= rb
      rb -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      gb += 1
    else:
      g += 1
  elif i == "B":
    if rg > 0:
      ans *= rg
      rg -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rb += 1
    elif g > 0:
      ans *= g
      g -= 1
      gb += 1
    else:
      b += 1
    ans %= mod 
print((factorial(n) * ans) % mod)


### FIXED CODE ###

def factorial(n):
  ans = 1
  for i in range(n):
    ans *= i+1
    ans %= mod
  return ans


mod = 998244353
n = int(input())
s = input()
ans = 1
r,g,b = 0,0,0
rg,rb,gb = 0,0,0
for i in s:
  if i == "R":
    if gb > 0:
      ans *= gb
      gb -= 1
    elif g > 0:
      ans *= g
      g -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      rb += 1
    else:
      r += 1
  elif i == "G":
    if rb > 0:
      ans *= rb
      rb -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      gb += 1
    else:
      g += 1
  elif i == "B":
    if rg > 0:
      ans *= rg
      rg -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rb += 1
    elif g > 0:
      ans *= g
      g -= 1
      gb += 1
    else:
      b += 1
  ans %= mod
print((factorial(n) * ans) % mod)
### BUGGY CODE ###

import os, sys, re, math


(H, W) = [int(n) for n in input().split()]


def set_moves(x, y, moves):
    if S[y + 1][x + 1] != '.':
        return
    if 0 <= grid[y][x] < moves:
        return

    grid[y][x] = moves
    set_moves(x, y - 1, moves + 1)
    set_moves(x, y + 1, moves + 1)
    set_moves(x - 1, y, moves + 1)
    set_moves(x + 1, y, moves + 1)


S = []
S.append('#' * (W + 2))
for i in range(H):
    S.append('#' + input() + '#')
S.append('#' * (W + 2))

result = 0
for gy in range(H):
    for gx in range(W):
        grid = []
        for i in range(H):
            grid.append([-1] * W)
        set_moves(gx, gy, 0)

        result = max(result, max([max(row) for row in grid]))

print(result)


### FIXED CODE ###

import os, sys, re, math


(H, W) = [int(n) for n in input().split()]


def set_moves(x, y, moves):
    if S[y + 1][x + 1] != '.':
        return
    if 0 <= grid[y][x] < moves:
        return

    grid[y][x] = moves
    set_moves(x, y - 1, moves + 1)
    set_moves(x, y + 1, moves + 1)
    set_moves(x - 1, y, moves + 1)
    set_moves(x + 1, y, moves + 1)


S = []
S.append('#' * (W + 2))
has_wall = False
for i in range(H):
    s = input()
    has_wall |= '#' in s
    S.append('#' + s + '#')
S.append('#' * (W + 2))

if not has_wall:
    result = W + H - 2
else:
    result = 0
    for gy in range(H):
        for gx in range(W):
            if S[gy + 1][gx + 1] != '.':
                continue
            grid = []
            for i in range(H):
                grid.append([-1] * W)
            set_moves(gx, gy, 0)

            result = max(result, max([max(row) for row in grid]))

print(result)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
miss = 0
max = p[0]
for i in range(n):
    s = p[0:i]
    if not s:
        continue
    if p[i] > p[i-1]:
        miss += 1
        continue
    if max < p[i]:
        max = p[i]
    if p[i] > max:
        miss += 1
        continue

    s = sorted(s,reverse=True)
    for j in range(i):
        if p[i] > s[j]:
            miss += 1
            break

print(n-miss)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
cnt = 0
t = p[0]

for i in range(n):
    if t >= p[i]:
        cnt += 1
        t = p[i]


print(cnt)
### BUGGY CODE ###

h, w, d = map(int, input().split())
a = []
dict = {}
for i in range(h):
	b = list(map(int, input().split()))
	for j in range(w):
		dict[b[j]] = [i,j]

dist = [0 for i in range(h*w)]
for i in range(1,h*w-d+1):
	dist[i-1] = abs(dict[i+d][1]-dict[i][1]) + abs(dict[i+d][0]-dict[i][0])
q = int(input())
for i in range(q):
	l, r = map(int, input().split())
	cnt = 0
	if l==r:
		print (cnt)
		continue
	for j in range(l,r+1,d):
		cnt += dist[j-1]
	cnt -= dist[r-1]
	print (cnt)


### FIXED CODE ###

h, w, d = map(int, input().split())
a = []
dict = {}
for i in range(h):
	b = list(map(int, input().split()))
	for j in range(w):
		dict[b[j]] = [i,j]

dist = [0 for i in range(h*w)]
for i in range(1,h*w-d+1):
	dist[i-1] = abs(dict[i+d][1]-dict[i][1]) + abs(dict[i+d][0]-dict[i][0])

for i in range(h*w-d-1,-1,-1):
	dist[i] += dist[i+d]

q = int(input())
for i in range(q):
	l, r = map(int, input().split())
	ans = dist[l-1] - dist[r-1]
	print (ans)
### BUGGY CODE ###

n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort()

dp = [[0 for _ in range(t)] for _ in range(n+1)]

ans = 0
i = 0
for a, b in ab:
    ans = max(ans, max(dp[i]) + b)
    if a < t:
        dp[i+1][a] = max(dp[i][a], b)
    for j in range(1, t):
        if dp[i][j] > 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if a + j < t:
                dp[i+1][a+j] = max(dp[i][a+j], dp[i][j] + b)
    i += 1

ans = max(ans, max(dp[n]))

print(ans)

### FIXED CODE ###

n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort()

dp = [[0 for _ in range(t)] for _ in range(n+1)]

ans = 0
i = 0
for a, b in ab:
    ans = max(ans, max(dp[i]) + b)
    if a < t:
        dp[i+1][a] = max(dp[i][a], b)
    for j in range(1, t):
        if dp[i][j] > 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if a + j < t:
                dp[i+1][a+j] = max(dp[i][a+j], dp[i][j] + b)
    i += 1

ans = max(ans, max(dp[n]))

print(ans)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter.get(0, 0)
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter.get(nv, 0)
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

import bisect
import numpy as np
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
s=np.array(s)
t=np.array(t)
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    l1=X-t[t1]
    if (t[t1]-X)>(X-t[t1-1]):
        l1=X-t[t1-1]
    s1=bisect.bisect_right(s,X)
    l2=X-s[s1]
    if (s[s1]-X)>(X-s[s1-1]):
        l2=X-s[s1-1]
    l3=bisect.bisect_right(s,X-l1)
    l4=bisect.bisect_right(t,X-l2)
    print(min(abs(l1)+min(s[l3]-X+l1,X-l1-s[l3-1]),abs(l2)+min(t[l4]-X+l2,X-l2-t[l4-1])))



### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

lac = list()
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        lac.append(i)


for i in range(q):
    l, r = map(int, input().split())
    print(sum(1 for x in lac if l-1 <= x <= r-2))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

lc = [0]
c = 0
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        c += 1
    lc.append(c)

for i in range(q):
    l, r = map(int, input().split())
    print(lc[r-1]-lc[l-1])
### BUGGY CODE ###

n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()] + [0]
tTotal = sum(t)*2
speed = []
for i in range(tTotal+1):
    speed.append(min(i/2,(tTotal-i)/2))

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)


### FIXED CODE ###

n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
tTotal = sum(t)*2
speed = [min(i/2,(tTotal-i)/2) for i in range(tTotal+1)]
#?

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans = 0
for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        c_candidate = [k for k in l[j+1:] if k < a+b]
        ans += len(c_candidate)

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans = 0
for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ans += bisect.bisect_left(l, a+b)-j-1

print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(" ")))

def bubble(A, N):
    count = 0
    flag = True
    while flag == True:
        for j in range(N-1, 0, -1):
            flag = False
            if A[j] < A[j - 1]:
                A[j -1],A[j] = A[j], A[j - 1]
                count += 1
                flag = True
    print(" ".join(map(str, A)))
    print(count)

bubble(A, N)            

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))


def bubble_sort(A, N):
    cnt = 0
    flag = True
    while(flag):
        flag = False
        for i in range(N-1, 0, -1):
            if(A[i-1] > A[i]):
                A[i-1], A[i] = A[i], A[i-1]
                cnt += 1
                flag = True

    print(" ".join(list(map(str, A))))
    print(cnt)

bubble_sort(A, N)
### BUGGY CODE ###

import re

n,q=map(int,input().split())
s=input()
pat=r'.*?AC.*?'
regex=re.compile(pat)
res=0

for i in range(q):
	l,r=map(int,input().split())
	l-=1
	res=len(regex.findall(s[l:r]))
	print(res)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ac=[0]*n
tmp=0
for i in range(1,n):
	if s[i-1]=='A' and s[i]=='C':
		tmp+=1
	ac[i]=tmp

for i in range(q):
	l,r=map(int,input().split())
	print(ac[r-1]-ac[l-1])