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

from bisect import bisect_left
import sys
input = sys.stdin.readline
M = 200001
n = int(input())
l = [None] * n
ans = 10 ** 18
for i in range(n):
    x, y, u = input().split()
    u = ('R', 'D', 'L', 'U').index(u)
    l[i] = (int(x), int(y), u)
for _ in range(3):
    l.sort()
    xy = [[] for _ in range(M * 2 - 1)]
    yx = [[] for _ in range(M * 2 - 1)]
    xs = [[] for _ in range(M)]
    k = []
    for i, t in enumerate(l):
        x, y, u = t
        u %= 4
        if u == 3:
            xy[x + y].append(x)
        elif u == 1:
            yx[x - y + M - 1].append(x)
        elif u == 2:
            xs[y].append(x)
        elif u == 0:
            k.append((x, y))
        l[i] = (y, -x + M - 1, u + 1)
    for x, y in k:
        idx = bisect_left(xs[y], x)
        if idx < len(xs[y]):
            ans = min(ans, (xs[y][idx] - x) * 5)
        idx = bisect_left(xy[x + y], x)
        if idx < len(xy[x + y]):
            ans = min(ans, (xy[x + y][idx] - x) * 10)
        idx = bisect_left(yx[x - y + M - 1], x)
        if idx < len(yx[x - y + M - 1]):
            ans = min(ans, (yx[x - y + M - 1][idx] - x) * 10)
if ans == 10 ** 18:
    print('SAFE')
else:
    print(ans)


### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline
M = 200001
n = int(input())
l = [None] * n
ans = 10 ** 18
for i in range(n):
    x, y, u = input().split()
    u = ('R', 'D', 'L', 'U').index(u)
    l[i] = (int(x), int(y), u)
for _ in range(3):
    l.sort(key=lambda x: x[0])
    xy = [[] for _ in range(M * 2 - 1)]
    yx = [[] for _ in range(M * 2 - 1)]
    xs = [[] for _ in range(M)]
    k = []
    for i, t in enumerate(l):
        x, y, u = t
        u %= 4
        if u == 3:
            xy[x + y].append(x)
        elif u == 1:
            yx[x - y + M - 1].append(x)
        elif u == 2:
            xs[y].append(x)
        elif u == 0:
            k.append((x, y))
        l[i] = (y, -x + M - 1, u + 1)
    for x, y in k:
        idx = bisect_left(xs[y], x)
        if idx < len(xs[y]):
            ans = min(ans, (xs[y][idx] - x) * 5)
        idx = bisect_left(xy[x + y], x)
        if idx < len(xy[x + y]):
            ans = min(ans, (xy[x + y][idx] - x) * 10)
        idx = bisect_left(yx[x - y + M - 1], x)
        if idx < len(yx[x - y + M - 1]):
            ans = min(ans, (yx[x - y + M - 1][idx] - x) * 10)
if ans == 10 ** 18:
    print('SAFE')
else:
    print(ans)
### BUGGY CODE ###

import collections
from operator import mul
from functools import reduce
mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

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

for k in range(N):
  A[k] -= (10**6)
  C = collections.Counter(A)
  A[k] += (10**6)
  values, counts = zip(*C.most_common())
  ans = 0
  for i in range(len(counts)):
    if counts[i] == 1:
      pass
    else:
      ans += cmb(counts[i],2,mod)
  print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = Counter(A)
ans = 0

for i in B.values():
  ans += i*(i-1)//2
for a in A:
  k = B[a]
  print(ans - (k*(k-1)//2)+((k-1)*(k-2)//2))
### BUGGY CODE ###

a,b,n= map(int,input().split())
t=[]
for k in range (n+1):
  s= int(a*k/b)-a*int(k/b)
  t.append(s)
  
print(max(t))
  

### FIXED CODE ###

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

if n < b-1:
    x = n
else:
    x = b-1

m = math.floor(a*x/b) - a*math.floor(x/b)
print(m)
### BUGGY CODE ###

N,Q = list(map(int,input().split()))
S = input()
ac_index = [i for i in range(N-1) if S[i:i+2]=="AC"]

for _ in range(Q):
    l,r = list(map(int,input().split()))
    l = l - 1
    r = r - 1
    print(len([i for i in ac_index if i >= l and i < r]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,q = list(map(int,input().split()))
s = input()
s2 = s[1::]
d = [list(map(int,input().split())) for i in range(q)]

#AC開始位置を記録する
ac_idx = []

aci_append = ac_idx.append
for i,v in enumerate(zip(s,s2)):
    if v == ("A","C"):
        aci_append(i)

#2分探索, nibuntansaku,二分探索
from bisect import bisect_left

for l,r in d:
    print(bisect_left(ac_idx,r-1) - bisect_left(ac_idx,l-1))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = 1
for i in range(N):
    S *= A[i]
if S > 100 ** 9:
    print("-1")
else:
    print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = 1
if 0 in A:
    print("0")
    exit()
    
for i in range(N):
    S *= A[i]
    if S > 1000000000000000000:
        print("-1")
        exit()

print(S)
### BUGGY CODE ###

N = int(input())
S = list(input())

i_range = [int(x) for x in range(1, N-1)]
j_range = [int(x) for x in range(2, N)]
k_range = [int(x) for x in range(3, N+1)]

val = 0

for k in k_range:
    for j in j_range:
        if(j >= k):
            break
        for i in i_range:
            if(i >= j):
                break
            if((S[i-1] != S[j-1]) and (S[j-1] != S[k-1]) and (S[i-1] != S[k-1]) and (j-i != k-j)):
                val = val + 1


print(val)

### FIXED CODE ###

N = int(input())
S = list(input())


"""
脳死で全探索で探すとO(n^3）で時間がかかる。
→1つめの条件で予め絞った後に、そこからさらに絞り込むやり方をやる。（補集合を引くパターン）
j-i=k-jを満たすもの（すなわちk=2j-i）を求めて、あとで引き算すればOK.
≠は＝で考えて引き算のほうがよい。
"""

r_count = S.count('R')
g_count = S.count('G')
b_count = S.count('B')


val = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2*j-i
        if(k < N):
            if((S[i] != S[j]) and (S[j] != S[k]) and (S[i] != S[k])):
                val += 1

print((r_count * g_count * b_count) - val)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# import numpy as np

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

pare_list = []
val_list = []

for i in range(N):
    tmp = 0
    for j in range(i,N):
        tmp += An[j]
        # pare_list.append((i,j))
        # for m in range(i,j+1):
        #     tmp += An[m]
        if tmp % M == 0:
            val_list.append(tmp)

print(len(val_list))
#
# count = 0
# for val in val_list:
#     if val % M == 0:
#         count += 1


# print(count)
# print(pare_list)
# print(val_list)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

Cn = [0]*(N+1)

for i,Ai in enumerate(An):
    if i == 0:
        Cn[i+1] = Ai
    else:
        Cn[i+1] = Cn[i] + Ai

# def func(n):
#     if n <= 1:
#         return 1
#     else:
#         tmp = 1
#         for i in range(2,n+1):
#             tmp = tmp * i
#         return tmp

mod = {}
for i in range(N+1):
    if Cn[i]%M in mod:
        mod[Cn[i]%M] += 1
    else:
        mod[Cn[i]%M] = 1

ans = 0
for val in mod.values():
    if val <= 1:
        continue
    elif val == 2:
        ans += 1
    else:
        # tmp = func(val) / (func(2) * func(val - 2))
        tmp = combinations_count(val,2)
        ans += int(tmp)

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

n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
counter = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        s = j + 1
        while s < n and l[i] + l[j] > l[s]:
            s += 1
        counter += s-j-1
print(counter)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
counter = 0
for i in range(n):
    s = i + 2
    for j in range(i+1,n):        
        while (s < n and l[i] + l[j] > l[s]):
            s += 1
        counter += s-j-1
print(counter)
### BUGGY CODE ###

from functools import lru_cache
import collections
import copy

@lru_cache(maxsize=2*10**5)
def f(p):
    c=copy.deepcopy(b)
    c[x]-=1
    d=collections.Counter(c.values())
    dk=d.keys()
    re=0
    for o in dk:
        if o>1:
            re+=o*(o-1)*d[o]
    return re//2


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

for x in a:
    print(f(x))

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
e=0
for x in b.values():
    e+=x*(x-1)
for x in a:
    t=b[x]
    p=e-t*(t-1)+(t-1)*(t-2)
    print(p//2)
### BUGGY CODE ###

s=input()

n=len(s)

x=[1]*n
z=[]
st=0
en=0
bk=0

r=[]
l=[]

for i in range(n):
	if s[i]=='R':
		r.append(i)       
	else:
		l.append(i)

for i in range(10**100):
	y=[0]*n
	for j in r:
		y[j+1]+=x[j]       
	for j in l:
		y[j-1]+=x[j]
	x=y
	z.append(y)
	if i>0:
		for k in range(i-1,0,-1):
			if z[i]==z[k]:
				st=k
				en=i
				bk=1
				break
	if bk==1:
		break

cy=en-st
po=(10*100-(st+1))%cy
res=z[st+po]

print(*res)

### FIXED CODE ###

s=input()

n=len(s)
x=[1]*n
x[n-1]=0
y=[1]*n
y[0]=0
z=[0]*n

for i in range(0,n-1):
	if s[i]=='R' and s[i+1]=='R':
		x[i+1]+=x[i]
		x[i]=0
	if s[i]=='L':
		x[i]=0   

for i in range(n-1,0,-1):
	if s[i]=='L' and s[i-1]=='L':
		y[i-1]+=y[i]
		y[i]=0
	if s[i]=='R':
		y[i]=0

i=1
while i<=n-2:
	if x[i]>1:
		if x[i]%2==0:
			x[i]=x[i]//2
			x[i+1]=x[i]
		else:
			x[i]=x[i]//2+1
			x[i+1]=x[i]-1
		i+=1
	i+=1
        
i=n-2
while i>=1:
	if y[i]>1:
		if y[i]%2==0:
			y[i]=y[i]//2
			y[i-1]=y[i]
		else:
			y[i]=y[i]//2+1
			y[i-1]=y[i]-1
		i-=1
	i-=1

for i in range(n):
	z[i]=x[i]+y[i]

print(*z)
### BUGGY CODE ###

n=int(input())
a=[0]*n
for i in range(n):
  a[i]=int(input())
for i in range(n):
  wk=a.copy()
  wk.pop(i)
  print(max(wk))

### FIXED CODE ###

n=int(input())
a={}
maxkey=0
maxindex=0
bkmaxkey=0
for i in range(n):
  key=int(input())
  if key in a:
    a[key]+=1
  else:
    a[key]=1
  if maxkey<key:
    if bkmaxkey!=0:
      bkmaxkey=maxkey
    maxkey=key
    maxindex=i
if a[maxkey]>1:
  for i in range(n):
    print(maxkey)
else:
  for i in range(n):
    if i==maxindex:
      a.pop(maxkey)
      print(max(a))
    else:
      print(maxkey)
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (w + 1)
for wi, vi in wv:
    for sum_w in range(w, wi - 1, -1):
        v = dp[sum_w - wi] + vi
        if dp[sum_w] < v:
            dp[sum_w] = v

print(dp[w])



### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])


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

from sys import stdin
import numpy as np

N, M = [int(x) for x in stdin.readline().rstrip().split()]

# カード。すべて通過できるなら１
cards = np.ones(N)

for i in range(M):
    L, R = [int(x) for x in stdin.readline().rstrip().split()]

    # [【Python】スライス操作についてまとめ \- Qiita](https://qiita.com/tanuk1647/items/276d2be36f5abb8ea52e)
    cards[:L-1] = 0
    cards[R:] = 0

print(int(np.sum(cards)))

### FIXED CODE ###

from sys import stdin
import numpy as np

N, M = [int(x) for x in stdin.readline().rstrip().split()]

#[競プロ等におけるpython3の標準入力 \- Qiita](https://qiita.com/zenrshon/items/c4f3849552348b3dbe67)
L = []
R = []
for i in range(M):
    l,r=[int(i) for i in input().split()]
    L.append(l)
    R.append(r)

tmp = int(min(R) - max(L))
          
if tmp < 0:
    print(0)
else:
    print(tmp + 1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
#グループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 #xのグループとyのグループを結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
#親を全部表示
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_groupmembers(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N, M ,K = map(int, input().split())
uf = UnionFind(N)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
to=[[] for i in range(N)]
for i in range(K):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    leng = uf.size(n)
    for j in to[n]:
        if(uf.same(n,j)):leng-=1
    print(str(leng-1-friend_count[n]), end=" ")

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(n)]
    
    def find(self,x):
        if(self.d[x]<0):return x
        self.d[x]=self.find(self.d[x])
        return self.d[x]
 
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        return True
 
    def same(self,x,y):return self.find(x)==self.find(y)
    def size(self,x):return -1*self.d[self.find(x)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")
### BUGGY CODE ###

n=int(input())
from math import gcd
a,b=map(int,input().split())
temp=a+b
for i in range(1,n):
    c,d=map(int,input().split())
    i=c+d
    j=i
    c1=c
    d1=d
    while i<temp or c<a or d<b:

        i+=j
        c+=c1
        d+=d1
        
        
        
    temp=i
    a=c
    b=d
    
print(temp)

### FIXED CODE ###

n=int(input())
from math import gcd
a,b=map(int,input().split())
temp=a+b
for i in range(1,n):
    c,d=map(int,input().split())
    j=c+d
    
    x=max(a-c,0)//c
    if max(a-c,0)%c!=0:
        x+=1
    y=max(b-d,0)//d
    if max(b-d,0)%d!=0:
        y+=1
    z=max(temp-j,0)//j
    if max(temp-j,0)%j!=0:
        z+=1
    l=[x,y,z]
    temp=max(l)*j+j
    a=max(l)*c+c
    b=max(l)*d+d
        
print(temp)
### BUGGY CODE ###

import sys 
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
@jit(cache=True)
def solve(n):
  a = np.zeros(N+1,np.int64)
  for i in range(1,N+1):
    a[i::i] += 1
  ans = 0
  for i in range(N+1):
    ans += i * a[i]
  return ans

N = int(readline())
print(solve(N))

### FIXED CODE ###

import sys 
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
@jit(cache=True)
def solve(n):
  a = np.zeros(N+1,np.int64)
  for i in range(1,N+1):
      for j in range(i,N+1,i):
        a[j] += j
  ans = a.sum()
  return ans
 
N = int(readline())
print(solve(N))
### BUGGY CODE ###

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

x_max = int(P**(1/N))
ans = 1
for i in range(x_max+1):
  x = x_max+1 - i
  if(P%x**N == 0):
    ans = x
    break
print(ans)

### FIXED CODE ###

N,P = map(int,input().split())
X = P
Factoring = []

if(N == 1):
 ans = X
 print(ans)
else:
 #素因数分解
 p = 2
 ans = 1

 while(p*p <= P):
  count = 0
  while(X%p == 0):
    X = X//p
    count += 1
  if(count != 0):
   Factoring.append([p,count])
   ans = ans*(p**(count//N))
  p += 1
  
 if(len(Factoring) == 0):
  ans = 1
 print(ans)
### BUGGY CODE ###

n = int(input())
a = [0]*(n)
for i in range(n):
    a[i] = int(input())
for i in range(n):
    max = 0
    for j in range(n):
        if j == i:
            continue
        if a[j] > max:
            max = a[j]
    print(max)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
num = a.index(max(a))
a_max = max(a)
a_second = sorted(a)[-2]
for i in range(n):
    if i == num:
        print(a_second)
    else:
        print(a_max)
### BUGGY CODE ###


import copy

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

chinpo = max(A)
B = copy.copy(A)
B.remove(max(A))
chinchin = max(B)

for i in range(N):
    if i == A.index(max(A)):
        print(chinchin)
    else:
        print(chinpo)


### FIXED CODE ###

import copy

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

chinpo = max(A)
B = copy.copy(A)
B.remove(max(A))
chinchin = max(B)

for i in range(A.index(max(A))):
    print(chinpo)
print(chinchin)
for i in range(A.index(max(A))+1,N):
    print(chinpo)
### BUGGY CODE ###

from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0

nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:

    d = deque()
    d.append(nosa)

    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)

    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break


for i in range(1,n+1):
    print(len(set(grouplist[gru[i]])-set(blo[i]))-len(fri[i])-1)

### FIXED CODE ###

from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


nans = [0]*n
for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    nans[i-1] = ans

print(*nans, sep='\n')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
for m in range(n-1):
    d = sum(a[m+1:n])
    b = b + a[m]*d
c = b % (10**9+7)
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
d = sum(a)
for m in range(n-1):
    d = d -a[m]
    b = b + a[m]*d
    if b >= 10**9+7:
        b = b % (10**9+7)
print(b)
### BUGGY CODE ###

import queue
import copy
import math
from collections import deque
import bisect

# 2つの入力を空白で分割し、数値化
n, k = map(int, input().split())

# 空白区切りの数値をリスト化
pn = list(map(int, input().split()))

expects = []

max_e = 0
start = -1

for i in range(0, n - k + 1):
    tmp = sum(pn[i:i+k])
    if tmp > max_e:
        start = i
        max_e = tmp

candidate = pn[start:start + k]

for p in candidate:
    e = (((1 + p) * p) // 2) / p
    expects.append(e)

print(sum(expects))

### FIXED CODE ###

import queue
import copy
import math
from collections import deque
import bisect

# 2つの入力を空白で分割し、数値化
n, k = map(int, input().split())

# 空白区切りの数値をリスト化
pn = list(map(int, input().split()))

expects = []
max_e = 0
prev_e = 0

for p, i in zip(pn, range(0, n)):
    e = (((1 + p) * p) // 2) / p
    expects.append(e)
    if i + 1 == k:
        max_e = sum(expects)
        prev_e = max_e
    elif i + 1 > k:
        current_e = prev_e + expects[-1] - expects[i-k]
        max_e = max(max_e, current_e)
        prev_e = current_e
    else:
        continue

print(max_e)
### BUGGY CODE ###

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

ab_list = []
ans =0
for i in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    ab_list.append([a, b])

for i in range(M):
    uf.union(ab_list[i][0], ab_list[i][1])

ans = 0
ans_list = list(uf.all_group_members().values())
for i in range(len(ans_list)):
    ans = max(ans,len(ans_list[i]))

print(ans)


### FIXED CODE ###

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

ab_list = []
ans =0
for i in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    uf.union(a, b)

ans = 0
ans_list = uf.roots()
for i in range(len(ans_list)):
    ans = max(ans, uf.size(ans_list[i]))

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

N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        dp[i+1][j+1] = (S[i] == T[j]) * sum[i][j] % MOD
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])

### FIXED CODE ###

N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = sum[i][j]
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])