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

def main():
    import heapq
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    h2 = []
    heapq.heapify(h)
    for i in range(n):
        heapq.heappush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = heapq.heappop(h)
        i=-i
        temp = i-a[j]
        sho=temp//(b[j-1]+b[(j+1)%n])
        if  sho==0:
            h2.append((i, j))
            continue
        cnt += sho
        b[j] -= (b[j-1]+b[(j+1)%n])*sho
        heapq.heappush(h, (-b[j], j))
    h2.sort(key=lambda x: x[1])
    for i in range(n):
        if a[i] != h2[i][0]:
            print(-1)
            return 0
    print(cnt)


main()


### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

N = int(input())
H_list = input().split(" ")
max_count = 0
for i in range(0, N):
    S = int(H_list[i])
    count = 0
    for j in range(i + 1, N):
        if S >= int(H_list[j]):
            S = int(H_list[j])
            count += 1
        else:
            break
    if max_count < count:
        max_count = count
    if max_count >= N - i:
        break
print(max_count)



### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

cost=[0]*200010
G=[[] for _ in range(200010)]
visited=[False]*200010
visited[0]=True

def dfs(s):
  global cost
  global G
  global visited
  for e in G[s]:
    if visited[e]==False:
      cost[e]+=cost[s]
      visited[e]=True
      dfs(e)
      visited[e]=False

def main():
  global cost
  global G
  global visited
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

  for i in range(q):
    p,x=LI()
    p-=1
    cost[p]+=x
  dfs(0)

  return ' '.join([str(x) for x in cost[:n]])

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]
level=[-1]*nmax

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    if level[e]==-1:
      level[e]=level[s]+1
    if level[e]>level[s]:
      l[e]+=l[s]
      dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  level[0]=0
  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

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

n = int(input())
s = input()
ans = {}
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if not s[i]+s[j]+s[k] in ans:
                ans[s[i]+s[j]+s[k]] = 0
print(len(ans))

### FIXED CODE ###

n = input()
s = input()
ans = 0
for i in range(10):
    a = s.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = s.find(str(j),a+1)
        if b == -1:
            continue
        for k in range(10):
            c = s.find(str(k),b+1)
            if c == -1:
                continue
            ans += 1
print(ans)
### BUGGY CODE ###

INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    a = [int(input()) for i in range(m)]
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

    for i in range(2,n+1):
        if issafe(i-1,a):
            dp[i] += dp[i-1]
        if issafe(i-2,a):
            dp[i] += dp[i-2]

    print(dp[n]%(10**9+7))


def issafe(i,a):
    if i in a:
        return False
    else:
        return True


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    issafe = [True]*n
    for i in range(m):
        a = int(input())
        issafe[a] = False
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

    for i in range(2,n+1):
        if issafe[i-1]:
            dp[i] += dp[i-1]
        if issafe[i-2]:
            dp[i] += dp[i-2]

    print(dp[n]%(10**9+7))


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

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i, n):
        if s[i] == s[j]:
            continue
        for k in range(j, n):
            if s[j] == s[k] or s[i] == s[k] or j-i == k-j:
                continue

            ans += 1

print(ans)

### FIXED CODE ###

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

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

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n: break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

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

H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque()
    seen = [[0]*(W+2)] + [[0] + [1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h,0))
                seen[h+1][w+1] =0
    while que:
        a,b,k = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1]:
                seen[ny+1][nx+1] = 0
                que.append((nx,ny,k+1))
    return k
print(bfs())

### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

n=int(input())
S=list(input())
ans=0
for i in range(n-2):
  for j in range(i,n-1):
    for k in range(j,n):
      if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k] and (j-i != k-j):
        ans+=1
print(ans)

### FIXED CODE ###

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

nr=s.count('R')
ng=s.count('G')
nb=s.count('B')
ans=nr*ng*nb
cnt=0

for i in range(n-1):
  for j in range(i+1,n):
    k=2*j-i
    if k>=n or k<=j:
      continue
    if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      cnt+=1
print(ans-cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import copy
for i in B:
    new_A=copy.copy(A)
    while i in new_A:
        new_A.remove(i)
    print(len(A)-len(new_A))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

from bisect import bisect_left

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        j = bisect_left(color, a)
        color.insert(j, a)
        color_min = a
    else:
        j = bisect_left(color, a)
        del color[j-1]
        j = bisect_left(color, a)
        color.insert(j, a)
        color_min = color[0]

print(len(color))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left

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

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(M) :
    b,c = map(int,input().split())
    A.extend([c]*b)
ans = sum(sorted(A,reverse=True)[:N])

print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

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

import sys,fractions
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

gcd = gcd_list(l)
L = [l[i]//gcd for i in range(N)]
lcm = lcm_list(L)

# print(lcm,gcd,'aaa')
ANS = 0
for i in range(N):
    elm = L[i]
    ANS += (lcm//elm)
    ANS %= u
print(ANS)

### FIXED CODE ###

import sys
from fractions import gcd
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

lcm = 1
s = 0
for i in range(N):
    k = l[i]
    g = gcd(k,lcm)
    t = k//g
    lcm = lcm*t
    s = s*t + lcm//k
print(s%u)
### BUGGY CODE ###

s=list(input())
for _ in range(int(input())):
  t=list(input().split())
  if int(t[0])==1:
    s.reverse()
  else:
    if int(t[1])==1:
      s.insert(0, t[2])
    else:
      s.append(t[2])
print(''.join(s))

### FIXED CODE ###

from collections import deque
s=deque(input())
f=False
for _ in range(int(input())):
  t=list(input().split())
  if t[0]=='1':
    if f is False:
      f = True
    else:
      f = False
  else:
    if t[1]=='1':
      if f is False:
      	s.appendleft(t[2])
      else:
        s.append(t[2])
    else:
      if f is False:
      	s.append(t[2])
      else:
        s.appendleft(t[2])
x=''.join(map(str,s))
if f is False:
	print(x)
else:
  print(x[::-1])
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
from collections import deque
queue=deque([st])
deep=[1]*(n**2)
while queue:
	p=queue.popleft()
	for x in d[p]:
		queue.append(x)
		deep[x]=deep[p]+1
print(max(deep))

### FIXED CODE ###

def main():
	from collections import deque
	n=int(input())
	battle=n*(n-1)//2
	lis=[[] for i in range(battle)]
	num=[-1]*(n**2)
	cnt=-1
	for x in range(n**2):
		if x//n<x%n:
			cnt+=1
			num[x]=cnt
	for i in range(n):
		a=list(map(int,input().split()))
		for j in range(n-2):
			x=a[j]-1
			y=a[j+1]-1
			px=num[min(i*n+x,x*n+i)]
			py=num[min(i*n+y,y*n+i)]
			lis[px].append(py)
	node_in=[0]*(battle)
	for i in range(battle):
		for x in lis[i]:
			node_in[x]+=1
	zero=deque([])
	days=[10**9]*(battle)
	for i in range(battle):
		if node_in[i]==0:
			zero.append(i)
			days[i]=1
	while zero:
		r=zero.popleft()
		for x in lis[r]:
			node_in[x]-=1
			if node_in[x]==0:
				zero.append(x)
				days[x]=days[r]+1
	if 10**9 in days:
		print(-1)
	else:
		print(max(days))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

# [l,r]での素数リスト
def primes(l,r):
    is_prime = [True] * (r + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(r**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, r + 1, i):
            is_prime[j] = False
    return len([i for i in range(l,r + 1) if is_prime[i] and i % 2 == 1 and is_prime[(i+1)//2]])

import sys
input = sys.stdin.readline

Q = int(input())
lr = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    print(primes(lr[i][0],lr[i][1]))

### FIXED CODE ###

MAXN = 10**5 + 1

# c[i]: [0,i]での素数の個数
f = [False] * (MAXN)
for i in range(2,MAXN):
    if not f[i]:
        for j in range(i+i,MAXN,i):
            f[j] = True
c = [0] * (MAXN)
for i in range(3,MAXN):
    if not f[i] and not f[(i+1)//2]:
        c[i] += 1
    c[i] += c[i-1]

Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    print(c[R] - c[L-1])
### BUGGY CODE ###

N=int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return len(divisors)

x=0
for c in range(1,N):
    x+=make_divisors(N-c)
print(x)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
ans=0
yakusu=[0]*(10**7+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        yakusu[j]+=1
for i in range(len(yakusu)):
    ans+=(i)*yakusu[i]
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
yakusu=[0]*(10**7+1)
for i in range(1,N+1):
    for j in range(i,N+1,i):
        yakusu[j]+=1
for i in range(len(yakusu)):
    ans+=(i)*yakusu[i]
print(ans)
### BUGGY CODE ###

class Node:
  def __init__(self):
    self.counter = 0
    self.childs = []
  def add_child(self, node):
    self.childs.append(node)

N, Q = [int(i) for i in input().split()]
ndic = {}
for i in range(1, N+1):
  ndic[i] = Node()
for i in range(N-1):
  a, b = [int(i) for i in input().split()]
  ndic[a].add_child(ndic[b])

for i in range(Q):
  p, x = [int(i) for i in input().split()]
  stack = []
  stack.append(ndic[p])
  while(len(stack) > 0):
    node = stack.pop()
    node.counter += x
    for n in node.childs:
      stack.append(n)
ans = ""
for k, v in ndic.items():
  ans += str(v.counter) + " "
print(ans[:-1])

### FIXED CODE ###

n, q = map(int, input().split())
 
tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
 
cnt = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
 
check = [0]*n
 
tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)
 
 
print(" ".join(map(str, cnt)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

def solve():
    N = int(input())
    #(i,j) -> E[i-1][j-2], i < j
    E = [[0 for j in range(N+1)] for i in range(N+1)]
    E[1][2] = 1
    cl = {1}
    for j in range(3,N+1):
        for i in range(j-1,0,-1):
            cl_ = cl.copy()
            for k in range(i+1,j):
                if E[i][k] == E[k][j]:
                    cl_ -= {E[i][k]}
            if cl-cl_:
                if cl_:
                    E[i][j] = min(cl_)
                else:
                    E[i][j] = max(cl)+1
                    cl.add(E[i][j])
            else:
                E[i][j] = 1
                
                    
    
    res = '\n'.join(' '.join(map(str,e[i+2:])) for i, e in enumerate(E[1:]))
    return str(res)

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

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N = int(input())
    E = np.array([[0,1],[0,0]])
    for i in range((N-1).bit_length()-1):
        E_ = E+(E>0)
        E = np.vstack([np.hstack([E_,np.ones_like(E)]),np.hstack([np.zeros_like(E), E_])])
    res = '\n'.join(' '.join(map(str,e[i+1:N])) for i, e in enumerate(E[:N]))
    return str(res)

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

N, M = map(int,input().split())
H = []
L = [[] for k in range(M+1)]

for k in range(N):
    P = list(map(int,input().split()))[1:]
    H.append(P)
    for e in P:
        L[e].append(k+1)

G = [0 for k in range(N+1)]
G[1] = 1
Q = [H[0]]
while len(Q) > 0:
    ima = Q.pop()
    for tsugi in ima:
        for e in L[tsugi]:
            if G[e] == 0:
                G[e] = 1
                Q.append(H[e-1])

for k in range(1,N+1):
    if G[k] == 0:
        print("NO")
        exit(0)
print("YES")

### FIXED CODE ###

N, M = map(int,input().split())
H = []
L = [[] for k in range(M+1)]

for k in range(N):
    P = list(map(int,input().split()))[1:]
    H.append(P)
    for e in P:
        L[e].append(k+1)

G = [0 for k in range(N+1)]
G[1] = 1
Q = [H[0]]
while len(Q) > 0:
    ima = Q.pop()
    for tsugi in ima:
        for e in L[tsugi]:
            if G[e] == 0:
                G[e] = 1
                if len(H[e-1]) > 1:
                    Q.append(H[e-1])

for k in range(1,N+1):
    if G[k] == 0:
        print("NO")
        exit(0)
print("YES")
### BUGGY CODE ###

import numpy as np

N = int(input())
l = list(map(int, input().split()))
nl = np.array(l)
a = []
for i in range(N-1):
    x = nl[0:i+1]
    y = nl[i+1:N]
    a.append(abs(x.sum() - y.sum()))
print(min(a))

### FIXED CODE ###

import numpy as np

N = int(input())
l = list(map(int, input().split()))
nl = np.array(l)
X = nl.sum()
a = []
x = 0
for i in range(N-1):
    x = x + nl[i]
    a.append(abs(2 * x - X))
print(min(a))
### BUGGY CODE ###


d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
l=len(t)
modlist=[10**i%13 for i in range(l)]
for n,c in enumerate(t):
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*modlist[n]+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d,e=e,d
    mul*=10
    #mulmod=mul%13
print(d[5])



### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)
### BUGGY CODE ###

n,m = map(int,input().split())
lScope = []
rScope = []
ans = 0
for i in range(m):
    l,r = map(int,input().split())
    lScope.append(l)
    rScope.append(r)
# k in keyScope[i] (i= 0~m) を確かめたい
for key in range(1,n+1):
    if max(lScope) <= key <= min(rScope):
        ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
lScope = []
rScope = []
ans = 0
for i in range(m):
    l,r = map(int,input().split())
    lScope.append(l)
    rScope.append(r)
# k in keyScope[i] (i= 0~m) を確かめたい
if min(rScope) >= max(lScope):
    print(min(rScope) - max(lScope) + 1)
else:
    print(0)
### BUGGY CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
Ds = {i:0 for i in range(A)}
Ds[A] = 10**11
cur = 0
for i in range(A):
    if S[i]<T[cur]:
        if cur==0:
            Ds[i] = T[cur]-S[i]
        else:
            Ds[i] = min(T[cur]-S[i],S[i]-T[cur-1])
    else:
        if T[cur+1]>S[i]:
                Ds[i] = min(T[cur+1]-S[i],S[i]-T[cur])
        else:
            while T[cur+1]<S[i]:
                cur += 1
            Ds[i] = min(T[cur+1]-S[i],S[i]-T[cur])
Dt = {j:0 for j in range(B)}
Dt[B] = 10**11
cur = 0
for j in range(B):
    if T[j]<S[cur]:
        if cur==0:
            Dt[j] = S[cur]-T[j]
        else:
            Dt[j] = min(S[cur]-T[j],T[j]-S[cur-1])
    else:
        if S[cur+1]>T[j]:
            Dt[j] = min(S[cur+1]-T[j],T[j]-S[cur])
        else:
            while S[cur+1]<T[j]:
                cur += 1
            Dt[j] = min(S[cur+1]-T[j],T[j]-S[cur])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    if inds==0:
        cnts = S[0]-x+Ds[0]
    else:
        cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    if indt==0:
        cntt = T[0]-x+Dt[0]
    else:
        cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))

### FIXED CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
S.insert(0,-10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
T.insert(0,-10**11)
Ds = {i:0 for i in range(1,A+1)}
Ds[A+1] = 10**11
Ds[0] = 10**11
for i in range(1,A+1):
    ind = bisect_right(T,S[i])
    Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(1,B+1)}
Dt[B+1] = 10**11
Dt[0] = 10**11
for j in range(1,B+1):
    ind = bisect_right(S,T[j])
    Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))
### BUGGY CODE ###

from functools import reduce

n = int(input())  # nは入力回数
l = [int(x) for x in list(str(n))]

num=len(l)
count=0

for i in range(num): 
    for j in range(num):
        if i>=j or j-i<3:
            pass
        else:
            new_n = int(reduce(lambda x, y: x + y, [str(x) for x in l[i:j+1]]))
            if new_n%2019==0:
              count=count+1  
print(count)
    

### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)
 
count=[0]*2019
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1
 
ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)