Background

伍子胥引荐专诸后，公子光为行刺之命，命专诸前往太湖，请名工铸造一柄短小锋利的宝剑，名曰“鱼肠剑”。剑成之后，需测试其分金段玉之能。

Description

现有n快精铁锭，其硬度分别为 a₁～aₙ。 专诸需依次进行q次试剑，每次试剑指定一个整数x，表示鱼肠剑的斩切力度。每块铁锭的硬度 aᵢ 将变为$\lfloor \frac{a_i}{x} \rfloor$,即硬度被剑力整除后的整数部分。

请你帮助专诸计算，在每次试剑操作结束后，所有铁锭的硬度之和 $$\sum_{i=1}^n a_i$$为多少？

Format

Input

第一行两个整数 n,q($1 \le n \le 10^6, 1 \le q \le 10^6$),整数之间用一个空格隔开。

第二行n个整数 $a_1 \sim a_n(1 \le a_i \le 2000)$,整数之间用一个空格隔开。

接下来q行，每行一个整数 x($1 \le x \le 10$),表示一次操作。

Output

输出q行，表示每次操作结束后的答案。

Samples

5 3
6 6 7 9 10
2
1
2

18
18
7

Limitation

1s, 1024KiB for each test case.