Cho dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Một đoạn con không rỗng ~[l,r]~ được gọi là phù hợp với giá trị ~x~ nếu

~\min_{l \le i \le r} a_i \cdot \max_{l \le i \le r} a_i \le x~.

Với mỗi truy vấn, hãy đếm số đoạn con phù hợp.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~q~ (~1 \le n \le 10^5~, ~1 \le q \le 20~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ (~1 \le a_i \le 10^9~).

• Mỗi dòng trong ~q~ dòng tiếp theo chứa một số nguyên ~x~ (~1 \le x \le 10^{18}~).

Output

Với mỗi truy vấn, in ra trên một dòng số đoạn con phù hợp.

Scoring

Sample Input 1

4 3
1 3 2 4
3
8
16

Sample Output 1

3
8
10

Notes

Với ~x=3~, ba đoạn phù hợp là ~[1,1]~, ~[1,2]~ và ~[1,3]~.

Với ~x=16~, cả ~10~ đoạn con không rỗng đều phù hợp.