31209번 - УМНОЖАВАЙ 다국어

Сашка 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$.