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

H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]

grid2 = [[0]*W for i in range(H)]
grid3 = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            grid2[i][j] = 0
        else:
            if j > 0:
                grid2[i][j] = grid2[i][j-1]+1
            else:
                grid2[i][j] = 1
    for j in reversed(range(W)):
        if grid2[i][j] != 0 and j != W-1:
            grid2[i][j] = max(grid2[i][j], grid2[i][j+1])

for j in range(W):
    for i in range(H):
        if grid[i][j] == "#":
            grid3[i][j] = 0
        else:
            if i > 0:
                grid3[i][j] = grid3[i-1][j]+1
            else:
                grid3[i][j] = 1
    for i in reversed(range(H)):
        if grid3[i][j] != 0 and i != H-1:
            grid3[i][j] = max(grid3[i][j], grid3[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, grid2[i][j] + grid3[i][j] - 1)

print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]

grid2 = [[0]*W for i in range(H)]
grid3 = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            grid2[i][j] = 0
        else:
            if j > 0:
                grid2[i][j] = grid2[i][j-1]+1
            else:
                grid2[i][j] = 1
    for j in reversed(range(W)):
        if grid2[i][j] != 0 and j != W-1:
            grid2[i][j] = max(grid2[i][j], grid2[i][j+1])

for j in range(W):
    for i in range(H):
        if grid[i][j] == "#":
            grid3[i][j] = 0
        else:
            if i > 0:
                grid3[i][j] = grid3[i-1][j]+1
            else:
                grid3[i][j] = 1
    for i in reversed(range(H)):
        if grid3[i][j] != 0 and i != H-1:
            grid3[i][j] = max(grid3[i][j], grid3[i+1][j])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, grid2[i][j] + grid3[i][j] - 1)

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

import itertools,copy
T = input()
TC = list(T)
N = T.count('?')
B = list(itertools.product(['P','D'], repeat=N))
point = [0]*len(B)
strs = [0]*len(B)
for b,i in zip(B,range(len(B))):
    count = 0
    TC = list(T)
    for j in range(len(T)):
        if TC[j] == '?':
            TC[j] = b[count]
            count += 1
    strs[i] = ''.join(TC)
    point[i] = TC.count('PD') + TC.count('D')
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

N, X, Y = map(int, input().split())
dis = [0] * (N - 1)

for i in range(1, N):
	for j in range(i + 1, N + 1):
		cmb = min(j - i, min(abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j)))
		dis[cmb - 1] += 1

[print(i) for i in dis]

### FIXED CODE ###

N, X, Y = map(int, input().split())
dis = [0] * (N - 1)

for i in range(1, N):
	for j in range(i + 1, N + 1):
		cmb = min(j - i, abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j))
		dis[cmb - 1] += 1

[print(i) for i in dis]
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i,j,k)
print(ans)
exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0
d = {}
vals = []
for i in range(1, K+1):
    for j in range(1, K+1):
        nums = [i,j]
        nums.sort()
        key = str(i) + '-' + str(j)
        if key in d:
            vals.append(d[key])
        else:
            val = gcd(i,j)
            d[key] = val
            vals.append(val)
#  print(vals)
#  print(d)
for val in vals:
    for k in range(1, K+1):
        #  print(val, k)
        nums = [i,j]
        nums.sort()
        key = str(val) + '-' + str(k)
        if key in d:
            ans += d[key]
        else:
            val = gcd(val, k)
            ans += val
            d[key] = val
print(ans)
exit()
### BUGGY CODE ###

import sys

n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin:
    s, t = map(int, line.split())
    s -= 1
    t -= 1
    links[s].add(t)

not_omitted = [0.0] * n
exp_get = not_omitted.__getitem__
for j in range(n - 2, -1, -1):
    next_e = tuple(map(exp_get, links[j]))
    not_omitted[j] = sum(next_e) / len(next_e) + 1

ans = 1e6

for i in range(n - 1):
    expected = [0.0] * (i + 1) + not_omitted[i + 1:]
    e_get = expected.__getitem__

    next_e = tuple(map(e_get, links[i]))
    if len(next_e) == 1:
        expected[i] = sum(next_e) / len(next_e) + 1
    else:
        expected[i] = (sum(next_e) - max(next_e)) / (len(next_e) - 1) + 1

    for j in range(i - 1, -1, -1):
        next_e = tuple(map(e_get, links[j]))
        expected[j] = sum(next_e) / len(next_e) + 1

    ans = min(ans, expected[0])

print(ans)


### FIXED CODE ###

import sys

n, m = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = map(int, line.split())
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1

not_omitted = [0.0] * n
exp_get = not_omitted.__getitem__
for j in range(n - 2, -1, -1):
    not_omitted[j] = sum(map(exp_get, links[j])) / counts[j] + 1

ans = 1e6

for i in range(n - 1):
    expected = [0.0] * n
    expected[i + 1:] = not_omitted[i + 1:]
    e_get = expected.__getitem__

    if counts[i] == 1:
        expected[i] = sum(map(e_get, links[i])) / counts[i] + 1
    else:
        exp = list(map(e_get, links[i]))
        expected[i] = (sum(exp) - max(exp)) / (counts[i] - 1) + 1

    for j in range(i - 1, -1, -1):
        expected[j] = sum(map(e_get, links[j])) / counts[j] + 1

    ans = min(ans, expected[0])

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

import bisect
 
N = int(input())
A = [int(i) for i in input().split()]
 
B = [0]
X = [0]
ans = 0
for i in range(N):
    X.append(X[i]+A[i])
    insert_index = bisect.bisect_left(B,X[i+1])
    ans += bisect.bisect_right(B,X[i+1])-insert_index
    B.insert(insert_index,X[i+1])
 
print(ans)

### FIXED CODE ###

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

B = {}
B[0] = 1

s = 0
ans = 0

for a in A:
    s += a
    ans += B.get(s,0)
    B[s] = B.get(s,0)+1

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

n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
l = []
for i in range(n):
    a,b=map(int,input().split())
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    t += dic[i+1]
    if len(t) ==0 : M = 0
    else:
        M = max(t)
        s +=M
        t.remove(M)
print(s)

### FIXED CODE ###

n,m = map(int,input().split())
import heapq
from collections import defaultdict
dic = defaultdict(list)
l = []
heapq.heapify(l)
for i in range(n):
    a,b=map(int,input().split())
    b = -b
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    for i in dic[i+1]:
        heapq.heappush(l,i)
    if len(l) ==0 : M = 0
    else:
        # print(l)
        M = heapq.heappop(l)
        s += -M
print(s)
### BUGGY CODE ###

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

if K == 1:
    print(0)
    exit()

A_List.sort()

def cmb(n, r):
    return fact(n) // fact(n - r) // fact(r) if n > 0 and r > 0 else 1

def fact(n):
    num = 1
    for i in range(2,n+1):
        num *= i
    return num

ans = 0

for under in range(N):
    for top in range(under,N):
        if top - under + 1 < K:
            continue
        fx = A_List[top] - A_List[under]
        ans += fx * cmb(top-under-1 , K-2)

print(ans % (10**9 + 7))





### FIXED CODE ###

SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)


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

smax=0
smin=0
for i in range(N):
    smax+=A[i]*choose(i,K-1)
    smax%=MOD
    smin+=A[i]*choose(N-i-1,K-1)
    smin%=MOD

print((smax-smin)%MOD)
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
ind_ls = list()
for i in range(len(S) - 1):
    if S[i:i+2] == "AC":
       ind_ls.append(i)
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    l -= 1
    r -= 1
    print(len([i for i in ind_ls if l <= i < r]))

### FIXED CODE ###

import bisect
import sys
N, Q = [int(i) for i in input().split()]
S = input()
ind_ls = list()
for i in range(len(S) - 1):
    if S[i:i+2] == "AC":
        ind_ls.append(i)
        i += 1
        continue
    if S[i+1] != "A":
        i += 1
for i in range(Q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    print(bisect.bisect_left(ind_ls, r) - bisect.bisect_left(ind_ls, l))
### BUGGY CODE ###

H = int(input())
div2 = 0
ans = 0
while True:
    H = H // 2
    div2 += 1
    ans += 2**(div2)
    if H == 1:
        break
print(ans+1)

### FIXED CODE ###

H = int(input())
div2 = 0
ans = 0
if H == 1:
    print(1)
    exit()
while True:
    H = H // 2
    div2 += 1
    ans += 2**(div2)
    if H == 1:
        break
print(ans+1)
### BUGGY CODE ###

import sys
import copy

def main():
  input = sys.stdin.readline
  n, k = map(int, input().split())
  a = [int(x)-1 for x in input().split()]
  key = [copy.deepcopy(a) for _ in range(61)]
  for i in range(60):
    for j in range(n):
      key[i+1][j] = key[i][key[i][j]]
  
  i = 0
  now = 0
  while k > 0:
    if k%2:
      now = key[i][now]
    k //= 2
    i += 1
  
  print(now+1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

already = [0]*n
already[0] = 0
now = 0
count = 1
while True:
  count += 1
  now = a[now]-1
  if already[now]:
    k1 = already[now]
    k2 = count-already[now]
    break
  else:
    already[now] = count

if k > k2+k1:
  k -= k2+k1
  k %= k2
  ans = 1
  for i in range(k1):
    ans = a[ans-1]
  for i in range(k):
    ans = a[ans-1]
else:
  ans = 1
  for i in range(k):
    ans = a[ans-1]
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    for _ in range(K):
        tmp = [0] * N
        for i in range(N):
            for j in range(max(i - A[i], 0), min(i + A[i] + 1, N)):
                tmp[j] += 1
        for i in range(N):
            A[i] = tmp[i] 
        if A.count(N) == N:
            break

    print(*A)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

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

N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)


### FIXED CODE ###

import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)
### BUGGY CODE ###

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

dp = [float('inf')] * (h+1)

for _ in range(n):
    damage, mp = map(int, input().split())
    for i in range(h+1):
        if i <= damage:
            dp[i] = min(dp[i], mp)
        else:
            dp[i] = min(dp[i], dp[i-damage] + mp)
print(dp[h])


### FIXED CODE ###

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

dp = [float('inf')] * (h+1)

for _ in range(n):
    damage, mp = map(int, input().split())
    for i in range(h+1):
        if i <= damage:
            dp[i] = min(dp[i], mp)
        else:
            dp[i] = min(dp[i], dp[i-damage] + mp)
print(dp[h])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import itertools
N = int(input())
S = (input())

r_index_lis, g_index_lis, b_index_lis = [], [], []
for i, s in enumerate(S):
    if s == 'R':
        r_index_lis.append(i)
    elif s == 'G':
        g_index_lis.append(i)
    else:
        b_index_lis.append(i)
count = 0

p = (itertools.product(r_index_lis, g_index_lis, b_index_lis))
for _p in p:
    _p = sorted(_p)
    if(_p[0] - _p[1] != _p[1] - _p[2]):
        count += 1
print(count)
# for r in r_index_lis:
#     for g in g_index_lis:
#         diff = r - g
#         if(b_index_lis)
#         count += len(b_index_lis)

# for b in b_index_lis:
#     rgb = sorted([r, g, b])
#     if (rgb[0] - rgb[1] != rgb[1] - rgb[2]):
#         count += 1


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import itertools
import time
N = int(input())
S = (input())
# start = time.time()
r_index_lis, g_index_lis, b_index_lis = [], [], []
for i, s in enumerate(S):
    if s == 'R':
        r_index_lis.append(i)
    elif s == 'G':
        g_index_lis.append(i)
    else:
        b_index_lis.append(i)
count = len(r_index_lis)*len(g_index_lis)*len(b_index_lis)
# print(time.time() - start)
# exit()

# for r in r_index_lis:
#     for g in g_index_lis:
#         diff = r - g
#         # count += len(b_index_lis)
#         if(min(r, g) - diff >= 0):
#             if S[min(r, g) - diff] == 'B':
#                 count -= 1
#         if(max(r, g) + diff < N):
#             if S[max(r, g) + diff] == 'B':
#                 count -= 1
#         if (r+g) % 2 == 0:
#             if S[int((r+g)/2)] == 'B':
#                 count -= 1

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


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

h,w,k=list(map(int,input().split()))

s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[(i>>j)&1 for j in range(h)]

    curcnt=sum(split)
    nsplit=curcnt+1
    sumlst=[0]*(nsplit)
    
    cw=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[l]+=s[ch][cw]

            if sumlst[l]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break

            if split[ch]==1:
                l+=1
        else:
            cw+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

### FIXED CODE ###

h,w,k=list(map(int,input().split()))
s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]

    cw=0
    memo=0
    chk=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[memo][l]+=s[ch][cw]

            if sumlst[memo][l]>k:
                memo+=1
                chk+=1
                break

            if split[ch]:
                l+=1
        else:
            chk=0
            cw+=1
            continue

        if chk>1:
            break
    else:
        cnt=min(cnt,curcnt+memo)

print(cnt)
### BUGGY CODE ###

n=int(input())
ans = [0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            v = i*i+j*j+k*k+i*j+j*k+k*i
            if v >n:
                break
            ans[v]+=1
for i in range(n):
    print(ans[i+1])

### FIXED CODE ###

N=int(input())
import math
ans=[0]*(N+1)
n=int(math.sqrt(N))+1
for i in range(1,n+1):
    if i*i +2*i >N:
        break
    for j in range(1,n+1):
        if i*i+j*j+i*j>N:
            break
        for k in range(1,n+1):
            if i*i+j*j+k*k+i*j+j*k+i*k>N:
                break
            else:
                #print(i*i+j*j+k*k+i*j+j*k+i*k,i,j,k)
                ans[i*i+j*j+k*k+i*j+j*k+i*k]+=1
for i in range(len(ans)):
    if i!= 0:
        print(ans[i])
### BUGGY CODE ###

n=int(input())
li=[]
cnt=0
for i in range(n):
    s=input()
    if s not in li:
        li.append(s)
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
li=[]
cnt=0
for i in range(n):
    li.append(input())

li.sort()
last=li[0]

for i in range(1,n):
    if last==li[i]:
        li[i]=0
    
    else:
        last=li[i]

print(n-li.count(0))
### BUGGY CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(N, s):
    MOD = int(1e9 + 7)
    dp = [[0] * N for _ in range(N)]
    for j in range(N):
        dp[0][j] = 1
    for i in range(1, N):
        dpi = dp[i]
        csum = list(accum(dp[i - 1], lambda x, y: (x + y) % MOD))
        csum_ = csum[N - i]
        for j in range(N - i):  # N-(i+1)+1 = N-i
            if s[i - 1] == "<":
                dpi[j] = (csum_ - csum[j]) % MOD
            else: #s[i-1] == ">"
                dpi[j] = csum[j]
    return(dp[-1][0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f(N, s))



### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f2(N, s):
    MOD = int(1e9 + 7)
    dp = [1] * N
    for i in range(1, N):
        csum = list(dp)
        for j in range(1, N - i + 1):
            csum[j] += csum[j - 1]
        csum_ = csum[N - i]
        i_ = i - 1
        for j in range(N - i):  # N-(i+1)+1 = N-i
            dp[j] = csum[j] if s[i_] == ">" else (csum_ - csum[j] + MOD) % MOD
    return(dp[0])

N = int(input()) # 2 <= N <= 30000
s = input().rstrip() # len(s) = N - 1
print(f2(N, s))
### BUGGY CODE ###

import bisect


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return bisect.bisect_left(A, x)


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-bisect.bisect_right(A, x)


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10 ** 18 + 1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)