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

import sys
input = sys.stdin.readline
import heapq

def main():
    N,M = map(int,input().split())
    INF = 10**10+1
    root = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N-1):
        root[i+1][i] = 0
    for _ in range(M):
        a,b,c = map(int,input().split())
        root[a-1][b-1] = c
        root[b-1][a-1] = c
    
    dist = [INF for _ in range(N)]
    que = [(0,0)]
    dist[0] = 0
    while que:
        dif,now = heapq.heappop(que)
        for f,fol in enumerate(root[now]):
            if (fol != INF and dist[f] > dist[now] + fol):
                dist[f] = dist[now] + fol
                heapq.heappush(que,(dist[f],f))
                
    if dist[-1] == INF:
        print(-1)
    else:
        print(dist[-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq

def main():
    N,M = map(int,input().split())
    INF = 10**15
    root = [[] for _ in range(N)]
    for i in range(N-1):
        root[i+1].append((0,i))
    for _ in range(M):
        l,r,c = map(int,input().split())
        root[l-1].append((c,r-1))
    
    dist = [INF for _ in range(N)]
    q = [(0,0)]
    dist[0] = 0
    while q:
        d,now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for cost,fol in root[now]:
            _d = d+cost
            if dist[fol] > _d:
                dist[fol] = _d
                heapq.heappush(q,(_d,fol))

    if dist[-1] == INF:
        print(-1)
    else:
        print(dist[-1])

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

def main():
    s=input()
    q=int(input())
    for _ in range(q):
        t=input()
        if t=='1':
            s=s[::-1]
        else:
            t = t.split()
            if int(t[1])==1:
                s = t[2] + s
            else:
                s  += t[2]
    print(s)
main()

### FIXED CODE ###

def main():
    s=input()
    q=int(input())
    rot = 0
    A = ''
    B = ''
    for _ in range(q):
        t=input()
        if t=='1':
            rot += 1
        else:
            t = t.split()
            if (int(t[1])+rot)%2==1:
                A += t[2] 
            else:
                B  += t[2]
    if not rot%2:
        print(''.join(A[::-1]+s+B))
    else:
        print(''.join(B[::-1]+s[::-1]+A))        
main()
### BUGGY CODE ###

n=int(input())
d={}
for i in range(n):
    tmp = input()
    if tmp in d:
        d[tmp]+=1
    else:
        d[tmp]=1
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
for i in max_k_list:
    print(i)
    

### FIXED CODE ###

n=int(input())
d={}
for i in range(n):
    tmp = input()
    if tmp in d:
        d[tmp]+=1
    else:
        d[tmp]=1
max_k_list=[]
max_d = max(d.values())
for k,v in d.items():
    if v == max_d:
        max_k_list.append(k)
max_k_list.sort()
for i in max_k_list:
    print(i)
### BUGGY CODE ###

from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y

def lcm(A):
    m = 1
    for a in A:
        m *= a//gcd(m,a)
    return m


def chinese_remainder_theorem(R, M):
    """
    returns x and lcm(M) s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    big_m = lcm(M)
    for m,r in zip(M,R):
        p = big_m//m
        s += r * p * pow(p, -1, m)
        s %= big_m
    return s, big_m


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods)[0]
    if t > 0:
        res = min2(res, t)

print(res)

### FIXED CODE ###

from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def chinese_remainder_theorem(R, M, prod):
    """
    returns x s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    for m,r in zip(M,R):
        p = prod//m
        s += r * p * modinv(p,m)
        s %= prod
    return s


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
    N *= 2
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods, N)
    if t > 0:
        res = min2(res, t)

print(res)
### BUGGY CODE ###

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

dp = [ [[0] * 3000 for _ in range(55)] for __ in range(55) ]
dp[0][0][0] = 1

for j in range(n+1):
    for k in range(n+1):
        for s in range(2555):
            if j > 0 and x[j-1] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif j > 0 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

ans = 0

for k in range(1, n+1):
    ans += dp[n][k][k*a]

print(ans)


### FIXED CODE ###

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

dp = [ [[0] * 3000 for _ in range(55)] for __ in range(55) ]
dp[0][0][0] = 1

for j in range(n+1):
    for k in range(n+1):
        for s in range(2555):
            if j > 0 and x[j-1] > s:
                dp[j][k][s] = dp[j-1][k][s]
            elif j > 0 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]

ans = 0

for k in range(1, n+1):
    ans += dp[n][k][k*a]

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

# -*- coding: utf-8 -*-


def main():
    n = int(input())

    p = 1

    for i in range(1, n+1):
        p *= i
    print(p%(10**9+7))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

N = int(input())
print(math.factorial(N)%(10**9+7))
### BUGGY CODE ###

n=int(input())
for i in range(1,10**9):
    if i%2==0 and i%n==0:
        print(i)
        exit()


### FIXED CODE ###

a=int(input())
b=2
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
print(lcm(a,b))
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R, C, K = NMI()
    item = {(0,0):0}

    for i in range(K):
        r_, c_, v_, = NMI()
        item[(r_ - 1,c_ - 1)] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                if (i,j) in item:
                    v = item[(i,j)]
                else:
                    v = 0

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R, C, K = NMI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = NMI()
        item[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))

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

import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(k,50)):
  imos=[0]*(n+1)
  for j in range(n):
    imos[max(j-a[j],0)]+=1
    imos[min(j+a[j]+1,n)]-=1
  a=list(itertools.accumulate(imos))
  if a[:n]==[n]*n:
    break
    
print(*a[:n]) 


### FIXED CODE ###

import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(k,50)):
  imos=[0]*(n+1)
  for j in range(n):
    imos[max(j-a[j],0)]+=1
    imos[min(j+a[j]+1,n)]-=1
  a=list(itertools.accumulate(imos))
  if a[:n]==[n]*n:
    break
    
print(*a[:n])
### BUGGY CODE ###

import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    for i in range(Q):
        print(sum([LR[i][0]<=like2017 <= LR[i ][1] for like2017 in like2017_list]))


    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    csum = [0]*(MAX_Q+1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q+1):
        csum[i] = cnt
        
    
    for i in range(Q):
        print(csum[LR[i][1]] - csum[LR[i][0]-1])


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

N, K = map(int, input().split())
P = list(map(int, input().split()))
result = 0
B = []

for i in range(len(P)-K+1):
    B.append(sum(P[i:i+K]))
        
A = B.index(max(B))
print(sum(P[A:A+K])/2+0.5*K)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
result = 0
B = [a / 2 + 0.5 for a in P]

result = sum(B[0:K])
t = sum(B[0:K])
for i in range(N-K):
    t -= B[i]
    t += B[i+K]
    if t > result:
        result = t

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

n,m=map(int,input().split())
t=[[]for _ in range(n)]
ne=(n-1)*n//2
ne_s=set()
e=[]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e.append([a,b])
  if b not in ne_s:
    ne_s.add(b)
    ne-=b
  t[a].append(b)
d=[0]*n
Q=[ne]
di=1
while Q:
  P=[]
  for i in Q:
    for j in t[i]:
      d[j]=max(d[j],di)
      P.append(j)
  di+=1
  Q=P
ans=[0]*n
for a,b in e:
  if d[a]+1!=d[b]:continue
  ans[b]=a+1
print(*ans)

### FIXED CODE ###

n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n+m-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t
top=find_loop(n,edge,1)
d=[0]*n
for i in range(n):
  for j in edge[top[i]]:d[j]=d[top[i]]+1
ans=[-1]*n
ans[d.index(0)]=0
for i in range(n):
  for j in edge[i]:
    if d[i]+1==d[j]:ans[j]=i+1
print(*ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

d.sort()
t.sort()

flag = True
for i in range(len(t)):
    if t[i] in d:
        del d[d.index(t[i])]
    else:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

d.sort()
t.sort()

d = array_count(d)
t = array_count(t)

for i in range(len(t)):
    t[i][1] = -1 * t[i][1]
    d.append(t[i])

d.sort()

for i in range(1,len(d)):
    if d[i-1][0] == d[i][0]:
        d[i-1][1] = d[i-1][1] + d[i][1]
        d[i][1] = 0

flag = True

for i in range(len(d)):
    if d[i][1] < 0:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import bisect

N = int(input())
L = sorted(list(map(int, input().split())))

cnt = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        idx = bisect.bisect_left(L, L[i] + L[j], lo=j + 1)
        cnt += max(0, idx - (j + 1))

print(cnt)

### FIXED CODE ###

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


L.sort(reverse=True)
dic = {}
cnt = 0

for i in range(1, N - 1):
    p = L[i]
    for j in range(i + 1, N):
        s = p + L[j]

        if s not in dic:
            dic[s] = 1
        else:
            dic[s] += 1

for i in range(N - 2):
    p = L[i]

    if i > 0:
        for x in range(i + 1, N):
            dic[p + L[x]] -= 1

    for key, value in dic.items():
        if key > p:
            cnt += value

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

n = int(input())
V = list(map(int, input().split()))
A = set(V)

if len(A) == 1:
	print(len(V)//2)
	exit(0)

ans = 0
for i in range(len(V)-2):
	if V[i] != V[i+2]:
		for d in A:
			if V[i] == d:
				V[i+2] = d
				ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int, input().split()))

even = []
odd = []
for i, v in enumerate(V):
	if i % 2 == 0: even.append(v)
	else: odd.append(v)

cnt_even = Counter(even).most_common(2)
cnt_odd = Counter(odd).most_common(2)

if cnt_even[0][0] != cnt_odd[0][0]:
	ans = len(V) - cnt_even[0][1] - cnt_odd[0][1]
else:
	if cnt_even[0][1] + cnt_odd[0][1] == len(V):
		ans = len(V) // 2

	elif len(cnt_odd) < 2 or len(cnt_even) < 2:
		ans = len(V) - cnt_even[0][1] - cnt_odd[0][1]
	else:
		ans1 = len(V) - cnt_even[0][1] - cnt_odd[1][1]
		ans2 = len(V) - cnt_even[1][1] - cnt_odd[0][1]
		ans = min(ans1, ans2)

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

N, K = map(int, input().split())
pn = list(map(int, input().split()))
 
maxlist = 0
for i in range(N-K+1):
    p = pn[i:i+K]
    maxlist = max(maxlist, sum(p))
 
ans = (maxlist+K)/2
print('{:.12f}'.format(ans))

### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
### BUGGY CODE ###

N=int(input())
A =list(map(int,input().split()))
sum =0
for i in range(N):
    for j in range(i+1,N):
        sum += A[i]*A[j]
a =10**9+7
print(sum%a)

### FIXED CODE ###

N=int(input())
A =list(map(int,input().split()))
S =(sum(A))**2
for i in A:
        S-=i**2
a =10**9+7
print((S//2)%a)
### BUGGY CODE ###

n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(m)]
C = [b for a, b in AB if a == 1]
for a, b in AB:
  if a in C and b == n:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(m)]

C, D = set(), set()
for a, b in AB:
  if a == 1:
    C.add(b)
  elif b == n:
    D.add(a)

if len(C & D):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
A = [int(input())-1 for i in range(N)]

light = 0
first = 0
ans = 0

while True:
    if light == A[light]:
        print(-1)
        exit()
    light = A[light]
    ans += 1
    if light == 1:
        print(ans)
        exit()
    if light == first:
        print(-1)
        exit()



### FIXED CODE ###

N = int(input())
A = [int(input())-1 for _ in range(N)]
p = 0
for i in range(N):
    if p == 1:
        print(i)
        break
    p = A[p]
else:
    print(-1)
### BUGGY CODE ###

a, b = (int(i) for i in input().split())

for i in range(0, 10**9):
  if (a-i) == (b-i):
    print(i)
    
print("IMPOSSIBLE")

### FIXED CODE ###

a, b = (int(i) for i in input().split())
 
if a % 2 != b % 2:
  print("IMPOSSIBLE")
else:
  print(int((a+b) / 2))
### BUGGY CODE ###

from collections import Counter
from functools import reduce

def modular_inverse(a, mod):
    return pow(a, mod-2, mod)

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split())
K=k-q
x=[]
for i in range (q):
    a=int(input())
    x.append(a)

for i in range (1,n+1,1):
    if  K+int(x.count(i))>0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n,k,q=map(int,input().split())
p=k-q
l=[p]*n
for i in range(q):
    a=int(input())
    l[a-1]+=1
for i in range(n):
    print('Yes' if l[i]>0 else 'No')
### BUGGY CODE ###

n, m = (int(x) for x in input().split())
ss = set(range(n))
for _ in range(m):
  l, r = (int(x) for x in input().split())
  ss = ss.intersection(range(l-1, r))
print(len(ss))

### FIXED CODE ###

n, m = (int(x) for x in input().split())
max_l = float('-inf')
min_r = float('inf')
for _ in range(m):
  l, r = (int(x) for x in input().split())
  max_l = max(max_l, l)
  min_r = min(min_r, r)
print(max(0, min_r - max_l+1))
### BUGGY CODE ###

import numpy as np

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

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = min(arr[1:] - arr[:-1])
        if result > answer:
            answer = result
    else:
        dfs(cur+1, times + [D[cur]])
        dfs(cur+1, times + [24-D[cur]])

answer = 0
dfs(0, [0, 24])
print(answer)

### FIXED CODE ###

import numpy as np

N = int(input())
D = list(map(int, input().split()))
if N > 23:
    print(0)
    exit()
for i in range(13):
    if D.count(i) >= 3:
        print(0)
        exit()
    elif D.count(i) == 2 and D.count(i+1) == 2:
        print(1)
        exit()

# 深さ優先探索で全通りを探索できるのでは curは０からスタート
def dfs(cur, times):
    global answer
    if cur == N:
        times.sort()
        arr = np.array(times)
        result = (arr[1:] - arr[:-1]).min()
        if result > answer:
            answer = result
    else:
        x = D[cur]
        dfs(cur+1, times + [x])
        dfs(cur+1, times + [24-x])

answer = 0
dfs(0, [0, 24])
print(answer)