Harryxun/stf_run huggingface dataset:
N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
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)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if (K-A*i)%B==0:
        j //= B
        n+=(memo[i]*memo[j])%998244353
        n%=998244353
print(n%998244353)

### FIXED CODE ###

N,A,B,K = map(int,input().split())
n = 0
MOD = 998244353
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)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v
for i in range(N+1):
    j = K-A*i
    if j < 0:
        break
    if j%B==0 and j/B <= N:
        j //= B
        n+=memo[i]*memo[j]
        n%=998244353
print(n%998244353)
L = [0 for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0

for i in range(N):
    tmp = format(As[i], 'b').zfill(60)

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i + 1)]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)


### FIXED CODE ###

N = int(input())
L = [0 for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0

for A in As:
    for i in range(60):
        if A >> i & 1 == 1:
            L[i] += 1

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[i]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)
S = input()
Steam = 0
mincraft = 0
for i in range()len(S):
    if S[i] == "+":
        minecraft += 1
    else:
        steam += 1
L = minecraft * 1
P = steam * -1
print(L + P)

### FIXED CODE ###

S = input()
Steam = 0
minecraft = 0
for i in range(len(S)):
    if S[i] == "+":
        minecraft += 1
    else:
        Steam += 1
L = minecraft * 1
P = Steam * -1
print(L + P)
sum_row = [0] * (c + 1)

for ri in range(r):
    data.append([int(i) for i in input().sprit()])
    data[ri].append(sum(data[ri]))
    print(" ".join([str(d) for d in data[ri]]))
    for ci in range(c + 1):
        sum_row[ci] += data[ri][ci]
        
print(" ".join([str(s) for s in sum_row]))
        

### FIXED CODE ###

r, c =[int(i) for i in input().split()]
 
date =[]
sum_row = [0] * (c + 1)
 
for ri in range(r):
    date.append([int(i) for i in input().split()])
    date[ri].append(sum(date[ri]))
    print(" ".join([str(d) for d in date[ri]]))
    for ci in range(c + 1):
        sum_row[ci] += date[ri][ci]
 
print(" ".join([str(s) for s in sum_row]))
def test():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    a.reverse()
    s=list(set(a))
    s.sort()
    s.reverse()
    ans=[]
    v=0
    for i in s:
        if 4<=a.count(i):
            v="i"
        elif 2<=a.count(i)<=3:
            ans.append(i)
        if v or 2<=len(ans):
            return max(int(v)*int(v),ans[0]*ans[1])
    return 0
t=test()
print(t)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import Counter
data=Counter(a)
two_i=[]
four_i=[]
for i,j in data.items():
    if 4<=j:
        four_i.append(i)
    elif 2<=j:
        two_i.append(i)
two_i.sort()
four_i.sort()
two_i.reverse()
four_i.reverse()
if len(four_i)==0:
    four_i.append(0)
if len(two_i)<=1:
    two_i.append(0)
    two_i.append(0)
four_area=four_i[0]*four_i[0]
two_area=two_i[0]*two_i[1]
mix_area=two_i[0]*four_i[0]
print(max(four_area,two_area,mix_area))
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

A, B, K = list(map(int, sys.stdin.readline().split()))

arr = list(range(A, B + 1))
a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))


### FIXED CODE ###

import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

# N, M, X = list(map(int, sys.stdin.readline().split()))
# A = np.array(list(map(int, sys.stdin.readline().split())))
#
# print(min(len(A[A > X]), len(A[A<X])))

A, B, K = list(map(int, sys.stdin.readline().split()))

a = list(range(A, min(B, A + K)))
b = list(range(max(A, B - K + 1), B + 1))



print('\n'.join(map(str, list(sorted(set(a + b))))))
s = input()
t = input()

result = s* t

if result % 2 == 0:
    print('Even')
else:
    print('Odd')


### FIXED CODE ###

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

result = a* b

if result % 2 == 0:
    print('Even')
else:
    print('Odd')
# -*- coding: utf-8 -*-

N = int(input())

print((N**2-N)/2

### FIXED CODE ###

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

N = int(input())
a = (N*(N-1)//2)
print (a)
w=input()
w1=input()
num=len(w)
num1=len(w1)
start=-1
if num<num1:
  b1=False
for i in range(num-num1+1):
  b=True
  for j in range(num1):
    if w[i+j]=="?" or w[i+j]==w1[j]:
      pass
    else:
      b=False
  if b:
      start=i
if start==-1:
  print("UNRESTORABLE")
else:
  word=""
  if start!=0:
    for i in range(start):
      if w[i]=="?":
        word+="a"
      else:
        word+=w[i]
    for i in range(start,num):
      word+=w1[i-start]
  else:
    word+=w1
    for i in range(num1,num):
      if w[i]=="?":
        word+="a"
      else:
        word+=w[i]
  print(word)


### FIXED CODE ###

w=input()
w1=input()
num=len(w)
num1=len(w1)
start=-1
if num<num1:
  b1=False
for i in range(num-num1+1):
  b=True
  for j in range(num1):
    if w[i+j]=="?" or w[i+j]==w1[j]:
      pass
    else:
      b=False
  if b:
      start=i
if start==-1:
  print("UNRESTORABLE")
else:
  word=""
  for i in range(num):
    if i<start:
      if w[i]=="?":
        word+="a"
      else:
        word+=w[i]
    elif start<=i and i<=start+num1-1:
      word+=w1[i-start]
    else:
      if w[i]=="?":
        word+="a"
      else:
        word+=w[i]
  print(word)
import sys
input = sys.stdin.readline


N = int(input().rstrip())
a_dict = {}
for i in range(N):
  a_dict[i+1] = int(input().rstrip())

target = 1
next_target = a_dict[target]
cont = True
ans = 0

while cont:
  del a_dict[target]
  target = next_target
  next_target = a_dict[target]
  ans += 1
  if next_target not in a_dict:
    ans = -1
    cont = False
  elif next_target == 2:
    ans += 1
    cont = False

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


N = int(input().rstrip())
a_dict = {}
for i in range(N):
  a_dict[i+1] = int(input().rstrip())

target = 1
next_target = a_dict[target]
cont = True
ans = 0

if next_target == 2:
  cont = False
  ans += 1

while cont:
  target = next_target
  next_target = a_dict[target]
  ans += 1
  del a_dict[target]
  if next_target not in a_dict:
    ans = -1
    cont = False
  elif next_target == 2:
    ans += 1
    cont = False
print(ans)
n = int(input())

def func(x):
  res = []
  for i in range(n):
    res.append(x%2)
    x //= 2
  return res

test = {}
for i in range(n):
  A = int(input())
  test[i+1] = []
  for a in range(A):
    x,y = map(int,input().split())
    test[i].append((x,y))

ans = 0
for i in range(2**n):
  people = func(i)
  for i in range(n):
    if people[i]:
      for x,y in test[i+1]:
        if people[x-1] == y:
          continue
        else:
          break
      else:
        continue
      break
  else:
    ans = max(sum(people),ans)
print(ans)

### FIXED CODE ###

n = int(input())

def func(x):
  res = []
  for i in range(n):
    res.append(x%2)
    x //= 2
  return res

test = {}
for i in range(n):
  A = int(input())
  test[i+1] = []
  for a in range(A):
    x,y = map(int,input().split())
    test[i+1].append((x,y))

ans = 0
for i in range(2**n):
  people = func(i)
  for i in range(n):
    if people[i]:
      for x,y in test[i+1]:
        if people[x-1] == y:
          continue
        else:
          break
      else:
        continue
      break
  else:
    ans = max(sum(people),ans)
print(ans)
a, b, x = map(int,input().split())
s = x/a
import math
if (a*b / 2 >= s):
  h = 2*s/b
  rad = math.atan(h/b)
  print(90.0 - math.degrees(rad))
else:
  rest = a*b - s
  l = 2*rest/a
  rad = math.atan(a/l)
  print(90.0 - math.degrees(rad))

### FIXED CODE ###

a, b, x = map(int,input().split())
s = x/a
import math
if s == a * b:
  print(0)
elif (a*b / 2 >= s):
  h = 2*s/b
  rad = math.atan(h/b)
  print(90.0 - math.degrees(rad))
else:
  l = 2*(b - s/a)
  rad = math.atan(a/l)
  print(90.0 - math.degrees(rad))
def main(pro):
    ans = 'keyence'
    try:
        lokasi = pro.index(ans)
        if lokasi > 0 and lokasi + len(ans) < len(pro):
            raise ValueError()
            return
        else:
            print('YES')
            return
    except:
        # it is split
        for i in range(len(ans)):
            if ans[i] != pro[i]:
                break
        r = len(ans) - i
        for a in range(1,r+1):
            if ans[-r] != pro[-r]:
                print('NO')
                return
        print('YES')
while True:
    main(input())

### FIXED CODE ###

def main(pro):
    ans = 'keyence'
    try:
        lokasi = pro.index(ans)
        if lokasi > 0 and lokasi + len(ans) < len(pro):
            raise ValueError()
        else:
            print('YES')
            return
    except:
        for i in range(len(ans)):
            if ans[i] != pro[i]:
                break
        r = len(ans) - i
        for a in range(1,r+1):
            if ans[-r] != pro[-r]:
                print('NO')
                return
        print('YES')

main(input())
N=int(input())
li=map(int,input().split())
for k in li:
  if k %2=0:
    if k%3=0 or k%5=0:
      continue
    else:
      print('APPROVED')
      break
  else:
    continue
  print('DENIED')

### FIXED CODE ###

N=int(input())
li=map(int,input().split())
a=0
for k in li:
  if k %2==0:
    if k%3==0 or k%5==0:
      continue
    else:
      a=1
      break
if a==0:
  print('APPROVED')
else:
  print('DENIED')
X, Y = map(int, input().split())
ans = 'No'
for a in range(X + 1):
    b = X - a
    if 2 * a + 4 * b == Y:
        ans = 'Yes'
        print(ans)


### FIXED CODE ###

X = list(map(int, input().split()))
if X[0] == 0:
    print(1)
elif X[1] == 0:
    print(2)
elif X[2] == 0:
    print(3)
elif X[3] == 0:
    print(4)
else:
    print(5)
def isprime_euclid2(N):
    if N<1:
        print 'N>2'
    elif N==2:
        return True
        
    
    def euclid(m,n):
        while m%n>0:
            r=m%n
            m,n=n,r
        else:
            return n
        
    euclid_list=[]
    for k in range(1,int(round(math.sqrt(N)))+1):
        euclid_list.append(euclid(N,k))
    temp=set(euclid_list)
    if len(temp)==1:
        return True
    else:
        return False  
           
import math
while True:
    n = int(raw_input())
    total = 0
    for k in range(n):
        if isprime_euclid2(int(raw_input())):
            total +=1
    print total
        

### FIXED CODE ###

import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
                      
while True:
    try:
        n = int(raw_input())
        total = 0
        for k in range(n):
            if is_prime(int(raw_input())):
                total +=1
        print total
    except EOFError:
        break
N = int(input())
A = list(map(int, input().split()))
cnt = 0
while True:
    for i in range(N):
        if A[i]%2==1:
            break
        A[i] = A[i]//2
    else:
        cnt += 1
        continue
    break

### FIXED CODE ###

vec = str(input())
cnt = 0
for s in vec:
    if s=="1":
        cnt += 1

print(cnt)
s,n=map(int,input().split())
x=list(int(input()) for _ in range(n))

w0=1
b0=0
cnt=0

for i in range(1,s):
	if i==x[cnt]:
		w1=0
		b1=w0
		w0=w1
		b0=b1
		if cnt<len(x)-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007) 

### FIXED CODE ###

s,n=map(int,input().split())
if n>0:
	x=list(int(input()) for _ in range(n))

w0=int(1)
b0=int(0)
cnt=0

for i in range(1,s):
	if n>0 and i==x[cnt]:
		w1=int(0)
		b1=w0
		w0=w1
		b0=b1
		if cnt<n-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007)
n=int(input())
for i in range(n):
  if i%2!=0:
    odd+=1
 
print(odd/n)

### FIXED CODE ###

n=int(input())
odd=0
for i in range(1, n+1):
  if i%2!=0:
    odd+=1
 
print(odd/n)
N = int(input())
def sieve(n, s):
    num = [True]*n
    num[0] = num[1] = False
    for i in range(2,int(n**0.5)+1):
        if num[i]:
            for j in range(i**2, n, i):
                num[j] = False
    return [i for i in range(2,n) if num[i] and i > s]
print(sieve(int(N*1.2), N)[0])

### FIXED CODE ###

S, T = input().split()
print(T + S)
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for i in range(Q)]
rui_count = []
AC_k = S.find('AC')
for i in range(N):
    if AC_k+1 > i:
        if i == 0:
            rui_count.append(0)
        else:
            rui_count.append(rui_count[i-1])
        continue
    AC_k = S[i:N].find('AC')
    if AC_k == -1:
        rui_count += [rui_count[i-1]+1 for j in range(i,N)]
        break
    AC_k += i
    rui_count.append(rui_count[i-1]+1)
count = []
for i in lr:
    count.append(rui_count[i[1]-1]-rui_count[i[0]-1])
for i in count:
    print(i)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for i in range(Q)]
rui_count = []
AC_k = S.find('AC')
if AC_k == -1:
    for i in range(Q):
        print(0)
    exit()
for i in range(N):
    if AC_k+1 > i:
        if i == 0:
            rui_count.append(0)
        else:
            rui_count.append(rui_count[i-1])
        continue
    AC_k = S[i:N].find('AC')
    if AC_k == -1:
        rui_count += [rui_count[i-1]+1 for j in range(i,N)]
        break
    AC_k += i
    rui_count.append(rui_count[i-1]+1)
count = []
for i in lr:
    count.append(rui_count[i[1]-1]-rui_count[i[0]-1])
for i in count:
    print(i)
k,s = list(map(int,input().split()))
ans = 0
for i in range(k):
  for j in range(k):
    if 0 <= s-i-j <= k
      ans += 1
print(ans)

### FIXED CODE ###

k,s = list(map(int,input().split()))
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if 0 <= s-i-j <= k:
      ans += 1
print(ans)
Input = list(map(int,input().split()))

point =[]
for i in range(Input[0]):
    point.append(0)

for i in range(Input[2]):
    aa = int(input())
    point[aa-1] +=1
gouhi =[]
for i in range(Input[0]):
    bb = 0
    if Input[1]-Input[2]+point[i] > 0 :
        bb = "Yes"
    else:
        bb = "No"
    gouhi.append(bb)
print("\n".join(gouhi))

### FIXED CODE ###

Input = int(input())

aa = int(Input**0.5)

for i in range(1,aa+1):
  if Input%(aa+1-i) == 0:
    num1 = aa+1-i
    num2 = Input/(aa+1-i)
    break
print(int(num1 + num2 -2))
x = list(map(int,input().split()))

num = 0

for i in range(len(x)):
	num += 1
    if x[i] == 0:
      print(num)
      break


### FIXED CODE ###

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

num = 0

for i in range(5):
	num += 1
	if x[i] == 0:
		break
        
print(num)
row1 = list(map(str, input().split()))
row2 = list(map(str, input().split()))
row3 = list(map(str, input().split()))
matrix = [row1, row2, row2]
print(matrix)
print(matrix[0][0]+matrix[1][1]+matrix[2][2])

### FIXED CODE ###

row1 = input()
row2 = input()
row3 = input()
print(row1[0]+row2[1]+row3[2])
n = int(input())
print('Yes' if n[0] == n[2] else 'No')

### FIXED CODE ###

n=input()
print("Yes" if n[0]==n[2] else "No")
A = list(map(int,input().split()))
    print(A)
    for i in range(3):
        if sum(x==A[i] for x in A) == 1:
            continue
        elif sum(x==A[i] for x in A) ==2:
            print("Yes")
            return
    print("No")


### FIXED CODE ###

def solve():
    A = list(map(int,input().split()))
    for i in range(3):
        if sum(x==A[i] for x in A) == 1 or sum(x==A[i] for x in A) == 3:
            continue
        elif sum(x==A[i] for x in A) ==2:
            print("Yes")
            return
    print("No")

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

def factorical(n):
  ret = 1
  for i in range(1,n+1):
    ret *= i%(10**9+7)
    ret %= (10**9+7)
  return ret%(10**9+7)

a = factorical(A)
b = factorical(B)
if(abs(M-N)>= 2):
  print(0)
elif(A == B):
  print(a*b*2%(10**9+7))
else:
  print(a*b%(10**9+7))

### FIXED CODE ###

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

def factorical(n):
  ret = 1
  for i in range(1,n+1):
    ret *= i
    ret %= 10**9+7
  return ret

diff = abs(N - M)
max_ = int(1e9+7)

if(diff >= 2):
  print(0)
elif(diff == 1):
  n = N % max_
  m = M % max_
  print((factorical(n)*factorical(m)) % max_)
else:
  n = N % max_
  m = M % max_
  print((2*factorical(n)*factorical(m)) % max_)
a=input()
a_l=len(a)
b=input()
b_l=len(b)
c=input()
c_l=len(c)
def check(s1,s2):
    l1=len(s1)
    l2=len(s2)
    ret=[0]*(l1+l2-1)
    for i in range(l1+l2-1):
        flag=True
        if i-l2+1<0:
            for j in range(i+1):
                if s1[j]!="?" and s2[l2-i+j-1]!="?" and s1[j]!=s2[l2-i+j-1]:
                    flag=False
                    break
        elif i-l2+1>=0 and i<=l1-1:
            for j in range(l2):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        else:
            for j in range(l1+l2-i-1):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        ret[i]=flag
    return ret
ab=check(a,b)
ab_l=len(ab)
ac=check(a,c)
ac_l=len(ac)
bc=check(b,c)
bc_l=len(bc)
ans=a_l+b_l+c_l
for i in range(-2000,ab_l+2000):
    if i<0 or i>=ab_l or ab[i]:
        for j in range(-2000,ac_l+2000):
            if j<0 or j>=ac_l or ac[j]:
                if j-i+b_l+1<0 or j-i+b_l+1>=bc_l or bc[j-i+b_l+1]:
                    l=max(a_l-1,i,j)-min(0,i-b_l+1,j-c_l+1)+1
                    ans=min(ans,l)
print(ans)

### FIXED CODE ###

a=input()
a_l=len(a)
b=input()
b_l=len(b)
c=input()
c_l=len(c)
def check(s1,s2):
    l1=len(s1)
    l2=len(s2)
    ret=[0]*(l1+l2-1)
    for i in range(l1+l2-1):
        flag=True
        if i-l2+1<0 and i<=l1-1:
            for j in range(i+1):
                if s1[j]!="?" and s2[l2-i+j-1]!="?" and s1[j]!=s2[l2-i+j-1]:
                    flag=False
                    break
        elif i-l2+1<0 and i>l1-1:
            for j in range(l1):
                if s1[j]!="?" and s2[l2-i+j-1]!="?" and s1[j]!=s2[l2-i+j-1]:
                    flag=False
                    break
        elif i-l2+1>=0 and i<=l1-1:
            for j in range(l2):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        else:
            for j in range(l1+l2-i-1):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        ret[i]=flag
    return ret
ab=check(a,b)
ab_l=len(ab)
ac=check(a,c)
ac_l=len(ac)
bc=check(b,c)
bc_l=len(bc)
ans=a_l+b_l+c_l
for i in range(-2000,ab_l+2000):
    if i<0 or i>=ab_l or ab[i]:
        for j in range(-2000,ac_l+2000):
            if j<0 or j>=ac_l or ac[j]:
                if j-i+b_l-1<0 or j-i+b_l-1>=bc_l or bc[j-i+b_l-1]:
                    l=max(a_l-1,i,j)-min(0,i-b_l+1,j-c_l+1)+1
                    ans=min(ans,l)
print(ans)
noded = {}
edad = {}

class Node:
    def __init__(self, index):
        self.index = index
        self.color = -1
        self.eda_list = []

class Eda:
    def __init__(self, index, w, left, right):
        self.index = index
        self.w = w
        self.left = left
        self.right = right

def color_oppo_of(node):
    c = node.color
    for eda in [edad[edai] for edai in node.eda_list]:
        if eda.right == node.index:
            oppo = eda.left
        else:
            oppo = eda.right

        if noded[oppo].color == -1:
            if eda.w % 2 == 0:
                noded[oppo].color = node.color
            else:
                noded[oppo].color = (node.color + 1) % 2
            color_oppo_of(noded[oppo])

def solve():
    n = int(input())
    for i in range(n-1):
        U, V, W = map(int, input().split())
        u = U
        v = V
        w = W

        eda = Eda(i, w, u, v)
        edad[i] = eda

        if u not in noded.keys():
            noded[u] = Node(u)
        noded[u].eda_list.append(i)

        if v not in noded.keys():
            noded[v] = Node(v)
        noded[v].eda_list.append(i)

    noded[1].color = 0
    color_oppo_of(noded[1])

    for i in range(1, n+1):
        print(vars(noded[i]))


solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

noded = {}
edad = {}

class Node:
    def __init__(self, index):
        self.index = index
        self.color = -1
        self.eda_list = []

class Eda:
    def __init__(self, index, w, left, right):
        self.index = index
        self.w = w
        self.left = left
        self.right = right

def color_oppo_of(node):
    c = node.color
    for eda in [edad[edai] for edai in node.eda_list]:
        if eda.right == node.index:
            oppo = eda.left
        else:
            oppo = eda.right

        if noded[oppo].color == -1:
            if eda.w % 2 == 0:
                noded[oppo].color = node.color
            else:
                noded[oppo].color = (node.color + 1) % 2
            color_oppo_of(noded[oppo])

def solve():
    n = int(input())
    if n == 1:
        print("0")
    else:
        do(n)


def do(n):
    for i in range(n-1):
        U, V, W = map(int, input().split())
        u = U
        v = V
        w = W

        eda = Eda(i, w, u, v)
        edad[i] = eda

        if u not in noded.keys():
            noded[u] = Node(u)
        noded[u].eda_list.append(i)

        if v not in noded.keys():
            noded[v] = Node(v)
        noded[v].eda_list.append(i)

    noded[1].color = 0
    color_oppo_of(noded[1])

    for i in range(1, n+1):
        print(noded[i].color)
        #print(vars(noded[i]))



solve()
import sys
import numpy as np
from numba import njit

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE' and 0:
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc.export(main, (i8,i8[:],i8[:,:],))
    cc.compile()

from my_module import main

N = int(input())
S = np.array([ord(_) for _ in input()])
dp = np.zeros((N + 1, N + 1), dtype=int)
print(main(N, S, dp))


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)