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

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
l=[0] * m
r=[0] * m
for i in range(m):
  l[i], r[i] = map(int, input().split())
count = 0
for i in range(n):
  for j in range(m):
    if (i+1 < l[j]) or (i+1 > r[j]):
      break
  else:
    count = count + 1
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
l=[0] * m
r=[0] * m
for i in range(m):
  l[i], r[i] = map(int, input().split())
l.sort()
r.sort()
if r[0] - l[m-1] + 1 > 0:
  print(r[0] - l[m-1] + 1)
else:
  print("0")
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue:
  _, act = heapq.heappop(queue)
  check[act] = True
  for edge in range(n + m - 1):
    if tail[edge] != act:
      continue
    vertex = head[edge]
    if check[vertex]:
      continue
    dist = dp[act] + cost[edge]
    if dp[vertex] > dist:
      heapq.heappush(queue, (dist, vertex))
      dp[vertex] = dist
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n-1)]
for _ in range(m):
  l, r, c = map(int, input().split())
  edge[l-1].append((c, r-1))

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

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

A.sort(reverse=1)
CS = [None,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M)]
def dfs(rest, i):
    if i == M:
        return EMP if rest == 0 else INV
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
print(*ans, sep='')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

N, M = map(int, readline().split())
*A, = map(int, readline().split())

A.sort(reverse=1)
CS = [0,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M+1)]
mM = memo[M]
mM[0] = EMP
for i in range(1, N+1):
    mM[i] = INV
def dfs(rest, i):
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
writelines(ans)
write("\n")
### BUGGY CODE ###

import sys 
input = sys.stdin.readline

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * 100010

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    Minimum = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,min(i,K)+1):
        Minimum = min(dp[i-j]+abs(h[i]-h[i-j]),Minimum)
    dp[i] = Minimum
    
print(dp[N-1])

### FIXED CODE ###

#import sys 
#input = sys.stdin.readline

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * 100010

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,min(K,N)):
    Minimum = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,i+1):
        Minimum = min(dp[i-j]+abs(h[i]-h[i-j]),Minimum)
    dp[i] = Minimum
if N > K:
    if K == 1:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            dp[i] = Minimum
        
    else:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            for (j,k) in zip(dp[i-K:i-1],h[i-K:i-1]):
                Minimum = min(j+abs(h[i]-k),Minimum)
            dp[i] = Minimum
        
print(dp[N-1])
### BUGGY CODE ###

import copy

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

c=0

a_uniq=[0]*(n+1)

for i in a:
  a_uniq[i]+=1

for i in a_uniq:
  c+=sum(range(1,i))
#a_uniq=list(set(a))
#for i in a_uniq:
#  c+=sum(range(1, a.count(i)))

for i in range(0,n):
  print('{:.0f}'.format(c-a.count(a[i])+1))


### FIXED CODE ###

import copy

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

c=0

a_uniq=[0]*(n+1)

for i in a:
  a_uniq[i]+=1

for i in a_uniq:
  c+=sum(range(1,i))
#a_uniq=list(set(a))
#for i in a_uniq:
#  c+=sum(range(1, a.count(i)))

for i in a:
  print('{:.0f}'.format(c-a_uniq[i]+1))
### BUGGY CODE ###

import itertools
import math
n = int(input())

lst = [_ for _ in range(1, n+1)]
lst2 = list(itertools.permutations(lst, 3))
lst3 = list(itertools.permutations(lst, 2)) * 3
l2 = sum([math.gcd(math.gcd(_[0],_[1]),_[2]) for _ in lst2])
l3 = sum([math.gcd(_[0], _[1]) for _ in lst3])
l4 = sum(lst)

ans = l2 + l3 + l4

print(ans)


### FIXED CODE ###

import itertools
import math
n = int(input())

lst = [_ for _ in range(1, n+1)]
lst2 = list(itertools.product(lst, repeat=2))

lst3 = [math.gcd(_[0], _[1]) for _ in lst2]

lst4 = list(itertools.product(lst3, lst))

lst5 = [math.gcd(_[0], _[1]) for _ in lst4]

print(sum(lst5))
### BUGGY CODE ###

import sys
import itertools

input = sys.stdin.readline

def main():
    l, r = [int(i) for i in input().split()] 

    mod = 0
    mod_min = 2019
    num_list = [num for num in range(l, r+1)]
    for i, j in itertools.combinations(num_list, 2):
        mod = (i*j % 2019)
        if mod == 0:
            print(mod)
            exit()
        elif mod < mod_min:
            mod_min = mod
            
    print(mod_min)

# main関数呼び出し
if __name__ == "__main__":
    main() 

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def func(l, r):
    mod_min = float('inf')

    for i in range(l, r):
        for j in range(i+1, r+1):
            mod = (i*j % 2019)

            if mod == 0:
                print(mod)
                exit()     

            elif mod < mod_min:
                mod_min = mod

    print(mod_min)

def main():
    l, r = [int(i) for i in input().split()] 
    func(l, r)
    
# main関数呼び出し
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
list_N = [int(input()) for _ in range(n)]
ans = []
for num in list_N:
    if num in ans:
        ans.remove(num)
    else:
        ans.append(num)
print(len(ans))

### FIXED CODE ###

from collections import Counter
n = int(input())
list_N = [int(input()) for _ in range(n)]
l = Counter(list_N)
k = l.values()
ans = 0
for num in k:
    if num % 2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def remove_01_10(S):
	N = len(S) 
	while True:
		if '01' in S or '10' in S:
			S = S.replace('10', '')
			S = S.replace('01', '')
		else:
			return(N - len(S))	

print(remove_01_10(input()))

### FIXED CODE ###

S = list(input())
N = len(S)
num0 = 0
for i in range(N):
	if S[i] == '0':
		num0 = num0 + 1

num1 = 0
for i in range(N):
	if S[i] == '1':
		num1 = num1 + 1
print(N - abs(num0 - num1))
### BUGGY CODE ###

def func():
    return

n = int(input())
# s = input()
# a, b = map(int, input().split())
p = list(map(int, input().split()))
# a = input().split()

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

print(cnt)

### FIXED CODE ###

def func():
    return

n = int(input())
# s = input()
# a, b = map(int, input().split())
p = list(map(int, input().split()))
# a = input().split()

cnt = 0
min_ = n
for i in range(n):
    min_ = min(min_, p[i])
    if min_ == p[i]:
        cnt += 1

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

from itertools import groupby, chain

N,K,Q,*A=map(int,open(0).read().split())
s=sorted
print(min((s(chain.from_iterable((v[:max(0,-~(len(v)-K))]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y)))))[Q-1:]or[2e9])[0]-Y for Y in set(A)))


### FIXED CODE ###

N, K, Q, *A = map(int, open(0).read().split())

ans = float("inf")
for Y in A:
    C = []
    tmp = []
    for a in A:
        if a >= Y:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                C += sorted(tmp)[:len(tmp) - K + 1]
            tmp = []
    if len(tmp) >= K:
        C += sorted(tmp)[:len(tmp) - K + 1]

    if len(C) >= Q:
        C.sort()
        X = C[Q - 1]
        ans = min(ans, X - Y)

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

N=int(input())
S = []
while N > 0:
  data=input()
  N-=1
  if data not in S:
    S.append(data)
print(len(S))

### FIXED CODE ###

N = int(input())
S = list()
for i in range(N):
  x = input()
  S.append(x)
  
A = set(S)
print(len(A))
### BUGGY CODE ###

N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
end = set()
end2 = set()
add = end.add
add2 = end2.add
result = a.count(-1)

leaves = {i for i in range(N) if a[i] > -1} - set(a)
for i in leaves:
    v = i
    l = 0
    n = 0
    while a[v] != -1:
        if v not in end2 and l < K:
            n += 1
            add2(v)
        l += 1
        v = a[v]
    result += n

print(result)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += (v not in visited)
        add(v)
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

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

from collections import Counter

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

nC2 = [0] * (N + 1)
nC2[0] = 0
nC2[1] = 0
for i in range(2, N + 1):
    nC2[i] = i * (i - 1) // 2

# print(nC2)

d = Counter(A)
# print(d)
k = d.keys()

# print(k)

for a in A:
    res = 0
    for kk in k:
        if a == kk:
            res += nC2[d[kk] - 1]
        else:
            res += nC2[d[kk]]
    # print(a, d[a], res)
    print(res)


### FIXED CODE ###

from collections import Counter

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


def comb(x):
    if x == 0:
        return 0
    if x == 1:
        return 0
    return x * (x - 1) // 2


d = Counter(A)
# print(d)
k = d.keys()

# print(k)
total = 0

for kk in k:
    total += comb(d[kk])

# print(total)

for a in A:
    res = total
    res -= comb(d[a])
    res += comb(d[a] - 1)
    print(res)
### 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)
    A.sort(reverse=True)
    A=A[:N]
A.sort(reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

from collections import defaultdict
N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=defaultdict(int)
s=set()
for i in A:
    BC[i]+=1
    s.add(i)
for i in range(M):
    B,C=map(int,input().split())
    BC[C]+=B
    s.add(C)
s=list(s)
s.sort(reverse=True)
res=0
ans=0
for i in s:
    k=min(N-res,BC[i])
    res+=k
    ans+=k*i
    if res==N:
        break
print(ans)
### BUGGY CODE ###

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

def floor(t):
  return int(t)

max = 0 
for x in range(N+1):
  y = floor(A*x/B)-A*floor(x/B)
  if y > max:
    max = y
    
print(max)

### FIXED CODE ###

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

def g(x):
  return int(A*x/B)-A*int(x/B)

print(g(min(B-1, N)))
### BUGGY CODE ###

import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    A = [0] * M
    B = [0] * M

    friend_list = [ set() for _ in range(N)]
    friend_list_len = 0

    for i in range(M):
        A[i],B[i] = map(int,input().split())

        for j in range(friend_list_len):
            flag = False
            if A[i] in friend_list[j]:
                friend_list[j].add(B[i])
                flag = True
            if B[i] in friend_list[j]:
                friend_list[j].add(A[i])
                flag = True
            if flag:
                break                
        else:
            friend_list[friend_list_len].add(A[i])
            friend_list[friend_list_len].add(B[i])
            friend_list_len += 1

    ans = 1
    for i in range(friend_list_len):
        ans = max(ans,len(friend_list[i]))

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():

    input = sys.stdin.readline

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

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

    UF = UnionFind(N)

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        UF.union(A,B)


    ans = 1
    for i in range(N):
        ans = max(ans,UF.size(i))

    print(ans)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

import math
K = int(input())
ans =0
def koyakusu(A,B,C):
  kotae = A
  kotae = math.gcd(kotae,B)
  kotae = math.gcd(kotae,C)
  return kotae
  
  
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans +=koyakusu(a,b,c)

print(ans)

### FIXED CODE ###

import math
K = int(input())+1
ans=0
for a in range(1,K):
  for b in range(1,K):
    gcdab = math.gcd(a,b)
    for c in range(1,K):
      ans += math.gcd(gcdab,c)

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

N = int(input())
print(sum(range(N)))

### FIXED CODE ###

N = int(input())
print(N * (N-1) // 2)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=(10**18)*5
r=range(n)
for i1 in r:
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in r:
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in r:
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n = int(input())
ans = []
cnt = 0
for i in range(1, int(n**0.7)+3):
    if n > cnt:
        ans.append(i)
        cnt += i
    else:
        if cnt - n in ans:
            ans.remove(cnt - n)
            break
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
ans = []
cnt = 0
for i in range(1, int(n**0.7)+3):
    if n > cnt:
        ans.append(i)
        cnt += i
    else:
        if cnt - n in ans:
            ans.remove(cnt - n)
        break
for i in ans:
    print(i)
### BUGGY CODE ###

import sys

n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10 ** 9 + 7

res = 0
for i, c in enumerate(c_ls):
    res += (2 ** (n - 2) * (i + 2)) * c % MOD
    res %= MOD
res = res * (2 ** n) % MOD
print(int(res))

### FIXED CODE ###

import sys

n = int(input())
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
MOD = 10 ** 9 + 7

res = 0
for i, c in enumerate(c_ls):
    res += (i + 2) * c % MOD
    res %= MOD
res = res * (4 ** (n - 1)) % MOD
print(int(res))
### BUGGY CODE ###

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

s = s[0] + s + str((int(s[-1])+1)%2)
a = []
l = 1
for i in range(1, n+2):
    if s[i] == s[i-1]:
        continue
    a.append(i-l)
    l = i
m = int(s[0])
ans = 0
for i in range(len(a)):
    ans = max(ans, sum(a[i:i+2*k+(m+i)%2]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
Nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつ並んでいるか
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now   # 0と1を切り替えるときの計算 now ^= 1
        cnt = 1
if cnt != 0:
    Nums.append(cnt)
# 1-0-1-0-1-0-1 って感じの配列が欲しい
# 1-0-1-0-1-0 みたいに0で終わっていたら適当に1つ足す
if len(Nums) % 2 == 0:
    Nums.append(0)

Add = 2 * K + 1
# 累積和を作る
# 0 1 2 3 4 5 6
#  0 1 2 3 4 5
sum = [0] * (len(Nums) + 1)
for i in range(len(Nums)):
    sum[i + 1] = sum[i] + Nums[i]
ans = 0
# 1-0-1... の1から始めるので、偶数番目だけ見る
for i in range(0, len(Nums), 2):
    # 次のleft, rightを計算する [left, right)
    left = i
    right = min(i + Add, len(Nums))
    tmp = sum[right] - sum[left]
    ans = max(tmp, ans)

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

s = input()
ans = 0
while s.count("ABC")!=0:
    s = s.replace("ABC", "BCA", 1)
    ans += 1
print(ans)

### FIXED CODE ###

s = input()
s = s.replace("BC","D")
a,ans = 0,0
#Dより前にあるB,C意外でつながったAの数をカウント
for i in s:
    if i == "A":
        a += 1
    elif i == "D":
        ans += a
    else:
        a = 0
print(ans)
### BUGGY CODE ###

input = raw_input

M = 2019
s = input()
n = len(s)
s = list(s)

#X = {}
counts = [0] * M
counts_tmp = [0] * M

inv10 = 202

out = 0
for i in range(n):
    c = int(s[i])

    new_counts = [0] * M
    for j in range(M):
        j2 = (j * 10 + c) % M
        new_counts[j2] += counts[j]
    counts = new_counts
    
    c = int(s[i])
    counts[c] += 1
    out += counts[0]

#print(counts, sum(counts))

print(out)

### FIXED CODE ###

input = raw_input

M = 2019
s = input()
#n = len(s)
#s = int(s)

div = 10

counts = [0] * M
#m = 1

counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    #m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)
### BUGGY CODE ###

import numpy as np
A, B, Q = map(int, input().split())
s = np.array([-10**10 - 1, -10**10] + [int(input()) for _ in range(A)] + [2*10**10])
t = np.array([-10**10 - 1, -10**10] + [int(input()) for _ in range(B)] + [2*10**10])
x = [int(input()) for _ in range(Q)]


def func(c, d, z):
    i = np.searchsorted(c, z)
    j1 = np.searchsorted(d, c[i - 1])
    j2 = np.searchsorted(d, c[i])
    return min(z - d[j1 - 1], z - c[i - 1] * 2 + d[j1], d[j2] - z, c[i] * 2 - z - d[j2 - 1])


for z in x:
    print(min(func(s, t, z), func(t, s, z)))

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
s = [-10**10 - 1, -10**10] + [int(input()) for _ in range(A)] + [2*10**10]
t = [-10**10 - 1, -10**10] + [int(input()) for _ in range(B)] + [2*10**10]
x = [int(input()) for _ in range(Q)]


def func(c, d, z):
    i = bisect.bisect_left(c, z)
    j1 = bisect.bisect_left(d, c[i - 1])
    j2 = bisect.bisect_left(d, c[i])
    return min(z - d[j1 - 1], z - c[i - 1] * 2 + d[j1], d[j2] - z, c[i] * 2 - z - d[j2 - 1])


for z in x:
    print(min(func(s, t, z), func(t, s, z)))