Chef has prepared a menu for his new restaurant. The menu consists of N dishes whose flavour is given by M_{1}, M_{2}, \dots, M_{N}, where M_{i} denotes the flavour of the i^{th} dish.

Chef has some rules in his restaurant-
A dish is served only if the customer has already eaten all the dishes preceding it on the menu. 
Each dish will only be served once.

Aman, the richest man in the area, stops by the restaurant one day and inquires about the deliciousness of a dinner that he may have there. Aman has a favourite ingredient p which is a prime number and he wants to eat dishes with the most flavour that contains this ingredient. A dish with flavour M_{i} contains the ingredient p only if p is a divisor of M_{i}.

In order for Aman to patronise Chef's restaurant on a regular basis, he agrees to reorder his menu to fulfil Aman's wishes. He decides that he will reorder the dishes that contain Aman's favourite ingredient while leaving the position of other dishes unchanged. For example, if M = [1, 2, 3, 4, 5, 6] and p = 2 then Chef can reorder his menu into [1, 4, 3, 2, 5, 6] or into [1, 4, 3, 6, 5, 2] but not into [2, 1, 3, 4, 5, 6] since the first dish with flavour 1 does not contain p as p is not a divisor of 1.

Aman wants to know the deliciousness of his meal, which is the total sum of flavours of all dishes if he eats k dishes (first k dishes of the menu) and his favourite ingredient is p. Can you help Chef find the maximum deliciousness after reordering his menu?

You have to answer Q queries and each query will contain the favourite ingredient p and the number of dishes Aman wants to eat k. Each query is independent, i.e. changes made to the menu in one query do not affect the next one.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains one integer N — the number of dishes.
- The next line contains N space-separated integers M_{1}, M_{2}, \ldots, M_{N}- the flavours of the dishes
- The third line contains Q — the number of queries.
- Each of the next Q lines contains two space-separated integers p and k — the favourite ingredient of Aman and the number of dishes he will eat. 

------ Output Format ------ 

For each test case, output Q lines, the i^{th} line containing the answer to the i^{th} query.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1 ≤ M_{i}, p ≤ 10^{5}$
$1 ≤ k ≤ N$
$p$ is a prime number 
- The sum of $N$ and $Q$ over all test cases does not exceed $2 \times 10^{5}$

----- Sample Input 1 ------ 
2
5
1 2 3 4 5
2
2 3
3 4
10
3 4 1 8 9 2 4 10 7 20
5
2 5
3 8
5 6
2 3
7 10
----- Sample Output 1 ------ 
8
10
43
41
27
24
68
----- explanation 1 ------ 
Test case $1$: The menu is $[1, 2, 3, 4, 5]$ and we have $2$ queries.
- The first query has $p = 2$ and $k = 3$. Chef can reorder the menu to $[1, 4, 3, 2, 5]$. Now Aman will eat dishes with flavour $1$, $4$ and $3$. Deliciousness will be $1 + 4 + 3 = 8$
- The second query has $p = 3$ and $k = 4$. Chef cannot reorder the menu and it remains the same. Now Aman will eat dishes with flavour $1$, $2$, $3$ and $4$. Deliciousness will be $1 + 2 + 3 + 4 = 10$

Test case $2$: The menu is $[3, 4, 1, 8, 9, 2, 4, 10, 7, 20]$.
- One optimal arrangement for the first query is $[3, 10, 1, 20, 9, 2, 4, 8, 7, 4]$
- One optimal arrangement for the second query is $[3, 4, 1, 8, 9, 2, 4, 10, 7, 20]$

Difficulty: VERY_HARD
Tags: Sorting

Range queries

Complete search

Number theory

Mathematics
Skill types: Sorting

Range queries

Complete search

Starter code:

Solutions:
import math

def search(k, a):
	lt = 0
	rt = len(a) - 1
	ans = -1
	while lt <= rt:
		mid = lt + (rt - lt) // 2
		if a[mid] > k:
			rt = mid - 1
		if a[mid] <= k:
			lt = mid + 1
			ans = mid
	return ans

def primes(n):
	l = set()
	while n % 2 == 0:
		l.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.add(i)
			n = n / i
	if n > 2:
		l.add(n)
	return l
for _ in range(int(input())):
	n = int(input())
	m = [int(i) for i in input().split()]
	pfs = {}
	for (ix, i) in enumerate(m):
		pf = primes(i)
		for p in pf:
			if p in pfs:
				pfs[p][0].append(i)
				pfs[p][1].append(ix)
			else:
				pfs[p] = [[i], [ix]]
	for pf in pfs:
		ps = pfs[pf][0].copy()
		ps.sort(reverse=True)
		for i in range(1, len(ps)):
			pfs[pf][0][i] = pfs[pf][0][i - 1] + pfs[pf][0][i]
			ps[i] = ps[i] + ps[i - 1]
		pfs[pf].append(ps)
	sm = m.copy()
	for i in range(1, n):
		sm[i] = sm[i] + sm[i - 1]
	q = int(input())
	for _ in range(q):
		(p, k) = [int(i) for i in input().split()]
		if p not in pfs:
			print(sm[k - 1])
		else:
			pt = search(k - 1, pfs[p][1])
			if pt == -1:
				ad = 0
				df = 0
			else:
				ad = pfs[p][2][pt]
				df = pfs[p][0][pt]
			print(sm[k - 1] - df + ad)


import numpy as np
T = int(input())
for t in range(T):
	dishes = int(input())
	menu = list(map(int, input().split(' ')))
	querries = int(input())
	ans_q = [0 for _ in range(querries)]
	Q = np.zeros((querries, 3))
	for q in range(querries):
		(p, k) = map(int, input().split(' '))
		Q[q] = [q, p, k]
	ind = np.lexsort((Q[:, 2], Q[:, 1]))
	prime = -1
	for i in range(querries):
		ele = Q[ind[i], :]
		if int(ele[1]) != prime:
			k = int(ele[2])
			prime = int(ele[1])
			multiple = [m for m in menu if m % prime == 0]
			multiple_s = np.sort(multiple)
			count_flv = 0
			count_extra = 0
			for j in range(k):
				if menu[j] % prime == 0:
					count_extra += 1
				else:
					count_flv += menu[j]
			for c in range(count_extra):
				count_flv += multiple_s[-(1 + c)]
			ans_q[int(ele[0])] = count_flv
		else:
			k_new = int(ele[2])
			extra_new = 0
			for j in range(k, k_new):
				if menu[j] % prime == 0:
					extra_new += 1
				else:
					count_flv += menu[j]
			for c in range(extra_new):
				count_flv += multiple_s[-(1 + count_extra + c)]
			ans_q[int(ele[0])] = count_flv
			count_extra = extra_new + count_extra
			k = k_new
	for a in range(querries):
		print(ans_q[a])


def get_factors(n):
	arr = [[i, []] for i in range(1, n + 1)]
	for j in range(1, len(arr)):
		(k, factors) = arr[j]
		if len(factors) > 0:
			continue
		for z in range(j, len(arr), k):
			arr[z][1].append(k)
	return arr
limit = 100000
factors = get_factors(limit)
t = int(input())
for i in range(t):
	n = int(input())
	values = [int(el) for el in input().split(' ')]
	num_queries = int(input())
	original_queries = []
	for query in range(num_queries):
		(p, k) = [int(el) for el in input().split(' ')]
		original_queries.append((p, k))
	sorted_values = sorted(values)
	primes = {}
	for n in sorted_values:
		ps = factors[n - 1][1]
		for p in ps:
			if p in primes:
				primes[p].append(primes[p][-1] + n)
			else:
				primes[p] = [n]
	zq = enumerate(original_queries)
	queries = [(i, p, k) for (i, (p, k)) in zq]
	queries.sort(key=lambda t: t[2])
	q = 0
	visited_primes = {}
	total = 0
	res = [0] * len(queries)
	for (i, v) in enumerate(values):
		total += v
		fs = factors[v - 1][1]
		for f in fs:
			if f in visited_primes:
				visited_primes[f][0] += 1
				visited_primes[f][1] += v
			else:
				visited_primes[f] = [1, v]
		while q < len(queries) and queries[q][2] == i + 1:
			(original_index, p, k) = queries[q]
			q += 1
			if p not in visited_primes or visited_primes[p][0] == len(primes[p]):
				res[original_index] = total
			else:
				res[original_index] = total - visited_primes[p][1] + primes[p][-1] - primes[p][len(primes[p]) - visited_primes[p][0] - 1]
	for r in res:
		print(r)


def prfx_sum(mn):
	l = [0]
	for m in mn:
		l.append(m + l[-1])
	return l
T = int(input())
for i in range(T):
	input()
	mn = list(map(int, input().split()))
	Q = int(input())
	prefixs = prfx_sum(mn)
	dp = {}
	biggest = {}
	replaced = {}
	for i in range(Q):
		(p, k) = map(int, input().split())
		if p not in dp:
			dp[p] = prfx_sum([m % p == 0 for m in mn])
			mult = [m for m in mn if m % p == 0]
			replaced[p] = prfx_sum(mult)
			biggest[p] = prfx_sum(sorted(mult)[::-1])
		n = dp[p][k]
		res = prefixs[k]
		if n != 0:
			res += biggest[p][n] - replaced[p][n]
		print(res)


def prefix_sum(arr):
	res = [0]
	for i in arr:
		res.append(res[-1] + i)
	return res
for _ in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	q = int(input())
	pre_sum = prefix_sum(arr)
	dp = {}
	biggest = {}
	replaced = {}
	for x in range(q):
		(p, k) = map(int, input().split())
		if p not in dp:
			dp[p] = prefix_sum([i % p == 0 for i in arr])
			multiples = [i for i in arr if i % p == 0]
			replaced[p] = prefix_sum(multiples)
			biggest[p] = prefix_sum(sorted(multiples, reverse=True))
		cur = dp[p][k]
		res = pre_sum[k]
		if cur != 0:
			res += biggest[p][cur] - replaced[p][cur]
		print(res)


def prefix_sum(ms):
	l = [0]
	for m in ms:
		l.append(m + l[-1])
	return l
for _ in range(int(input())):
	input()
	ms = list(map(int, input().split()))
	q = int(input())
	prefixes = prefix_sum(ms)
	memo_n = {}
	memo_prefix = {}
	memo_biggest = {}
	for _ in range(q):
		(p, k) = map(int, input().split())
		if p not in memo_n:
			memo_n[p] = prefix_sum([m % p == 0 for m in ms])
			multiples = [m for m in ms if m % p == 0]
			memo_prefix[p] = prefix_sum(multiples)
			memo_biggest[p] = prefix_sum(sorted(multiples)[::-1])
		n = memo_n[p][k]
		result = prefixes[k]
		if n != 0:
			result += -memo_prefix[p][n] + memo_biggest[p][n]
		print(result)


for T in range(int(input())):
	n = int(input())
	menu = list(map(int, input().split()))
	tmp = {}
	for Q in range(int(input())):
		(p, k) = map(int, input().split())
		L = []
		if p not in tmp:
			for (i, num) in enumerate(menu):
				if num % p == 0:
					L.append(num)
			L.sort()
			sumL = []
			sum = 0
			for i in range(n):
				if menu[i] % p != 0:
					sum += menu[i]
				else:
					sum += L.pop()
				sumL.append(sum)
			tmp[p] = sumL
		print(tmp[p][k - 1])


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	q = int(input())
	has = {}
	for i in range(q):
		(p, k) = map(int, input().split())
		stk = []
		if p not in has:
			for (i, num) in enumerate(m):
				if num % p == 0:
					stk.append(num)
			stk = sorted(stk)
			sumtilj = []
			sum = 0
			for j in range(n):
				if m[j] % p != 0:
					sum += m[j]
				else:
					sum += stk.pop()
				sumtilj.append(sum)
			has[p] = sumtilj
		ans.append(has[p][k - 1])
for an in ans:
	print(an)


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	sorted_m = m[:]
	sorted_m.sort(key=lambda x: -x)
	cached_answers = {}
	q = int(input())
	for _ in range(q):
		(p, k) = map(int, input().split())
		if cached_answers.get(p, None) is None:
			ms = filter(lambda x: x % p == 0, sorted_m)
			s = [0]
			for i in m:
				if i % p == 0:
					s.append(next(ms) + s[len(s) - 1])
				else:
					s.append(i + s[len(s) - 1])
			cached_answers[p] = s
		print(cached_answers[p][k])


from bisect import bisect
for tcase in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	s = [0]
	for mi in m:
		s.append(s[-1] + mi)
	(di, dm, ds, dt) = (dict(), dict(), dict(), dict())
	for qi in range(int(input())):
		(p, k) = map(int, input().split())
		ans = s[k]
		if p not in di:
			di[p] = []
			dm[p] = []
			ds[p] = [0]
			dt[p] = [0]
			for (i, mi) in enumerate(m):
				if mi % p == 0:
					di[p].append(i + 1)
					dm[p].append(mi)
					ds[p].append(ds[p][-1] + mi)
			dm[p].sort(reverse=True)
			for mi in dm[p]:
				dt[p].append(dt[p][-1] + mi)
		i = bisect(di[p], k)
		ans -= ds[p][i]
		ans += dt[p][i]
		print(ans)


import bisect
t = int(input())
for _ in range(t):
	N = int(input())
	M = list(map(int, input().split()))
	Q = int(input())
	h = {}
	for i in range(Q):
		(p, k) = map(int, input().split())
		if p not in h:
			res = 0
			l = []
			for (idd, j) in enumerate(M):
				if j % p == 0:
					l.append(j)
			l.sort(reverse=True)
			z = 0
			ki = []
			for g in range(N):
				if M[g] % p != 0:
					res += M[g]
				else:
					res += l[z]
					z += 1
				ki.append(res)
			h[p] = ki
		print(h[p][k - 1])


import collections
A = 200000
sieve = [0] * (A + 1)
for j in range(2, A + 1, 2):
	sieve[j] = 2
for j in range(3, A + 1, 2):
	if not sieve[j]:
		for k in range(j * j, A + 1, 2 * j):
			sieve[k] = j
		sieve[j] = j
t = int(input())
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	mp = collections.defaultdict(list)
	for x in m:
		(done, c) = (set(), x)
		while x != 1:
			if sieve[x] not in done:
				mp[sieve[x]].append(c)
				done.add(sieve[x])
			x //= sieve[x]
	for (x, y) in mp.items():
		y.sort(reverse=True)
		for j in range(1, len(y)):
			y[j] += y[j - 1]
	qs = [[] for _ in range(n)]
	q = int(input())
	for j in range(q):
		(p, k) = map(int, input().split())
		qs[k - 1].append((j, p))
	(ps, psum, pno) = (0, collections.defaultdict(int), collections.defaultdict(int))
	ans = [0] * q
	for j in range(n):
		x = m[j]
		ps += x
		done = set()
		while x != 1:
			if sieve[x] not in done:
				psum[sieve[x]] += m[j]
				pno[sieve[x]] += 1
				done.add(sieve[x])
			x //= sieve[x]
		for (x, y) in qs[j]:
			if not pno[y]:
				ans[x] = ps
			else:
				ans[x] = ps - psum[y] + mp[y][pno[y] - 1]
	for x in ans:
		print(x)