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

import numpy as np

def LCS():
  X = input()
  Y = input()
  
  dp = np.zeros([len(Y) + 1,len(X) + 1],dtype = int)
  for y in range(len(Y)):
    for x in range(len(X)):
      if Y[y] == X[x]:
        #Xのi文字目とYのj文字目が一致した時のみ値が更新される
        #文字列が一致する直線、i - 1,j - 1目までの最大一致数に、1を足す
        dp[y + 1][x + 1] = dp[y][x] + 1
        
      else:
        dp[y + 1][x + 1] = max(dp[y][x + 1],dp[y + 1][x])
        
    
  x = len(X)
  y = len(Y)
  ans = ""
  
  while x > 0 and y > 0:
    if dp[y][x] == dp[y - 1][x]:
      y -= 1
    elif dp[y][x] == dp[y][x - 1]:
      x -= 1
    else:
      ans = Y[y - 1] + ans
      y,x = y - 1,x - 1
  
  print(ans)
  
LCS()


### FIXED CODE ###

import numpy as np
#文字列をASCII codeのリストで管理
S = np.array([ord(i) - 97 for i in input()], dtype=int)
T = np.array([ord(i) - 97 for i in input()], dtype=int)
ls = len(S)
lt = len(T)
#S[i] == T[j]であれば、i * j行列の[i,j]成分が1となる行列
equal = np.equal.outer(S,T).astype(int)
#print(equal)
 
dp = [np.zeros(lt + 1,dtype = int)]
#print(dp)
for i in range(ls):
  #追加された最後のdp列をx,newDPとする
  x = dp[-1].copy()
  newDP = x.copy()
  #一致しているところで1を足し、そうでないところはそのまま
  newDP[1:] = np.maximum(x[:-1] + equal[i],newDP[1:])
  #dp[i] = i以前のdpの最大値に更新
  np.maximum.accumulate(newDP, out = newDP)
  #最大共通部分を計算するだけなら一列のdp列を使い回せば良いが
  #文字列の復元のために、dp列を追加する
  dp.append(newDP)
  #print(dp)
 
 
ans = ""
i, j = ls, lt
#数列の復元と文字列への復元
while i > 0 and j > 0:
  if S[i - 1] == T[j - 1]:
    ans += chr(S[i - 1] + 97)
    i -= 1
    j -= 1
    continue
  if dp[i][j] == dp[i - 1][j]:
    i -= 1
  else:
    j -= 1

#リバース
print(ans[::-1])
### BUGGY CODE ###

from copy import deepcopy as dcp
delta = ((1, 0), (0, 1), (-1, 0), (0, -1))
def ds(here, lb, ub, field, count):
	result = 11
	for dx, dy in delta:
		next = (here[0]+dx,here[1]+dy)
		if ( not (lb[0] <= next[0] <= ub[0] and lb[1] <= next[1] <= ub[1]) or
		   field[next[1]][next[0]] == 1) :
		    continue
		tmp = slide(next, (dx,dy), lb, ub, dcp(field), count + 1) 
		if tmp < result :
			result = tmp
	return result

def slide(here, di, lb, ub, field, count):
	while lb[0] <= here[0] <= ub[0] and lb[1] <= here[1] <= ub[1]:
		if here == goal:
			return count
		if field[here[1]][here[0]] == 1:
			field[here[1]][here[0]] = 0
			return ds((here[0]-di[0],here[1]-di[1]), lb, ub, field, count)
		here = (here[0]+di[0],here[1]+di[1])
	else:
		return 11
while 1:
	w, h = map(int,raw_input().split(" "))
	if w == h == 0: break
	board = [[0 for _ in range(w)] for _ in range(h)]
	for j in range(h):
		inp = map(int,raw_input().split(" "))
		for i in range(w):
			tmp = inp[i]
			if tmp == 0: continue
			if tmp == 1: board[j][i] = 1
			elif tmp == 2: start = (i,j)
			else : goal = (i,j)
	count = ds(start, (0,0), (w-1,h-1), board, 0) 
	print count if count < 11 else -1

### FIXED CODE ###

delta = ((1, 0), (0, 1), (-1, 0), (0, -1))
def ds(here, field, count, lb, ub, min_count):
	if count == min_count:
		return min_count
	ans = min_count
	for dx, dy in delta:
		nx, ny = (here[0]+dx,here[1]+dy)
		neighbor = (nx, ny)
		while lb[0] <= nx <= ub[0] and lb[1] <= ny <= ub[1]:
			if field[ny][nx] == 1:
				if (nx, ny) != neighbor:
					field[ny][nx] = 0
					ans = ds((nx-dx,ny-dy),field, count+1, lb, ub, ans)
		    		field[ny][nx] = 1
				break
			if field[ny][nx] == 3:
				if count + 1 < ans:
					ans = count + 1
				break
			nx += dx
			ny += dy
	return ans
while 1:
	w, h = map(int,raw_input().split(" "))
	if w == h == 0: break
	board = [ map(int,raw_input().split(" ")) for _ in range(h)]
	for j in range(h):
		for i in range(w):
			if board[j][i] == 2:
				start = (i,j)
	result = ds(start, board, 0, (0,0), (w-1,h-1), 11)
	print result if result < 11 else -1
### BUGGY CODE ###

from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(
        M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        dp[i+1][used] = min(dp[i+1][used], dp[i][state] + A[i])

        dp[i+1][state] = min(dp[i+1][state], dp[i][state])

ans = dp[-1][-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

INF = 10**18
dp = [INF]*(1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]
for q in range(Q):
    q_lis = S[lr[q][0] -1:lr[q][1]]
    print(q_lis.count('AC'))


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
ansers = [0] * (N+1)
for i in range(N):
    ansers[i+1] = ansers[i] + (1 if S[i:i+2] == 'AC' else 0)
for q in range(Q):
    l,r = map(int,input().split())
    print(ansers[r-1] - ansers[l-1])
### BUGGY CODE ###

N = int(input())
A = [int(v) for v in input().split()]
P = sorted([(v, i) for i, v in enumerate(A)], key=lambda x: x[0], reverse=True)
dp = [[0 for j in range(2005)] for i in range(2005)]

for i in range(N):
    pi = P[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi - l) * A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((N-r-1) - pi) * A[pi])

ans = 0
for i in range(N+1):
    ans = max(ans, dp[N][i])

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(v) for v in input().split()]
P = sorted([(v, i) for i, v in enumerate(A)], key=lambda x: x[0], reverse=True)
dp = [[0 for j in range(2005)] for i in range(2005)]

for i in range(N):
    pi = P[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi - l) * A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((N-r-1) - pi) * A[pi])

ans = 0
for i in range(N+1):
    ans = max(ans, dp[N][i])

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

from bisect import insort_left as sort

import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
list = sorted(list)
for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      sort(temp,list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans += temp.pop()
print(ans)

### FIXED CODE ###

import heapq as hp
import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n+1), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    max_n = n
    max_n = math.sqrt(max_n)
    max_n = math.ceil(max_n)

    ans = [0] * 10050

    for i in range(1, max_n+1):
        for j in range(1, max_n+1):
            for k in range(1, max_n+1):
                v = i*i + j*j + k*k + i*j + j*k + k*i
                if v < 10050:
                    ans[v] += 1

    for i in range(n):
        print(ans[i+1])

    """
    p = itertools.combinations_with_replacement(range(1, max_n), 3)

    #print(len(list(p)))
    ans_list = []


    for v in p:

        x, y, z = v
        ans_cnt = 0
        ans_list.append(x * x + y * y + z * z + x * y + y * z + z * x)



        if ans == m:
            if x == y == z:
                ans_cnt += 1
            elif x == y or y == z or x == z:
                ans_cnt += 3
            else:
                ans_cnt += 6
    """


    """
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)
    """


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


S = str(input())
Q = int(input())
query=[]

# for line in range(Q):
# 	query.append(list(input().split()))

for i in range(Q):
	q=list(input().split())
	if int(q[0])==1:
		S=S[::-1]
	else:
		if int(q[1])==1:
			S=q[2]+S
		else:
			S=S+q[2]
print(S)




### FIXED CODE ###


S = str(input())
Q = int(input())
query=[]
a=""
b=""
# for line in range(Q):
# 	query.append(list(input().split()))
t=True

for i in range(Q):
	q=list(input().split())
	if int(q[0])==1:
		t= not t
	else:
		if int(q[1])==1:
			if t:
				a=q[2]+a
			else:
				b=b+q[2]

		else:
			if t:
				b=b+q[2]
			else:
				a=q[2]+a

if t:
	print(a+S+b)
else:
	print(b[::-1]+S[::-1]+a[::-1])
### BUGGY CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.pop()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
import numpy as np
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
      
    A = np.array(A)
    ans = max(ans,max(A[A<10**5]))
    
print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate

def main():
  input = sys.stdin.readline
  N, C = map(int, input().split())
  X = []
  V = []
  for _ in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)
  Vr = V[::-1]
  Xr = X[::-1]
  
  
  R = list(accumulate(V))
  for i in range(N):
    R[i] = R[i] - X[i]

  L = list(accumulate(Vr))
  for i in range(N):
    L[i] = L[i] - (C - Xr[i])

  Rmax = max(R)
  Lmax = max(L)
  
  RLmax = 0
  for i in range(N-1):
    cur = R[i] + max(L[:-(i+1)]) - X[i]
    RLmax = max(RLmax, cur)
    if R[i] == Rmax:
      break
  
  LRmax = 0
  for i in range(N-1):
    cur = L[i] + max(R[:-(i+1)]) - (C - Xr[i])
    LRmax = max(LRmax, cur)
    if L[i] == Lmax:
      break
  
  ans = max(0, Rmax, Lmax, RLmax, LRmax)
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
from itertools import accumulate

def main():
  input = sys.stdin.readline
  N, C = map(int, input().split())
  X = []
  V = []
  for _ in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)
  Vr = V[::-1]
  Xr = X[::-1]

  F = list(accumulate(V))
  R = list(accumulate(Vr))
  F[0], R[0] = F[0] - X[0], R[0] - (C - Xr[0])
  for i in range(1, N):
    F[i] = max(F[i-1], F[i] - X[i])
    R[i] = max(R[i-1], R[i] - (C - Xr[i]))

  val = 0
  for i in range(N-1):
    v1 = F[i] + R[N-(i+2)] - X[i]
    v2 = R[i] + F[N-(i+2)] - (C - Xr[i])
    val = max(val, v1, v2)
  
  ans = max(0, val, max(F), max(R))
  print(ans)


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

N,M = map(int,input().split())
one_to = []
to_N = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        one_to.append(b)
    if b == N:
        to_N.append(a)
one_to.sort()
to_N.sort()
ans = 0 
for i in one_to:
    count = 0
    for j in range(len(to_N)):
        if i == to_N[j]:
            ans = 1
            break
        if i > to_N[j]:
            count += 1
        if i < to_N[j]:
            break
    to_N = to_N[count:]
    if ans == 1:
        break
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

### FIXED CODE ###

N,M = map(int,input().split())
ans = 0
dic = {str(i):0 for i in range(1,N)}
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        dic[str(b)] += 1
        if dic[str(b)] == 2:
            ans = 1
    if b == N:
        dic[str(a)] += 1
        if dic[str(a)] == 2:
            ans = 1
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

import bisect
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    min_num = min(a)
    process = []
    p_append = process.append

    for i in range(m):
        array = list(map(int, input().split()))
        if array[1] > min_num:
            p_append(array)


    a.sort()
    process = sorted(process, key=lambda x: -x[1])

    for i in range(len(process)):
        index = bisect.bisect_left(a, process[i][1])
        ooo = min(index, process[i][0])
        if ooo == 0:
            continue
        else:
            a = a[ooo:] + [process[i][1] for k in range(ooo)]
        if a[0] > process[i][1]:
            break

    print(sum(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from operator import itemgetter

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    change = []
    process = []
    p_append = process.append

    for i in range(m):
        array = list(map(int, input().split()))
        p_append(array)

    process.sort(key = itemgetter(1),reverse=True)

    for i in range(len(process)):
        change += [process[i][1]] * process[i][0]
        if len(change) >= n:
            break

    a = a + change
    a.sort(reverse=True)
    a = a[:n]
    print(sum(a))

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

import copy
n = int(input())
ai = [int(i) for i in input().split()]

a2 = [[0 for i in range(20)] for j in range(n)]

#keta = len(format(max(ai),'b'))

for i in range(n):
    tmp = format(ai[i], '0'+str(20)+'b')
    for j in range(20):
        a2[i][j] = int(tmp[j])
    #print()

tmp = a2[0]
flag = True
ans = 0
cnt = 1

for i in range(n-1):
    #print(ans)
    flag = True
    if cnt == 0:
        tmp = a2[i]
        cnt = 1
    while flag == True:
        if i+cnt-1 == n:
            cnt -= 1
            ans += cnt
            flag = False
            break
            #print(i+cnt-1,n,cnt)
            #exit()
        for m in range(i+cnt,n):
            c_tmp = copy.deepcopy(tmp)
            #print(tmp,cnt,m)
            if flag == False:
                break
            for j in range(20):
                if c_tmp[j] + a2[m][j] > 1:
                    flag = False
                    ans += cnt
                    cnt -= 1
                    for j in range(20):
                        tmp[j] -= a2[i][j]
                    break
                else:
                    c_tmp[j] += a2[m][j]
                    #print(c_tmp,tmp,111111,a2[m][j],j)
            if flag == False:
                break
            tmp = c_tmp
            cnt += 1
            if m == n-1:
                #print(m,n-1,i)
                flag = False
                ans += cnt
            if flag == False:
                break
            
print(ans+1)

### FIXED CODE ###

n = int(input())
ai = [int(i) for i in input().split()]

ans = 0
s = 0
x = 0

r = 0
            
for l in range(n):
    while r <= n-1 and s+ai[r] == x^ai[r]:
        s += ai[r]
        x ^= ai[r]
        r += 1
    ans += (r-l)
    
    if l == r:
        r += 1
    else:
        s -= ai[l]
        x ^= ai[l]
        
print(ans)
### BUGGY CODE ###

(N,K,Q) = map(int,list(input().split()))
ansed = []
for x in range(0,Q):
    ansed.append(int(input()))
for y in range(1,N+1):
    if K - Q + ansed.count(y) > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

points = []
for x in range(N):
    points.append(K-Q)

for y in range(Q):
    ansed = int(input()) - 1
    points[ansed] += 1

for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())

count = 0
for i in range(1, 10):
    for j in range(1, 10):
        cij = 0
        cji = 0
        
        for k in range(1, n+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                cij += 1
                
            if str(k)[0] == str(j) and str(k)[-1] == str(i):
                cji += 1
        
        count += cij * cji

print(count)

### FIXED CODE ###

n = input()
digit_num = len(n)
if digit_num == 1:
    print(n)

else:
    first_digit = int(n[0])
    last_digit = int(n[-1])
    n = int(n)
    count = 0
    
    for i in range(1, 10):
        for j in range(i, 10):
            ci = 0
            cj = 0
            
            if i == j:
                if i < first_digit:
                    for k in range(digit_num - 1):
                        ci += 10 ** k
                    ci += 1
                
                elif i == first_digit:
                    for k in range(digit_num - 2):
                        ci += 10 ** k
                    ci += 1
                    ci += (n % (10 ** (digit_num-1))) // 10
                    if last_digit >= i:
                        ci += 1
                
                else:
                    for k in range(digit_num - 2):
                        ci += 10 ** k
                    ci += 1
            
                count += ci ** 2
            
            else:
                if j < first_digit:
                    for k in range(digit_num - 1):
                        ci += 10 ** k
                    cj = ci
                
                elif j == first_digit:
                    for k in range(digit_num - 1):
                        ci += 10 ** k
                    for k in range(digit_num - 2):
                        cj += 10 ** k
                    cj += (n % (10 ** (digit_num-1))) // 10
                    if last_digit >= i:
                        cj += 1
                
                elif i < first_digit and j > first_digit:
                    for k in range(digit_num - 1):
                        ci += 10 ** k
                    for k in range(digit_num - 2):
                        cj += 10 ** k
                
                elif i == first_digit:
                    for k in range(digit_num - 2):
                        ci += 10 ** k
                    ci += (n % (10 ** (digit_num-1))) // 10
                    if last_digit >= j:
                        ci += 1
                    
                    for k in range(digit_num - 2):
                        cj += 10 ** k
                    
                else:
                    for k in range(digit_num - 2):
                        ci += 10 ** k
                    cj = ci
                    
                count += ci * cj * 2

    print(count)
### BUGGY CODE ###

# coding: utf-8
N = int(input())

P = [i+1 for i in range(N)]

res = 0
for i in range(N-1):
    res += (i+1) % P[i+1]

print(res)

### FIXED CODE ###

N = int(input())

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

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

import functools
import operator

n = functools.reduce(operator.mul, A)

if n > 10 ** 18:
    n = -1

print(n)


### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    for i in range(N):
        n = n * A[i]
        if n > 10 ** 18:
            n = -1
            break

    print(n)
### BUGGY CODE ###

import math
import numpy as np

N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
#for i in range(len(P)): #Pの中身は次の動く先の位置なのでデクリメントする
#    P[i] -= 1

ans = -99999999999999

for i in range(N):
    x = i
    total = 0
    s=[]
    while(1):#サイクルごとに長さをまず求める，
        x = P[x]-1
        s.append(C[x])
        total += C[x]
        if x == i:
            break
    l = len(s)#サイクルの長さ
    t = 0
    for i in range(l):#サイクルの中でどこで終わるのがベストか探す
        t += s[i]
        if i+1> K:#Kがサイクルより短かったらそこで終わる
            break
        now = t
        if total > 0:
            cycle = int((K-i-1)/l)
            now += total*cycle

        ans = max(ans, now)

print(ans)


### FIXED CODE ###

#import math
#import numpy as np

N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
#for i in range(len(P)): #Pの中身は次の動く先の位置なのでデクリメントする
#    P[i] -= 1

ans = -99999999999999

for i in range(N):
    x = i
    total = 0
    s=[]
    while(1):#サイクルごとに長さをまず求める，
        x = P[x]-1
        s.append(C[x])
        total += C[x]
        if x == i:
            break
    l = len(s)#サイクルの長さ
    t = 0
    for i in range(l):#サイクルの中でどこで終わるのがベストか探す
        t += s[i]
        if i+1> K:#Kがサイクルより短かったらそこで終わる
            break
        now = t
        if total > 0:
            cycle = int((K-i-1)/l)
            now += total*cycle

        ans = max(ans, now)

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

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]

N_K = [K for i in range(N)]
for i, a in enumerate(A):
    for j, n_k in enumerate(N_K):
        if a-1 != j:
            N_K[j] = n_k - 1

for k, n_k in enumerate(N_K):
    if n_k <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0]*N
# print(A)

for i in range(Q):
    A[int(input())-1] +=1
    # print(A)

for i in range(N):
    if K-Q+A[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

n = int(input())
sequence = [input()]
if n!=1:
    for i in range(n-1):
        a = input()
        for sen in sequence:
            if a == sen:
                break
            else:
                if sen == sequence[-1]:
                    sequence.append(a)
print(len(sequence)) 

### FIXED CODE ###

n = int(input())
sequence = [input() for _ in range(n)]

print(len(set(sequence)))