“[Riddle] Delicious Queries solution codechef”

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.

“[Riddle] Delicious Queries solution codechef”

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.

Delicious Queries solution codechef

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

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq M_i, p \leq 10^5
• 1 \leq k \leq N
• p is a prime number
• The sum of N and Q over all test cases does not exceed 2 \times 10^5

Input

“[Riddle] Delicious Queries solution codechef”

Output

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
8
10
43
41
27
24
68

Delicious Queries solution codechef Explanation:

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 14 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 123 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]

Solve more problems at codechef