题目描述

给定一个素数 $p$ 和 $q$ 个整数 $a_1,a_2,\dots,a_q$，对每个 $a_i$ 求出它在模 $p$ 意义下的乘法逆元 $a_i^{-1}$，即满足

的整数（结果取 $1\sim p-1$ 之间）。

输入格式

第一行两个整数 $p,q$。

第二行 $q$ 个整数。

输出格式

输出 $q$ 行，每行一个整数，表示对应 $a_i$ 的逆元。

输入输出样例 #1

输入 #1

13 3
2 3 12

输出 #1

7
9
12

说明

数据范围

• 对于 $100\%$ 的数据，$1\le q\le 10^5$，$2\le p\le 2^{31}-1$ 且 $p$ 是素数，$1\le a_i<p$。