Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + V_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
a.b =map(int,input().split())
print("Odd" if (a*b)%2!=0 else "Even")

### FIXED CODE ###

a,b =map(int,input().split())
print("Odd" if (a*b)%2!=0 else "Even")
r=input()
print(3*r**2)

### FIXED CODE ###

r=int(input())
print(3*r**2)
import math
import sys

def prime_calc(n):
    rootN = math.floor(math.sqrt(n))
    prime = [2]
    data = [i + 1 for i in range(2,n,2)]
    while True:
        p = data[0]
        if rootN <= p:
            return len(prime + data)
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(line)        

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

if __name__ == "__main__":
    main()
import numpy as np
N=int(input())
X = list(map(int,input().split()))
X.sort()
a=list()
c=N-1
for i in range(X[0],X[c]):
    b=0
    for j in range(0,N):
        b+=(i-X[j])**2
    a.append(b)
print(min(a))

### FIXED CODE ###

import numpy as np
N=int(input())
X = list(map(int,input().split()))
X.sort()
a=list()
c=N-1
for i in range(X[0],X[c]+1):
    b=0
    for j in range(0,N):
        if i-X[j]>10**5:
            break
        b+=(i-X[j])**2
    a.append(b)
print(min(a))
import collections
def C(n):
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = []
sm = 0
for k,v in c.most_common():
    d[k] = v
    sm += C(v)
for a in A:
    print (sm - d[a] + 1)

### FIXED CODE ###

import collections
def C(n):
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = {}
sm = 0
for k,v in c.most_common():
    d[k] = v
    sm += C(v)
for a in A:
    print (sm - d[a] + 1)
N = input()
a = []
for i in range(len(N)):
    a.append(int(N[i]))

X = [0]*(n-1)
flag = False

for i in range(2**(n-1)):
    if flag:
        break
    S = a[0]
    for j in range(n-1):
        if (i >> j) & 1 == 1:
            X[j] = 1
            S += a[j+1]
        else:
            X[j] = 0
            S -= a[j+1]
    if S == k:
        flag = True
        break
print(a[0], end="")
for i in range(3):
    if X[i] == 1:
        print('+', end='')
    else:
        print('-', end='')
    print(a[i+1], end="")
print('=', end='')
print(k)







### FIXED CODE ###

N = input()
A = []
for i in range(len(N)):
    A.append(int(N[i]))

for i in range(2 ** 3):
    List = []
    for j in range(3):
        if (i >> j) & 1 == 1:
            List.append(1)
        elif (i >> j) & 1 == 0:
            List.append(0)
    ans = A[0]
    for k in range(len(List)):
        if (List[k]):
            ans += A[k+1]
        else :
            ans -= A[k+1]

    if ans == 7:
        break

print(A[0], end="")
for i in range(3):
    if List[i]:
        print("+", end="")
    else:
        print("-", end="")
    print(A[i + 1], end="")
print("=7",end="")
import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi:int = 0
ansi = ans1
print(ansi)
 
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) / ( i - 1 ) *  (n-k - i + 2) / i 
    print(int(ansi % 1000000007))

### FIXED CODE ###

import math
 
stri = input()
ary = stri.split()
n = int(ary[0])
k = int(ary[1])
 
ans1 = 1 * (n-k +1 )
ansi = 0
ansi = int(ans1)
print(ansi)
for i in range(2,k+1):
    ansi = ansi * (k- i + 1) // int( i - 1 ) *  (n-k - i + 2) // int(i) 
    type(ansi)
    print(int(ansi % int(1000000007)))
S = input()
a = 0

if S = 'SUN':
  a = 7
elif S = 'MON':
  a = 6
elif S = 'TUE':
  a = 5
elif S = 'WED':
  a = 4
elif S = 'THU':
  a = 3
elif S = 'FRI':
  a = 2
elif S = 'SAT':
  a = 1

print(a)

### FIXED CODE ###

S = input()
a = 0
 
if S == 'SUN':
  a = 7
elif S == 'MON':
  a = 6
elif S == 'TUE':
  a = 5
elif S == 'WED':
  a = 4
elif S == 'THU':
  a = 3
elif S == 'FRI':
  a = 2
elif S == 'SAT':
  a = 1

print(a)
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod

ans=0
DP=[[0]*n for _ in range(n)]
for i in range(1,n):
  for j in range(1,i+1):
    if j==1:
      DP[i][j]=F[i-1]
    elif j==i:
      DP[i][j]=1
    else:
      DP[i][j]=DP[i-1][j-1]+(i-1)*DP[i-1][j]
    ans=(ans+j*DP[i][j]*(X[i]-X[i-1])*F[n-1]//F[i])%mod
print(ans)

### FIXED CODE ###

import sys
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)


ans=0
DP=[0]*n
DP[0]=1
DP[1]=1
ans=(ans+DP[1]*(X[1]-X[0])*F[n-1]*FI[0])%mod
for i in range(2,n):
  DP[i]=(F[i-1]+DP[i-1]*i)%mod
  ans=(ans+DP[i]*(X[i]-X[i-1])*F[n-1]*FI[i])%mod
print(ans)
import sys

s = list(input())
t = list(input())

for i in range(len(s)):
    tmp = s.pop(len(s)-1)
    s.insert(0, tmp)

    if s == t:
        print('Yes')
        sys.exit(1)

print('No')


### FIXED CODE ###

import sys

s = list(input())
t = list(input())

for i in range(len(s)):    
    if s == t:
        break

    tmp = s.pop(len(s)-1)
    s.insert(0, tmp)

if s == t:
    print("Yes")
else:
    print("No")
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
n,m,s,t = map(int, input().split())
money = np.zeros((n+1,n+1))
snu = np.zeros((n+1,n+1))
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u][v] = money[v][u] = a
    snu[u][v] = snu[v][u] = b
money = dijkstra(csr_matrix(money))
snu = dijkstra(csr_matrix(snu))
for i in range(n):
    ans = 0
    for j in range(i+1,n+1):
        ans = max(ans, (10**15) - (money[s][j] + snu[j][t]))
    print(int(ans))


### FIXED CODE ###

import numpy as np
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

n,m,s,t = map(int, input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    graph[u].append([v,a,b])
    graph[v].append([u,a,b])
money = dijkstra(s,0)
snu = dijkstra(t,1)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = '-' + sr()
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17
line = list(input())
N = len(line)
i = 1
for i in range(N):
    if line[i] == "?":
        if line[i-1] == "P":
            line[i] = "D"
        elif i <= 2 and line[i-2] == "D":
            line[i] = "D"
        else:
            line[i] = "P"
print("".join(line))

### FIXED CODE ###

line = list(input())
N = len(line)
i = 1
for i in range(N):
    if line[i] == "?":
        line[i] = "D"
print("".join(line))
n = int(input())
s = input()

count = 0
for i in range(n-1):
  if int(s[i]) > int(s[i+1]):
    count += 1

print("YES" if count < 3 else "NO")

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
ans=0
p=sorted(s)
for i in range(n):
    if s[i]!=p[i]:
        ans+=1
print("NO" if ans>2 else "YES")
a,b=map(int,input().split())
A=input().split()
n=0
for i in range(b) :
  n+=A[i-1]
if n>a :
  print(-1)
else :
  print(a-n)

### FIXED CODE ###

a,b=map(int,input().split())
A=input().split()
n=0
for i in range(b) :
  n+=int(A[i-1])
if n>a :
  print(-1)
else :
  print(a-n)
input_list=list(input())

#A,B,C,K
a = int(list[3]) - int(list[0])
b = int(list[3]) - int(list[1])- int(list[0])
c = int(list[3]) - int(list[2])- int(list[1])- int(list[0])
if b <= 0:
  calc = list[0]
else:
  calc = list[0] - list[2]


### FIXED CODE ###

input_list=list(input().split(" "))
#2000000000 0 0 2000000000
#A,B,C,K
a = int(input_list[3]) - int(input_list[0])
b = int(input_list[3]) - int(input_list[1])- int(input_list[0])
c = int(input_list[3]) - int(input_list[2])- int(input_list[1])- int(input_list[0])
if a < 0:
    calc = int(input_list[3])
elif b <= 0 and a >=0:
  calc = int(input_list[0])
else:
  calc = int(input_list[0]) - b
print(calc)
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
# -infに設定しないと数字の選択時にミスる
dp = [-inf for _ in range(N+1)]
dp[0] = 0

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if dp[many - num(k)] == dp[many] - 1:
            ans += str(k)
            many -= num(k)
            break
        else:
            pass

print(int(ans))


### FIXED CODE ###

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

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
# -infに設定しないと数字の選択時にミスる
dp = [-inf for _ in range(N+1)]
dp[0] = 0

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if many - num(k) < 0:
            pass
        else:
            if dp[many - num(k)] == dp[many] - 1:
                ans += str(k)
                many -= num(k)
                break
            else:
                pass

print(int(ans))
n, k = map(int, input().split())
A=list(map(int, input().split()))
L=[1]
def f(L):
  L.append(A[l[-1]]) if A[l[-1]] in L
f(L)
print(L[k//len(L)])
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
S = {1}

def f(L, S):
    last = L[-1]-1
    if A[last] not in S:
        L.append(A[last])
        S |= {A[last]}
        return f(L, S)
    else:
        return L
P = f(L, S)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j

if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])
s=input()
x=0;y=0
for i in range(len(s)):
  if s[i]=='C':
    x=i+1
    break
for j in range(len(s)):
  if s[j]=='F':
    y=j+1
if x*y!=0 and x<y:print('Yes')
else:print('No')​

### FIXED CODE ###

s=input()
x=0;y=0
for i in range(len(s)):
  if s[i]=='C':
    x=i+1
    break
for j in range(len(s)):
  if s[j]=='F':
    y=j+1
if x*y!=0 and x<y:print('Yes')
else:print('No')
R = input()
print (R*6.28)

### FIXED CODE ###

R = float(input())
print(R*6.28)
d = {}
for i in range(n):
    if s[i] in d:
        d[s[i]] += 1
    else:
        d[s[i]] = 1
m = d[max(d)]
l=[]
for i in d:
    if d[i] == m:
        l.append(i)
for i in sorted(l):
    print(i)

### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
N=int(input())
A=list(map(int,input().split()))
dif=9999999999999999999
x=-1
ans=0
for i in range(N):
  long=abs(sum(A[i+1:])-sum(A[:i+1]))
  if long<dif:
    dif=long
    x=i+1
pl=max(sum(A[:x]),sum(A[x:]))
mi=min(sum(A[:x]),sum(A[x:]))
while mi<pl:
  mi+=1
  ans+=1
  if mi==pl:
    break
print(ans)


### FIXED CODE ###

X,Y=map(int,input().split())
ans=0
if X==1:
  ans+=300000
if X==2:
  ans+=200000
if X==3:
  ans+=100000
if Y==1:
  ans+=300000
if Y==2:
  ans+=200000
if Y==3:
  ans+=100000
if X==1 and Y==1:
  ans+=400000
print(ans)
A, B = map(int,input().split())
ans = int(A*B)
print(ans)

### FIXED CODE ###

A, B = input().split()
A = int(A)
C, D = B.split('.')
B = 100 * int(C) + int(D)
ans = A * B // 100
print(ans)
A_count = int(input());
A = [int(n) for n in input().split()];
M_count = int(input());
M = [int(n) for n in input().split];

def solve(start, target):
    if target == 0:
        return True;
    elif start >= n:
        return False:
    else:
        return solve(start + 1, target) || solve(start + 1, target - A[start]);

for m in M:
    if solve(0, m):
        print("yes");
    else:
        print("no");


### FIXED CODE ###

A_count = int(input());
A = [int(n) for n in input().split()];
M_count = int(input());
M = [int(n) for n in input().split()];

memo = [[None for i in range(2000)] for j in range(A_count + 1)];

def solve(start, target):
    if memo[start][target] is not None:
        return memo[start][target];
    if target == 0:
        return True;
    elif start >= A_count:
        return False;
    else:
        result = solve(start + 1, target) or solve(start + 1, target - A[start]);
        if result:
            memo[start][target] = True;
            return True;
        else:
            memo[start][target] = False;
            return False;

for m in M:
    if solve(0, m):
        print("yes");
    else:
        print("no");
a, b = map(int, input().split())
x = (a + b) / 2
print(math.ceil(x))

### FIXED CODE ###

a, b = map(int,input().split())
print((a + b + 1) // 2)
H, W, m = map(int, input().split())
hs = [0] * (H+1)
ws = [0] * (W+1)
fs = [[0]*(W+1) for i in range(H+1)]
for i in range(m):
    hi,wi = map(int, input().split())
    hs[hi-1] += 1
    ws[wi-1] += 1
    fs[hi-1][wi-1] += 1


### FIXED CODE ###

H, W, m = map(int, input().split())
hs = [0] * (H+1)
ws = [0] * (W+1)
from collections import defaultdict
d = defaultdict(bool)
N = 10**6
for i in range(m):
    hi,wi = map(int, input().split())
    hi -= 1
    wi -= 1
    hs[hi] += 1
    ws[wi] += 1
    d[hi*10**6+wi] = True

hmx = max(hs)
hset = set()
for i,h in enumerate(hs):
    if h == hmx:
        hset.add(i)
wmx = max(ws)
wset = set()
for j, w in enumerate(ws):
    if w == wmx:
        wset.add(j)

flg = False
ans = 0
cnt = 0
for i in hset:
    for j in wset:
        ans = max(ans, hmx+wmx-d[i*N+j]) 
        if cnt >= m:
            flg = True
            break
        cnt += 1
    if flg:break

print(ans)
import collections

N = int(input())
data = [input() for i in range(N)]

dicdata = collections.Counter(data)

m = max(dicdata.values())

newdata = [k for k, v in dicdata.items() if v == m]

newdata.sort()

[print(i) for i in newdata]


### FIXED CODE ###

import numpy as np

a, b, c = map(int, input().split())

if (a == b or a == c or b == c) and not(a == b == c):
	print("Yes")
else:
	print("No")
from scipy.misc import comb
N=int(input())
A=list(map(int,input().split()))
nset=set([])
ndict={}
for a in A:
  if a in nset:
    ndict[a]+=1
  else:
    nset.add(a)
    ndict[a]=1
#print(nset,ndict)
all=0
for n in nset:
  tmp=ndict[n]
  if tmp>=2:
    all+=comb(tmp,2,exact=True)
all=int(all)
for a in A:
  tmp=ndict[a]
  if tmp==1:
    print(all)
  elif tmp==2:
    print(all-1)
  else:
    print( all-comb(tmp,2,exact=True)+comb(tmp-1,2,exact=True) )


### FIXED CODE ###

from scipy.misc import comb
N=int(input())
A=list(map(int,input().split()))
nset=set([])
ndict={}
for a in A:
  if a in nset:
    ndict[a]+=1
  else:
    nset.add(a)
    ndict[a]=1
#print(nset,ndict)
all=0
for n in nset:
  tmp=ndict[n]
  if tmp>=2:
    all+=comb(tmp,2,exact=True)
all=int(all)
for a in A:
  tmp=ndict[a]
  if tmp==1:
    print(all)
  elif tmp==2:
    print(all-1)
  else:
    print( all-comb(tmp,2,exact=True)+comb(tmp-1,2,exact=True) )
n = input()
c = 0
for i in range 1 to n:
    c += i
print(c)

### FIXED CODE ###

n = int(input())
c = 0
for i in range(1,n+1):
  c += i
print(c)
while True:
	n=int(input())
	if n==0: break
	l=[]
	d={}
	for i in range(n):
		i,p,q=list(map(int,input().split()))
		if a in d:
			d[a]+=b*c
		else:
			d[a]=b*c
			l.append(a)
	if max(d.values())<1000000:
		print("NA")
	else:
		for k in l:
			if d[k]>=1000000:
				print(k)

### FIXED CODE ###

while True:
	n=int(input())
	if n==0: break
	l=[]
	d={}
	for _ in range(n):
		a,b,c=list(map(int,input().split()))
		if a in d:
			d[a]+=b*c
		else:
			d[a]=b*c
			l.append(a)
	if max(d.values())<1000000:
		print("NA")
	else:
		for k in l:
			if d[k]>=1000000:
				print(k)
def main(N=None, K=None):
    if not N:
        N = int(input())
        K = int(input())
    ans = (K-N-2)*(2*K*K-K*(N+2)-N*N-N-6)//6
    ans %= 10**9+7
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 10
    # assert main(200000, 200001) == 1
    # assert main(141421, 35623) == 220280457
    main()


### FIXED CODE ###

def main(N=None, K=None):
    if not N:
        N, K = map(int, input().split())
    ans = (K-N-2)*(2*K*K-K*(N+2)-N*N-N-6)//6
    ans %= 10**9+7
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 10
    # assert main(200000, 200001) == 1
    # assert main(141421, 35623) == 220280457
    main()
A = int(input())
B = int(input())
A*B

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
s_in = input()
s_out = s.replace(",", " ", 2)
print(s_out)

### FIXED CODE ###

s_in = input()
s_out = s_in.replace(",", " ", 2)
print(s_out)
x,b,z = input().split()
a=int(x)
c=int(z)
while b!="?":
    if b=="+":
        print(a+c)
    elif b=="-":
        print(a-c)
    elif b=="*":
        print(a*c)
    elif b=="/":
        print(a/c)
    a,b,c = input().split()

### FIXED CODE ###

x,b,z = input().split()
a=int(x)
c=int(z)
while b!="?":
    if b=="+":
        print(a+c)
    elif b=="-":
        print(int(a)-int(c))
    elif b=="*":
        print(a*c)
    elif b=="/":
        print(int(a/c))
    x,b,z = input().split()
    a=int(x)
    c=int(z)
import math

def C(n, r):
	fact = math.factorial
	return fact(n) // fact(r) // fact(n-r)

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

v_sort = sorted(v, reverse=True)

print(sum(v_sort[:A])/A)

a, b = v_sort.count(v_sort[A-1]), v_sort[:A].count(v_sort[A-1])

if v_sort[0] == v_sort[A-1]:
	print(sum([C(a, r) for r in range(A, min(B, a)+1)]))
else:
	print(C(a, b))


### FIXED CODE ###

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

A, B = map(int, input().split())

output = (A + B)%24

print(output)
A=int(input())
B=int(input())
print(A*B-(A+B-1))

### FIXED CODE ###

A,B=map(int,input().split())
print(A*B-(A+B-1))
S = [int(e) for e in input().split()]

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print("Bad")
else:
    print("Good")

### FIXED CODE ###

S = str(input())

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print("Bad")
else:
    print("Good")
numbers = input()
number = list(number)
sum = 0
if number[0] == 1:
  sum = sum + 1
if number[1] == 1:
  sum = sum + 1
if number[2] == 1:
  sum = sum + 1
print(sum)

### FIXED CODE ###

number = input()
sum = 0

for i in range(3):
  if number[i] == '1':
    sum += 1
print(sum)
a=[int(i) for i in input().split()]
a.sort()
if a=[5, 5, 7]:
 print("YES")
else print("NO"):
 
  

### FIXED CODE ###

a=input().split()
a=[int(i) for i in a]
a.sort()
if a[0]==5 and a[1]==5 and a[2]==7:
	print("YES")
else:
 	print("NO")