#P18619. Square Sum

Square Sum

Square Sum

给定整数 mm 和整数序列 z1,z2,…,znz_1,z_2,\ldots,z_n。

对每个 ziz_i,求满足下列条件的有序整数对 (x,y)(x,y) 的数量:

0≤x,y<m,x2+y2≡zi(modm).0\le x,y<m,\qquad x^2+y^2\equiv z_i\pmod m.

输入格式

第一行包含两个整数 m,nm,n,其中 1≤m≤1091\le m\le10^9,1≤n≤1051\le n\le10^5。

第二行包含 nn 个整数 z1,…,znz_1,\ldots,z_n,其中 0≤zi<m0\le z_i<m。

输入只有一组数据。

输出格式

对每个 ziz_i,按输入顺序输出一个整数,表示满足条件的有序对数量。相邻答案用空白分隔即可;可以每行输出一个答案。

输出完整的计数,不对答案取模。

样例输入 1

3 3
0 1 2

样例输出 1

1 4 4

样例输入 2

4 4
0 1 2 3

样例输出 2

4 8 4 0

样例输入 3

5 1
3

样例输出 3

4