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

N, K, L = map(int, input().split())
ans = [1 for i in range(N)]
setA = []
setB = []
for i in range(K):
    X = set(int(x)-1 for x in input().split())
    for A in setA:
        if len(A & X) != 0:
            setA.remove(A)
            setA.append(A | X)
            break
    else:
        setA.append(X)
#print(setA)
for i in range(L):
    Y = set(int(y)-1 for y in input().split())
    for B in setB:
        if len(B & Y) != 0:
            setB.remove(B)
            setB.append(B | Y)
            break
    else:
        setB.append(Y)
#print(setB)
for A in setA:
    for B in setB:
        for i in A & B:
            ans[i] = len(A & B)
for i in range(N):
    print(ans[i], end=" ")

### FIXED CODE ###

N, K, L = map(int, input().split())

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

A.insert(0,0)
A.append(0)
dist = []
dist_warp = []

for i in range(1,N+2):
    dist.append(abs(A[i]-A[i-1]))
    if i != 1:
        dist_warp.append(abs(A[i]-A[i-2]))

for i in range(1,N+1):
    print(sum(dist)-dist[i-1]-dist[i]+dist_warp[i-1])

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

A.insert(0,0)
A.append(0)

S = 0

for i in range(1,N+2):
    S += abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(S + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

a.sort() # 4 の倍数消した後, 2 の倍数消したら, 例えば 6 が消せなかったり
d = defaultdict(int)
for x in a:
    d[x] += 1

for x in d:
    for j in list(range(2, N)):
        if x * j >= N or b[x * j] == 1: #debuged
            break
        else:
            b[x * j] = 1

ans = 0
for x in a:
    if b[x] == 1:
        continue
    else:
        if d[x] >= 2:
            continue
        else:
            ans += 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

for x in a:
    if b[x] == 0:
        for y in list(range(2 * x, N, x)):
            b[y] += 1
    b[x] += 1

ans = 0
for x in a:
    if b[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
for i in range(2, gcd + 1):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break

print(ans)

### FIXED CODE ###

from math import gcd
a, b = map(int, input().split())

gcd = gcd(a, b)
ans = 1
n = int(gcd**0.5) + 2
for i in range(2, n):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if gcd >= n:
    ans += 1
if ans == 1 and gcd != 1:
    ans = 2
    
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys

def main():
    input = sys.stdin.readline
    n=int(input())
    dic=defaultdict(int)
    for i in range(n):
        dic[input().strip('\n')]+=1
    max_kv_list=[k for k,v in dic.items() if v==max(dic.values())]
    max_kv_list.sort()
    for i in range(len(max_kv_list)):
        print(max_kv_list[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import sys

def main():
    input = sys.stdin.readline
    n=int(input())
    dic=defaultdict(int)
    st=set([])
    for i in range(n):
        s=input().strip('\n')
        st.add(s)
        dic[s]+=1
    maxv=max(dic.values())
    l=sorted(st)
    for i in range(len(l)):
        if dic[l[i]]==maxv:
            print(l[i])
        
    

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

N, M = map(int, input().split())
  
broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
      
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

def step_memo(N):
    if N == 0 and N not in broken_step:
        memo[N] = 1
        return 1
    elif N == 0 and N in broken_step:
        memo[N] = 0
        return 0
    
    if N == 1 and N not in broken_step:
        memo[N] = 1
        return 1
    elif N == 1 and N in broken_step:
        memo[N] = 0
        return 0

    a = 1
    b = 1
    
    if N in broken_step:
        a, b = 0, 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (a * step_memo(N-1) + b * step_memo(N-2)) % mod
    return (a * step_memo(N-1) + b * step_memo(N-2)) % mod

print(step_memo(N))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
p,S = 0,0
for i in range(N-1):
    AA = 0
    aa = 0
    for j in range(i+1,N):
        AA += A[j]
    aa = A[i]*AA
    a = aa%1000000007
    S += a
p = S%1000000007
print(p)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
a,s = 0,0
for i in range(N):
    a += s*A[i]
    s += A[i]
    a %= mod
print(a)
### BUGGY CODE ###

N, X = map(int, input().split())
lst = list(map(int, input().split()))
ans = []
for i in lst:
    ans.append(abs(i-X))
small = min(ans)
for i in ans:
    if i%small == 0:
        continue
    else:
        while i != small:
            i = i%small
            small = small - i
print(small)

### FIXED CODE ###

N, X = map(int, input().split())
lst = list(map(int, input().split()))
ans = []
for i in lst:
    ans.append(abs(i-X))
small = min(ans)
for i in ans:
    if i%small != 0:
        while i%small != 0:
            i = i%small
            small = small - i
print(small)
### BUGGY CODE ###

import itertools
import sys

input = sys.stdin.readline

maxn = 10000000000

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.append(-maxn)
B.append(-maxn)
C.append(-maxn)

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

apos, bpos, cpos = 0, 0, 0

while (apos + 1) * (bpos + 1) * (cpos + 1) < min(10 ** 7 - 5 * 10 ** 6, X * Y * Z):
    if (
        apos < len(A) - 2
        and abs(A[apos] - A[apos + 1]) < abs(B[bpos] - B[bpos + 1])
        and abs(A[apos] - A[apos + 1]) < abs(C[cpos] - C[cpos + 1])
    ):
        apos += 1
    elif bpos < len(B) - 2 and B[bpos] - B[bpos + 1] < C[cpos] - C[cpos + 1]:
        bpos += 1
    else:
        cpos += 1

res = []
for a in list(itertools.product(A[: apos + 1], B[: bpos + 1], C[: cpos + 1])):
    res.append(a[0] + a[1] + a[2])

res.sort(reverse=True)
for k in range(K):
    print(res[k])


### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

maxn = 10000000000

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

cand = []
for i, a in enumerate(A):
    for j, b in enumerate(B):
        for k, c in enumerate(C):
            if (i + 1) * (j + 1) * (k + 1) <= K:
                cand.append(a + b + c)
            else:
                break

cand.sort(reverse=True)
for k in range(K):
    print(cand[k])
### BUGGY CODE ###

def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0]*(n+1) for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a][b] = 1
        hw[b][a] = 1
    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] == 1:
                if arr[i] == -1:
                    arr[i] = a
                    que.append(i)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])

resolve()

### FIXED CODE ###

def resolve():
    import collections
    n, m = map(int, input().split())
    hw = [[0] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        hw[a].append(b)
        hw[b].append(a)

    dis = [0] * (n+1)
    arr = [-1] * (n+1)
    que = collections.deque([1])
    while len(que) != 0:
        a = que.popleft()
        test = hw[a]
        for i in range(len(test)):
            if test[i] != 0:
                goal = test[i]
                if arr[goal] == -1:
                    arr[goal] = a
                    que.append(goal)
    if 0 in arr[2:]:
        print("No")
    else:
        print("Yes")
        for i in range(2, len(arr)):
            print(arr[i])
resolve()
### BUGGY CODE ###

#coding:utf-8

n = int(input())
a = input().split()

list_n = [0 for i in range(n)]
basic = 0

for i in a:
    aa = int(i)
    count = list_n[aa - 1]
    basic += count
    list_n[aa - 1] += 1

ans = 0
for i in range(n):
    ans = 0
    lislis = list_n.copy()
    a1 = int(a[i])
    ans = basic - lislis[a1 - 1] + 1
    print("{}".format(int(ans)))

### FIXED CODE ###

#coding:utf-8

n = int(input())
a = input().split()

list_n = [0 for i in range(n)]
basic = 0

for i in a:
    aa = int(i)
    count = list_n[aa - 1]
    basic += count
    list_n[aa - 1] += 1

ans = 0
for i in range(n):
    ans = 0
    a1 = int(a[i])
    ans = basic - list_n[a1 - 1] + 1
    print("{}".format(int(ans)))
### BUGGY CODE ###

def solve(N, Q, S, L_R):
    answers = [None] * Q
    ac_index = [0] * len(S)
    for i in range(len(S) - 1):
        s = S[i:i + 2]
        if s == "AC":
            ac_index[i] = 1
    q = 0
    for l, r in L_R:
        arr = ac_index[l - 1:r]
        ans = sum(arr)
        if arr[-1] == 1:
            ans -= 1
        answers[q] = ans
        q += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)
### BUGGY CODE ###

a = list(map(int, input().split()))
 
p = [list(map(int, input().split())) for i in range(a[1])]
q = [list(map(int, input().split())) for i in range(a[2])]
 
res = [[0]*a[0] for i in range(a[0])]
 
def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1
 
for l,r in p:
    lsadd(l,r)
 
for l,r in q:
    print(sum(res[l-1][:r]))

### FIXED CODE ###

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

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

for i in range(a[1]):
    n,m = map(int,input().split())
    c[n][m] += 1

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

for i in range(a[2]):
    n,m = map(int,input().split())
    s = 0
    for j in range(n,m+1):
        s += d[j][m+1] - d[j][j]
    print(s)
### BUGGY CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import queue

n = int(input())

withdraws = [1]
price = 1
while True:
    price *= 6
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

price = 1
while True:
    price *= 9
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

money = 0
count = 0

que = queue.Queue()

que.put((0,0))
while not(que.empty()):
    money,count = que.get()
    # print(money,count)
    if money > n:
        pass
    else:
        for withdraw in withdraws:
            if money+withdraw == n:
                print(count+1)
                exit()
            else:
                next = (money+withdraw,count+1)
                que.put(next)


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import queue

n = int(input())

withdraws = [1]
price = 1
while True:
    price *= 6
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

price = 1
while True:
    price *= 9
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break


withdraws.sort(reverse = True)
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

que.put((0,0))
memory = []
while not(que.empty()):
    money,count = que.get()
    print(money,count)
    if money > n:
        pass
    else:
        for withdraw in withdraws:
            if money+withdraw == n:
                print(count+1)
                exit()

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''

# 分割

ans = 10**10
if n < 6:
    ans = n
for i in range(n+1):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

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

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

ab.sort()

AB=[[ab[i][0]]*ab[i][1] for i in range(n)]
ans=0
cnt=0
for i in AB:
    for z in i:
        ans+=z
        cnt+=1
        if cnt>=m:
            print(ans)
            exit()

### FIXED CODE ###

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

ab.sort()

ans=0
B=0
cnt=0
for a,b in ab:
    B+=b
    if B<m:
        ans+=a*b
        cnt+=b
    else:
        ans+=a*(m-cnt)
        print(ans)
        exit()
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]+=1
                if j**2==i:
                    continue
                tl[i//j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))

### FIXED CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]+=1
                if j**2==i:
                    continue
                tl[i//j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))
### BUGGY CODE ###

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

l = [0] * q
r = [0] * q

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

s_list = list(s)

ac_list = []

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list.append(i)

#print(ac_list)

for i in range(0,q):
    count = 0
    for j in range(l[i],r[i]):
        if j in ac_list:
            count = count + 1
    print(count)

### FIXED CODE ###

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

l = [0] * q
r = [0] * q

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

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

#print(ac_list)

w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]

#print(w)

for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = sum(A)
a = 0
b = 0
for i in range(len(A)):
    if S/2 >= sum(A[:i]):
        a = sum(A[:i])
    else:
        b = sum(A[:i])
        break
print(min(abs(S-a*2),abs(S-b*2)))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = sum(A)
b = 0
a = 0
c = 0
if N == 2:
    print(abs(A[0]-A[1]))
else:
    for i in range(len(A)):
        if S/2-0.5 > a:
            a += A[i]
        else:
            b = a + A[i]
            c = a - A[i-1]
            break
        if i == len(A)-1:
            b = a
            a = a-A[i]
        else:
            None
    print(min(abs(S - a*2), abs(S - b*2),abs(S-c*2)))
### BUGGY CODE ###

def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = []
	for _ in range(m):
		a.append(int(input()))
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i in a:
			continue
		multi = []
		if i-1 not in a:
			multi.append(dp[i-1])
		if i-2 not in a:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

### FIXED CODE ###

def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = [False]*n
	for _ in range(m):
		a[int(input())] = True
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i < n and a[i]:
			continue
		multi = []
		if not a[i-1]:
			multi.append(dp[i-1])
		if not a[i-2]:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()
### BUGGY CODE ###

#Mo
import sys
input = sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
print('\n'.join(map(str,ans[:q])))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
### BUGGY CODE ###

n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    for i in range(9):
        for p in range(s-1):
            for q in range(p):
                for t in range(1,10):
                    for u in range(1,10):
                        if n>=(10**(s-1))*(i+1)+(10**p)*t+(10**q)*u:
                            ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    f=int(list(str(n))[0])
    ans+=(f-1)*81*(s-1)*(s-2)//2
    for p in range(s-1):
        for q in range(s-1):
            if p<q:
                for t in range(1,10):
                    for u in range(1,10):
                        if n>=(10**(s-1))*f+(10**p)*t+(10**q)*u:
                            ans+=1
print(ans)
### BUGGY CODE ###

import bisect as bi

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

s=[-10**11]
for i in range(A):
    s.append(int(input()))
s.append(10**11)

t=[-10**11]
for i in range(B):
    t.append(int(input()))
t.append(10**11)

for k in range(Q):
    x=int(input())
    i=bi.bisect_left(s,x)
    sl=s[i-1];sr=s[i]
    j=bi.bisect_left(t,x)
    tl=t[j-1];tr=t[j]
    # print(sl,sr,tl,tr)
    print(min(abs(x-sl)+abs(sl-tl),abs(x-sl)+abs(sl-tr),abs(x-sr)+abs(sr-tl),abs(x-sr)+abs(sr-tr),\
        abs(x-tl)+abs(tl-sl),abs(x-tl)+abs(tl-sr),abs(x-tr)+abs(tr-sl),abs(x-tr)+abs(tr-sr)))

### FIXED CODE ###

import bisect as bi

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

s=[-10**11]
for i in range(A):
    s.append(int(input()))
s.append(10**11)

t=[-10**11]
for i in range(B):
    t.append(int(input()))
t.append(10**11)

for k in range(Q):
    x=int(input())
    i=bi.bisect_left(s,x)
    sl=s[i-1];sr=s[i]
    j=bi.bisect_left(t,x)
    tl=t[j-1];tr=t[j]
    # print(sl,sr,tl,tr)
    print(min(abs(x-sl)+abs(sl-tl),abs(x-sl)+abs(sl-tr),abs(x-sr)+abs(sr-tl),abs(x-sr)+abs(sr-tr),\
        abs(x-tl)+abs(tl-sl),abs(x-tl)+abs(tl-sr),abs(x-tr)+abs(tr-sl),abs(x-tr)+abs(tr-sr)))
### BUGGY CODE ###

t_max = 10 ** 5

N, C = map(int, input().split())
imos = [[0] * (t_max + 1) for _ in range(C + 1)]
# imos[c][x]:=チャンネルc,時刻xの使用有無
# c: 1-indexed
# x: 1-indexed

for _ in range(N):
    s, t, c = map(int, input().split())
    imos[c][s] += 1
    imos[c][t] -= 1

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        imos[c][i] += imos[c][i - 1]

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        x = imos[c][i]
        if x > 0 and imos[c][i - 1] == 0:
            imos[c][i - 1] = x

ans = 0
for i in range(1, t_max + 1):
    ans = max(ans, sum(imos[c][i] for c in range(1, C + 1)))
print(ans)


### FIXED CODE ###

t_max = 10 ** 5

N, C = map(int, input().split())
imos = [[0] * (t_max + 1) for _ in range(C + 1)]
# imos[c][x]:=チャンネルc,時刻xの使用有無
# c: 1-indexed
# x: 1-indexed

for _ in range(N):
    s, t, c = map(int, input().split())
    imos[c][s] += 1
    imos[c][t] -= 1

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        imos[c][i] += imos[c][i - 1]
        if imos[c][i] > 0 and imos[c][i - 1] == 0:
            imos[c][i - 1] = imos[c][i]

ans = 0
for i in range(1, t_max + 1):
    ans = max(ans, sum(imos[c][i] for c in range(1, C + 1)))
print(ans)