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

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

root = [[pow(10,9)]*n for _ in range(n)]

from collections import deque

root=[0]*n
r=[[]for i in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    r[a].append(b)
    r[b].append(a)

dist =[-1]*n
dist[0] = 0

q = deque([0])
prev=[-1] * n

while len(q)!=0:
    v = q.popleft()

    for j in r[v]:
        if dist[j]!=-1:
            continue
        else:
            dist[j] = dist[v] + 1
            prev[j] = v
            q.append(j)


for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)


### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
r=[[] for i in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    r[a].append(b)
    r[b].append(a)

# dist =[-1]*n
# dist[0] = 0

q = deque([0])
prev=[-1] * n

while q:
    v = q.popleft()

    for j in r[v]:
        if prev[j]==-1:
            prev[j] = v
            q.append(j)
            # dist[j] = dist[v] + 1
            

for i in range(n):
    if i==0:
        print('Yes')
    else:
        print(prev[i]+1)
### BUGGY CODE ###

N, A, B = map(int, input().split())
count_all = 0
count_blue = 0

is_blue = True

while True:
    if is_blue:
        if count_all + A > N:
            count_blue += A - ((count_all + A) - N)
            break

        count_all += A
        count_blue += A
        is_blue = not is_blue
    else:
        if count_all + B > N:
            break
        count_all += B
        is_blue = not is_blue

print(count_blue)

### FIXED CODE ###

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

AB = A+B
C = N // AB
n = N - AB * C

if n > A:
    print(C * A + A)
else:
    print(C * A + A - (A - n))
### BUGGY CODE ###

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

num_list = []
index_list = []
for i in range(len(A)):
    if(not A[i] in num_list):
        num_list.append(A[i])
        index_list.append([i])
    else:
        index_list[num_list.index(A[i])].append(i)

T = 0
remain = []
while True:
    N_remain = len(remain)
    B = remain + A
    i = 0
    remain = []
    while(i < len(B)):
        temp_list = index_list[num_list.index(B[i])]
        ind_list = []
        for j in range(len(temp_list)):
            if(temp_list[j] + N_remain > i):
                ind_list.append(temp_list[j] + N_remain)
        
        if(len(ind_list) >= 1):
            i = ind_list[0] + 1
        else:
            remain.append(B[i])
            i += 1
    T += 1
    if(remain == []):
        break

M = K % T
for _ in range(M):
    N_remain = len(remain)
    B = remain + A
    i = 0
    remain = []
    while(i < len(B)):
        temp_list = index_list[num_list.index(B[i])]
        ind_list = []
        for j in range(len(temp_list)):
            if(temp_list[j] + N_remain > i):
                ind_list.append(temp_list[j] + N_remain)
        
        if(len(ind_list) >= 1):
            i = ind_list[0] + 1
        else:
            remain.append(B[i])
            i += 1


ans = ''
for i in range(len(remain)):
    ans += str(remain[i]) + ' '
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))

if n == 1:
    if k % 2:
        print(*arr)
    else:
        print(*[])
    exit()

table = {}
original_table = {}
move = {}

for i, a in enumerate(arr):
    if a not in table:
        table[a] = i
        original_table[a] = i
    else:
        move[table[a]], move[i] = i + 1, original_table[a] + 1
        table[a] = i

res = {}
idx = 0

for i in range(1, k + 1):
    while idx in move and move[idx] > idx:
        idx = move[idx]

    res[i] = idx
    if idx == len(arr):
        k %= len(res)
        if not k:
            k = len(res)
        break

    if idx in move:
        idx = move[idx]
    else:
        idx += 1

idx = res[k]
response = []

while idx < len(arr):
    while idx in move and move[idx] > idx:
        idx = move[idx]
    if idx < len(arr):
        response.append(arr[idx])
    idx += 1

print(*response)
### BUGGY CODE ###

ans = []
for i in range(int(input())):
    a = int(input())
    if a in ans:
        ans.remove(a)
    else:
        ans.append(a)
print(len(ans))

### FIXED CODE ###

from collections import Counter

A = [int(input()) for _ in range(int(input()))]
C = Counter(A)

ans = 0
for c in C.values():
    if c%2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def abc092_c():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        tmp_a = a.copy()
        del tmp_a[i]
        money = abs(tmp_a[0]) + abs(tmp_a[-1])
        for j in range(n - 2):
            money += abs(tmp_a[j] - tmp_a[j + 1])
        print(money)


abc092_c()

### FIXED CODE ###

def abc092_c():
    n = int(input())
    a = [0] + list(map(int, input().split())) + [0]
    money = 0
    for i in range(n + 1):
        money += abs(a[i] - a[i + 1])
    for i in range(1, n+1):
        print(money - abs(a[i] - a[i - 1]) - abs(a[i] - a[i + 1]) + abs(a[i + 1] - a[i - 1]))


abc092_c()
### BUGGY CODE ###

n,m = map(int,input().split())
years = [[]for i in range(n)]
yearss = []

for i in range(m):
  p,y = map(int,input().split())
  years[p-1].append(y)
  yearss.append([p,y])


for i in range(n):
  years[i].sort()

for i in range(m):
  print("{0:06d}".format(yearss[i][0]),"{0:06d}".format(int(years[yearss[i][0]-1].index(yearss[i][1]))+1),sep="")


### FIXED CODE ###

import bisect

n,m = map(int,input().split())
years = [[]for i in range(n)]
yearss = []

for i in range(m):
  p,y = map(int,input().split())
  years[p-1].append(y)
  yearss.append([p,y])


for i in range(n):
  years[i].sort()

for i in range(m):
  print("{0:06d}".format(yearss[i][0]),"{0:06d}".format(bisect.bisect_right(years[yearss[i][0]-1],yearss[i][1])),sep="")
### BUGGY CODE ###

S = input()
lenS = len(S)
ans = 0
flag = True

while flag is True:
    i = S.find('ABC')
    if i == -1:
      falg = False
      break
      
    num_l_A = 0
    if i>=1:
      for ia in range(i-1,-1,-1):
        if S[ia] == 'A':
          num_l_A += 1
        else:break
    num_r_BC = 0
    if i+3 < lenS:
      for ibc in range(i+3,lenS):
        if S[ibc:ibc+1] == 'BC': num_r_BC += 1
        else:break
    ans += 1 + num_l_A + num_r_BC
    S = S[:i-num_l_A] + 'BC'*(1+num_r_BC) + 'A'*(1+num_l_A) + S[i+num_r_BC*2+3:]
print(ans)


### FIXED CODE ###

def sol(S):
  N = len(S)
  nums = [0 for _ in range(N+1)]
  i = N-1
  while i >= 0:
    if S[i-1:i+1] == 'BC':
      nums[i-1] = nums[i+1] + 1
      nums[i] = nums[i+1] + 1
      i -= 2
    else:
      nums[i] = nums[i+1]
      i -= 1
  ans = 0
  for i, s in enumerate(S):
    if s == 'A':
      ans += nums[i]
  return ans

S = input()
ans = 0
N = len(S)
si, i = 0, 0
while i < N:
  if S[i] == 'A':
    i += 1
  elif S[i:i+2] == 'BC':
    i += 2
  else:
    ans += sol(S[si:i+1])
    si = i + 1
    i += 1
ans += sol(S[si:])
print(ans)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
Names = [""] * n
for i in range(n):
  Names[i] = input()
march = ["M", "A", "R", "C", "H"] 
counter = 0
for three_man in combinations(Names, 3):
  if three_man[0][0] in march and three_man[1][0] in march and three_man[2][0] in march:
    if three_man[0][0] != three_man[1][0] and three_man[1][0] != three_man[2][0] and three_man[2][0] != three_man[0][0]:
      counter += 1
print(counter)

### FIXED CODE ###

from itertools import combinations
n = int(input())
dic = {"M":0, "A":0, "R":0, "C":0, "H":0}
march = ["M", "A", "R", "C", "H"]
for i in range(n):
  kashira = input()[0]
  if kashira in march:
    dic[kashira] += 1

ans = 0
for items in combinations(march, 3):
  ans += dic[items[0]] * dic[items[1]] * dic[items[2]]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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 main():
    n,k,l = map(int,input().split())
    Road = [list(map(int,input().split())) for i in range(k)]
    Train = [list(map(int,input().split())) for i in range(l)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots = [[0]*n for i in range(n)]

    for i in range(n):
        Roots[uf_r.find(i)][uf_t.find(i)] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots[uf_r.find(i)][uf_t.find(i)]

    print(*ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

def main():
    n,k,l = map(int,input().split())
    Road = [list(map(int,input().split())) for i in range(k)]
    Train = [list(map(int,input().split())) for i in range(l)]

    uf_r = UnionFind(n)
    uf_t = UnionFind(n)

    for i in range(k):
        uf_r.union(Road[i][0]-1,Road[i][1]-1)

    for i in range(l):
        uf_t.union(Train[i][0]-1,Train[i][1]-1)

    Roots_dict = defaultdict(int)
    Roots = []
    for i in range(n):
        Roots.append(str(uf_r.find(i))+' '+str(uf_t.find(i)))
        Roots_dict[Roots[i]] += 1

    ans = [0]*n

    for i in range(n):
        ans[i] = Roots_dict[Roots[i]]

    print(*ans)

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

n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  flag = True
  cnt = 0
  while flag:
    for i in range(2,25):
      for j in range(1,10):
        for l in range(1,i):
          for m in range(1,10):
            for o in range(l):
              for p in range(1,10):
                if j*(10**i)+m*(10**l)+p*(10**o) <= n:
                  cnt += 1
                else:
                  flag = False
                  break
print(cnt)

### FIXED CODE ###

n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] #dp[p][0][count]は、p桁目まではnより小さいことが確定している
#countは「0以外の桁」の登場回数、あくまで各桁に登場したt「以下」の数字かどうかを判定する。dp[p][1]は「〜と同じ」
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])
### BUGGY CODE ###

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

dist = []
for i in range(N-1):
    dist.append(a[i + 1] - a[i])
dist.append(a[0] + (K - a[-1]))

total = []
for i in range(len(dist)):
    total.append(sum(dist) - dist[i])

print(min(total))


### FIXED CODE ###

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

dist = []
for i in range(N-1):
    dist.append(a[i + 1] - a[i])
dist.append(a[0] + (K - a[-1]))

ans = sum(dist) - max(dist)

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

n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = [[0]*n for i in range(n)]
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            c[cur][next_i] = col
            c[next_i][cur] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[a][b]+1)


### FIXED CODE ###

n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)
### BUGGY CODE ###

import copy

def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y)

def cal(array):
  while(len(array) > 1):
    a = int(array.pop(0))
    b = int(array.pop(0))
    array.append(gcd(a, b))
  return array[0]

n = int(input())
a = input().split()

answer_list = []

for i in range(int(n)):
  copy_a = copy.copy(a)
  copy_pop_a = copy_a.pop(i)
  answer_list.append(cal(copy_a))

answer = max(answer_list)

print(answer)


### FIXED CODE ###

import copy
import heapq
import fractions

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

gcd_l = [0]
gcd_r = [0]

for i in range(N):
  gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
  gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))

gcd_r = gcd_r[::-1]
ans = []

for i in range(N):
  ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

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

H, W = map(int, input().split())
grid = [input() for i in range(H)]
count = [[[0, 0] for j in range(W)] for i in range(H)]
for i in range(H):
    row = '#' + grid[i] + '#'
    left = 0
    while True:
        right = row.find('#', left+1)
        if right == -1:
            break
        for j in range(left, right-1):
            count[i][j][0] = right - left - 1
        left = right
columns = list(zip(*grid))
for j in range(W):
    column = '#' + ''.join(columns[j]) + '#'
    left = 0
    while True:
        right = column.find('#', left+1)
        if right == -1:
            break
        for i in range(left, right-1):
            count[i][j][1] = right - left - 1
        left = right
print(max(sum(count[i][j]) for i in range(H) for j in range(W)) - 1)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
grid = np.array([list(input()) for i in range(H)]) == '.'
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
for i in range(1, H):
    U[i] = (U[i-1] + 1) * grid[i-1]
for i in reversed(range(H-1)):
    D[i] = (D[i+1] + 1) * grid[i+1]
for i in range(1, W):
    L[:, i] = (L[:, i-1] + 1) * grid[:, i-1]
for i in reversed(range(W-1)):
    R[:, i] = (R[:, i+1] + 1) * grid[:, i+1]
print(((U + D + L + R) * grid).max() + 1)
### BUGGY CODE ###

from collections import deque

# 初期化周り
N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)

# 目印
sign = [-1]*(N+1)
sign[0] = None
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

ans = "Yes"

for i in range(2, N+1):
    S = sign[i]
    while S > 0:
        S = sign[S]

    if not S == 0:
        ans = "No"

print(ans)
if ans == "Yes":
    for i in range(2, N+1):
        print(sign[i])


### FIXED CODE ###

from collections import deque

# 初期化周り
N, M = map(int, input().rstrip().split())
G = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().rstrip().split())
    G[A].append(B)
    G[B].append(A)

# 目印
sign = [-1]*(N+1)
sign[0] = None
sign[1] = 0

queue = deque([1])

while queue:
    node = queue.popleft()
    for next in G[node]:
        if sign[next] > -1:
            continue
        sign[next] = node
        queue.append(next)

if -1 in sign:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(sign[i])
### BUGGY CODE ###

W, H, N = map(int, input().split())
X = []
for k in range(N):
  x,y,a = map(int, input().split())
  if a == 1:
    for z in range(1,x+1):
      for j in range(1,H+1):
        if [z,j] not in X:
          X.append([z,j])
  elif a == 2:
    for z in range(x+1,W+1):
      for j in range(1,H+1):
        if [z,j] not in X:
          X.append([z,j])
  elif a == 3:
    for z in range(1,y+1):
      for i in range(1,W+1):
        if [i,z] not in X:
          X.append([i,z])
  else:
    for z in range(y+1,H+1):
      for i in range(1,W+1):
        if [i,z] not in X:
          X.append([i,z])
print(W*H - len(X))

### FIXED CODE ###

W, H, N = map(int, input().split())
X = [0, 0, W, 0, H]
for k in range(N):
  x,y,a = map(int, input().split())
  if a == 1:
    X[a] = max(x,X[a])
  elif a == 2:
    X[a] = min(x,X[a])
  elif a == 3:
    X[a] = max(y,X[a])
  else:
    X[a] = min(y,X[a])
tate = X[4] - X[3]
yoko = X[2] - X[1]
ans = tate*yoko
if tate<0 or yoko<0:
  print(0)
else:
  print(ans)
### BUGGY CODE ###

from itertools import product


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    s = ["#" + _s + "#" for _s in s]
    s = ["#" * (w + 2)] + s + ["#" * (w + 2)]
    ans = 0
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for _h, _w in product(range(1, h + 1), range(1, w + 1)):
        if s[_h][_w] == "#":
            continue
        c = [[h * w] * (w + 2) for _ in range(h + 2)]
        c[_h][_w] = 0
        q = list()
        for x, y in d:
            if s[_h + x][_w + y] == ".":
                q.append((_h + x, _w + y, _h, _w))
        while q:
            cx, cy, px, py = q.pop()
            if c[px][py] + 1 >= c[cx][cy]:
                continue
            c[cx][cy] = c[px][py] + 1
            for x, y in d:
                nx = cx + x
                ny = cy + y
                if s[nx][ny] == ".":
                    q.append((nx, ny, cx, cy))
        for i, j in product(range(1, h + 1), range(1, w + 1)):
            ans = max(ans, c[i][j] * (s[i][j] == "."))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

from itertools import product


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    s = ["#" + _s + "#" for _s in s]
    s = ["#" * (w + 2)] + s + ["#" * (w + 2)]
    ans = 0
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for _h, _w in product(range(1, h + 1), range(1, w + 1)):
        if s[_h][_w] == "#":
            continue
        c = [[h * w] * (w + 2) for _ in range(h + 2)]
        c[_h][_w] = 0
        q = list()
        for x, y in d:
            if s[_h + x][_w + y] == ".":
                q.append((_h + x, _w + y, _h, _w))
        if len(q) > 2:
            continue
        while q:
            cx, cy, px, py = q.pop()
            if c[px][py] + 1 >= c[cx][cy]:
                continue
            c[cx][cy] = c[px][py] + 1
            for x, y in d:
                nx = cx + x
                ny = cy + y
                if s[nx][ny] == ".":
                    q.append((nx, ny, cx, cy))
        for i, j in product(range(1, h + 1), range(1, w + 1)):
            ans = max(ans, c[i][j] * (s[i][j] == "."))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

for zk in range(n):
    for i in reversed(range(n)):
        if i == n - 1:
            dp[zk][i] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            for v in range(zk):
                cnt = mod(cnt + dfs(v, i + 1))
        else:
            for v in range(zj):
                cnt = mod(cnt + dfs(zk + v, i + 1))
        dp[zk][i] = cnt

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum([dp[v][0] for v in range(n)]) % M)


### FIXED CODE ###

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v


dp = [[1] * n + [0] for _ in range(2)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        cnt = 0

        if s[i]:
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = mod(cnt)

print(sum(dp[1]) % M)
### BUGGY CODE ###

from math import ceil
import numpy as np
def chk(A, C, x, K):
    cnt = 0
    for i in range(len(A)):
        cnt += max(ceil(A[i]-x/C[i]), 0)
        if cnt > K:
            return False
    return True
def main():
    N, K = map(int,input().split())
    A = np.array(list(map(int,input().split())))
    C = np.array(list(map(int,input().split())))
    A.sort()
    A = A[::-1]
    C.sort()
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(A, C, m, K):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import ceil
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort(reverse=True)
    C.sort()
    def chk(x):
        cnt = 0
        for i in range(N):
            cnt += max(ceil(A[i]-x/C[i]), 0)
            if cnt > K:
                return False
        return True
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(m):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()