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

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

lst=[[0]*w for i in range(h)]

lst[0][0]={abs(a[0][0]-b[0][0]):1}
# print(lst)
d=deque([(0,0)])
while d:
    now=d.popleft()
    if now[0]+1<h:
        ab=abs(a[now[0]+1][now[1]]-b[now[0]+1][now[1]])
        if lst[now[0]+1][now[1]]==0:
            d.append((now[0]+1,now[1]))
            lst[now[0]+1][now[1]]={}

        for i in lst[now[0]][now[1]].keys():
            lst[now[0]+1][now[1]][i+ab]=1
            lst[now[0]+1][now[1]][abs(i-ab)]=1

    # print(lst)
    if now[1]+1<w:
        ab=abs(a[now[0]][now[1]+1]-b[now[0]][now[1]+1])
        if lst[now[0]][now[1]+1]==0:
            d.append((now[0],now[1]+1))
            lst[now[0]][now[1]+1]={}

        for i in lst[now[0]][now[1]].keys():
            lst[now[0]][now[1]+1][i+ab]=1
            lst[now[0]][now[1]+1][abs(i-ab)]=1
    # print(d)
    # print(lst)
anslst=list(lst[-1][-1].keys())
anslst.sort(key=lambda x: abs(x))
print(abs(anslst[0]))

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
### BUGGY CODE ###

n,m = map(int,input().split())
a,b = [0 for _ in range(n)],[0 for _ in range(n)]

for i in range(n):
    a[i],b[i] = map(int,input().split())

bought = 0
ans = 0

if len(a) == 1:
    print(a[0]*m)
    exit()

while(bought <= m):
    remain = m - bought
    amin = min(a)
    bmin = b[a.index(amin)]
    if bmin <= remain:
        ans += amin*bmin
        bought += bmin
        b.remove(bmin)
        a.remove(amin)
    else:
        ans += amin*remain
        break
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort(key = lambda a:a[0])
bought = 0
price = 0
for i in range(n):
    remain = m - bought
    if a[i][1] < remain:
        bought += a[i][1]
        price += a[i][0] * a[i][1]
    else:
        price += a[i][0]*remain
        print(price)
        exit()
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input().replace("BC","X")
#    print(s)
    c=0
    while "AX" in s:
        c+=s.count("AX")
        s=s.replace("AX","XA")
    print(c)    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input().replace("BC","X")
#    print(s)
    c=0
    d=0
    for i in s:
        if i=="A":
            c+=1
        elif i=="X":
            d+=c
        else:
            c=0
    print(d)
#    while "AX" in s:
#        s=s.replace("AX","XA")
#        print(s)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def expect(n):
    return (int(n)+1)/2
N, K = map(int,input().split()) 
P = list(map(expect,input().split()))
sumlist = [sum(P[i:i+K]) for i in range(N-K+1)]
print(max(sumlist))

### FIXED CODE ###

def expect(n):
    return (int(n)+1)/2
N, K = map(int,input().split()) 
P = list(map(expect,input().split()))
sumlist = [sum(P[0:K])]
sumnumber = sum(P[0:K])
for i in range(N-K):
    sumnumber -=P[i]
    sumnumber +=P[i+K]
    sumlist.append(sumnumber)
print(max(sumlist))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    s = S()
    l = len(s)

    fm = {}
    def f(i):
        if i in fm:
            return fm[i]
        t = set()
        r = 0
        for j in range(i, l):
            t.add(s[j])
            if len(t) == 26:
                t = set()
                r += 1
        fm[i] = r + 1
        return r + 1

    r = []
    def g(i):
        t = set()
        m = inf
        k = set()
        for j in range(i, l):
            if s[j] not in t:
                ji = f(j+1)
                if m > ji:
                    m = ji
                    k = set([(s[j], j)])
                elif m == ji:
                    k.add((s[j], j))
                t.add(s[j])
                if len(t) == 26:
                    break
        if len(t) < 26:
            for k in string.ascii_lowercase:
                if k not in t:
                    r.append(k)
                    break
        else:
            tr = sorted(list(k))[0]
            r.append(tr[0])
            g(tr[1]+1)

    g(0)

    return ''.join(r)

print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a = S()
    l = len(a)
    t = {}
    for c in string.ascii_lowercase:
        t[c] = l
    b = [(1,0,0) for _ in range(l)]
    b.append((1,'a',l))
    b.append((0,'',l+1))

    for c,i in reversed(list(zip(a,range(l)))):
        t[c] = i
        b[i] = min([(b[t[d]+1][0] + 1,d,t[d]+1) for d in string.ascii_lowercase])

    r = ''
    i = 0
    while i < l:
        r += b[i][1]
        i = b[i][2]
    return r

print(main())
### BUGGY CODE ###

def gcd(a,b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def gcd_l(A):
    if len(A) == 1:
        return A[0]
    x = gcd(A[0], A[1])
    if len(A) == 2:
        return x
    for i in range(2, len(A)):
        x = gcd(x, A[i])
    return x

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

B = []
x = A[0]
for i in range(N):
    x = gcd(x, A[i])
    B.append(x)

ans = 1
for i in range(1, N-1):
    ans = max(ans, gcd(B[i-1], gcd_l(A[i+1:])))
ans = max(ans, B[N-1], gcd_l(A[1:]))

print(ans)


### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def gcd_l(A):
    if len(A) == 1:
        return A[0]
    x = gcd(A[0], A[1])
    if len(A) == 2:
        return x
    for i in range(2, len(A)):
        x = gcd(x, A[i])
    return x

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

B = []
C = []
x = A[0]
y = A[-1]
for i in range(N):
    x = gcd(x, A[i])
    B.append(x)
    y = gcd(y, A[N-1-i])
    C.append(y)
    
ans = 1

for i in range(1, N-1):
    ans = max(ans, gcd(B[i-1], C[N-2-i]))

ans = max(ans, B[N-2], C[N-2])

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

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

r,g,b,n = get_nums_l()

ans = 0
for ra in range(n//r + 1):
    for ga in range(n//g + 1):
        now = r * ra + g * ga
        nokori = n - now
        if nokori >= 0 and nokori % b == 0:
            ans += 1

print(ans)

### FIXED CODE ###

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

r,g,b,n = get_nums_l()

ans = 0
for ra in range(n//r + 1):
    for ga in range(n//g + 1):
        now = r * ra + g * ga
        nokori = n - now
        if nokori >= 0 and nokori % b == 0:
            ans += 1

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

import bisect
import sys
input = sys.stdin.readline


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = max(i, tree.get_maximum(i, max_index))
    tree.update(i, max_move)
    ans_array[i] = (ans_array[i+1] + ans_array[max_move + 1]) % mod

print(ans_array[0])


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def get_maximum(self, l, r):
        L = l+self.len
        R = r+self.len
        ANS = -1 << 30

        while L < R:
            if L & 1:
                ANS = max(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = max(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = max(i, tree.get_maximum(i, max_index))
    tree.update(i, max_move)
    ans_array[i] = (ans_array[i+1] + ans_array[max_move + 1]) % mod

print(ans_array[0])
### BUGGY CODE ###

#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(N-1)]
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i] =a,b            #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
aa=[]
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A[i] #n_a,n_b =i番目の辺とつながっている頂点
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(color_node[n_a][-1]) +1
    while True:
        #color +=1
        q,color =divmod(color,color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            color_node[n_a].append(color)    #前の頂点に使った色を追加、
            color_node[n_b].append(color)    #前の頂点に使った色を追加、

            break
        else:
            color +=1      
#出力
print(color_max)
for i in color_edge:
    print(i)

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

import sys
sys.stdin.readline
INF = float("inf")

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def solve():
    n = int(input())
    s = int(input())
    if s == n: return n+1
    if s > n: return -1
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s: return b
    ans = INF
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == INF:
        ans = -1
    return ans

if __name__ == "__main__":
    print(solve())

### FIXED CODE ###

import sys
sys.stdin.readline
INF = float("inf")

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def solve():
    n = int(input())
    s = int(input())
    if s == n: return n+1
    if s > n: return -1
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s: return b
    ans = INF
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if b < 2: continue
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == INF:
        ans = -1
    return ans

if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

n=int(input())
s=input()
ans=10**10
ans1=n-s.count('#')
ans2=n-s.count('.')
for i in range(n):
  tmp=s[:i].count('#')+s[i+1:].count('.')
  if tmp<ans:
    ans=tmp
print(min(ans,ans1,ans2))

### FIXED CODE ###

n=int(input())
s=input()+'?'
ans=10**10
arr=[0]*n
ans1=n-s.count('#')
ans2=n-s.count('.')
if s[0]=='.':
  arr[0]=1
for i in range(1,n):
  if s[i]=='.':
    arr[i]=arr[i-1]+1
  else:
    arr[i]=arr[i-1]
for i in range(1,n):
  tmp=(i-arr[i-1])+(arr[-1]-arr[i])
  if tmp<ans:
    ans=tmp
print(min(ans,ans1,ans2))
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.asarray(list(map(int, input().split())))
inv = np.asarray([[-1 if j in [(i + 2 * k + 1) % n for k in range(n//2)] else 1 for j in range(n)] for i in range(n)])
print(*np.dot(inv, a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
r = []
c = 0
for j in range(n):
  if j % 2 == 1:
    c -= a[j]
  else:
    c += a[j]
r.append(c)
for i in range(n-1):
  r.append((a[i] - r[i] // 2) * 2)
print(*r)
### BUGGY CODE ###

# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    def main2(afters):
        #print('step %d' % cl)
        n = 0
        for i in range(N):
            for j in range(N):
                before = c[i][j]
                after = afters[(i + j) % 3]
                if before  == after:
                    continue
                iwakan = D[before-1][after-1]
                n += iwakan
        return n
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = main2((c1+1, c2+1, c3+1))
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()


### FIXED CODE ###

# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    E = [[0] * C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i]==s[j]:
            continue
        else:
            for k in range(j+1,n):
                if s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k<n and s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
            ans -= 1

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

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [99**99]
t=[int(input()) for _ in range(B)] + [99**99]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))


### FIXED CODE ###

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [10**11]
t=[int(input()) for _ in range(B)] + [10**11]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    S = input()

    ans = 0

    for i in range(10**4):
        if '0011' in S:
            ans += 4 * S.count('0011')
            S = S.replace('0011', '')
        if '1010' in S:
            ans += 4 * S.count('1010')
            S = S.replace('1010', '')
        if '0101' in S:
            ans += 4 * S.count('0101')
            S = S.replace('0101', '')
        if '1100' in S:
            ans += 4 * S.count('1100')
            S = S.replace('1100', '')
    for i in range(10**4):
        if '01' in S:
            ans += 2 * S.count('01')
            S = S.replace('01', '')
        if '10' in S:
            ans += 2 * S.count('10')
            S = S.replace('10', '')
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    S = input()

    ans = min(S.count('0'), S.count('1'))
    print(ans * 2)


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

def main():
    s = input()
    t = input()
    s2 = s * 2
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[] for _ in range(lens)]
    for i in range(lens):
        for j in sett:
            index[i].append(s2[i:].index(j))
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        ans += index[n % lens][j] + 1
        n += index[n % lens][j] + 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    t = input()
    s2 = s * 2
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[-1] * len(sett) for _ in range(lens)]
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        if index[n][j] == -1:
            index[n][j] = s2[n:].index(i)
        ans += index[n][j] + 1
        n += index[n][j] + 1
        n %= lens
    print(ans)


if __name__ == '__main__':
    main()