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

import sys
N=int(sys.stdin.readline())
array=sorted([int(x) for x in sys.stdin.readline().split()])
duplicate={}
#check for duplicates
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
#loop from the list to check which are divisible and mark them as False
for i in range(N):
	if array[i]==False:
		continue
	for j in range(i+1,N):
		if array[j]==False:
			continue
		if array[j]%array[i]==0:
			array[j]=False

#remove all False
array=[x for x in array if x!=False]

#after that if the only remaining are duplicates, mark them as False
for i in range(len(array)):
	if duplicate[array[i]]>1:
		array[i]=False

#remove all False
array=[x for x in array if x!=False]

print(len(array))


### FIXED CODE ###

N=int(input())
lineup=sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
b=max(lineup)+1
sieve=[1]*(b)
counter=0
for i in range(N):
	for j in range(lineup[i]*2,b,lineup[i]):
		sieve[j]=0
	if duplicate[lineup[i]]==1 and sieve[lineup[i]]==1:
		counter+=1
print(counter)
### BUGGY CODE ###

n = int(input())
s = []
t = {}
for i in range(n):
    inp = input()
    if inp in s:
        t[inp] += 1
    else:
        s.append(inp)
        t[inp] = 1

keys = list(t.keys())
values = list(t.values())
ans = []
for j in [i for i,v in enumerate(values) if v == max(values)]:
    ans.append(keys[j])
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
c = Counter(s)
m = 0
for v in c.values():
	m = max(m, v)
ans = []
for k, v in c.items():
	if v == m:
		ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
const = 10**9 + 7

ans = 0

for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        ans += a[i]^a[j]
        ans %= const

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = tuple(map(int,input().split()))
const = 10**9 + 7

ans = 0

zero = [0] * 60
one = [0] * 60

for i in range(60):
    for j in range(n):
        if a[j] >> i & 1:
            one[i] += 1
        else:
            zero[i] += 1

ans = 0

for i in range(60):
    ans += one[i] * zero[i] * 2**i
    ans %= const

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

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = 0
    max_L = 0
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
l = 0
r = n-1
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid-1
    else:
        thresh = a[mid]+m 
        amari = (v-p)*m
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=min(m,thresh-a[i])
        if amari<=0:
            l = mid
        else:
            r=mid-1
print(r+1)

### FIXED CODE ###

from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
l = 0
r = n
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r-1:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid
    else:
        thresh = a[mid]+m 
        amari = (v-p)*m
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=min(m,thresh-a[i])
        if amari<=0:
            l = mid
        else:
            r=mid
print(l+1)
### BUGGY CODE ###

# coding:utf-8
def main():
    import math

    a, b, n = map(int, input().split())
    ans = 0

    for x in range(1, n + 1):
        tmp = math.floor((a * x) / b) - a * (math.floor(x / b))
        ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding:utf-8

import math

a, b, n = map(int, input().split())
x = min(b - 1, n)

ans = math.floor((a * x) / b) - a * (math.floor(x / b))

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

import math
k = int(input())
tot = 0

for l in range(1, k + 1):
    for m in range(1, k + 1):
        for n in range(1, k + 1):
            __ = math.gcd(l, m)
            tot += math.gcd(__, n)
print(tot)  

### FIXED CODE ###

from math import gcd

k = int(input())
tot = 0

for l in range(1, k + 1):
    for m in range(1, k + 1):
        for n in range(1, k + 1):
            tot += gcd(gcd(l, m), n)
print(tot)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1
    tmp1 = []
    tmp2 = []

    flag = 0
    for w in al[u]:
        if seen[w] == 0:
            seen[w] = 1
            bb, ww = bfs(w)
            tmp1.append(ww)
            tmp2.append(bb + ww)
            flag = 1

    if flag == 0:
        return 1, 1

    ans_b = reduce(mul, tmp1) % mod
    ans_w = reduce(mul, tmp2) % mod

    return ans_b, ans_w

p, q = bfs(1)

print((p + q) % mod)






### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1

    b[u] = 1
    w[u] = 1

    for v in al[u]:
        if seen[v] == 0:
            seen[v] = 1
            bfs(v)
            b[u] = (b[u] * w[v]) % mod
            w[u] = (w[u] * ((b[v] + w[v]) % mod)) % mod

bfs(1)

print((b[1] + w[1]) % mod)
### BUGGY CODE ###

n=int(input())
s = [0] * (n+1)

print(0,flush=True)
a = input()
if a=='Vacant':
    exit()
s[0]=a
s[n]=a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m,flush=True)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m


### FIXED CODE ###

n=int(input())
s = [0] * (n+1)

print(0,flush=True)
a = input()
if a=='Vacant':
    exit()
s[0]=a
s[n]=a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m,flush=True)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
### BUGGY CODE ###

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

x=a[0]
for i in range(1,n):
    x=x*a[i]

if x>10**18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

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

x=a[0]

if 0 not in a:
    for i in range (1,n):
        x=x*a[i]
        if x > pow(10,18):
            print(-1)
            exit()           
    print(x)         
else:
    print(0)
### BUGGY CODE ###

import numpy as np

l =int(input())
mass = list(map(int,input().split()))
move =np.zeros(l,np.int)
for i in range(l):
   for j in range(l-i-1):
      if mass[i+j]>=mass[i+j+1]:
         move[i]+=1
      else:
         break

print(max(move))

### FIXED CODE ###


l =int(input())
mass = list(map(int,input().split()))

ans = 0
old_ans = 0
for i in range(l-1):

   if mass[i]>=mass[i+1]:
      ans = ans+1
   else:
      ans =0

   if old_ans < ans:
      old_ans = ans


#   print(i,"no", ans,old_ans)


print(old_ans)
### BUGGY CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
def bfs3(v, n, ans):
    if n == 0:
        ans.append(v)
    else:
        for u in graph[v]:
            bfs3(u, n-1,ans)

visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        ans = []
        bfs3(v, 3, ans)
        con = list(set(ans))
        #print(con)
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
graph = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v+N)
    graph[u+N].append(v+2*N)
    graph[u+2*N].append(v)
S, T = map(int,input().split())
S, T = S-1, T-1
visit = [False for i in range(3 * N)]
length = [0 for i in range(3 * N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while Q:
        v = Q.pop(0)
        for u in graph[v]:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(int(length[T] //3))
else:
    print(-1)
### BUGGY CODE ###


if __name__ == "__main__":
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    dp = [float("inf")]*len(arr)
    curr = 1 
    dp[0] = 0
    dp[1] = abs(arr[1]-arr[0])
    cost = 0
    for i in range(2,len(arr)):
        x = i-1
        c = 0
        while(x>=0 and c<k):
            dp[i]= min(dp[i],dp[x]+abs(arr[i]-arr[x]))
            x -= 1
            c += 1 
    print(dp[-1]) 

### FIXED CODE ###


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

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

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,q = map(int, input().split())
d = list(map(int, input().split()))

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  return ans
  
    

for _ in range(q):
  n,x,m = map(int, input().split())
  print(query(n,x,m))


### FIXED CODE ###

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

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,q = map(int, input().split())
d = list(map(int, input().split()))

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  print(ans)
  
    

for _ in range(q):
  n,x,m = map(int, input().split())
  query(n,x,m)
### BUGGY CODE ###

n, m = map(int, input().split())
vertices = {i: [] for i in range(n)}
for _ in range(m):
    l, r, d = map(int, input().split())
    vertices[l - 1].append((r - 1, d))
    vertices[r - 1].append((l - 1, -d))


def answer():
    x = [None] * n

    while any(i is None for i in x):
        i = x.index(None)
        x[i] = 0
        queue = [i]

        while queue:
            i0 = queue.pop()
            for i1, d in vertices[i0]:
                # print(i0, i1, x[i0], x[i1], d)
                if x[i1] is None:
                    x[i1] = x[i0] + d
                    queue.append(i1)
                elif x[i1] != x[i0] + d:
                    return False

    return True


if answer():
    print('Yes')
else:
    print('No')





### FIXED CODE ###

n, m = map(int, input().split())
vertices = {i: [] for i in range(n)}
for _ in range(m):
    l, r, d = map(int, input().split())
    vertices[l - 1].append((r - 1, d))
    vertices[r - 1].append((l - 1, -d))


def answer():
    x = [None] * n

    for i in range(n):
        if x[i] is not None:
            continue
        x[i] = 0
        queue = [i]

        while queue:
            i0 = queue.pop()
            for i1, d in vertices[i0]:
                # print(i0, i1, x[i0], x[i1], d)
                if x[i1] is None:
                    x[i1] = x[i0] + d
                    queue.append(i1)
                elif x[i1] != x[i0] + d:
                    return False

    return True


if answer():
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 1
TempList = []
xlr = 0
while (l < n - 1):
	while (r < n):
		TempList = ListP[l : r + 1]
		TempList.remove(max(TempList))
		xlr += max(TempList)
		r += 1
	l += 1
	r = l + 1
print(xlr)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

import sys

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

U = 10**18
ret = 1

for x in A:
  ret *= x
  if ret > U:
    ret += 1
    
if ret > U:
  ret = -1

print(ret)

### FIXED CODE ###

import sys

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

U = 10**18
ret = 1

for x in A:
  ret *= x
  if ret > U:
    ret = U+1
    
if ret > U:
  ret = -1

print(ret)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int64)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit(cache = True)
def func(vws_choose, L):
    bits = np.arange(1 << len(vws_choose))
    values = np.zeros_like(bits, np.int64)
    weights = np.zeros_like(bits, np.int64)
    for i in range(len(vws_choose)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vws_choose[i][0]
        weights[indices] += vws_choose[i][1]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2

        func(vws_choose, L)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

N, M = map(int, input().split())
ABC = []
for i in range(M):
    ab = list(map(int,input().split()))
    c = list(map(int, input().split()))
    ab.append(c)
    ABC.append(ab)
    
INF = float('inf')
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    d = 0
    for c in ABC[i][2]:
        d |= (1 << (c-1))
        
    for j in range(2**N):
        dp[j|d] = min(dp[j|d], dp[j]+ABC[i][0])
        
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
ABC = []
for i in range(M):
    ab = list(map(int,input().split()))
    c = list(map(int, input().split()))
    ab.append(c)
    ABC.append(ab)
    
INF = float('inf')
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    d = 0
    for c in ABC[i][2]:
        d |= (1 << (c-1))
        
    for j in range(2**N):
        dp[j|d] = min(dp[j|d], dp[j]+ABC[i][0])
        
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

X = int(input())
a = 1
b = 1
while True:  
  if(a**5 - b**5 == X):
    print(a , b)
    break
  a += 1
  for i in range(X):
    b += 1
    if(a**5 - b**5 == X):
      print(a , b)
      exit()
while True:
  if(a**5 - b**5 == X):
    print(a , b)
    break
  b -= 1
  for j in range(X):
    b -= 1
    if(a**5 - b**5 == X):
      print(a , b)
      exit()

### FIXED CODE ###

X = int(input())
 
for a in range(-119 , 120 , 1):
  A = a**5
  for b in range(-119 , 120 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue