h2. Cerinta

Pentru un şir de numere $a$, definim _costul_ că fiind suma gcdurilor† tututor prefixelor lui $a$. De exemplu, costul şirului $[12, 6, 9, 2]$ este $gcd(12) + gcd(12, 6) + gcd(12, 6, 9) + gcd(12, 6, 9, 2) = 12 + 6 + 3 + 1 = 22$.

Pentru un şir de numere $a$, definim _costul_ ca fiind suma gcdurilor{$†$} tututor prefixelor lui $a$. De exemplu, costul şirului $[12, 6, 9, 2]$ este $gcd(12) + gcd(12, 6) + gcd(12, 6, 9) + gcd(12, 6, 9, 2) = 12 + 6 + 3 + 1 = 22$.

Definim $f(n,k)$ că fiind suma costurilor tuturor partitiilor lui $n$ în $k$ termeni‡.

Definim $f(n,k)$ ca fiind suma costurilor tuturor partitiilor lui $n$ în $k$ termeni.{$‡$}

Dându-se $n$ şi $m$, si un sir $k{~1~}, k{~2~}, ..., k{~m~}$, voi trebuie să calculaţi $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$

† Prin $gcd(a{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
‡ Prin o partiţie a lui $n$ în $k$ termeni, înţelegem un şir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea că $a{~1~} · a{~2~}· ... · a{~k~}=n$

$†$ Prin $gcd(a{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
$‡$ Prin o partiţie a lui $n$ în $k$ termeni, înţelegem un şir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea că $a{~1~} · a{~2~}· ... · a{~k~}=n$

h2. Date de intrare

Pe prima şi singură linie a fişierului $jupanul.în$ conţine numerele $n$ şi $m$ separate printr-un spaţiu.

Pe prima linie a fişierului $jupanul.în$ conţine numerele $n$ şi $m$ separate printr-un spaţiu. Pe a doua linie, se vor afla $m$ numere $k{~1~}, k{~2~}, ..., k{~m~}$

h2. Date de ieşire

Pe prima şi singură linie a fişierului $jupanul.out$ se vor află $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$ separate prin exact un spaţiu.

Pe prima şi singura linie a fişierului $jupanul.out$ se vor afla $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$ separate prin exact un spaţiu.

h2. Restricţii

h2. Subtaskuri
* $Subtask %{color:#55DDE0; font-weight:bold} Componente Triconexe% - 9 puncte: n ≤ 5 000$

* $Subtask %{color:#33658A; font-weight:bold} Cinci greedyuri fac cat un DP% - 6 puncte: n ≤ 100 000$

* $Subtask %{color:#33658A; font-weight:bold} Emde van Boas% - 6 puncte: n ≤ 100 000$

* $Subtask %{color:#2F4858; font-weight:bold} Legile lui Kirchhoff% - 8 puncte: n ≤ 1 000 000$
* $Subtask %{color:#D4ADCF; font-weight:bold} Metoda Ungureasca% - 7 puncte: m ≤ 5$
* $Subtask %{color:#F6AE2D; font-weight:bold} Aici ar trebui sa intre doar AIB% - 37 puncte: m ≤ 1 500$

* $Subtask %{color:#D62828; font-weight:bold} Intersectie de Meteoriti% - 33 puncte: Fără restricţii suplimentare$

* $Subtask %{color:#D62828; font-weight:bold} Meteoriti% - 33 puncte: Fără restricţii suplimentare$

h2. Exemplu