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

import sys
sys.setrecursionlimit(200005)

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

to = [[] for i in range(n)]


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

score = [0]*n

for i in range(q):
    p, x = map(int, input().split())
    score[p-1] += x


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(0)

for i in range(len(score)):
	print(score[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

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


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###


N=int(input())
data=[int(input()) for i in range(N)]
mae=N//2+N%2
i=1
count=0

maelist=[]
maeset=set()
usirolist=[]
usiroset=set()
flag=1
lst=set()
nikaime=0
dellst=set()
while flag:
    flag=0
    if lst:
        lst.clear()
    for i in range(len(data)):
        if data[i] in dellst:
            dellst.remove(data[i])
            data[i]=0
            continue
        lst.add(data[i])
        if data[i]+1 in lst or data[i]+1 in maeset:
            flag=2
            count+=1
            if data[i]<=mae:
                maelist.append(data[i])
                maeset.add(data[i])

                data[i]=0


            else:
                usirolist.append(data[i]+1)
                usiroset.add(data[i]+1)
                dellst.add(data[i]+1)

    for i in usirolist:
        if i+1 in set(data):
            dellst.add(i+1)
            usirolist.append(i+1)
            count+=1
            flag=1

    if flag:
        data=[i for i in data if i]
    if not nikaime:
        nikaime=1

maelist.reverse()
print(count)


### FIXED CODE ###

N=int(input())
data=[int(input()) for i in range(N)]
count=0
dic={}
for i in data:

    if i-1 in dic:
        num=dic.pop(i-1)
        dic.update({i:num+1})
    else:
        dic.update({i:1})
print(N-max([dic[i] for i in dic]))
### BUGGY CODE ###

n,p = map(int,input().split())
s = [int(c) for c in input()] 
num = 0
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if s[i]%p == 0:
			ans += i+1	
	print(ans)
	exit()
arr = [0]*p
s = s[::-1]
z = 1
t = 0
for ss in s:
	t = (t + z*ss)%p	
	z *=10 %p
	#print(t)
	arr[t] += 1
arr[0]+=1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

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

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

if K == 1:
    print(0)
else:
    while True:
        preN = N
        N = abs(N - K)
        if N >= preN :
            print(preN)
            break

### FIXED CODE ###

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

amari = N % K
absplus = abs(amari - K)


if N <= (K // 2):
    print(N)
elif amari >= absplus:
    print(absplus)
else:
    print(amari)
### BUGGY CODE ###

n = int(input())
numbers = list(map(int, input().split(' ')))

counters = {}
cevap_list = {}
sayilar = set(numbers)
for i in sayilar:
    count = numbers.count(i)
    counters[i] = count

for i in sayilar:
    sonuc = 0
    for sayi in counters:
        count = counters[sayi]
        if i == sayi:
            count -= 1
        sonuc += count * (count - 1) / 2
    cevap_list[i] = int(sonuc)

for i in range(n):
    print(cevap_list[numbers[i]])

### FIXED CODE ###

n = int(input())
numbers = list(map(int, input().split(' ')))

counters = {}
cevap_list = {}
sayilar = set(numbers)
for i in numbers:
    if i in counters:
        counters[i] += 1
    else:
        counters[i] = 1

sonuc = 0
for sayi in counters:
    count = counters[sayi]
    sonuc += int(count * (count - 1) / 2)


for i in range(n):
    print(sonuc-counters[numbers[i]]+1)
### BUGGY CODE ###

def find(i, m):
    if m[i] < 0:
        return i
    return find(m[i], m)


def count(i, m):
    if m[i] < 0:
        return abs(m[i])
    return count(m[i], m)


def union(i, j, m):
    pi, pj = find(i, m), find(j, m)
    if pi != pj:
        m[pj] += m[pi]
        m[pi] = pj

    return m


def main():
    import sys
    sys.setrecursionlimit(200000)
    n, m, *ab = map(int, open(0).read().split())
    ab = ab[::-1]
    tmp = n * (n - 1) // 2
    utl = []
    par = [-1] * (n + 1)
    for u, v in zip(ab[::2], ab[1::2]):
        if find(u, par) == find(v, par):
            utl.append(tmp)
        else:
            i, j = count(u, par), count(v, par)
            utl.append(tmp)
            tmp -= i * j
            par = union(u, v, par)

    ans = '\n'.join(map(str, utl[::-1]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def find(i, m):
    if m[i] < 0:
        return i
    return find(m[i], m)


def count(i, m):
    if m[i] < 0:
        return abs(m[i])
    return count(m[i], m)


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = ab[::-1]
    tmp = n * (n - 1) // 2
    utl = []
    par = [-1] * (n + 1)

    for u, v in zip(ab[::2], ab[1::2]):
        if find(u, par) == find(v, par):
            utl.append(tmp)
        else:
            i, j = find(u, par), find(v, par)
            utl.append(tmp)
            tmp -= par[i] * par[j]
            if par[i] > par[j]:
                i, j = j, i
            par[i] += par[j]
            par[j] = i

    ans = '\n'.join(map(str, utl[::-1]))
    print(ans)


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

def getlist():
	return list(map(int, input().split()))

X = []
N = int(input())
for i in range(N):
	A = getlist()
	A.reverse()
	X.append([0] + A)

day = 0
while True:
	j = "No"
	check = [0] * N
	for i in range(N):
		x = X[i][-1] - 1
		if x != -1:
			if check[i] == 0 and check[x] == 0 and X[x][-1] == i + 1:
				check[i], check[x] = 1, 1
				X[x].pop(-1)
				X[i].pop(-1)
				j = "Yes"
	day += 1
	if j == "No":
		break

cc = "Yes"
for i in range(N):
	if X[i] != [0]:
		cc = "No"
		break

if cc == "No":
	print(-1)
else:
	print(day - 1)

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#入力
	N = int(input())
	outE = defaultdict(list)
	inE = defaultdict(int)
	for i in range(N):
		A = getlist()
		for j in range(N - 2):
			a, b = sorted([A[j] - 1, i])
			c, d = sorted([A[j + 1] - 1, i])
			outE[a * N + b].append(c * N + d)
			inE[c * N + d] += 1

	#キュー初期化
	Q = []
	for i in range(N):
		for j in range(i + 1, N):
			if inE[i * N + j] == 0:
				Q.append(i * N + j)
	#print(Q)
	#計算
	judge = "Yes"
	cnt = 0
	ans = 1
	while True:
		q = []
		for i in Q:
			for j in outE[i]:
				inE[j] -= 1
				cnt += 1
				if inE[j] == 0:
					q.append(j)

		if q == []:
			break
		else:
			Q = q
		ans += 1
	# print(ans)
	# print(cnt)

	if cnt != N * (N - 2):
		print(-1)
	else:
		print(ans)

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

A, B, Q = map(int, input().split())
s = [-10**10] + [int(input()) for _ in range(A)] + [2*10**10, 2*10**10 + 1]
t = [-10**10] + [int(input()) for _ in range(B)] + [2*10**10, 2*10**10 + 1]
x = [int(input()) for _ in range(Q)]


def searchindex(p, z):
    for i, d in enumerate(p):
        if d > z:
            return i - 1


def func(c, d, z):
    i = searchindex(c, z)
    j1 = searchindex(d, c[i])
    j2 = searchindex(d, c[i + 1])
    return min(z - d[j1], z - c[i] * 2 + d[j1 + 1], d[j2 + 1] - z, c[i + 1] * 2 - z - d[j2])


for z in x:
    print(min(func(s, t, z), func(t, s, z)))


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
s = [-10**10 - 1, -10**10] + [int(input()) for _ in range(A)] + [2*10**10]
t = [-10**10 - 1, -10**10] + [int(input()) for _ in range(B)] + [2*10**10]
x = [int(input()) for _ in range(Q)]


def func(c, d, z):
    i = bisect.bisect_left(c, z)
    j1 = bisect.bisect_left(d, c[i - 1])
    j2 = bisect.bisect_left(d, c[i])
    return min(z - d[j1 - 1], z - c[i - 1] * 2 + d[j1], d[j2] - z, c[i] * 2 - z - d[j2 - 1])


for z in x:
    print(min(func(s, t, z), func(t, s, z)))
### BUGGY CODE ###

import numpy as np
n, x = map(int, input().split())
ans = 1
def check(n, li):
    for i in li:
        if i != 0:
            if abs(i) % n != 0:
                return False
    return True
li = list(map(int, input().split()))
li.append(x)
li = list(set(li))
li.sort()
start_index = li.index(x)
li = np.array(li)
if start_index == len(li)-1:
    n = li[start_index] - li[start_index - 1]
    for i in reversed(range(1, n+1)):
        if check(i, li-x) and i > ans:
            ans = i
            break
        
elif start_index == 0:
    n = li[start_index+1] - li[start_index]
    for i in reversed(range(1, n+1)):
        if check(i, li-x) and i > ans:
            ans = i
            break
else:
    n = li[start_index] - li[start_index - 1]
    for i in reversed(range(1, n+1)):
        if check(i, li-x) and i > ans:
            ans = i
            break
    n = li[start_index+1] - li[start_index]

    for i in reversed(range(1, n+1)):
        if check(i, li-x) and i > ans:
            ans = i
            break
        if ans > i:
            break

print(ans)


### FIXED CODE ###

import numpy as np
n, x = map(int, input().split())
ans = 1
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
def check(n, li):
    for i in li:
        if i != 0:
            if abs(i) % n != 0:
                return False
    return True
li = list(map(int, input().split()))
li.append(x)
li = list(set(li))
li.sort()
start_index = li.index(x)
li = np.array(li)
if start_index == len(li)-1:
    n = li[start_index] - li[start_index - 1]
    n_div = make_divisors(n)
    for i in n_div[::-1]:
        if check(i, li-x) and i > ans:
            ans = i
            break
        
elif start_index == 0:
    n = li[start_index+1] - li[start_index]
    n_div = make_divisors(n)
    for i in n_div[::-1]:
        if check(i, li-x) and i > ans:
            ans = i
            break
else:
    n = li[start_index] - li[start_index - 1]
    n_div = make_divisors(n)
    for i in n_div[::-1]:
        if check(i, li-x) and i > ans:
            ans = i
            break
    n = li[start_index+1] - li[start_index]
    n_div = make_divisors(n)
    
    for i in n_div[::-1]:
        if check(i, li-x) and i > ans:
            ans = i
        if ans > i:
            break

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

import collections

N = int(input())

A = [x for x in input().split()]

c = collections.Counter(A)

ans = 0
for i in range(N):
  for k,v in c.items():      
    if v > 1 and k != A[i]:
      ans += (v*(v-1))//2
    elif v > 1 and k == A[i]:
      ans += ((v-1)*(v-2))//2
    else:
      continue
  print(ans, sep="\n");ans=0

### FIXED CODE ###

import collections

N = int(input())

A = [x for x in input().split()]

c = collections.Counter(A)

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

for i in range(N):
  z = c[A[i]] - 1   
  print(ans-z, sep="\n")
### BUGGY CODE ###

import collections
s = input()
n = len(s)
mod = [0]*(n+1)
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow(10,i))%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

import collections
s = list(input())
n = len(s)
mod = [0]*(n+1)
pow10 = 1
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow10)%2019
    pow10 = pow10*10%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

s=input()
K=int(input())
ans=''
for c in s:
    if c!='a' and ord('z')+1-ord(c)<=K:
        ans+='a'
        K-=ord('z')+1-ord(c)
    else:
        ans+=c
if K>0:
    ans=ans[:-1]+chr(ord(ans[-1])+K%26)

print(ans)

### FIXED CODE ###

s=input()
K=int(input())
ans=''
for c in s:
    if c!='a' and ord('z')+1-ord(c)<=K:
        ans+='a'
        K-=ord('z')+1-ord(c)
    else:
        ans+=c
if K>0:
    ans=ans[:-1]+chr(ord(ans[-1])+K%26)

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

import sys
sys.setrecursionlimit(10 ** 6)
n,q = map(int,input().split())
g = [[] for _ in range(n)]
p = [0]*n
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
for _ in range(q):
    a,b = map(int,input().split())
    a -= 1
    p[a] += b

def dfs(now, prev=-1):
    for nx in g[now]:
        if nx==prev:
            continue
        p[nx] += p[now]
        dfs(nx, now)
dfs(0)
print(*p)

### FIXED CODE ###

from collections import deque
def main():
    n,q = map(int,input().split())
    values = [0]*n
    links = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = map(int,input().split())
        links[a-1].append(b-1)
        links[b-1].append(a-1)
    
    for _ in range(q):
        p,x = map(int,input().split())
        values[p-1] += x
    d = deque()
    d.append((0,-1))
    
    while len(d) != 0:
        i,p = d.popleft()
        for j in links[i]:
            if j==p:
                continue
            values[j] += values[i]
            d.append((j,i))
    print(*values)
    
main()
### BUGGY CODE ###

L, R = map(int, input().split())
a = []
b = []
for i in range(L,R):
    for j in range(i+1, R+1):
        a.append((i*j)%2019)
    b.append(min(a))
print(min(b))

### FIXED CODE ###

l, r = map(int, input().split())
m = []
if r-l >= 2018:
  print(0)
else:
  L = l%2019
  R = r%2019
  if L == 0 or R == 0:
    print(0)
  elif L>R:
    print(0)
  else:
    for i in range(L, R+1):
      for j in range(i+1, R+1):
        m.append(i*j%2019)
    print(min(m))
### BUGGY CODE ###

n =int(input())
s = [input() for i in range(n)]
z = list(set(s))
ans = []
x = 0
for i in z:
    if s.count(i) > x:
        ans.clear()
        ans.append(i)
        x = s.count(i)
    elif s.count(i) == x:
        ans.append(i)
ans.sort()
print("\n".join(ans))

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())
s.sort()
k = 0
f = s
mk = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    k = k+1
    if k == mk :
      mk = k
      f.append(s[i])
    elif k > mk :
      mk = k
      f = [s[i]]
  else:
    k = 0
for i in range(len(f)):
  print(f[i])
### BUGGY CODE ###

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append([x,y,x+y])

a.sort(key=lambda x: x[2])

for i in a:
    c = b.copy()
    if len(b) > 0:
        if i[0]-i[1] <= max(b):
            b.extend(list(range(i[0]-i[1], i[0]+i[1])))
            b2 = b.copy()
            b = list(set(b))
            if len(b2) != len(b):
                b = c.copy()
                count += 1
        else:
            b = []
            b.extend(list(range(i[0]-i[1], i[0]+i[1])))
    else:
        b.extend(list(range(i[0]-i[1], i[0]+i[1])))
        
    
print(n - count)

### FIXED CODE ###

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0
max = 0

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append([x,y,x+y])

a.sort(key=lambda x: x[2])

for i in a:
    if max != 0 and i[0]-i[1] < max:
        count += 1
    else:
        max = i[2]
    
print(n - count)
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())

index = 0
dxys = [(1, 0), (0, -1), (-1, 0), (0, 1)]

ss = set([(0, 0, 0)])
ns = set()
while len(s) > 0:
    c = s[0]
    p = 0
    if c == 'F':
        while len(s) and s[0] == 'F':
            p += 1
            s = s[1:]
    elif c == 'T':
        s = s[1:]
    for e in ss:
        if len(s) + p < abs(e[0] - x) + abs(e[1] - y):
            continue
        if c == 'T':
            ns.add((e[0], e[1], (e[2]+1)%4))
            ns.add((e[0], e[1], (e[2]-1+4)%4))
        elif c == 'F':
            nx, ny = e[0] + p*dxys[e[2]][0], e[1] + p*dxys[e[2]][1]
            ns.add((nx, ny, e[2]))
    ss = ns
    ns = set()

yes = False
for i in range(4):
    if (x, y, i) in ss:
        yes = True
        break
if yes:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
hL = len(s)
L = 2 * hL

dp = [[False] * (L + 1) for i in range(2)]
ndp = [False] * (L + 1)

def next(i):
    global s
    while i < hL and s[i] != 'T':
        i += 1
    i += 1
    return i

def c(x):
    global hL
    return x + hL

index = 0
t = 0
js = [1]
dp[0][c(0)] = True
dp[1][c(0)] = True
mini, maxi = 0, 1
while index < hL:
    ni = next(index)
    dx, index = ni - index - 1, ni
    for i in range(mini, maxi):
        for j in js:
            if -hL <= i + j * dx <= hL:
                nx = c(i + j * dx)
                ndp[nx] = ndp[nx] or dp[t][c(i)]
    for i in range(mini, maxi):
        dp[t][c(i)] = False
    dp[t], ndp = ndp, dp[t]
    mini, maxi = mini - dx, maxi + dx
    js = [-1, 1]
    t = (t + 1) % 2
print('Yes' if dp[0][c(x)] and dp[1][c(y)] else 'No')
### BUGGY CODE ###

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

ans = [0] * N

for i in range(N):
    num = A.index(i+1) + 1
    ans[i] = str(num) + " "

s = "".join(ans)

print(s)

### FIXED CODE ###

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

ans = [0] * N

for i in range(N):
    num = A[i]
    ans[num-1] = i + 1

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

n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    dp[i] = float("inf")
    for j in range(1,k+1):
        if i-j >=0:
            val = (abs(arr[i]-arr[i-j]) + dp[i-j]) 
            dp[i] = min(dp[i],val)
print(dp[n-1])


### FIXED CODE ###

n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [float("inf")] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j < n:
            dp[j] = min(dp[j],abs(arr[i]-arr[j]) + dp[i])
print(dp[n-1])
### BUGGY CODE ###

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

def main():
    n, m = map(int, input().split())
    L = [[0] for _ in range(n)]
    for _ in [0] * m:
        a, b = map(int, input().split())
        L[a-1].append(b-1)
        L[b-1].append(a-1)
    L[0][0] = 1
    ans = [0] * n
    dq = deque([0])
    while len(dq) > 0:
        t = dq.popleft()
        for i in range(1, len(L[t])):
            if ans[L[t][i]] == 0:
                ans[L[t][i]] = t + 1
            if L[L[t][i]][0] == 0:
                dq.append(L[t][i])
        else:
            L[t][0] = 1
    print('Yes')
    print(*ans[1:], sep='\n')

main()


### FIXED CODE ###

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

def main():
    n, m = map(int, input().split())
    L = [[0] for _ in range(n)]
    for _ in [0] * m:
        a, b = map(int, input().split())
        L[a-1].append(b-1)
        L[b-1].append(a-1)
    L[0][0] = 1
    ans = [0] * n
    dq = deque([0])
    while dq:
        t = dq.popleft()
        for i in range(1, len(L[t])):
            next = L[t][i]
            if ans[next] != 0:
                continue
            ans[next] = t + 1
            dq.append(next)
        else:
            L[t][0] = 1
    print('Yes')
    print(*ans[1:], sep='\n')

main()
### BUGGY CODE ###

#import numpy as np
from sys import stdin,stdout

input = stdin.readline
print = stdout.write

vi = [0]
wi = [0]

n,W=map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    vi.append(b)
    wi.append(a)
#print(str(vi),'\n',str(wi))
    #dp = np.zeros((n+1,MW+1),dtype=np.int64)
dp = [[0]*(W+1) for i in range(n+1)]
    
for j in range(1,n+1):
    for k in range(1,W+1):
        if(wi[j]>k) :
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = max(dp[j-1][k],dp[j-1][k-wi[j]]+vi[j])

print(str(dp[n][W]))
    
        
    





### FIXED CODE ###

def KnapSack(val, wt, n, W): 
      
    # matrix to store final result  
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    # iterate through all items  
    i = 0
    while i < n: # one by one traverse  
                 # each element  
        j = 0 # traverse all weights j <= W 
          
        # if i is odd that mean till  
        # now we have odd number of  
        # elements so we store result   
        # in 1th indexed row  
        if i % 2 == 0: 
            while j < W: # check for each value  
                j += 1
                if wt[i] <= j: # include element  
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: # exclude element 
                    mat[1][j] = mat[0][j] 
                      
        # if i is even that mean till  
        # now we have even number  
        # of elements so we store  
        # result in 0th indexed row  
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    # Return mat[0][W] if n is  
    # odd, else mat[1][W]  
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  
# Driver code
n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W))
### BUGGY CODE ###

S = input()

def recur(s,c):
  if len(set(s)) == 1:
    return c
  else:
    ret = []
    roll = 2 ** (len(s) - 2)
    for i in range(roll):
      sen = ""
      for j in range(len(s) - 1):
        if ((i >> j) & 1):
          sen += s[j + 1]
        else:
          sen += s[j]
      ret.append(recur(sen,c + 1))
    return min(ret)
      
print(recur(S,0))

### FIXED CODE ###

S = input()
type = sorted(set(S))
count = [0] * len(type)

for i,t in enumerate(type):
  sen = S
  con = 0
  while True:
    tmp = ""
    if len(set(sen)) == 1:
      count[i] = con
      break
    for j in range(len(sen) - 1):
      if (sen[j] == t) or (sen[j + 1] == t):
        tmp += t
      else:
        tmp += sen[j]
    con += 1
    sen = tmp

print(min(count))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
keys=[i+1 for i in range(N)]
dic=dict(zip(keys,L))
OK=[(x,y,z) for x in dic.values() for y in dic.values() for z in dic.values() if(x<y+z and y<x+z and z<x+y and [k for k, v in dic.items() if v ==x][0]!=[k for k, v in dic.items() if v ==y][0] and [k for k, v in dic.items() if v ==y][0]!=[k for k, v in dic.items() if v ==z][0] and [k for k, v in dic.items() if v ==x][0]!=[k for k, v in dic.items() if v ==z][0])]
print(len(OK)//6)

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(N-2):
  for j in range(N-i-2):        
    ans+=min(N-i-j-2,N-bisect.bisect_left(L,L[-j-1]-L[i]+1)-j-1)
print(ans)
### BUGGY CODE ###

N=int(input())
a=[int(e) for e in input().split()]
flg=0
for i in range(N-1):
    if(flg==0):
        for j in range(i+1,N):
            if(flg==0):
                if a[i]==a[j]:
                    flg=1
                    print("NO")

if(flg==0):
    print("YES")

### FIXED CODE ###

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

a.sort()
flg=0
if(a[0]==a[1]):
    flg=1
for i in range(1,N-1):
    if(a[i]==a[i-1]):
        flg=1
if flg==1:
    print("NO")
else:
    print("YES")