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

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    d = {}
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])
                d[(i, j)] = -1

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1]+=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

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

N = int(input())

ans = 0

N = N - int(str(N)[-1])

while True:
    if N < 10:
        break
    ans += str(N).count('0')
    N = N-10

print(ans)

### FIXED CODE ###

N = int(input())

if N%2 != 0:
    print(0)
    exit()

ans = 0

denom = 10
while True:
    if denom > N:
        break

    ans += N//denom
    denom = denom*5

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

import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            while k != j:
                if L[i] < L[j] + L[k] and L[j] < L[i] + L[k]:
                    count += 1
                k -= 1
    print(count)


if __name__ == "__main__":
    main() 


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            count += k - j
    print(count)


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

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    n,k=map(int,input().split())
    p=list(map(int,input().split()))
    temp=0
    max=0
    maxi=0
    for i in range(k):
        temp=sum(p[0:k])
    if n>=2:
        for i in range(1,n-k+1):
            temp-=p[i-1]
            temp+=p[i+k-1]
            if temp>max:
                max=temp
                maxi=i
    total=0
    for i in range(maxi,maxi+k):
        total+=(1+p[i])

    print(total/2)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    n,k=map(int,input().split())
    p=list(map(int,input().split()))
    temp=0
    max=sum(p[0:k])
    maxi=0
    temp=max
    if n>=2:
        for i in range(1,n-k+1):
            temp-=p[i-1]
            temp+=p[i+k-1]
            if temp>max:
                max=temp
                maxi=i
    total=(max+k)/2
#    for i in range(maxi,maxi+k):
 #       total+=(1+p[i])

    print(total)

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

from sys import stdin

def main():
    N, Q = map(int, input().split())
    S = input()
    LR = [tuple(map(int, input().split())) for _ in [0] * Q]

    for l, r in LR:
        n = S[l-1:r].count('AC')
        print(n)

input = lambda: stdin.readline().rstrip()
main()


### FIXED CODE ###

from sys import stdin

def main():
    N, Q = map(int, input().split())
    S = input()
    LR = [tuple(map(int, input().split())) for _ in [0] * Q]

    cnt = [0] * N
    prev = ''
    for i, s in enumerate(S):
        if prev + s == 'AC':
            cnt[i] = cnt[i-1] + 1
        else:
            cnt[i] = cnt[i-1]
        prev = s

    for l, r in LR:
        n = cnt[r-1] - cnt[l-1]
        print(n)

input = lambda: stdin.readline().rstrip()
main()
### BUGGY CODE ###

n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dif=[]
for i in range(n):
  if v[i]>c[i]:
    dif.append(v[i]-c[i])

ans=0
for i in range(1 << len(dif)):
    sum=0
    for j in range(len(dif)):
        if ((i>>j)&1)==1:
            sum += dif[j]
    ans = max(ans, sum)
print(ans)

### FIXED CODE ###

n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dif=[]
for i in range(n):
  if v[i]>c[i]:
    dif.append(v[i]-c[i])
print(sum(dif))
### BUGGY CODE ###

n = int(input())
s = input()
dp = [[0]*(n) for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(i-1, -1, -1):
        if i == (n-1):
            if s[i] == s[j]:
                dp[i][j] += 1
            continue

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        

ans = 0
for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        ans = max(ans, min(abs(j-i), dp[i][j]))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0]*(n) for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(i-1, -1, -1):
        if i == (n-1):
            if s[i] == s[j]:
                dp[i][j] += 1
            continue

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        

ans = 0
for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        ans = max(ans, min(abs(j-i), dp[i][j]))
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
nums = [[] for i in range(N)]
for i in range(N):
    t, d = map(int, input().split())
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

a,b,k = na()
f = [i for i in range(a,b+1)]
ans = []
ans += f[:k]
ans_d = []
ans_d += f[::-1][:k]
ans += ans_d
for i in sorted(set(ans)):
    print(i)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

a,b,k = na()
if (b-a+1) // 2 >= k:
    ans = list(range(a,a+k)) + list(range(b-k+1,b+1))
else:
    ans = list(range(a,b+1))
for i in ans:
    print(i)
### BUGGY CODE ###

inp=input().split(" ")
H=int(inp[0])
W=int(inp[1])
N=int(inp[2])
square=[]
plot=[]
times=[0 for i in range(10)]
times[0]=(H-2)*(W-2)
from collections import defaultdict
count=defaultdict(lambda:0)
def check(a,b,square):
    for i in range(3):
        for j in range(3):
            if a-i>=0 and b-j>=0 and a+2-i<=H-1 and b+2-j<=W-1:
                square.append([a-i,b-j])
for i in range(N):
    plot.append(list(map(int,input().split(" "))))
    check(plot[i][0]-1,plot[i][1]-1,square)
for i in range(len(square)):
    count[str(square[i])]+=1
for i in count.values():
    times[i]+=1
    times[0]-=1
for i in range(len(times)):
    print(times[i])

### FIXED CODE ###

inp=input().split(" ")
H=int(inp[0])
W=int(inp[1])
N=int(inp[2])
plot=[]
times=[0 for i in range(10)]
times[0]=(H-2)*(W-2)
from collections import defaultdict
count=defaultdict(lambda:0)
def check(a,b,count):
    for i in range(3):
        for j in range(3):
            if a-i>=0 and b-j>=0 and a+2-i<=H-1 and b+2-j<=W-1:
                count[str([a-i,b-j])]+=1
for i in range(N):
    plot.append(list(map(int,input().split(" "))))
    check(plot[i][0]-1,plot[i][1]-1,count)
for i in count.values():
    times[i]+=1
    times[0]-=1
for i in range(len(times)):
    print(times[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
B = [0] + B
C.sort()
C = [0] + C
# A > B > Cなる組み合わせの数を求める
ans = 0

for a in A:
    left, right = 0, N
    if a >= B[N]:
        continue
    while abs(left - right) > 1:
        mid = (left + right) // 2
        if B[mid] > a:
            right = mid
        else:
            left = mid
    nB = B[right:]
    for nb in nB:
        left2, right2 = 0, N
        if nb >= C[N]:
            continue
        while abs(left2 - right2) > 1:
            mid2 = (left2 + right2) // 2
            if C[mid2] > nb:
                right2 = mid2
            else:
                left2 = mid2
        ans += N - right2 + 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()
ans = 0

for b in B:
    if b <= A[0] or b >= C[N-1]:
        continue
    # Aに対して
    l, r = -1, N
    while abs(l - r) > 1:
        mid = (l + r) // 2
        if A[mid] < b:
            l = mid
        else:
            r = mid
    # Bに対して
    l2, r2 = -1, N
    while abs(l2 - r2) > 1:
        mid = (l2 + r2) // 2
        if C[mid] > b:
            r2 = mid
        else:
            l2 = mid
    ans += (l+1) * (N - r2)
print(ans)
### BUGGY CODE ###

I=lambda:list(map(int,input().split()))
p,n=I()
l=I()
mi=10**9+7
for i in range(n):
    te=0
    j=i
    while (j+1)%n!=i%n:
        if j==n-1:
            te+=abs(l[-1]-sum(l))
        else:
            te+=abs(l[j%n]-l[(j+1)%n])
        j+=1
    mi=min(te,mi)
l=l[::-1]
for i in range(n):
    te=0
    j=i
    while (j+1)%n!=i%n:
        if j==n-1:
            te+=abs(l[-1]-sum(l))
        else:
            te+=abs(l[j%n]-l[(j+1)%n])
        j+=1
    mi=min(te,mi)


print(mi)
        


### FIXED CODE ###

I=lambda:list(map(int,input().split()))
p,n=I()
l=I()
ne=[]
ma=10**9+7
for i in range(n-1):
    ne.append(abs(l[i]-l[i+1]))
if l[-1]==p:
    ne.append(l[0]-l[-1])
else:    
    ne.append(l[0]+abs(p-l[-1]))
g=sum(ne)
for i  in ne:
    ma=min(ma,g-i)
print(ma)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0

for i in range(n):
  a=max(0,i-k)
  for j in range(a,i):
    dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp=[100000000000000000]*n
dp[0]=0
for i in range(1,n):
  for j in range(k):
    if i > j:
      dp[i] = min(dp[i],dp[i-j-1]+abs(h[i]-h[i-j-1]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    t = a[i]
    a.remove(t)
    print(max(a))
    a.insert(i,t)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = a[:]
mx = max(b)
b.remove(mx)
mx2 = max(b)

for t in a:
    if t == mx:
        print(mx2)
    else:
        print(mx)
### BUGGY CODE ###

import collections

N = int(input())
num_list = list(map(int,input().split()))
memo = [0]*(N+1)
memo_flg = [False]*(N+1)
c = collections.Counter(num_list)

def calc(k):
    num = num_list[k]
    
    if(memo_flg[num] is True):
        return memo[num]
    ans = 0
    
    for i,j in c.items():
        if(i==num):
            j -= 1
        ans += (j*(j-1))//2
    memo[num] = ans
    memo_flg[num] = True
    return ans

[print(calc(i)) for i in range(N)]


### FIXED CODE ###

import collections

N = int(input())
num_list = list(map(int,input().split()))
memo = [0]*(N+1)
memo_flg = [False]*(N+1)
counter = [0] * (N+1)
counter_ans = [0] * (N+1)

for i in num_list:
    counter[i] += 1
for i in range(N+1):
    counter_ans[i] = (counter[i]*(counter[i]-1))//2

all_sum = sum(counter_ans)
def calc(k):
    num = num_list[k]
    
    if(memo_flg[num] is True):
        return memo[num]
    ans = 0
    
    wrong = counter_ans[num]
    c = counter[num]-1
    right = (c*(c-1))//2
    
    ans = all_sum - wrong + right
    memo[num] = ans
    memo_flg[num] = True
    return ans

[print(calc(i)) for i in range(N)]
### BUGGY CODE ###

MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*(13) for _ in range(len(S)+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul *= 10 % 13
print(dp[l][5]%MOD)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N,Ma,Mb=map(int,input().split())

dp = [[10**18 for _ in range(401)] for _ in range(401)]

dp[0][0]=0
for i in range(N):
    a,b,c=map(int,input().split())
    for ca in range(361, -1, -1):
        for cb in range(361, -1, -1):
            dp[ca+a][cb+b] = min(dp[ca+a][cb+b],dp[ca][cb]+c)

ans = 10**18
for i in range(1, 40):
    if ans > dp[Ma * i][Mb * i]:
        ans = dp[Ma * i][Mb * i]
        
if ans == 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N,Ma,Mb=map(int,input().split())

dp = [[10**18 for _ in range(401)] for _ in range(401)]

dp[0][0]=0
for i in range(N):
    a,b,c=map(int,input().split())
    for ca in range(i * 10, -1, -1):
        for cb in range(i * 10, -1, -1):
            dp[ca+a][cb+b] = min(dp[ca+a][cb+b],dp[ca][cb]+c)

ans = 10**18
for ca in range(401):
    for cb in range(401):
        if not ca*Mb == cb*Ma or ca == 0:
            continue
        if ans > dp[ca][cb]:
            ans = dp[ca][cb]
        
if ans == 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
*A,=map(int,input().split())

point=[0]*N
count_X=0
count_Y=0
i=0
while all(j<3 for j in point):
    if all(j<2 for j in point):
        count_X+=1
    point[i]+=1
    i=A[i]-1
    if any(k>1 for k in point):
        count_Y+=1
count_Y-=1

if K>=count_X:
    Z=count_X+(K-count_X)%count_Y
else:
    Z=K

i=0
ans=1
while i<Z:
    ans=A[ans-1]
    i+=1

print(ans)
    

### FIXED CODE ###

N,K=map(int,input().split())
*A,=map(int,input().split())

point=[0]*N
count_X=0
count_Y=0
i=0
while point[i]!=3:
    if point[i]<2:
        count_X+=1
    point[i]+=1
    i=A[i]-1
    if point[i]>1:
        count_Y+=1
count_Y-=1

if K>=count_X:
    Z=count_X+(K-count_X)%count_Y
else:
    Z=K

i=0
ans=1
while i<Z:
    ans=A[ans-1]
    i+=1

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

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, A, B = map(int, sys.stdin.readline().split())

    isBlue = True
    ret = []
    for n in range(N):
        for a in range(A):
            if len(ret) == N:
                break
            ret.append('b')

        for b in range(B):
            if len(ret) == N:
                break
            ret.append('r')

        if len(ret) == N:
            break

    print(ret.count('b'))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, A, B = map(int, sys.stdin.readline().split())

    ret = 0
    cnt = N // (A + B)

    if N % (A + B) == 0:
        print(int(A * cnt))
    elif N < A + B:
        print(min(N, A))
    else:
        ret += A*cnt
        if N - (A+B)*cnt <= A:
            ret += N - (A+B)*cnt
        else:
            ret += A

        print(ret)


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

n,q = [int(x) for x in input().split()]
s = input()
lst = []
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    lst.append([l,r])

for i in range(q):
    print(s[lst[i][0]-1:lst[i][1]].count("AC"))

### FIXED CODE ###

n,q = [int(x) for x in input().split()]
s = input()

t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)

for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
value1=2*(10**10)
for zzz in range(Q):
    x=int(input())
    value=value1
    s1=bisect_left(S,x)
    for s in range(s1-1,s1+1):
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in range(t1-1,t1+1):
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in range(t1-1,t1+1):
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in range(s1-1,s1+1):
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)


### FIXED CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
X=[int(input()) for i in range(Q)]
value1=2*(10**10)
for x in X:
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)