Harryxun/stf_run huggingface dataset:
N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
w.insert(0,"0")
v.insert(0,"0")
for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]






Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))
        

### FIXED CODE ###


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


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
    


Wmin = min(w)    
w.insert(0,"0")
v.insert(0,"0")
for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]



nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))
h,w = map(int,input().split())
c = [[] for i in range(0,h+2)]
ans = "Yes"
c[0] = ["."for i in range(0,w+2)]
c[h+1] = ["."for i in range(0,w+2)]
for i in range(1,h+1):
    d = []
    d = list(input())
    d.append(".")
    d.insert(0,".")
    c[i] = d
for i in range(1,h+1):
    for j in range(1,w+1):
        if c[j][i] == "#":
            flag = "No"
            if(c[j][i-1] == "#"):
                flag = "Yes"
            if(c[j][i+1] == "#"):
                flag = "Yes"
            if(c[j-1][i] == "#"):
                flag = "Yes"
            if(c[j+1][i] == "#"):
                flag = "Yes"
            if(flag == "No"):
                ans = "No"
print(ans)


### FIXED CODE ###

h,w = map(int,input().split())
c = [[] for i in range(0,h+2)]
ans = "Yes"
c[0] = ["."for i in range(0,w+2)]
c[h+1] = ["."for i in range(0,w+2)]
for i in range(1,h+1):
    d = []
    d = list(input())
    d.append(".")
    d.insert(0,".")
    c[i] = d
for j in range(1,h+1):
    for i in range(1,w+1):
        if c[j][i] == "#":
            flag = "No"
            if(c[j][i-1] == "#"):
                flag = "Yes"
            if(c[j][i+1] == "#"):
                flag = "Yes"
            if(c[j-1][i] == "#"):
                flag = "Yes"
            if(c[j+1][i] == "#"):
                flag = "Yes"
            if(flag == "No"):
                ans = "No"
print(ans)
import math
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    div_list = []
    d = 2
    ans = 1
    MOD = 10**9+7
    while M != 1:
        count = 0
        while M%d == 0:
            count += 1
            M //= d
        div_list.append(count)
        d += 1
    _m = max(div_list)
    fac = [1]
    for i in range(1,_m+N):
        fac.append(fac[-1]*i%MOD)
    use = max(N-1,_m)
    
    def power(x,y):
        if y == 0:return 1
        elif y == 1:return x%MOD
        elif y%2 == 0:return power(x,y//2)**2%MOD
        else:return power(x,y//2)**2*x%MOD
        
    invfac = [0 for _ in range(use+1)]
    invfac[-1] = power(fac[use],MOD-2)
    for i in range(use-1,-1,-1):
        invfac[i] = invfac[i+1]*(i+1)%MOD
        
    for i in div_list:
        a = fac[i+N-1]
        b = invfac[i]
        c = invfac[N-1]
        ans *= (a*b*c)%MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import copy

def main():
    N,M = map(int,input().split())
    d = defaultdict(int)
    MOD = 10**9+7
    R = 10**5+100
    fac = [0 for _ in range(R+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,R+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        num = (((fac[x+y]*invfac[y])%MOD)*invfac[x]%MOD)
        return num

    while M%2 == 0:
        d[2] += 1
        M //= 2
    f = 3
    while f ** 2 <= M:
        if M % f == 0:
            d[f] += 1
            M //= f
        else:
            f += 2
    if M != 1:
        d[M] += 1
    
    l = list(d.values())
    ans = 1
    for num in l:
        ans *= coef(num,N-1)
        ans %= MOD
        
    print(ans)
    
if __name__ == "__main__":
    main()
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(change_cnt, minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()


### FIXED CODE ###

MOD = 10 ** 9 + 7


def mul_mod(x, y, mod):
    return x * y % mod


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if k == 1:
        res = max(a) % MOD
    elif k == n:
        res = 1
        for e in a:
            res *= e
            res %= MOD
    elif max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(change_cnt, minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()
S=input()
T=input()
ans=0
if S[0]==T[0]:
	ans += 1
if S[1]==T[1]
	ans += 1
if S[2]==T[2]
	ans += 1
ans

### FIXED CODE ###

S=input()
T=input()
ans=0
if S[0]==T[0]:
    ans+=1
if S[1]==T[1]:
    ans+=1
if S[2]==T[2]:
    ans+=1
print(ans)
D N =input()
if D ==0:
    print(N)
elif D == 1:
    print(N*100)
elif D == 2:
    print(N*10000)

### FIXED CODE ###

D,N =map(int,input().split())
if D ==0 and N <100:
    print(N)
elif D ==0 and N ==100:
    print(N+1)
elif D == 1 and N <100:
    print(N*100)
elif D ==1 and N ==100:
    print((N+1)*100)

elif D == 2 and N <100:
    print(10000*N)
elif D == 2 and N==100:
    print((N+1)*10000)
a,b,c,d = map(int,input().split())
if c < b < d:
  print(b-C)
elif a < d < b:
  print(d-a)
elif a < c < b and a< d < b:
  print(d-c)
elif c < a < d and c < b < d:
  print(b-a)
else:
  print(0)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
ans = 0
for i in range(101):
  if a <= i < b and c <= i < d:
    ans += 1
print(ans)
n, m = map(int, input().split())
T = [list(map(int, input().split())) for i in range(m)]

for i in range(10 ** (n - 1), 10 ** n):
    for j in range(m):
        ans = 0
        if (str(i))[(T[j][0] - 1)] != str(T[j][1]):
            ans = -1
            break
    if ans == 0:
        ans = i
        break

print(ans)


### FIXED CODE ###

N, M = map(int,(input().split()))
table = [input().split() for l in range(M)]
ans = 0
array1 = []
array2 = []
array3 = []
keta1 = -1
keta2 = -1
keta3 = -1
s1 = 0
s2 = 0
s3 = 0
for k in range(M):
    for j in range(2):
        table[k][j] = int(table[k][j])

for k in range(M):
    if table[k][0] == 1:
        if (N != 1 and table[k][1] == 0) or (not(table[k][1] in array1) and s1 == 1):
            keta1 = -1
        else:
            keta1 = table[k][1]
        s1 = 1
        array1.append(table[k][1])

    elif table[k][0] == 2:
        if not(table[k][1] in array2) and s2 == 1:
            keta2 = -1
        else:
            keta2 = table[k][1]
        s2 = 1
        array2.append(table[k][1])
    else:
        if not(table[k][1] in array3) and s3 == 1:
            keta3 = -1
        else:
            keta3 = table[k][1]
        s3 = 1
        array3.append(table[k][1])

if s1 != 1:
    keta1 = 1
if s2 != 1 or M == 0:
    keta2 = 0
if s3 != 1 or M == 0:
    keta3 = 0
if N == 1 and M == 0:
    keta1 = 0

if keta1 == -1 or keta2 == -1 or keta3 == -1:
    ans = -1
elif N == 3:
    ans = keta1 * 100 + keta2 * 10 + keta3
elif N == 2:
    ans = keta1 * 10 + keta2
else:
    ans = keta1
    
print(ans)
r1,c1,r2,c2 = map(int,input().split())

mod = 10 ** 9 + 7
MAX = 10**6+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
f = fac[r1+c1]*finv[r1]*finv[c1]
for r in range(r1,r2+1):
    for c in range(c1,c2+1):
       ans += fac[r+c]*finv[r]*finv[c]
       
ans %= mod
print(ans)

### FIXED CODE ###


r1,c1,r2,c2 = map(int,input().split())

mod = 10 ** 9 + 7
MAX = (10**6)*2 + 100
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

ans = 0
for c in range(c1, c2+1):
    ans += ((r2+1)*fac[r1]*fac[c+r2+1]-r1*fac[r2+1]*fac[c+r1])*finv[c]*finv[r1]*finv[r2+1]*inv[c+1]
    ans %= mod
    
print(ans)
import sys
sys.setrecursionlimit(10**5)

mod = 7+10**9

def expo(x,n):
  ans = 1
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def fac(n):
  if not memo_f[n]:
    memo_f[n] = (n*fac(n-1))%mod
  return memo_f[n]

def combi(n,k):
  return (((fac(n)*(expo(fac(k),mod-2)))%mod)*expo(fac(n-k),mod-2))%mod


n,k = map(int,input().split())
memo_f = [1]+[0]*n

if k == 1:
  ans = combi(n-1,k)*combi(n,k)%mod
elif k >= n:
  ans = 0
  for i in range(n):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
else:
  ans = 0
  for i in range(k+1):
    ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

### FIXED CODE ###

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

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

ans = 1
for i in range(1,min(n,k+1)):
    ans += combi(n,i)*combi(n-1,i)%mod
    ans %= mod
print(ans)
a,b = map(int, input().split())
l = []
l.append(a+b)
l.append(a-b)
l.append(a*b)
print(max(a))

### FIXED CODE ###

a, b = map(int, input().split())
num = []
num.append(a+b)
num.append(a-b)
num.append(a*b)
print(max(num))
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num

def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)

    for edge in ki[i]["eda"]:
        if edge[1] != base:
            num *= saiki(edge[1], i, ki)
            num = num % 1000000007
            #print(num)

    return num

total_num = K * P(K-1, len(ki[0]["eda"]))
for edge in ki[0]["eda"]:
    total_num *= saiki(edge[1], 0, ki)
    total_num = total_num % 1000000007
    if total_num == 0:
        break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
import math

def finddigit(n, b):
    dig = (math.floor(math.log(n)/math.log(b))+1)
    print(dig)

finddigit(n,b)


### FIXED CODE ###

import math

def finddigit(n, b):
    dig = (math.floor(math.log(n)/math.log(b))+1)
    print(dig)

n,b = map(int,input().split())
finddigit(n,b)
while(1):
  table = {}
  output = ''
  table_number = int(input())
  if table_number == 0:
    break
  for i in range(table_number):
    a, b = raw_input().split()
    table[a] = b
  string_number = int(input())
  for i in (string_number):
    string = input()
    if string in table:
      output += table[string]
    else:
      output += string
  print output

### FIXED CODE ###

while(1):
  table = {}
  output = ''
  table_number = int(input())
  if table_number == 0:
    break
  for i in xrange(table_number):
    a, b = raw_input().split()
    table[a] = b
  string_number = int(input())
  for i in xrange(string_number):
    string = raw_input()[0]
    if string in table:
      output += table[string]
    else:
      output += string
  print output
import sys
import heapq


input = sys.stdin.readline
n = int(input())
n_list = list(range(1,n))
print(sum(n_list))

### FIXED CODE ###

import sys
import heapq


input = sys.stdin.readline
n = int(input())
result = n*(n-1)//2
print(result)
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

cnt = [0]*(10**5)
cnt2 = [0]*(10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        # print("i: " + str(i))
        # print("nxt: " + str(nxt))
        loop = i - cnt2[nxt]
        modC = max(0, cnt2[nxt])
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop
# print("-------")
# print(t)
# print("modC: " + str(modC))
# print("modK: " + str(modK))
# print("loop: " + str(loop))
# print(modK)
# print(loop)
# print("-------")

if k < modC:
    print(t[k] + 1)
else:
    print(t[modC + modK] + 1)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

cnt = [0]*(2*10**5)#何回出たか
cnt2 = [0]*(2*10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(2*10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        # print("i: " + str(i))
        # print("nxt: " + str(nxt))
        loop = i - cnt2[nxt]
        modC = cnt2[nxt]
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop
# print("-------")
# print(t)
# print("modC: " + str(modC))
# print("modK: " + str(modK))
# print("loop: " + str(loop))
# print(modK)
# print(loop)
# print("-------")

if k < modC:
    print(t[k] + 1)
else:
    print(t[modC + modK] + 1)

"""
発想はあってる
テストケース公開されたら試してみる！
"""
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+5)*(n+5))
def ind(i,j,k): 
    return 4*(n+5)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])
# print(dp)
mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+1)*(n+1))
def ind(i,j,k): 
    return 4*(m+1)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])
# print(dp)
mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)
import heapq

N, k = int(input()), int(input())

h = []
while N > 0:
  heapq.heappush(h, int(input()))
  N -= 1
  
trees = heapq.nlargest(k, h)
if len(trees) <= 1:
  print(0)
else:
  print(trees[-1] - trees[0])

### FIXED CODE ###

import heapq
 
N, k = [int(s) for s in input().split(' ')]
 
h = []
while len(h) != N:
    heapq.heappush(h, int(input()))
  
min_height = 1000000000
h = heapq.nsmallest(N, h)
for start in range(0, N - k + 1):
    end = start + k - 1
    diff = h[end] - h[start]
    if diff < min_height:
        min_height = diff
print(min_height)
c=str(int(input())).count("x")
print("YES" if c<=7 else "NO")

### FIXED CODE ###

c=str(input()).count("x")
print("YES" if c<=7 else "NO")
L,N=map(int,input().split())
l=[]
for i in range(N):
  s=list(input())
  s.sort()
  a=''.join(s)
  l.append(a)
  
l.sort()
print(''.join(l))


### FIXED CODE ###

N,L=map(int,input().split())
l=[]
for i in range(N):
  l.append(input())
  
l.sort()
print(''.join(l))
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			exit(print("No"))
	last = min(last, arr[i])
print("Yes")

### FIXED CODE ###

from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			print("No")
			exit(0)
	last = min(last, arr[i])
print("Yes")
str = input()
S = list(str)

ans = 0
num = 0

for i in range(len(str)):
  if list[i] == "A" or list[i] == "G" or list[i] == "T" or list[i] == "C":
    num = 1
    for j in range(len(str)):
      list[j] == "A" or list[j] == "G" or list[j] == "T" or list[i] == "j":
        num = num + 1
      else :
        break
  if ans < num :
    ans = num
  num = 0
  
print(ans)

### FIXED CODE ###

str = input()
S = list(str)

ans = 0
num = 0

for i in range(len(S)):
  if S[i] == "A" or S[i] == "G" or S[i] == "T" or S[i] == "C":
    num = 1
    for j in range(i+1,len(S)):
      if S[j] == "A" or S[j] == "G" or S[j] == "T" or S[j] == "C":
        num = num + 1
      else :
        break
  if ans < num :
    ans = num
  num = 0
  
print(ans)
a,b,c,d=map(int,input().split())
import math
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=math.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-a//lcm
print((b-a+1)-(cc+dd-cd))


### FIXED CODE ###

a,b,c,d=map(int,input().split())
import fractions as f
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=f.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))
aa, bb, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(m):
  x1, y1, c1 = list(map(int,input().split()))
  x.append(x1)
  y.append(y1)
  c.append(c1)

price = []
  
for i in range(m):
  price.append(a[x[i] - 1] + b[y[i] - 1] - c[i])
  
  
  
print(min(price, min(a) + min(b)))

### FIXED CODE ###

aa, bb, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = []
y = []
c = []
for i in range(m):
  x1, y1, c1 = list(map(int,input().split()))
  x.append(x1)
  y.append(y1)
  c.append(c1)

price = []
  
for i in range(m):
  price.append(a[x[i] - 1] + b[y[i] - 1] - c[i])
  
  
  
print(min(min(price), min(a) + min(b)))
print(input().count('1')

### FIXED CODE ###

print(input().count("1"))
S, T = map(input().split())
a, b = map(input().split())
U = input()

if S==U:
    a-=1
else:
    b-=1

print("{} {}".format(a, b))

### FIXED CODE ###

S, T = input().split()
a, b = input().split()
U = input()

a = int(a)
b = int(b)

if S==U:
  a-=1
if T==U:
  b-=1

print("{} {}".format(a, b))
x1, y1, x2, y2 = map(int, input().split())

a, b = abs(x2 - x1), abs(y1 - y2)

if (x1 <= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 + a
    x4, y4 = x3 - a, y3 - b
elif (x1 > x2)and(y1 < y2):
    x3, y3 = x2 - b, y2 - a
    x4, y4 = x3 + a, y3 - b
elif (x1 > x2)and(y1 > y2):
    x3, y3 = x2 + b, y2 - a
    x4, y4 = x3 + a, y3 + b
elif (x1 < x2)and(y1 > y2):
    x3, y3 = x2 + b, y2 + a
    x4, y4 = x3 - a, y3 + b


print(x3, y3, x4, y4)

### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())

a, b = abs(x2 - x1), abs(y1 - y2)

if (x1 <= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 + a
    x4, y4 = x3 - a, y3 - b
elif (x1 >= x2)and(y1 <= y2):
    x3, y3 = x2 - b, y2 - a
    x4, y4 = x3 + a, y3 - b
elif (x1 >= x2)and(y1 >= y2):
    x3, y3 = x2 + b, y2 - a
    x4, y4 = x3 + a, y3 + b
elif (x1 <= x2)and(y1 >= y2):
    x3, y3 = x2 + b, y2 + a
    x4, y4 = x3 - a, y3 + b

print(x3, y3, x4, y4)
a,b=map(int,input()split())
if a+b=15:
    print('+')
elif a*b=15:
    print('*')
else:
    print('x')

### FIXED CODE ###

a,b=map(int,input().split())
if a+b==15:
    print('+')
elif a*b==15:
    print('*')
else:
    print('x')