一条直线上有个点，对于第个点有一个给定的 ，代表可以任选一个点与号点连接，连接的代价是，点可以和自身连接。

定义为号点与任选一个点连接的最小代价。

给出个询问，每次询问给出一个，代表询问的值，然而对于每一个询问都输出一个答案实在是太麻烦了，所以我们只需要输出所有询问的答案之和。

由于这个数字可能很大，你只需要输出它对取模的结果。

表示和的最大公约(因)数。

由于本题输入量较大，请使用以下快读函数代替你的scanf或cin输入


inline void read(int &num)
{
int s = 0 ; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') s = (s<<3) + (s<<1) + ch - '0', ch = getchar();
num = s;
}

第一行两个整数和。

第二行个整数，第个整数代表。

接下来行，代表个询问。

一个整数，代表所有询问答案之和对取模的结果。

3 3
1 1 1
1
2
3

3