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

import sys
input=sys.stdin.readline
K = int(input())
def bunkai(N):
    k = 0
    while 10 ** k <= N:
        k += 1
    oldk = k
    order = [0] * k
    k -= 1
    while N > 0:
        a = N // (10**k)
        N = N % (10**k)
        order[oldk-k-1] = a
        k -= 1
    return order
c = 0
for i in range(1,3234566668):
    d = 0
    arr = bunkai(i)
    n = len(arr)
    if n == 1:
        c += 1
    else:
        for j in range(n-1):
            if abs(arr[j] - arr[j+1]) >1:
                d = 1
                break
        if d == 0:
            c += 1 
    if c == K:
        print(i)
        break

### FIXED CODE ###

import sys
input=sys.stdin.readline
K = int(input())
LEN = 32345666
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
def enqueue(Q,x,tail):#末尾にクラスPの要素xを加える。ぐるっと回った場合
    Q[tail] = x       #以前dequeueで取り出したものが書き換えられる。
    if tail+1 == LEN: #headは先頭のindex,tailは末尾のindex+1
        tail = 0
    else:
        tail += 1
    return tail
def dequeue(Q,head):
    x = Q[head]
    if head+1 == LEN:
        head = 0
    else:
        head += 1
    return x,head
Q = [1,2,3,4,5,6,7,8,9]+[0]*(LEN-9)
head = 0
tail = 9

i = 0
while i < K:
    x,head = dequeue(Q,head)
    if x % 10 == 0:
        tail = enqueue(Q,10*x,tail)
        tail = enqueue(Q,10*x+1,tail)
    elif x % 10 == 9:
        tail = enqueue(Q,10*x+8,tail)
        tail = enqueue(Q,10*x+9,tail)
    else:
        y = x%10
        tail = enqueue(Q,10*x+y-1,tail)
        tail = enqueue(Q,10*x+y,tail)
        tail = enqueue(Q,10*x+y+1,tail)
    i += 1
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
INF = 10**10

h, w = map(int, input().split())
C = [input().rstrip() for _ in range(h)]
def solve(b):
  cost = [[0]*(h+1) for _ in range(h+1)]
  dp = [[INF]*(h+1) for _ in range(h+1)]
  dp[0][0] = 0
  for i in range(h+1):
    for j in range(h+1):
      if i and j:
        cost[i][j] = cost[i-1][j-1] - (C[h-i][b] == C[h-j][b+1])
      else:
        for r in range(min(h-i, h-j)):
          cost[i][j] += C[j+r][b] == C[i+r][b+1]
      if i:
        dp[i][j] = min(dp[i][j], dp[i-1][j]+cost[i-1][j])
      if j:
        dp[i][j] = min(dp[i][j], dp[i][j-1]+cost[i][j-1])
  return dp[h][h]
ans = 0
for b in range(w-1):
  ans += solve(b)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = 10**10
h, w = map(int, input().split())
C = [input().rstrip() for _ in range(h)]
def solve(b):
  cost = [[0]*(h+1) for _ in range(h+1)]
  dp = [[INF]*(h+1) for _ in range(h+1)]
  dp[0][0] = 0
  for i in range(h+1):
    for j in range(h+1):
      if i and j:
        cost[i][j] = cost[i-1][j-1] - (C[h-i][b] == C[h-j][b+1])
      else:
        for r in range(min(h-i, h-j)):
          cost[i][j] += C[j+r][b] == C[i+r][b+1]
      if i:
        dp[i][j] = min(dp[i][j], dp[i-1][j]+cost[i-1][j])
      if j:
        dp[i][j] = min(dp[i][j], dp[i][j-1]+cost[i][j-1])
  return dp[h][h]
ans = 0
for b in range(w-1):
  ans += solve(b)
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, X, Y = map(int, readline().split())

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for i, a in enumerate(answer):
    if i != 0:
        print(a)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, X, Y = map(int, readline().split())

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i-j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for i, a in enumerate(answer):
    if i != 0:
        print(a)
### BUGGY CODE ###

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

for _ in range(q):
    l,r=map(int, input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=input()
cnt = 0
list=[0]
for i in range(0,len(s)-1):
    if s[i: i + 2] == 'AC':
        cnt += 1
    list.append(cnt)

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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, Q = LI()

abcd = []
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans
# 10進数のnを2進数のリストに変換
# def n2kdigit(n,k):
#     digits = []
#     before = 0
#     while n > 0:
#         if before > n % k:
#             return None
#         digits.append(n % k)
#         before = n % k
#         n = n // k
#     if len(digits) < N:
#         return None

#     return digits
def n2kdigit(n, k):
    bi=''
    before = 0
    while n!=0:
        if before <= (n % k):
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi[::-1]) < N:
        return None
    return bi

ans = -1
for i in range(M ** (N)):
    A = n2kdigit(i, M)
    if A is not None:
        ans = max(ans, cal_ans([int(i) for i in A]))
ans = max(ans, cal_ans([0 for i in range(N)]))
print(ans)



    



### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import itertools
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []

all = 0
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
    all += d

abcd = sorted(abcd, key= lambda x:x[3], reverse= True)
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi) < N:
        return None
    return bi
ans = 0

for i in itertools.combinations_with_replacement(range(1, M+1), N):
    # print(i)
    ans = max(ans, cal_ans(i))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
q = int(input())

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

#def power(x, y):
#    if   y == 0     : return 1
#    elif y == 1     : return x % mod
#    elif y % 2 == 0 : return power(x, y//2)**2 % mod
#    else            : return power(x, y//2)**2 * x % mod
def power(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

for j in range(q):
    x,d,n=(int(i) for i in input().split())  
    xd=div(x, d)
    ans=1
    if mod <= xd+n-1:
        ans=0

    for i in range(n):
        ans=mul(ans,xd+i)
    
    print((power(d,n)*ans)%mod)
  



### FIXED CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(n):
    i = i+1
    ans = ans * i
print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(n):
    i = i+1
    ans = (ans * i) % (10**9+7)
print(ans)
### BUGGY CODE ###

import random

D = int(input())
C = [*map(int, input().split())]
S = [[*map(int, input().split())] for _ in range(D)]

O = [[0]*26 for _ in range(D)]
A = [[0]*26 for _ in range(D)]

def last(d,t):
    for i in range(d,-1,-1):
        if O[i][t] > 0: return i
    return 0

T = []
t = 0
for d in range(D):
    t = int(random.uniform(1,27))
    T.append(t)

# print(*T,sep='\n')

score = 0
t = 0
for d in range(D):
    t = T[d] - 1
    O[d][t] = 1
    dw = 0
    for i in range(26):
        dw += C[i]*((d+1) - last(d,i))
    A[d][t] = S[d][t] - dw
    score += A[d][t]
# print(score)

# for _ in range(10000):
    # a = int(random.uniform(0,D))
    # q = int(random.uniform(1,27))
    # old = T[a]
    # T[a] = q

for a in range(D):
    old = T[a]
    for q in range(1,27):
        T[a] = q

        now = 0
        t = 0
        for d in range(D):
            t = T[d] - 1
            O[d][t] = 1
            dw = 0
            for i in range(26):
                dw += C[i]*((d+1) - last(d,i))
            A[d][t] = S[d][t] - dw
            now += A[d][t]
        if score > now:
            T[a] = old
        else:
            score = now

# print(score)

print(*T,sep='\n')


### FIXED CODE ###

D = int(input())
C = [*map(int, input().split())]
S = [[*map(int, input().split())] for _ in range(D)]

# print(D)
# print(C)
# print(*S,sep='\n')

O = [[0]*26 for _ in range(D)]
A = [[0]*26 for _ in range(D)]

def last(d,t):
    for i in range(d,-1,-1):
        if O[i][t] > 0: return i
    return 0

score = 0
t = 0
for d in range(D):
    O[d][t] = 1
    dw = 0
    for i in range(26):
        dw += C[t]*(d - last(d,i))
    A[d][t] = S[d][t] - dw
    score += A[d][t]
    print(t+1)
    t = (t+1) % 26
# print(score)

# t = 0
# for d in range(D):
#     O[d][t] = 1
#     dw = 0
#     for i in range(26):
#         dw += C[t]*(d - last(d,i))
#     A[d][t] = S[d][t] - dw
#     print(t)
#     t = (t+1) % 26

# for d in range(D):
#     s = 0
#     for t in range(26):
#         s += C[t]*(d - last(d,t))
#     print(s)
### BUGGY CODE ###

def resolve():
    N = int(input())
    V = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    maxA = 0
    for i in range(2**N):
        X = 0
        Y = 0
        for j in range(N):
            if (i >> j) & 1:
                X += V[j]
                Y += C[j]
        maxA = max(maxA, X - Y)
    print(maxA)


resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    V = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    ans = 0
    for i in range(N):
        if V[i] > C[i]:
            ans += V[i] - C[i]
    print(ans)


resolve()
### BUGGY CODE ###

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real=set(real)

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    test={i for i in range(l[i],r[i]+1)}
    print(len(test&real))

### FIXED CODE ###

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real.sort()

Q=int(input())
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=map(int,input().split())
for i in range(0,Q):
    if r[i]<3 or l[i]>99877:
        print(0)
    else:
        s=0
        t=0
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if real[test]>=l[i]:
                end=test
            else:
                start=test
        if real[start]>=l[i]:
            s=start
        else:
            s=end
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if r[i]>=real[test]:
                start=test
            else:
                end=test
        if r[i]>=real[end]:
            t=end
        else:
            t=start
        print(t-s+1)
### BUGGY CODE ###

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

ans = 0
while True:
    if n >= a:
        n -= a
        ans += a
    else:
        ans += n
        break

    if n >= b:
        n -= b
    else:
        break
print(ans)


### FIXED CODE ###

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

ans = n//(a+b)*a
amari = n-(a+b)*(n//(a+b))
ans += min(amari, a)

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

from operator import itemgetter
n,k = map(int,input().split())
li=[]
s=[]
t=[]
g=0
ans=[]
for _ in range(n):
    a,b=map(int,input().split())
    li.append([a,b])
li=sorted(li,key=itemgetter(1),reverse=True)
for i in range(k):
    g+=li[i][1]
    if li[i][0] not in s:
        s.append(li[i][0])
    else:
        t.append(li[i][1])
g+=len(s)**2
ans.append(g)
for i in range(k,n):
    if len(t)==0:
        break
    if li[i][0] not in s:
        g=g-t[-1]+li[i][1]+2*len(s)+1
        ans.append(g)
        s.append(li[i][0])
print(max(ans))

### FIXED CODE ###

from operator import itemgetter
n,k = map(int,input().split())
li=[]
s=[]
t=[]
g=0
ans=[]
retu=[0]*n
p=0
q=0
for _ in range(n):
    a,b=map(int,input().split())
    li.append([a,b])
li=sorted(li,key=itemgetter(1),reverse=True)
for i in range(k):
    g+=li[i][1]
    if retu[li[i][0]-1]==0:
        retu[li[i][0]-1]+=1
        p+=1
    else:
        t.append(li[i][1])
        q+=1
g+=p**2
ans.append(g)
for i in range(k,n):
    if q==0:
        break
    if retu[li[i][0]-1]==0:
        g=g-t[q-1]+li[i][1]+2*p+1
        p+=1
        q-=1
        ans.append(g)
        retu[li[i][0]-1]+=1
print(max(ans))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N,D,A = map(int,readline().split())
m = map(int,read().split())
XH = np.array(list(zip(m,m)), np.int64)
sortlist = np.argsort(XH[:,0])
XH = XH[sortlist]

ans = 0
for i in range(N):
	if XH[i,1] <= 0:
		continue
	cp = XH[i,0]
	R = cp + (2*D)
	ind = np.searchsorted(XH[:,0],R, side='right')
	attack = -(-XH[i,1]//A)
	ans += attack
	XH[i:ind,1] -= attack*A

print(ans)


### FIXED CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

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

'''
なんで通らないのかわからん
Xの値もしかして間違ってた？
多分TLE
'''


import sys
import math

X = 1000000

prime = []

for i in range(2,X+1):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(prime)
#print(len(prime))

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

#print(det)
#print(B)

if len(B) <= len(prime):

    m = 1

    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        #print(p,count,m)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

import math

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

A_max = max(A)

D = [i for i in range(1+A_max)]

for i in range(2,1+int(A_max**(1/2))):
    if D[i] == i:
        for j in range(2,1+A_max//i):
            D[i*j] = i

prime = {}

for i in range(2,1+A_max):
    if D[i] == i:
        prime[i] = 0

for a in A:
    X = []
    aa = a
    while aa > 1:
        X.append(D[aa])
        aa //= D[aa]
    
    X = set(X)

    for x in X:
        prime[x] += 1

if all([v<=1 for v in prime.values()]):
    print('pairwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

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

LR = [list(map(int, input().split())) for i in range(M)]
pq = [list(map(int, input().split())) for i in range(Q)]

res = [[0]*N for i in range(N)]

def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1

for l,r in LR:
    lsadd(l,r)

for p,q in pq:
    print(sum(res[p-1][:q]))


### FIXED CODE ###

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

LR = [list(map(int, input().split())) for i in range(M)]
pq = [list(map(int, input().split())) for i in range(Q)]

res = [[0]*N for i in range(N)]

def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1

for l,r in LR:
    lsadd(l,r)

for p,q in pq:
    print(sum(res[p-1][:q]))
### BUGGY CODE ###

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

a = [0]
a.extend(list(map(int, input().split())))
a1 = []
for i in range(0, len(a)):
    a1.append(0)
step = 1
t = 0
if k<=5:
    for i in range(0, k):
        step = a[step]
    print(step)
else:

    for i in range(0, 4):
        step = a[step]

        step1 = step
    while(True):
        t += 1
        step1 = a[step1]
        if step1 == step:
            break
    result = step
    k = (k-4) % t
    for i in range(0, k):
        result = a[result]

    print(result)


### FIXED CODE ###

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

a = [0] + list(map(int, input().split()))
a1 = [0] * (n+1)

step = 1
start = 0
while(True):
    start += 1
    a1[step] += 1
    step = a[step]
    if a1[step] == 1:
        break
c = step
gap = 0
while(True):
    gap += 1
    step = a[step]
    if step == c:
        break
result = 1
if k > start:
    k = (k-start) % gap
    result = c
for _ in range(k):
    result = a[result]

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

n,q = map(int,input().split())
s = input()
for i in range(q):
    l,r = map(int,input().split())
    print(s[l-1:r].count('AC'))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
count = [0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1] == 'AC':
        count[i]+=1
for j in range(q):
    l,r = map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline
#import numpy as np

 

 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_&1:
        S.add(x)
        heappush(H,x)
    elif not type_:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

### FIXED CODE ###

# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        if(x in S):S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
D=[]

for i in A:
    if i in S:
        D.append(i)
    else:
        S.append(i)
S=set(S)

import sys
if D==[]:
    print(N)
    sys.exit()

M=N-len(D)
if len(D)%2==1:
    print(M-1)
else:
    MaxD,MinD=D[-1],D[0]
    Med=-1
    for i in S:
        if MinD<=i<=MaxD:
            Med=i
            print(M)
            break
    if Med==-1:
        print(M-2)

### FIXED CODE ###

N=int(input());A=list(map(int,input().split()));S=len(set(A));print(S-1+S%2)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(x) for x in input().split() ]

while m > 0:
    a.sort(reverse=True)
    tmp = a[0] // 2
    for i in range(n):
        if a[i] > tmp and m > 0:
            a[i] //= 2
            m -= 1
        else:
            break

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, tmp * (-1))

print(sum(a) * (-1))
### BUGGY CODE ###

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

ans = 0

for i in range(n):
  ans += a[i]*sum(a[i+1:n])
  
print(ans % (1000000000+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
zenbu = sum(a)
ans = 0

for i in range(n):
  ans += a[i]*(zenbu-a[i])
 
print(ans // 2 % 1000000007)