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

from numba import njit


def comb(li):
    return len(li) * (len(li) - 1) // 2


@njit
def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)


### FIXED CODE ###

def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)
### BUGGY CODE ###

from collections import Counter
N = input()
count=0
S=[0]
mod_count=[]
ans=0
for K in range(1,len(N)+1):
  S.append(int(N[-K])*(10**(K-1))+S[K-1])
for X in S:
  mod_val=(X % 2019)
  mod_count.append(str(mod_val))

c = Counter(mod_count)

for Y in c.values():
  ans+= Y*(Y-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

from decimal import Decimal, getcontext

getcontext().prec = 100000

a, b, c = map(Decimal, input().split())
print('Yes' if a.sqrt() + b.sqrt() < c.sqrt() else 'No')

### FIXED CODE ###

from decimal import *
a, b, c = map(int, input().split())
a, b, c = Decimal(a).sqrt(), Decimal(b).sqrt(), Decimal(c).sqrt()

if a + b < c:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###


def q3():
    import math
    k = int(input())
    sum_n = 0
    gcd_2_dict = {}
    gcd_3_dict = {}

    def gcd(n1, n2):
        if n1 < n2:
            sorted_nums = tuple([n1, n2])
        else:
            sorted_nums = tuple([n2, n1])
        if sorted_nums in gcd_2_dict:
            return gcd_2_dict[sorted_nums]
        gcd_num = math.gcd(n1, n2)
        gcd_2_dict[sorted_nums] = gcd_num
        return gcd_num

    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                sorted_nums = tuple(sorted([a, b, c]))
                if sorted_nums in gcd_3_dict:
                    gcd_num = gcd_3_dict[sorted_nums]
                else:
                    gcd_num = gcd(gcd(sorted_nums[0], sorted_nums[1]), sorted_nums[2])
                    gcd_3_dict[sorted_nums] = gcd_num
                sum_n += gcd_num

    print(sum_n)

q3()

### FIXED CODE ###


from math import gcd

K = int(input())

a = 0
for ai in range(1, K + 1):
  for bi in range(1, K + 1):
    gcd_ab = gcd(ai, bi)
    for ci in range(1, K + 1):
      a += gcd(gcd_ab, ci)

print(a)
### BUGGY CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        c = 1
        while True:
            if s[i + c] == "L":
                if c % 2 != 0:
                    li[i + c - 1] += 1
                else:
                    li[i + c] += 1
                break
            c += 1
    else:
        c = 1
        while True:
            if s[i - c] == "R":
                if c % 2 != 0:
                    li[i - c + 1] += 1
                else:
                    li[i - c] += 1
                break
            c += 1

print(*li)

### FIXED CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        t = s[i:].index("L")
        if t % 2 != 0:
            li[i + t - 1] += 1
        else:
            li[i + t] += 1
    else:
        t = s[:i].rfind("R")
        if (i - t) % 2 != 0:
            li[t + 1] += 1
        else:
            li[t] += 1

print(*li)
### BUGGY CODE ###

def xor(a, b):
    ab = "{0:020b}".format(a)
    bb = "{0:020b}".format(b)
    r = ""
    for i in range(20):
        if ab[i] == bb[i]:
            r += "0"
        else:
            r += "1"
    return int(r, 2)


def D(n, a):
    count = 0
    
    for l in range(n):
        x = a[l]
        sum = a[l]
        if x == sum:
            count += 1
        
        for r in range(l + 1, n):
            x = xor(x, a[r])
            sum += a[r]
            if x == sum:
                count += 1
    return count

n = int(input())
a = list(map(int, input().split()))
print(D(n, a))

### FIXED CODE ###

def D(n, a):
    n = len(a)
    count = 0
    
    l = 0
    r = 0
    
    sum = 0
    for l in range(n):
        while r < n:
            if sum & a[r] == 0:
                sum += a[r]
                x = sum
                r += 1
            else:
                break
        count += r - l
        sum -= a[l]
        
    return count

n = int(input())
a = list(map(int, input().split()))
print(D(n, a))
### BUGGY CODE ###

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%DIV)


### FIXED CODE ###

from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

fact = [1] * (N*M+1)
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i % MOD

def comb(n, r):
    r = n-r if n-r < r else r
    return fact[n] * pow(fact[r], MOD-2, MOD) * pow(fact[n-r], MOD-2, MOD) % MOD

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt % MOD
ans = ans * p % MOD

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

import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
first_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)
    if a == 1:
        first_list.append(b)

for first in first_list:
    if first in way_list:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
dp = [0]+ [100000000000]*(n-1)

for i in range(1,n):
    ans = dp[i]
    for j in range(1,m+1):
        if i-j >= 0:
            ans = min(ans,dp[i-j]+abs(l[i]-l[i-j]))
    dp[i] = ans
print(dp[n-1])

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    l = list(map(int,input().split()))
    dp = [0]+ [100000000000]*(n-1)

    for i in range(1,n):
        
        for j in range(1,m+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
        
    print(dp[n-1])

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

n=int(input())
c=list(map(int,input().split()))
count1=0
for i in range(n):
  count=0
  for j in range(i):
    if c[i]<c[j]:
      count+=1

  if count==i:
    count1+=1
print(count1)


### FIXED CODE ###

n=int(input())
c=list(map(int,input().split()))
minimum=100000000
count=0
for i in range(len(c)):
    if c[i]<minimum:
        minimum=c[i]
    if c[i]<=minimum:
        count+=1
print(count)
### BUGGY CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
cnt = [[-3]*w for _ in range(h)]

for i in range(h):
    c = 1
    for j in range(w):
        if s[i][j] == "#": c = 1
        else:
            cnt[i][j] += c
            c += 1
    c = 1
    for j in range(w)[::-1]:
        if s[i][j] == "#": c = 1
        else:
            cnt[i][j] += c
            c += 1

for j in range(w):
    c = 1
    for i in range(h):
        if s[i][j] == "#": c = 1
        else:
            cnt[i][j] += c
            c += 1
    c = 1
    for i in range(h)[::-1]:
        if s[i][j] == "#": c = 1
        else:
            cnt[i][j] += c
            c += 1

print(max(max(i) for i in cnt))

### FIXED CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
u1 = [[0 for _ in range(w)] for _ in range(h)]
u2 = [[0 for _ in range(w)] for _ in range(h)]
d1 = {}
d2 = {}

idx = 1
cnt = 0
for i in range(h):
    flag = False
    for j in range(w):
        if s[i][j] == ".":
            flag = True
            u1[i][j] = idx
            cnt += 1
        elif flag:
            d1[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d1[idx] = cnt
        cnt = 0
        idx += 1

idx = 1
cnt = 0
for j in range(w):
    flag = False
    for i in range(h):
        if s[i][j] == ".":
            flag = True
            u2[i][j] = idx
            cnt += 1
        elif flag:
            d2[idx] = cnt
            cnt = 0
            idx += 1
            flag = False  
    if flag:
        d2[idx] = cnt
        cnt = 0
        idx += 1

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, d1[u1[i][j]]+d2[u2[i][j]]-1)
print(ans)
### BUGGY CODE ###

N = int(input())
L = [[int(x) for x in input().split()] for _ in range(N-1)]

dic = {}
dic_d = {}
visited = [0]*(N+1)
for i in range(N-1):
    if visited[L[i][0]] == 1:
        dic[L[i][0]].append(L[i][1])
        dic_d[L[i][0]].append(L[i][2])
    else:
        dic[L[i][0]] = [L[i][1]]
        dic_d[L[i][0]] = [L[i][2]]
        visited[L[i][0]] = 1
    if visited[L[i][1]] == 1:
        dic[L[i][1]].append(L[i][0])
        dic_d[L[i][1]].append(L[i][2])
    else:
        dic[L[i][1]] = [L[i][0]]
        dic_d[L[i][1]] = [L[i][2]]
        visited[L[i][1]] = 1

ans_list = ["0"]*(N+1)
q = [1]
D = [0]
while q:
    v = q.pop(0)
    d = D.pop(0)
    for i in range(len(dic[v])):
        if visited[dic[v][i]] == 1:
            q.append(dic[v][i])
            D.append((d+dic_d[v][i])%2)
            visited[dic[v][i]] = 2
            if (d+dic_d[v][i])%2 == 1:
                ans_list[dic[v][i]] = "1"
                
for i in range(1, N+1):
    print(ans_list[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])
    
d = [0]*(N)

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)
### BUGGY CODE ###

import collections
import math

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

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	for i in range(len(s)):
		cur = (cur + int(s[len(s) - 1 - i]) * 10 ** i) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))

### FIXED CODE ###

import collections
import math

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

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))
### BUGGY CODE ###

S = (input())
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    x = int(i)
    n += x*t
    cnt[n%2019] += 1
    t *= 10
print(sum(i*(i-1)//2 for i in cnt))


### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

from fractions import gcd

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
    ans %= MOD
print(ans)


### FIXED CODE ###

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

def func(x):
    if x <= 1:
        return []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            count = 0
            while x%i==0:
                x //= i
                count += 1
            return [[i,count]]+func(x)
    return [[x,1]]
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = [0]*(10**6)
for i in A:
    for a,b in func(i):
        lcm[a] = max(lcm[a],b)
L = 1
for i in range(2,10**6):
    L *= pow(i,lcm[i],MOD)
    L %= MOD
ans = 0
for i in A:
    ans += L*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr

    n = int(input())
    a = list(map(int, input().split()))
    import copy

    gcddict = {}
    adiv = []
    for i in range(n):
        primes = factorization(a[i])
        adiv.append(primes)
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = adiv[i]
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= k **test[k]
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))
resolve()

### FIXED CODE ###

def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])
    lsd = lsd % mod

    ans = 0
    for i in range(n):
        ans += (lsd * pow(a[i], mod-2, mod)) % mod

    print(int(ans % mod))

resolve()
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())

a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

if len(a)==0:
  if now==5:
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if i==0:
    for k in range(10):
      dp[i][(now+a[i][k])%13] = 1
  else:
    for k in range(10):
      temp = a[i][k]
      for l in range(13):
        dp[i][(l+temp)%13] += dp[i-1][l]
        dp[i][(l+temp)%13] = dp[i][(l+temp)%13]%mod
print(dp[len(a)-1][5])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0]*13 for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])] += 1
    else:
      for j in range(10):
        dp[i][j] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k*10+int(S[i]))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k*10+j)%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])
### BUGGY CODE ###

import sys
import bisect


def main():

    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    bc = []
    for _ in range(m):
        bc.append(list(map(int,input().split())))

    a.sort()
    a = tuple(a)

    bc.sort(key=lambda x: x[1], reverse=True)

    num = 0
    ans = 0

    for i in range(m):
        b = bc[i][0]
        c = bc[i][1]
        index = bisect.bisect_left(a[num:],c)
        if index == 0:
            break
        elif index > b:
            ans += c * b
        else:
            ans += c * index
            ans += sum(a[num+index:num+b])

        num += b
        if num >= n:
            break

    if num < n:
        print(ans + sum(a[num:]))
    else:
        print(ans)
if __name__ == '__main__':
    input = sys.stdin.readline
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    bc = []
    for _ in range(m):
        bc.append(list(map(int,input().split())))

    a.sort()
    a = tuple(a)

    bc.sort(key=lambda x: x[1], reverse=True)

    num = 0
    ans = 0

    for i in range(m):
        b = bc[i][0]
        c = bc[i][1]
        for j in range(num,min(num+b,n)):
            if c > a[j]:
                ans += c
            else:
                ans += a[j]

        num += b
        if num >= n:
            break

    if num < n:
        print(ans + sum(a[num:]))
    else:
        print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

N = int(raw_input())
array = []
for i in range(N):
    array.append(int(raw_input()))

array.sort()

def euclid(a, b):
    while a != b:
        if a > b:
            if a % b == 0:
                return b
            a = a-b
        else:
            if b % a == 0:
                return a
            b = b-a
    return a

result = array[0]
for i in array[1:]:
    result = result * i / euclid(result, i)
print result

### FIXED CODE ###

import sys

def scp(a, b):
    if b > a:
        tmp_a = a
        a = b
        b = tmp_a
    while b:
        r = a % b
        a = b
        b = r
    return a
    #for i in xrange(100000, 2, -1):
    #    if a % i == b % i == 0:
    #        return a * b / i
    #return a * b

N = int(raw_input())
array = []
for i in range(N):
    array.append(int(raw_input()))

array.sort()

#if array[-1] > pow(10, 9):
#    print array[-1]
#    sys.exit(0)

result = array[0]
for i in array[1:]:
    result = result / scp(result, i) * i
print result
### BUGGY CODE ###

def resolve():
    s = input()
    t = input()

    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

    print(dp[len(s)][len(t)])

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

# dpに文字列を格納 (TLE)
def resolve():
    s = input()
    t = input()

    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

    print(dp[len(s)][len(t)])

def resolve():
    s = input()
    t = input()

    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    # 後ろから探索
    # s[i-1]が、LCSに含まれるかどうか判定
    # dp[i][j]とdp[i-1][j]またはdp[i][j-1]が一致(変化なし)の場合、s[i-1]はLCSに含まれない
    res = ""
    i = len(dp) - 1
    j = len(dp[0]) - 1
    while i != 0 and j != 0:
        if dp[i][j] == dp[i - 1][j]: 
            i -= 1 
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res = s[i-1] + res
            i -= 1
            j -= 1

    print(res)

if __name__ == "__main__":
    resolve()