Harryxun/stf_run huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0
    if point2 == 99:
        print(ans)
        exit()
    for i in range(point2,100):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0
        if point3 == 999:
        print(ans)
        exit()
    for i in range(point3,1000):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-3)
    print(ans-delay)




### FIXED CODE ###

#ABC154-E Almost Everywhere Zero

#桁DP

"""
問題：
n以下の0以外の数字の数が丁度k個である整数の個数を求めよ。

解法：
桁DP
以下の条件があったら桁DPを疑うべし
・桁に関している
・制約が大きい
・整数nがある範囲を動くときの、〜〜〜の最大値を求めよ
・整数nがある範囲を動くときの、〜〜〜という条件を満たすものは何通りあるか←今回はコッチ

考え方：
桁DPでは上位桁から条件を絞っていって、下位桁にクエリを出すという再帰方法で解く。この時、何回もこの再帰をやっていると
下位桁が全く同じ条件になることが出現するので、それをメモ化、呼び出しして動的に解く。
そのためのdpテーブルは３次元で、各階層に対応するのは以下のようなデータ。

dp[i][j][k] = (上から)i桁まで見た,j個Kを使った,k=0:制約ありk=1:自由     の時の条件を満たす場合の個数(value)

問題により多少dpテーブルの内容や順番は異なるが、i桁目まで見た、と、自由度kについての制約は必ずテーブルの中に入る。
もうひとつ、今回で言えばjのテーブルは、kをいくつ使ったか、全桁の合計がD以下であるみたいな問題はいま合計はいくらか
みたいなデータになる。
"""

n = input() #桁DPの場合、nはstr型で取る
m = len(n)
K = int(input()) #DPテーブルのkとかぶって紛らわしいので、大文字にする

dp = [[[0]*2 for j in range(4)] for i in range(105)]
dp[0][0][0] = 1
for i in range(m): #m=桁数
    for j in range(4): #0以外の数はj回使っている
        for k in range(2): #制約,自由の2通り(制約がかかってから気にするんじゃなくて、
            #最初から全桁に制約がかかってるもんだと思って全部計算する)
            nd = int(n[i]) #その桁の数字(制約ありの時に使う)
            for d in range(10): #下位桁に対して10回(0~9まで)まわす
                ni = i+1 #下位桁に
                nj = j #0以外を使った回数はj回
                nk = k #制約か自由か
                if d != 0: nj += 1 #その桁を0だと仮定して場合、現在までの0の個数+=1
                if nj > K: continue #0の個数がKを超えていたら条件を満たさない
                if k == 0: #制約ありの場合
                    if d > nd:continue #その桁の制約を超えていたら飛ばす
                    if d < nd:nk = 1 #逆にd未満ならば、下位桁は自由になるので、k=1:自由にしてやる
                #この下位桁に対するforループを全て満たした時、dpテーブルを更新
                dp[ni][nj][nk] += dp[i][j][k]

ans = dp[m][K][0] + dp[m][K][1] #制約ありでもなしでも良いので、両方足す

print(ans)
n,h = map(int,input().split())
al=[]
bl=[]
for _ in [0]*n:
  a,b = map(int,input().split())
  al.append(a)
  bl.append(b)
al.sort()
bl.sort()
ans = 0
while h>0:
  if bl[-1]>al[-1]:
    h-=bl[-1]
    ans+=1
    del bl[-1]
  else:
    ans += -(-h//al[-1])
    h=0
print(ans)

### FIXED CODE ###

n,h = map(int,input().split())
al=[]
bl=[]
for _ in [0]*n:
  a,b = map(int,input().split())
  al.append(a)
  bl.append(b)
al.sort()
bl.sort()
ans = 0
while h>0:
  if len(bl)>0 and bl[-1]>al[-1]:
    h-=bl[-1]
    ans+=1
    del bl[-1]
  else:
    ans += -(-h//al[-1])
    h=0
print(ans)
a=int(input())
b,c=map(int,input().split())

flag=False
for i in range(a,b+1):
   if i%a==0:
   flag=True
   break
print("OK" if flag else "NG")
  
  




### FIXED CODE ###

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

flag=False
for i in range(b,c+1):
   if i%a==0:
    flag=True
    break
print("OK" if flag else "NG")
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect
from scipy.special import comb
from scipy.special import perm

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
L = list(itertools.permutations(xy, 2))
num = math.factorial(N-1) / comb(N, 2)
ans = 0
for i in range(N-1):
    for l in range(i+1, N):
        ans += math.sqrt((xy[i][0]-xy[l][0])**2+(xy[i][1]-xy[l][1])**2)
ans *= num
print(ans)


### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline
N = int(input())
ans = 0
xy = [list(map(int, input().split())) for i in range(N)]


def maken(n):
    s = 1
    for i in range(1, n+1):
        s *= i
    return s


for i in range(N):
    xy2 = copy.deepcopy(xy)
    c = xy2[i]
    del xy2[i]
    for l in xy2:
        ans += (((c[0]-l[0])**2+(c[1]-l[1])**2)**(1/2))*(maken(N-1))
print(ans/maken(N))
def main():
    n, a, b = map(int, input().split())
    value_max = 2 * (10 ** 5)
    com = [0 for _ in range(value_max + 1)]
    com[1] = n
    mod = 10 ** 9 + 7
    mod_inverse = [pow(i, mod - 2, mod) for i in range(1, value_max + 1)]
    ans = pow(2, n, mod)
 
    # KeyInsight:
    # 全体 - 条件を満たす場合
    # modの世界では割り算の代わりに逆元を使う
    # See:
    # https://www.youtube.com/watch?v=lzAMKPMLdtU&feature=youtu.be
    for i in range(2, min(n, value_max) + 1):
        if (n - i + 1) == 0:
            break
 
        com[i] = com[i - 1] * (n - i + 1)
        com[i] *= mod_inverse[i - 1]
        com[i] %= mod
 
    diff = (com[a] + com[b] + 1) % mod
    print((ans - diff) % mod)
 main()

### FIXED CODE ###

n, a, b = map(int, input().split())
value_max = 2 * (10 ** 5)
com = [0 for _ in range(value_max + 1)]
com[1] = n
mod = 10 ** 9 + 7
mod_inverse = [pow(i, mod - 2, mod) for i in range(1, value_max + 1)]
ans = pow(2, n, mod)

for i in range(2, min(n, value_max) + 1):
    if (n - i + 1) == 0:
        break

    com[i] = com[i - 1] * (n - i + 1)
    com[i] *= mod_inverse[i - 1]
    com[i] %= mod

diff = (com[a] + com[b] + 1) % mod
print((ans - diff) % mod)
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(N):
    A[i] -= i+1

b_index = N // 2

def regret(A, b):
    result = 0
    for a in A:
        result += abs(a-b)
    return result

print(min(regret(A, A[b_index]), regret(A, A[b_index+1])))


### FIXED CODE ###

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

ans = 0
for i in range(N):
    A[i] -= i+1

b_index = N // 2
A.sort()

def regret(A, b):
    result = 0
    for a in A:
        result += abs(a-b)
    return result

ans = regret(A, A[b_index])
if b_index + 1 < N:
    ans = min(ans, regret(A, A[b_index+1]))
print(ans)
N=int(input())
S=input()
arr=[]
v=0
for s in S:
	if s=="I":
		v+=1
		arr.append(v)
	else:
		v-=1
		arr.append(v)
print(max(0,arr))

### FIXED CODE ###

N=int(input())
S=input()
arr=[]
v=0
for s in S:
	if s=="I":
		v+=1
		arr.append(v)
	else:
		v-=1
		arr.append(v)
print(max(0,max(arr)))
# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

count = [0 for _ in range(n)]
for i in reversed(range(1, n + 1)):
    tmp = 0
    for j in range(i, n, i):
        if j % i == 0:
            tmp += a[j]
    if a[i-1] % 2 != tmp % 2:
        count[i] += 1
m = count.count(1)
ans = []
for i in range(n):
    if count[i] == 1:
        ans.append(str(i))

print(m)
print(' '.join(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

count = [0 for _ in range(n)]
for i in reversed(range(1, n + 1)):
    tmp = 0
    for j in range(i, n+1, i):
        tmp += count[j-1]
    #print(tmp)
    if a[i-1] % 2 != tmp % 2:
        count[i-1] += 1
#print(count)
m = sum(count)
ans = []
for i in range(n):
    if count[i] == 1:
        ans.append(str(i+1))

print(m)
print(' '.join(ans))
n=int(input())
i=0
b=[]
pos=0
maxi=0
while(i<n):
  k=int(input())
  b.append(k)
  if(k>maxi):
    pos=i
    maxi=k
  i+=1
b.sort()
ns=b[n-2]
i=0
while(i<n):
  if(i==posi)
  	print(ns)
  else:
    print(b[i])
  i+=1

### FIXED CODE ###

n=int(input())
i=0
b=[]
pos=0
maxi=0
while(i<n):
  k=int(input())
  b.append(k)
  if(k>maxi):
    pos=i
    maxi=k
  i+=1
b.sort()
ns=b[n-2]
i=0
while(i<n):
  if(i==pos):
  	print(ns)
  else:
    print(b[n-1])
  i+=1
count = 0
n = int(input())
arr = list(map(int,input().split()))
ar = []
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if triv(arr[i],arr[j],arr[k]):
        if arr[i]==arr[j] or arr[i]==arr[k] or arr[j]==arr[k]:
          continue
        if arr[i]+arr[j]>arr[k]:
          count+=1
print(count)

### FIXED CODE ###

count = 0
n = int(input())
arr = list(map(int,input().split()))
arr.sort()
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if arr[i]==arr[j] or arr[i]==arr[k] or arr[j]==arr[k]:
        continue
      if arr[i]+arr[j]>arr[k]:
        count+=1
print(count)
n = int(input())
a = list(map(int, input().split()))

b = [0 for _ in range(n)]

i = 0
j = n - 1

while(j > 0):
    b[i] = a[j]
    i += 1
    j -= 2

j = 1 if j == 0 else 0

while(i < n):
    b[i] = a[j]
    i += 1
    j += 2

ans = ' '.join(map(str, b))
print(ans)

### FIXED CODE ###

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

b = [0 for _ in range(n)]
i = 0
j = n - 1

while(j >= 0):
    b[i] = a[j]
    i += 1
    j -= 2

j = 0 if j == -1 else 1

while(i < n):
    b[i] = a[j]
    i += 1
    j += 2

ans = ' '.join(map(str, b))
print(ans)
import bisect

N, M, K = input().split()

desk1 = list(map(int, input().split()))
desk2 = list(map(int, input().split()))

max_time = int(K)
item1 = [0]
item2 = [0]
for i in desk1:
    item1.append(item1[-1] + i)
for i in desk2:
    item2.append(item2[-1] + i)

ret = 0
for i, t in enumerate(item1):
    remain_time = max_time - t
    if remain_time > 0:
        j = bisect.bisect(item2, remain_time) - 1
        if j < 0:
            j = 0
        ret = max(ret, i + j)
    else:
        ret = max(ret, i)
print(ret)import bisect

N, M, K = input().split()

desk1 = list(map(int, input().split()))
desk2 = list(map(int, input().split()))

max_time = int(K)
item1 = [0]
item2 = [0]
for i in desk1:
    item1.append(item1[-1] + i)
for i in desk2:
    item2.append(item2[-1] + i)

ret = 0
for i, t in enumerate(item1):
    remain_time = max_time - t
    if remain_time > 0:
        j = bisect.bisect(item2, remain_time) - 1
        if j < 0:
            j = 0
        ret = max(ret, i + j)
    else:
        ret = max(ret, i)
print(ret)

### FIXED CODE ###

import bisect

N, M, K = input().split()

desk1 = list(map(int, input().split()))
desk2 = list(map(int, input().split()))

max_time = int(K)
item1 = [0]
item2 = [0]
for i in desk1:
    item1.append(item1[-1] + i)
for i in desk2:
    item2.append(item2[-1] + i)

ret = 0
for i, t in enumerate(item1):
    remain_time = max_time - t
    if remain_time >= 0:
        j = bisect.bisect(item2, remain_time) - 1
        ret = max(ret, i + j)

print(ret)
from collections import Counter
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
c = Counter(a)
x = 0
for i in range(k):
  x+=c.most_common()[i][1]
print(n-x)

### FIXED CODE ###

from collections import Counter
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
print(sum(sorted(Counter(a).values())[:-k]))
class UnionFind:
    def __init__(self, length):
        self.r = [-1] * length

    def root(self, x):
        if (self.r[x]) < 0:
            return x

        return self.r[x] - self.root(self.r[x])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

    def size(self, x):
        return -self.r[self.root(x)]


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


relateions = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    relateions.unite(A, B)

max_ = -1
for i in range(N):
    max_ = max(relateions.size(i), max_)

print(max_)


### FIXED CODE ###

class UnionFind:
    def __init__(self, length):
        self.r = [-1] * length

    def root(self, x):
        rx = self.r[x]
        if (rx) < 0:
            return x

        return self.root(rx)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

    def size(self, x):
        return -self.r[self.root(x)]

    def debug(self):
        print(self.r)


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


relations = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    relations.unite(A-1, B-1)

max_ = -1
for i in range(N):
    max_ = max(relations.size(i), max_)

print(max_)
import fractions
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

def gcd(*numbers):
  return reduce(math.gcd, numbers)
def gcd_list(numbers):
  return reduce(math.gcd, numbers)

print(gcd(*new_lst))


### FIXED CODE ###

import fractions
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

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

print(gcd(*new_lst))
n = int(input())
otoshidama = {"JPY":0, "BTC":0}
for i in range(n):
    a, b = map(str, input().split())
    a = float(a)
    if b == "JPY":
        otoshidama["JPY"] = otoshidama["JPY"] + a
    else:
        otoshidama["BTC"] = otoshidama["BTC"] + a
ans = otochidama["JPY"] + otochidama["BTC"] * 380000.0
print(ans)

### FIXED CODE ###

N = int(input())
x = [0]*N
u = [0]*N
answer = 0
for i in range(N):
    x[i], u[i] = map(str, input().split())
    if u[i] == "JPY":
        answer += int(x[i])
    else:
        answer += (float(x[i]) * 380000)



print(answer)
n=int(input())
fir=int(input())
sec=int(input())
max_=sec
if(fir>sec):
    min_=sec
elif(fir<=sec):
    min_=fir
max_dif=sec-fir
if n>2:
    for i in range(n-3):
        x=int(input())
        if x>max_num:
            max_num = x
            if max_dif < x-min_:
                max_dif = x-min_
        if x<min_:
            min_ = x
            max_num=1
print(max_dif)

### FIXED CODE ###

#ALDS1_1_D Maximum Profit
n=int(input())
A=[]
max_dif=-1*10**9
for i in range(n):
    A.append(int(input()))
min=A[0]
for i in range(n-1):
    if(A[i+1]-min>max_dif):
        max_dif=A[i+1]-min
    if(min>A[i+1]):
        min=A[i+1]
print(max_dif)
def color(A, dic):
  if len(A) == 0:
    return 1
  t = A.pop()
  dic[t] -= 1
  return (3-dic[t])*color(A, dic)

n = int(input())
A = list(map(int, input().split()))
dic = {}
for i in range(n):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1
print(color(A, dic))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
que = [-1, -1, -1]
ans = 1
for i in range(n):
  if que[0]+1 == a[i]:
    if que[0] == que[1] and que[0] == que[2]:
      ans *= 3
      ans %= (10**9 + 7)
    elif que[0] == que[1]:
      ans *= 2
      ans %= (10**9 + 7)
    que[0] = a[i]
  elif que[1]+1 == a[i]:
    if que[1] == que[2]:
      ans *= 2
      ans %= (10**9 + 7)
    que[1] = a[i]
  elif que[2]+1 == a[i]:
    que[2] = a[i]
  else:
    ans = 0
    break
print(ans)
n = int(input())
w = input().split(' ')

a = []
k = False
for i in range(n):
    a.append(int(w[i]))
    if a[i] < 0:
       a[i] *= -1
       k = not(k)
    if i == 1:
        min = a[i]
    if a[i] < min:
        min = a[i]

sum = sum(a)
if k:
    sum -= min
print(sum)

### FIXED CODE ###

n = int(input())
w = input().split(" ")

a = []
m = 0
k = False
for i in range(n):
    a.append(int(w[i]))
    if a[i] < 0:
        a[i] *= -1
        k = not (k)
    if i == 0:
        m = a[i]
    if a[i] < m:
        m = a[i]

sum = sum(a)
if k:
    sum -= m*2
print(sum)
t=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p,q=[0],[0]
x,y=[(a[0]-b[0])*t[0],(a[1]-b[1])*t[1]]
#print(x,y,abs(x)<abs(y))
#exit()
if x+y==0:
    print("infinity")
elif (x<0 and y<0) or (x>0 and y>0):
    print(0)
elif (x<0 and x+(x+y)>0) or (x>0 and x+(x+y)<0):
    print(1)
#elif x<0 and x+y>0: OKOK
#    print((abs(x)//(x+y))*2+[0,1][abs(x)%(x+y)>1])
elif x<0 and x+y<0:
    print((y//abs(x+y))*2+[0,1][y%abs(x+y)>1])
else:
    print(hhh)

### FIXED CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
 
P = (A1 - B1) * T1
Q = (A2 - B2) * T2
if P > 0:
	P *= -1
	Q *= -1
 
if P + Q < 0:
	print(0)
elif P + Q == 0:
	print("infinity")
else:
	S = (-P) // (P + Q)
	T = (-P) % (P + Q)
	if T != 0:
		print(S * 2 + 1)
	else:
		print(S * 2)
while True:
    m,n=map(int,raw_input().split())
    if m==n==0:
        break
    L=[]
    s=range(1,m+1)
    for i in range(1,n+1):
        if i%15==0:
            L.append("FizzBuzz")
        elif i%5==0:
            L.append("Buzz")
        elif i%3==0:
            L.append("Fizz")
        else:
            L.append(str(i))

    j=0
    for chars in L:
        t=raw_input()
        if t<>chars:
            del s[j%m]
        j+=1
    for i in s:
        print i

### FIXED CODE ###

def Judge(i):
    if i%15==0: return "FizzBuzz"
    if i%5==0:  return "Buzz"
    if i%3==0:  return "Fizz"
    return str(i)

while True:
    m,n=map(int,raw_input().split())
    if m==n==0:break
    L=range(1,m+1)
    j=0
    for i in range(1,n+1):
        c=raw_input()
	if len(L)>1:
            if Judge(i)!=c:
                del L[j]
                j%=len(L)
            else:
                j=(j+1)%len(L)
    print " ".join(map(str,L))
#!/usr/bin/env python
# coding=utf-8
w=input()
arr=[]
for i in set(s):
    arr.append(s.count(i)%2==0)
print(all(arr))


### FIXED CODE ###

w=input()
arr=[]
for i in set(w):
    arr.append(w.count(i)%2==0)
print("Yes" if all(arr) else "No")
a = []
for i in range(3):
   a.append(input())
print((a[0] + a[1]) * a[2] / 2)

### FIXED CODE ###

a = []
for i in range(3):
   a.append(input())
print((a[0] + a[1]) * a[2] / 2)
import copy
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = []
c1 = []
c2 = []
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0.append(cs[i][j])
        elif (i+j) % 3 == 1:
            c1.append(cs[i][j])
        else:
            c2.append(cs[i][j])
d = 10**9
l0 = len(c0)
l1 = len(c1)
l2 = len(c2)
for i in range(C):
    d0 = 0
    for l in range(l0):
         if (c0[l]-1) != i:
            d0 += ds[c0[l]-1][i]
    for j in range(C):
        if i == j:
            continue
        d1 = copy,copy(d0)
        for h in range(l1):
            if (c1[h]-1) != j:
                d1 += ds[c1[h]-1][j]
        for k in range(C):
            if i == k or j == k:
                continue
            d2 = copy.copy(d1)
            for l in range(l2):
                if (c2[l]-1) != k:
                    d2 += ds[c2[l]-1][k]
            if d > d2:
                d = d2
print(d)



### FIXED CODE ###

import collections
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = collections.defaultdict(int)
c1 = collections.defaultdict(int)
c2 = collections.defaultdict(int)
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0[cs[i][j]] += 1
        elif (i+j) % 3 == 1:
            c1[cs[i][j]] += 1
        else:
            c2[cs[i][j]] += 1
            
d = 10**9
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            d0 = 0
            for l in c0:
                d0 += c0[l] * ds[l-1][i]
            for l in c1:
                d0 += c1[l] * ds[l-1][j]
            for l in c2:
                d0 += c2[l] * ds[l-1][k]
            if d > d0:
                d = d0
            
print(d)
#ABC145 E
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
ab.sort()

a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
    
dp = [[0 for j in range(T)] for _ in range(N+1)]
# i番目より前まで注文してT分以内(max T-1)で完食する
    
for i in range(N):
    for t in range(T): 
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(N):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)


### FIXED CODE ###

n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t+1)] for i in range(n+1)]
 
for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)
k = input()
a, b = map(int, input().split())

for i in range(a,b+1):
  if i%k == 0:
    print("OK")
    break
  else:
    print("NG")
    

### FIXED CODE ###

k = int(input())
a, b = map(int, input().split())
 
for i in range(a,b+1):
  if i%k == 0:
    print("OK")
    break
else:
  print("NG")
import math
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# モンスターの体力を0にすることができる魔力の最小値
dp = [[10**9] * (H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0


for i in range(1, N+1):
    for j in range(1, H+1):
        # j 倒すモンスターのHP
        a, b = AB[i-1]
        # a 攻撃力
        # b 消耗する魔力
        h = math.ceil(j/a)
        # h AB[i]のみを使った場合に必要な魔力
        dp[i][j] = min(dp[i][j], h*b, dp[i-1][j], dp[i-1][j-a]+b)

print(dp[-1][-1])

### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))
N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
for i in range(M):
  dp[a] = -1
k = 10**9+7
d = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if dp[i] == -1:
      continue
    elif i==1:
      dp[i] = 1
    elif i==2:
      dp1 = dp[i-1] if dp[i-1] != -1 else 0
      d += dp[1]
      dp[i] = d
    else:
      dp1 = dp[i-1] if dp[i-1] != -1 else 0
      dp3 = dp[i-3] if dp[i-3] != -1 else 0
      d = d-dp3+dp1
      dp[i] = d
  print(dp[N]%k)

### FIXED CODE ###

N,M = map(int,input().split())
a = set([int(input()) for _ in range(M)])
k = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if i in a:
      continue
    elif i==1:
      dp[1] = 1
    elif i==2:
      dp[i] = 1+dp[1]
    else:
      dp[i] = dp[i-1]+dp[i-2]
  print(dp[N]%k)
import sys
import numpy as np
import collections as cl
import itertools as it
# import more_itertools as mit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

n = int(readline())
w = list(readlines().split())
dic = set()

for i in w:
    if i == 0:
        dic.append(i)
        continue
    if i in dic or dic[i-1][-1] != dic[i][0]:
        print('No')
        sys.exit()
    dic.append(i)
print('Yes')

### FIXED CODE ###

import sys
import numpy as np
import collections as cl
import itertools as it
# import more_itertools as mit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000)

n = int(readline())
w = [input().strip() for _ in range(n)]
dic = set()

for num, i in enumerate(w):
    if num == 0:
        dic.add(i)
        continue
    if i in dic or w[num-1][-1] != i[0]:
        print('No')
        sys.exit()
    dic.add(i)
print('Yes')