Harryxun/stf_run huggingface dataset:
import numpy as np
N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1)
value = np.full(N + 1, -1)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans =  knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))


### FIXED CODE ###

import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)
A,B,C = map(int,input().split())
if A<C & C<B:
	print("yes")
else:
  if A>C & C>B:
    print("yes")
  else:
	print("No")


### FIXED CODE ###

A,B,C = map(int,input().split())
if A>C & C>B:
	print("Yes")
if B>C & C>A:
   	print("Yes")
if C>A & A>B:
	print("No")
if B>A & A>C:
	print("No")
if A>B & B>C:
	print("No")
if C>B & B>A:
	print("No")
N = int(input())
sX = input()

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for i in range(N):
    if(one_r_count != '0'):
        one_mod = (one_mod << 1) + int(sX[i]) % one_r_count
    zero_mod = (zero_mod << 1) + int(sX[i]) % zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,22000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1

for i in range(1,N+1):
    if(sX[i-1] == '1'):
        if(one_r_count != 0):
            Xi_n = one_mod - pow(2,N-i)
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + pow(2,N-i)
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

### FIXED CODE ###

N = int(input())
sX = input()

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    if sX[i-1] == '0':
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)
n, q = map(int, input().split())

connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

print(*ans)
def calc(a, b):
    return a**4+a**3*b+a**2*b**2+a*b**3+b**4

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()
    return divisors

x = int(input())
div = make_divisors(x)
ans = 0
for yakusu in div:
    num = x // yakusu
    left = 0
    right = int(num**0.25) + 1
    while left+1 < right:
        mid = (left+right) // 2
        a, b = mid, mid-yakusu
        result = calc(a, b)
        if abs(result) > num:
            right = mid
        else:
            left = mid
    if abs(calc(right, right-yakusu)) == num:
        ans = (right, right-yakusu)
        break
    if abs(calc(left, left-yakusu)) == num:
        ans = (left, left-yakusu)
        break

if ans[0]**5 - ans[1]**5 > 0:
    print(ans[0], ans[1])
else:
    print(ans[1], ans[0])

### FIXED CODE ###

x = int(input())

ans = 0
for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5 - b**5 == x:
            ans = [a, b]
            break
    if ans != 0:
        break
print(ans[0], ans[1])
import math
sosu = 10 ** 9 + 7
N, K = map(int, input().split())
def conv(n, r):
    ans = math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) % sosu
    return(ans)

for i in range(1, K+1):
    if N-K+1 >= i:
        fir = conv(K-1, i-1)
        #print(fir)
        sec = conv(N-K+1, i)
        #print(sec)
        ans = fir * sec % sosu
        print(int(ans))
    else:
        print(0)


### FIXED CODE ###

import math
sosu = 10 ** 9 + 7
N, K = map(int, input().split())
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def conv(n, r):
    bunbo = math.factorial(n) % sosu
    bunsi1 = mod_inv(math.factorial(r), sosu)
    bunsi2 = mod_inv(math.factorial(n-r), sosu)
    ans = bunbo * bunsi1 * bunsi2 % sosu
    return(ans)
#print(conv(1997,2))

for i in range(1, K+1):
    if N-K+1 >= i:
        fir = conv(K-1, i-1)
        sec = conv(N-K+1, i)
        ans = fir * sec % sosu
        print(int(ans))
    else:
        print(0)
n,d = map(int,input().split())
sight = 2*d+1
i = 1
while(True)
  if n <= i*sight:
    print(i)
    break
  i += 1
    

### FIXED CODE ###

n,d = list(map(int,input().split()))
sight = 2*d+1
print((n//sight) + (n%sight != 0))
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				print(street)
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

### FIXED CODE ###

def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				# print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				# print(street)
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	setter(x, y, False, visited)
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



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

dp = [0] * (n + 1)

for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""


### FIXED CODE ###

n, m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""
a, b, c, d = map(int, input().split())
if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('R

### FIXED CODE ###

a, b, c, d = map(int, input().split())
if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('Right')
a, b, c, d = map(int, input().split())
takahashi = [a, b] if a>b else [b, a]
aoki = [c, d] if c>d else [d, c]
attackers = [takahashi, aoki]
attacker = 0

while 0 not in takahashi and 0 not in aoki:
  attackers[attacker^1][1] = max(0, attackers[attacker^1][1]-attackers[attacker][0])
  attackers[attacker^1].sort(reversed=True)
  attacker = attacker^1

if 0 in attackers[0]:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

a, b, c, d = map(int, input().split())
takahashi = [a, b]
aoki = [c, d]
attackers = [takahashi, aoki]
attacker = 0

while attackers[0][0]!=0 and attackers[1][0]!=0:
  attackers[attacker^1][0] = max(0, attackers[attacker^1][0]-attackers[attacker][1])
  attacker = attacker^1

if attackers[0][0]==0:
  print('No')
else:
  print('Yes')
N,L=map(int,input().strip().split(" "))
a=[]

for i in range(L):
    a.append(input())

a.sort()

b=str(a)
b=b.replace(",","")
b=b.replace("[","")
b=b.replace("]","")
b=b.replace("'","")
b=b.replace(" ","")


print(b)


### FIXED CODE ###

N,L=map(int,input().strip().split(" "))
a=[]

for i in range(N):
    a.append(input())

a.sort()

b=str(a)
b=b.replace(",","")
b=b.replace("[","")
b=b.replace("]","")
b=b.replace("'","")
b=b.replace(" ","")


print(b)
import bisect

lis[1, 12]

str = input()
tp = int(str[:2])
bt = int(str[2:])
if

tplo = bisect.bisect_right(lis, tp)
btlo = bisect.bisect_right(lis, bt)

if tp == 0:
    if bt == 1:
        jd = 3
    else:
        jd == 0
elif tp == 1:
    if bt == 1:
        jd == 2
    else:
        jd == 1
else:
    if bt == 1:
        jd == 0
    else:
        jd == 3

judge = ["YYMM", "MMYY", "AMBIGUOUS", "NA"]
print(judge[jd])


### FIXED CODE ###

import bisect

lis = [1, 13]

str = input()
tp = int(str[:2])
bt = int(str[2:])

tplo = bisect.bisect_right(lis, tp)
btlo = bisect.bisect_right(lis, bt)

if tplo == 1:
    if btlo == 1:
        jd = 2
    else:
        jd = 1
else:
    if btlo == 1:
        jd = 0
    else:
        jd = 3

judge = ["YYMM", "MMYY", "AMBIGUOUS", "NA"]

print(judge[jd])
n = int(input())
 
a = list(map(int,input().split()))
 
total = 0
 
cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
    
for i in cnt:
    if i > 0:
        total += (i*(i-1))//2
 
for i in range(n):
    ans = 0
    before = (cnt[a[i]]*(cnt[a[i]]-1))//2
    after = ((cnt[a[i]]-1)*(cnt[a[i]]-2))//2
    
    ans = total - before + after
    print(ans)

### FIXED CODE ###

import collections

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

a=collections.Counter(A)

total=0
for v in a.values():
    if v>1:
        c=(v*(v-1))//2
        total+=c

for i in A:
    ans=total-(a[i]*(a[i]-1))//2+((a[i]-1)*(a[i]-2))//2
    print(ans)
import math

N, M = map(int, imput().split())
count = 0

def nCr(n):
  if n >= 2:
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
  else:
    return 0

print(nCr(N)+nCr(M))

### FIXED CODE ###

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

print( (N*(N-1))//2 + (M*(M-1))//2 )
import numpy as np
H,W,K=map(int, input().split())
M=np.array([list(input()) for _ in range(H)])
ans=np.zeros((H,W),int)
k=0
l
for i in range(H):
    l=0
    for j in range(W):
        if M[i,j]=='#':
            k+=1
            ans[i,l:j+1]=k
            l=j+1

for i in range(H):
    if sum(ans[i,:])==0:
        if i!=0:
            ans[i,:]=ans[i-1,:]
        if i==0:
            ans[i,:]=ans[1,:]
for i in range(H):
    for j in range(W):
        if ans[i,j]==0:
            ans[i,j]=ans[i,j-1]
            
for row in ans:
    print(*row)

### FIXED CODE ###

import numpy as np
H,W,K=map(int, input().split())
M=np.array([list(input()) for _ in range(H)])
ans=np.zeros((H,W),int)
k=0

for i in range(H):
    l=0
    for j in range(W):
        if M[i,j]=='#':
            k+=1
            ans[i,l:j+1]=k
            l=j+1

            
for i in range(H):
    for j in range(W):
        if ans[i,j]==0:
            ans[i,j]=ans[i,j-1]
            
            
for j in range(W):
    J=W-j-1
    for i in range(H):
        I=H-i-1
        if I!=H-1 and ans[I,J]==0:
            ans[I,J]=ans[I+1,J]


for i in range(H):
    if sum(ans[i,:])==0:
        if i!=0:
            ans[i,:]=ans[i-1,:]
        if i==0:
            ans[i,:]=ans[1,:]
            
for row in ans:
    print(*row)
import numpy as np
import numba

@numba.jit(nopython=True)
def main(ls):
    total = 0

    for i in range(len(ls) - 2):
        for j in range(i + 1, len(ls) - 1):
            a = ls[i]
            b = ls[j]
            ls2 = ls[j + 1:]
            if a + b == ls2[0]:
                 num = 0
            else:
                 num = np.searchsorted(ls2, a + b, side='right')
            total += num

    print(total)


_n = input()
ls = np.array(list(sorted(map(int, input().strip().split()))))

main(ls)


### FIXED CODE ###

import bisect


def main(ls):
    total = 0

    for i in range(len(ls) - 2):
        for j in range(i + 1, len(ls) - 1):
            a = ls[i]
            b = ls[j]
            left = j + 1
            num = bisect.bisect_left(ls, a + b) - left
            total += num

    print(total)


_n = input()
ls = list(sorted(map(int, input().strip().split())))

main(ls)
a = input()
b = input()
c = input()

len_a = len(a)
len_b = len(b)
len_c = len(c)

def match(a, b):
    return a=='?' or b=='?' or a==b


ab = [True] * 20000
ac = [True] * 20000
bc = [True] * 20000

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+10000] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = len(a)+len(b)+len(c)

ans = len_max
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+10000] and ac[j+10000] and bc[j-i+10000]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)



### FIXED CODE ###

"""
a = 'a'*2000
b = 'b'*2000
c = 'c'*2000
"""
a = input()
b = input()
c = input()


len_a = len(a)
len_b = len(b)
len_c = len(c)

def match(a, b):
    return a=='?' or b=='?' or a==b

dp_len=50000
ab = [True] * dp_len
ac = [True] * dp_len
bc = [True] * dp_len

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+dp_len//2] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000

ans = len_a+len_b+len_c
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+dp_len//2] and ac[j+dp_len//2] and bc[j-i+dp_len//2]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
print(g)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
print(g)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
suf = 0
for i in range (n):
  if men1 != n-1:
  	men1 = a[i]
  	men2 = a[i + 1] 
  	suf += b[men1]
  	if (men1 + 1 == men2):
    	suf += c[men1]
  else:
    men1 = a[i]
    suf += b[men1]
print(suf)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
suf = 0
for i in range (n):
  suf += b[i]
  if i >= 1 and a[i - 1]  + 1 == a[i]:
    suf += c[a[i - 1] - 1]
print(suf)
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in enumerate(F):
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  ri = root(R, i)
  rj = root(R, j)
  if ri <= rj:
    R[rj] = ri
  else:
    R[ri] = rj
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if N < 2 * (N - M - 1):
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)
n = int(input())
plist = list(map(int, input().split()))
counter = 0

for i in range(2, n):
    a, b, c = plist[i - 1:i + 2]
    if a < b < c or c < b < a:
        counter += 1

print(counter)

### FIXED CODE ###

n = int(input())
plist = list(map(int, input().split()))
counter = 0

for i in range(1, n-1):
    a, b, c = plist[i-1:i+2]
    if a < b < c or c < b < a:
        counter += 1

print(counter)
s=[ord(ch) for ch in input()]
t=[ord(ch) for ch in input()]
# 
#print("#")
 
# minimize
mnmz={i for i in s} & {j for j in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz]
t=[ z for z in t if z in mnmz]
if len(s)>len(t): s, t = t, s
#print(s)
#print(t)
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    acc={}
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                acc[temp]=res[prev].copy()+[s[j]]
        prev, dp[j] = dp[j], temp
    res.update(acc)
    if dp[-1]==len(s): break
 
#print(dp)
 
print("".join([ chr(i) for i in res[dp[-1]]]))

### FIXED CODE ###

s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame init
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: #and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if i==0 and j==0: break
    if j>0 and dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)


print("".join(chr(i+97) for i in reversed(res)))