УМНОЖАВАЙ

Сашка e влюбена във всякакви числови редици. Тя особено харесва любимата си редица $a\_1$, $a\_2$, $\dots$, $a\_N$ от $N$ цели положителни числа. Тъй като Вие току що научихте операцията умножение, Сашка ще Ви изпита на нея чрез редицата си. Тя ще иска да намерите такава редица $b\_1$, $b\_2$, $\dots$, $b\_N$ от $N$ цели положителни числа, така че да минимизирате $\sum\_{i=1}^{N}{a\_i \times b\_i} = a\_1 \times b\_1 + a\_2 \times b\_2 + \cdots + a\_N \times b\_N$. Обаче има уловка – не трябва да има стойност $x$, която да се среща на повече от $K$ места в редицата $b\_1$, $b\_2$, $\dots$, $b\_N$ (т.е. не трябва да има повече от $K$ различни $i$-та, за които $b\_i = x$ и $1 ≤ i ≤ N$). Тъй като би било прекалено скучно да отговорите на един въпрос, Сашка ще Ви зададе $Q$ въпроса, като $i$-тият от тях ще бъде за минималното произведение при $K = k\_i$. Напишете програма prod, която да отговаря на въпросите на Сашка.

На първия ред от стандартния вход са дадени целите положителни числа $N$ и $Q$, съответно равни на броят числа в редицата и на броят въпроси. На втория ред от стандартния вход са дадени $N$ числа $a\_1$, $a\_2$, $\dots$, $a\_N$. На последният ред от стандартния вход са дадени $Q$ числа $k\_1$, $k\_2$, $\dots$, $k\_Q$.

На стандартния изход изведете един ред, съдържащ $Q$ числа, като $i$-тото от тях да е равно на отговора на $i$-тия въпрос.

• $1 ≤ N ≤ 500\\, 000$
• $1 ≤ Q ≤ 750\\, 000$
• $1 ≤ a\_i ≤ 10^6$
• $1 ≤ k\_i ≤ 10^9$

Отговорът за първия въпрос може да се получи чрез $b = \\{1,1,1,2,1,1,1,1\\}$, защото $1 \times 40 + 1 \times 100 + 1 \times 77 + 2 \times 15 + 1 \times 44 + 1 \times 22 + 1 \times 47 + 1 \times 38 = 398$.