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

N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
ans = 0
n = 2
for X in range(1,2**len(D)):
  k = Base_10_to_n(X, n).zfill(len(D))
  cur = 1
  for i in range(len(k)):
    if k[i] == '1':
      cur *= D[i]
  ans = (ans+cur)%(10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
L = [chr(ord('a') + i) for i in range(26)]
cnt = [0]*26
for i in range(len(S)):
  cnt[ord(S[i])-97] += 1
D = []
for i in range(26):
  if cnt[i] != 0:
    D.append(cnt[i])
ans = 1
for i in range(len(D)):
  ans *= (D[i]+1)
  ans = ans%(10**9+7)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
DP = [[0] * (W+1) for i in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  for w in range(1,W+1):
    if w >= wn:
      DP[n][w] = max(DP[n-1][w-wn] + vn, DP[n-1][w])
    else:
      DP[n][w] = DP[n-1][w]
print(DP[N][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int)
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  dp[wn:]=np.maximum(dp[wn:], dp[:-wn]+vn)
print(dp[W])
### BUGGY CODE ###

import math
import copy
H,N=map(int,input().split())

#inf=float('inf')
dp=[0]+[int(1e8)]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j],ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    if A>=H:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])


### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        for w in range(target + 1):
            if vi > 0:
                P[vi][w] = P[vi - 1][w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        P[vi][w] = new
            else:
                if w >= W[vi]:
                    P[vi][w] = V[vi]
    return P[len(V) - 1][target]

assert knapsack(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

n, w = map(int, input().split())
W, V = [], []
for _ in range(n):
    weight, value = map(int, input().split())
    W.append(weight)
    V.append(value)
ans = knapsack(w, W, V)
print(ans)


### FIXED CODE ###

# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [-1] * (target + 1)
    P[target] = 0 # default + max

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if P[i] != -1 and P[i - we] < P[i] + va:
                P[i - we] = P[i] + va

    return max(P)

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
### BUGGY CODE ###

from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
field = list(list(input()) for _ in range(H))
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            field[i][j] = 1
            q.append((i, j, 0))
        else:
            field[i][j] = 0

res = 0
while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and field[ny][nx] == 0:
            field[ny][nx] = 1
            q.append((ny, nx, lv+1))

print(res)


### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
### BUGGY CODE ###

size=input()
pro=input()

p=pro.split(" ")

for i in range(len(p)):
    p[i]=int(p[i])

k_end=max(p)
k_start=min(p)

c=0
for k in range(k_start,k_end+1):
    a=[]
    b=[]
    for x in p:
        if(k<=x):
            a.append(x)
        else:
            b.append(x)
    if(len(a)==len(b)):
        c+=1
    else:
        pass
print(c)

### FIXED CODE ###

import numpy as np

size=input()
pro=input()

p=np.array(pro.split(" "),dtype=np.int32)
p=np.sort(p)

me=int(len(p)/2)

print(p[me]-p[me-1])
### BUGGY CODE ###

X,K,D = map(int,input().split())
flag=False
for i in range(K):
    if X>0:
        X-=D
        if X<=0:
            if (K-i)%2==1:
                ans=abs(X)
                flag=True
                break
            else:
                ans=abs(X+D)
                flag=True
                break
    else:
        X+=D
        if X>=0:
            if (K-i)%2==1:
                ans=abs(X)
                flag=True
                break
            else:
                ans=abs(X-D)
                flag=True
                break
if flag == False:
    ans=abs(X)

print(ans)


### FIXED CODE ###

X,K,D = map(int,input().split())
X=abs(X)
q=X//D
mod=X%D

if q <= K:
    if (K-q)%2==0:
        ans=mod
    else:
        ans=D-mod
else:
    ans=X-K*D
print(ans)
### BUGGY CODE ###

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=lambda x: x[0])
List_S = []
 
result = 0
p = 0
 
for i in range(1,M+1):
    add = 0
    for j in range(p,N):
        if List[j][0] <= i:
            List_S.append(List[j][1])
            p += 1
            add = 1
        else:
            break
    if len(List_S) != 0:
        if add == 1:
            List_S.sort()
        result += List_S[len(List_S)-1]
        List_S.pop()
 
print(result)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)
### BUGGY CODE ###


def main():
    S,K=input().split()
    K=int(K)
    K=min(K,300)
    mod=998244353
    a=[]
    val=0
    for i in range(len(S)):
        if S[i]=="0":
            a.append(val)
            val=0
        else:
            val+=1
    
    if val!=0:
        a.append(val)
    m=len(a)
    
    dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]
    
    for j in range(K+1):
        dp[m][j][j]=1
    
    for i in range(m-1,-1,-1):
        for j in range(K+1):
            for k in range(K+1):
                M=max(k-j,-a[i])
                if M>=0:
                    for l in range(max(0,M),K-j+1):
                        dp[i][j][k]+=dp[i+1][j+l][k]
                        dp[i][j][k]%=mod
                else:
                    for l in range(max(0,M),K-j+1):
                        dp[i][j][k]+=dp[i+1][j+l][k]
                        dp[i][j][k]%=mod
                    for l in range(1,min(K-k,-M)+1):
                        dp[i][j][k]+=dp[i+1][j][k+l]
                        dp[i][j][k]%=mod
    
    print(dp[0][0][0])

if __name__=="__main__":
    main()


### FIXED CODE ###

S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(min(b[i],K)+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])
### BUGGY CODE ###

import numpy as np
N = int(input())
ll=[]
ll = np.array(list(map(int, input().split())))

num =0
for i in range(N):
  if ll[:i+1].min() == ll[i]:
    num+=1
print(num)


### FIXED CODE ###

import sys

N = int(input())
ll=[]
ll = list(map(int, input().split()))

num =0
mi = ll[0]
for i in range(N):
  a = ll[i]
  if mi >= a:
    mi = a
    num += 1

print(num)
### BUGGY CODE ###

import collections
s = raw_input()
t = raw_input()
i = 0
c = 0
while(True):
	progress = False
	j = 0
	for j in range(len(s)):
		if s[j] == t[i]:
			i+=1
			progress = True
			if i == len(t): break
	if progress is False: break
	if i == len(t): break
	c += 1
print c * len(s) + j + 1 if progress else -1

### FIXED CODE ###

import collections
s = raw_input()
t = raw_input()
sb = s + s
h = {chr(ord('a') + i):-1 for i in range(26)}
dp = []
for j in range(len(sb)-1,-1,-1):
	dp.append({k:h[k] for k in h})
	h[sb[j]] = j
special = h
dp = dp[::-1]
i = -1
j = 0
c = 0
while(j < len(t)):
	ha = dp[i] if i >= 0 else special
	letter = t[j]
	if ha[letter] != -1:
		i = ha[letter]
		j += 1
	else:
		j = -1
		break

	if i >= len(s):
		i %= len(s)
		c+=1

print (c * len(s) + i + 1) if j != -1 else -1
### BUGGY CODE ###

n=int(input())

sm=0
lis=[1]*(n+1)

for i in reversed(range(2,n+1)):
    for mul in range(1,10**10):
        if i*mul > n:
            break
        lis[i*mul]+=1

ans=0

for i in range(len(lis)):
    ans+=(i*lis[i])
print(ans)

### FIXED CODE ###

n=int(input())

x=[-1]*(10**7+5)
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**7+1:

    if x[i]==-1:
        x[i]=i
        prime.append(i)

    for j in prime:
        if i*j>10**7+1 or j>x[i]:break
        x[j*i]=j
    i+=1



def f(k):
    if k==1:
        return 1

    z=[]
    p=x[k]
    m=1
    ans=1
    while k>=2:
        k=k//p
        if p==x[k]:
            m+=1
        else:
            z.append(m)
            m=1
            p=x[k]

    for i in range(len(z)):
        ans*=z[i]+1
    return ans
ans=0
for i in range(1,n+1):
    #print(i,f(i))
    ans += i*f(i)

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

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [{} for _ in range(N)]

b = 1
for i in range(N):
    if a[0][i]: dp[0][b] = 1
    b <<= 1

for i in range(1,N):
    for k,v in dp[i-1].items():
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                if m in dp[i]: dp[i][m] = (dp[i][m] + v) % MOD
                else: dp[i][m] = v
            b <<= 1
ans = sum(dp[-1].values()) % MOD
print(ans)

### FIXED CODE ###

import sys

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

    print(dp[-1][2**N-1])

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

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

def comb(a, b):
  s = 1
  for i in range(a, b, -1):
    s *= i
  return s/2
import math

ans = (0, 0)
AL = 0
for i in A:
  for j in A:
    if i == j:
      continue
    if i < j:
      continue
    r = math.factorial(i) // (math.factorial(i-j) * math.factorial(j))
    if AL < r:
      AL = r
      ans = (i, j)
    
print(ans[0], ans[1])

### FIXED CODE ###

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

def comb(a, b):
  s = 1
  for i in range(a, b, -1):
    s *= i
  return s/2
import math

MA = max(A)
A.remove(MA)
SA = sorted(A)

h = MA // 2

da = 10**10
ans = 0
for a in SA:
  diff = abs(a-h)
  if da >= diff:
    da = diff
    ans = a
print(MA, ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = numpy.zeros(2 ** 13).astype(numpy.int32)
  dp[1:] = MAX
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(dp.shape[0]):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if (ans:=dp[2**(n+1)-2]) != MAX:
    print(ans)
  else:
    print(-1)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = [MAX] * (2 ** 13)
  dp[0] = 0
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(len(dp)):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

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

from numpy import*
def main():
  M=10**9+7
  n,*a=open(0)
  n=int(n)
  a=array([int8(t.split())for t in a],'?')
  dp=zeros(2**n,'i8')
  dp[0]=1
  j=1<<arange(n)
  for i in range(2**n-1):
    to=i|j[a[bin(i).count('1')]]
    dp[to]+=dp[i]
    dp[to]%=M
  print(dp[-1])
main()

### FIXED CODE ###

def main():
  M=10**9+7
  n,*a=open(0)
  n=int(n)
  a=[list(map(int,t[::2]))for t in a]
  dp=[1]+[0]*(2**n-1)
  for i in range(2**n-1):
    j=bin(i).count('1')
    for k in range(n):
      to=i|1<<k
      if to==i or not a[j][k]:continue
      dp[to]+=dp[i]
      dp[to]%=M
  print(dp[-1])
main()
### BUGGY CODE ###

n, k = map(int,input().split())
p = [(int(a) * (int(a)+1) / 2 / int(a)) for a in input().split()]

max_index = 0
max_sum = 0
for i in range(n-k+1):
  t = sum(p[i:i+k])
  if max_sum < t:
    max_sum = t
    max_index = i

print(max_sum)


### FIXED CODE ###

n, k = map(int,input().split())
i = 0
kitaichi = [0] * n
kitaichi_sum = [0] * n
ans = 0
for p in input().split():
  kitaichi[i] = int(p) * (int(p)+1) / 2 / int(p)
  if i == 0:
    kitaichi_sum[i] = kitaichi[i]
  elif i >= k:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i] - kitaichi[i-k]
    if kitaichi_sum[i] > ans:
      ans = kitaichi_sum[i]
  else:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i]
  if kitaichi_sum[i] > ans:
    ans = kitaichi_sum[i]
  i += 1
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for i in range(N):
        A_num[A[i]-1] += 1
        
    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        a = A_num[i]
        A_product[i] = int(a * (a-1) / 2)
        if a == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((a-1) * (a-2) / 2)

    for i in range(N):
        k = A[i]
        s = sum(A_product) - A_product[k-1] + A_product_1[k-1]
        print(s)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for a in A:
        A_num[a-1] += 1

    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        a = A_num[i]
        A_product[i] = int(a * (a-1) / 2)
        if a == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((a-1) * (a-2) / 2)


    su = sum(A_product)
    for k in A:
        print(su - A_product[k-1] + A_product_1[k-1])


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

import sys
input = sys.stdin.readline

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

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())
### BUGGY CODE ###

from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
ans = 0
for i in range(1, n+1):
  for j in range(i):
    if (L[i]-L[j])%m == 0:
      ans += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
L = [ i%m for i in L ]
C = Counter(L)
ans = 0
for i in C.values():
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
s = set(a)
for i in range(1,n+1):
    if i in s:
        print(a.count(i))
    else:
        print(0)

### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
for i in range(1,n+1):
    if i in c:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
bn = (n-1).bit_length()
b_num = 2**bn
mx = 10**9
segl=[mx]*2*b_num 

if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,0,x,i), (t-x,1,x,i)]
    xs.sort()
    xs+=[(mx,0,x,i+1)]
    ys = set()
    q = int(input())
    for x in xs:
        if q < x[0]:
            for _ in range(bn):
                nys = set()
                for k in ys:
                    segl[k] = min(segl[k*2+1],segl[k*2+2])
                    nys.add((k-1)//2)
                ys = nys
            mm = segl[0] if segl[0]!= mx else -1
            ys = set()
            while True:
                if q < x[0]:
                    print(mm)
                    Q-=1
                    if Q==0:
                        sys.exit()
                    q = int(input())
                    continue
                break
        segl[x[3]+b_num-1] = mx if x[1] else x[2]
        ys.add((x[3]+b_num-2)//2)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

s = input()
t = input()

ans = ""

for x in range(2**len(s)):
  tmp = ""
  r1 = -1
  _s = "" 
  for y in range(len(s)):
    if ((x >> y) & 1):
      _s += s[y]
  for i in range(len(_s)):
    for j in range(len(t)):
      if _s[i] == t[j]:
        if j > r1:
          tmp += _s[i]
          r1 = j
          break
  if len(tmp) > len(ans):
    ans = tmp

print(ans)

### FIXED CODE ###

import sys

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

class Solver(object):
    def __init__(self):
        pass

    def solve(self,s:str,t:str) -> int:
        ## DP loop
        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] = 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][j+1])
        
        ans = ""

        ## Recover the LCS from DP table
        ## checking the update point
        l,m = len(s),len(t)
        while l > 0 and m >0:
            if dp[l][m] == dp[l-1][m]:
                l -= 1
            elif dp[l][m] == dp[l][m-1]:
                m -= 1
            else:
                ans = t[m-1] + ans
                l -= 1
                m -= 1

        return ans

def main():
    s = input().rstrip()
    t = input().rstrip()
    solver = Solver()
    print(solver.solve(s,t))

if __name__ == "__main__":
    main()