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

from collections import deque
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        low = j
        high = n
        while high - low > 1:
            mid = (high + low) // 2
            if tris[i] < tris[j] + tris[mid] and tris[j] < tris[i] + tris[mid] and tris[mid] < tris[i] + tris[j]:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        r = bisect.bisect_left(tris, a+b)
        cnt += r - j - 1
print(cnt)
### BUGGY CODE ###

from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        tn = 2 ** ceil(log2(n))
        self.a = [0] * (tn * 2)
        self.tn = tn

    def get_sum(self, s, t):
        return self.__get_sum(1, 1, self.tn, s, t)

    def __get_sum(self, c, l, r, s, t):
        if l == r:
            return self.a[c]
        mid = (l + r) // 2
        if t <= mid:
            return self.a[c] * (t - s + 1) + self.__get_sum(c * 2, l, mid, s, t)
        elif s > mid:
            return self.a[c] * (t - s + 1) + self.__get_sum(c * 2 + 1, mid + 1, r, s, t)
        else:
            return self.a[c] * (t - s + 1) + \
                   self.__get_sum(c * 2, l, mid, s, mid) + \
                   self.__get_sum(c * 2 + 1, mid + 1, r, mid + 1, t)

    def add(self, s, t, x):
        self.__add(1, 1, self.tn, s, t, x)

    def __add(self, c, l, r, s, t, x):

        if l == s and r == t:
            self.a[c] += x
            return

        mid = (l + r) // 2
        if t <= mid:
            self.__add(c * 2, l, mid, s, t, x)
        elif s > mid:
            self.__add(c * 2 + 1, mid + 1, r, s, t, x)
        else:
            self.__add(c * 2, l, mid, s, mid, x)
            self.__add(c * 2 + 1, mid + 1, r, mid + 1, t, x)


n, q = map(int, input().split())
st = SegmentTree(n)
buf = []
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        st.add(*map(int, query[1:]))
    else:
        buf.append(st.get_sum(*map(int, query[1:])))
print('\n'.join(map(str, buf)))

### FIXED CODE ###

class BinaryIndexedTree:
    def __init__(self, n):
        self.a = [0] * (n + 1)
        self.n = n

    def add(self, i, x):
        while i <= self.n:
            self.a[i] += x
            i += i & -i

    def sum(self, i):
        ret = 0
        while i > 0:
            ret += self.a[i]
            i -= i & -i
        return ret


class Solve:
    def __init__(self, n):
        self.n = n
        self.p = BinaryIndexedTree(n + 1)
        self.q = BinaryIndexedTree(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def get_sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

    def dump(self):
        print(*(self.get_sum(i, i) for i in range(self.n + 1)))


n, q = map(int, input().split())
st = Solve(n)
buf = []
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        st.add(*map(int, query[1:]))
    else:
        buf.append(st.get_sum(*map(int, query[1:])))
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

import itertools
import bisect

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

aa = [0] + list(itertools.accumulate(A))
bb = [0] + list(itertools.accumulate(B))

ans = 0
for i in reversed(range(N+1)):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if i + M <= ans:
        continue

    if ans != 0 and bb[(ans-i+1)] >= tmp_K:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue

    mn = 0
    mx = M
    while True:
        if mn == mx:
            if tmp_K >= bb[mn]:
                ans = max(ans, i+mn)
            break

        mid = (mn+mx//2)
        if bb[mid] <= tmp_K:
            if mn == mid:
                mn = mid+1
            else:
                mn = mid

        else:
            if mx == mid:
                mx = mid-1
            else:
                mx = mid
            if i+mx <= ans:
                break
print(ans)


### FIXED CODE ###

import itertools
import bisect

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

aa = [0] + list(itertools.accumulate(A))
bb = [0] + list(itertools.accumulate(B))

ans = bisect.bisect_left(aa, K)-1
ans = max(ans, bisect.bisect_left(bb, K)-1)

for i in reversed(range(N+1)):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if i + M <= ans:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue

    ans = max(ans, bisect.bisect_left(bb, tmp_K)-1+i)
print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre1 = []
    pre2 = []
    que = deque()
    for e in range(n):
        dis = [-1 for _ in range(n)]
        dis[e]=0
        if e == k-1:
            pre1.append(0)
        else:
            que.append(e)
        while que:
            tank = deque()
            while que:
                i = que.pop()
                for j in range(len(graph[i])):
                    go = graph[i][j][0]
                    d = graph[i][j][1]
                    if dis[go]!=-1:
                        continue
                    dis[go] = dis[i] + d
                    if k-1 == go:
                        pre1.append(dis[go])
                        tank=deque()
                        que=deque()
                        break
                    tank.append(go)
            que = tank
    que = deque()
    que.append(k-1)
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        tank = []
        while que:
            i = que.pop()
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if dis[go]!=-1:
                    continue
                dis[go] = dis[i] + d
                tank.append(go)
        que = tank
    pre2 = dis

    pre1 = tuple(pre1)
    pre2 = tuple(pre2)
    for _ in range(q):
        x,y = map(int,input().split())
        print( pre1[x-1] + pre2[y-1] ) 

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

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

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

n = int(input())
ans = []

for i in range(n):
    command = input().split()
    if command[0] == "insert":
        ans.insert(0, command[1])
    elif ans == []:
        continue
    elif command[0] == "delete":
        try:
            ans.remove(command[1])
        except:
            pass
    elif command[0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

### FIXED CODE ###

# -*- coding:utf-8 -*-
import collections
n = int(input())
ans = collections.deque()

for i in range(n):
    command = input().split()
    if command[0] == "insert":
        ans.appendleft(command[1])
    elif ans == []:
        continue
    elif command[0] == "delete":
        try:
            ans.remove(command[1])
        except:
            pass
    elif command[0] == "deleteFirst":
        ans.popleft()
    else:
        ans.pop()

print (' '.join(ans))
### BUGGY CODE ###

def main():
    def chmin(i,j):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

    N,K = (int(x) for x in input().split())
    h = [int(x) for x in input().split()]
    dp = [float('INF')]*N
    dp[0] = 0

    for i in range(1, N):
        if i <= K:
            for j in range(1, i+1):
                chmin(i,j)
        else:
            for j in range(1, K+1):
                chmin(i,j)
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

def main():
    N, K = (int(x) for x in input().split())
    h = np.array([int(x) for x in input().split()])
    INF = 10**10
    dp = np.array([INF]*N)
    dp[0] = 0

    for i in range(N):
        dp[i:i+K+1] = np.minimum(dp[i:i+K+1], dp[i]+np.abs(h[i:i+K+1]-h[i]))

    print(int(dp[N-1]))

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

# 入力
num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

# dpの初期化
dp = [[0 for _ in range(num + 1)] for _ in range(weight_limit + 1)]

for w in range(1, weight_limit + 1):
    for n in range(1, num + 1):
        weight = wv_list[n-1][0]
        value = wv_list[n-1][1]

        if weight <= w and value + dp[w - weight][n-1] > dp[w][n-1]:
            dp[w][n] = value + dp[w - weight][n-1]

        else:
            dp[w][n] = dp[w][n-1]

print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

dp = np.zeros(weight_limit + 1)

for n in range(num):
    w = wv_list[n][0]
    v = wv_list[n][1]
    dp[w:] = np.maximum(dp[:-w] + v, dp[w:])

print(int(dp[-1]))
### BUGGY CODE ###

from itertools import accumulate
def sgn(n):
    if n>0:
        return 1
    elif n==0:
        return 0
    else:
        return -1
n=int(input())
a=[int(i) for i in input().split()]
b=list(accumulate(a))
#print(list(accumulate(a)))
if b[0]>0:
    f=1
else:
    f=-1
ans=0
for i in range(n):
    #print(i,b)
    if ((i%2==0) and(sgn(b[i])!=f)) or ((i%2==1) and(sgn(b[i])!=-f)):
        tmp = abs(b[i])+1
        ans += tmp
        for j in range(i,n):
            b[j] += -tmp*f*(-1)**(i-1)
#print(b)
print(ans)
        

### FIXED CODE ###

def sgn(n):
    if n>0:
        return 1
    elif n==0:
        return 0
    else:
        return -1
    
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2-1) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.f(lres, rres)
        
n=int(input())
b=[int(i) for i in input().split()]
l = SegmentTree(size=n)
p0=0
for i in range(n):
    l.update(i,b[i])
for i in range(n):
    sg=(-1)**(i)
    v=l.query(0,i+1)
    #print(v,p0)
    if sgn(v) != sg:
        tmp= abs(v)+1
        #print(f'{b[i]}---{tmp}--->{sg}')
        p0 += tmp
        l.update(i,b[i]+tmp*sg)
        
l = SegmentTree(size=n)
for i in range(n):
    l.update(i,b[i])
p1=0
#print()
for i in range(n):
    sg=(-1)**(i+1)
    v=l.query(0,i+1)
    #print(v,p1)
    if sgn(v) != sg:
        tmp= abs(v)+1
        #print(f'{b[i]}---{tmp}--->{sg}')
        p1 += tmp
        l.update(i,b[i]+tmp*sg)
    #print(l.query(0,i+1),p1)
print(min(p0,p1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力

if __name__ == "__main__":
    
    N = int(input())
    INPUT = list(map(int, input().split()))

    output = 1
    ketasuu = 0
    
    for i in INPUT:
        output = output * i
        
        if output > 10 ** 18:
            output = -1

    print(output)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力

if __name__ == "__main__":
    
    N = int(input())
    INPUT = list(map(int, input().split()))


    if 0 in INPUT:
        output = 0
    else:
        output = 1
        for i in INPUT:
            output = output * i
            
            if output > 10 ** 18:
                output = -1
                break

    print(output)
### BUGGY CODE ###

import bisect

def cmb(n,r):
    if r > n:
        return 0
    if n - r < r:
         r = n - r
    if r > n:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
a = list(map(int, input().split()))
a.sort()
index = bisect.bisect_left(a,a[-1]//2)
x = cmb(a[-1],a[index])
y = cmb(a[-1],a[index-1])
if x>y:
    print(a[-1],a[index])
else:
    print(a[-1],a[index-1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
for i in range(n-1):
    b.append([abs(a[-1]/2 -a[i]),a[i]])
b.sort()
print(a[-1],b[0][1])
### BUGGY CODE ###

from bisect import *

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
A = reads()
B = reads()

D = 28
xor = 0
for d in range(D + 1):
  mask = (1 << (d + 1)) - 1 # [1] * (d+1)
  BB = sorted(x & mask for x in B)
  count = 0
  for a in (x & mask for x in A):
    count += bisect_left(BB, (1 << (d + 1)) - a) - bisect_left(BB, (1 << d) - a)
    count += bisect_left(BB, (1 << (d + 2)) - a) - bisect_left(BB, (1 << d) + (1 << (d + 1)) - a)
  if count & 1:
    xor |= 1 << d

print(xor)



### FIXED CODE ###

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
N = read()
A = reads()
B = reads()
 
D = 28
xor = 0
for d in range(D + 1):
  mask = (1 << (d + 1)) - 1 # [1] * (d+1)
  AA = sorted(x & mask for x in A)
  BB = sorted(x & mask for x in B)
  count = 0
  itr = [N] * 4
  for a in AA:
    vs = [
      (1 << d) - a,
      (1 << (d + 1)) - a,
      (1 << d) + (1 << (d + 1)) - a,
      (1 << (d + 2)) - a
    ]
    for i in range(4):
      while 0 < itr[i] and vs[i] <= BB[itr[i]-1]:
        itr[i] -= 1
    count += (itr[1] - itr[0]) + (itr[3] - itr[2])
  if count & 1:
    xor |= 1 << d
 
print(xor)
### BUGGY CODE ###

N = int(input())
if N % 4 == 0:
  h, n, w = (3 * N) // 4, (3 * N) // 4, (3 * N) // 4
elif N % 4 == 2:
  h, n, w = N, N, N // 2
elif N % 4 == 3:
  s = N // 4 + 1
  h, n, w = 2 * s, 2 * s, s * N
elif N % 4 == 1:
  s = (N // 4) + 1
  if s % 3 == 0:
    h = s
    n = 2 * (s // 3) * (4 * s - 3)
    w = 2 * (s // 3) * (4 * s - 3)
  elif s % 3 == 2:
    h = N
    n = 4 * (s // 3) + 2
    w = (4 * (s // 3) + 2) * (12 * (s // 3) + 5)
  elif s % 3 == 1:
    for i in range(1, 3501):
      for j in range(1, 3501):
        if (N * i * j) / (4 * i * j - N * i - N * j) == int((N * i * j) / (4 * i * j - N * i - N * j)):
          h, n, w = i, j, int((N * i * j) / (4 * i * j - N * i - N * j))
          break
print(h, n, w)


### FIXED CODE ###

N = int(input())
if N % 4 == 0:
  h, n, w = (3 * N) // 4, (3 * N) // 4, (3 * N) // 4
elif N % 4 == 2:
  h, n, w = N, N, N // 2
elif N % 4 == 3:
  s = N // 4 + 1
  h, n, w = 2 * s, 2 * s, s * N
elif N % 4 == 1:
  s = (N // 4) + 1
  if s % 3 == 0:
    h = s
    n = 2 * (s // 3) * (4 * s - 3)
    w = 2 * (s // 3) * (4 * s - 3)
  elif s % 3 == 2:
    h = N
    n = 4 * (s // 3) + 2
    w = (4 * (s // 3) + 2) * (12 * (s // 3) + 5)
  elif s % 3 == 1:
    l = (N+3)//4
    p = 0
    for i in range(l, 3501):
      m = (N*i)//(4*i-N)+1
      for j in range(m, 3501):
        #print(i, j, (N*i*j)%(4*i*j-N*(i+j)), 4*i*j-N*(i+j))
        if (N*i*j) % (4*i*j-N*(i+j)) == 0 and 4*i*j-N*(i+j) > 0:
          p = 1
          h, n, w = i, j, (N*i*j) // (4*i*j-N*(i+j))
          break
      if p == 1:
        break
print(h, n, w)
### BUGGY CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0 for _ in range(n+1)]

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")


### FIXED CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

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

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = np.array([int(i) for i in input().split()])

for _ in range(m):
    imax = np.argmax(a)
    a[imax] = a[imax] // 2

print(a.sum())



### FIXED CODE ###

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

#%%

# n, m, a = 3, 3, [1,2,3,4,7,9, 10,8,16,14]

#%%
max_heap = [a[0]]
#%%
def add_heap(array, number):
    array.append(number)

    def swap(array, number, idx):
        if idx == 1:
            return array[idx-1]

        ai = array[idx-1]
        target_idx = (idx//2)
        target = array[target_idx-1]
        
        if ai >= target:
            array[idx-1], array[target_idx-1] =  target, ai

            number = swap(array, number, target_idx)
        else:
            return array[idx-1]

    return swap(array, number, len(array))


#%%
for ai in a[1:]:
    add_heap(max_heap, ai)

#%%
for _ in range(m):
    
    #half
    max_heap[0] //= 2
    
    def sort_heap(array, number, idx):
        top = number
        left_idx = idx*2
        right_idx = idx*2 + 1
        
        if left_idx > len(array):
            left = -1
        else:
            left = array[left_idx - 1]

        if right_idx > len(array):
            right = -1
        else:        
            right = array[right_idx - 1]

        if top >= left and top >= right:
            return array
        elif left > right:
            array[idx-1], array[left_idx-1] = left, top
            sort_heap(array, top, left_idx)
        else:
            array[idx-1], array[right_idx-1] = right, top
            sort_heap(array, top, right_idx)

    sort_heap(max_heap, max_heap[0], 1)

#%%
print(sum(max_heap))

#%%
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = collections.Counter(a)
cnt = 0
c = b.most_common()[::-1]
while len(c) > k:
	cnt += c[0][1]
	c.pop(0)
print (cnt)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = collections.Counter(a)
cnt = 0
c = b.most_common()
s = 0
for i in range(len(c)):
	cnt += 1
	if cnt > k:
		for j in range(i,len(c)):
			s += c[j][1]
		break
print (s)
### BUGGY CODE ###

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

R = S.count('R')
G = S.count('G')
B = N - (R + G)

ans = R*G*B
answ = 0

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

### FIXED CODE ###

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

R = S.count('R')
G = S.count('G')
B = N - (R + G)

ans = R*G*B
answ = 0

for i in range(0,N):
    for j in range(i+1,(N+i)//2 +1):
        if S[i] != S[j]:
            if 2*j-i < N and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

#import numpy as np
#print(np.array(dp))

from collections import deque
ans = deque()

#ans = []
i, j = ls, lt
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:
        i -= 1
        j -= 1
        ans.appendleft(s[i])
        #ans = s[i] + ans
print(''.join(ans))

#print(ans)

### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

#import numpy as np
#print(np.array(dp))

#from collections import deque
#ans = deque()

ans = ''
i, j = ls, lt
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:
        i -= 1
        j -= 1
        #ans.appendleft(s[i])
        ans = s[i] + ans
#print(''.join(ans))
print(ans)