You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

今年欢笑复明年，不知退役在眼前。

Description

你需要通过给出的 $b,m$ 实现一个 Hash 函数：

int f(char c) { return 'A' <= c && c <= 'Z' ? c - 'A' + 1 : c - 'a' + 1 + 26; }
int Hash(string &s, const int b, const int m)
{
    int res = 0;
    for (int i = 0; i < s.size(); i++)
        res = (1ll * res * b + f(s[i])) % m;
    return res;
}

有 $t$ 个询问，每次给出一个整数 $x$，保证 $1\leq x\leq 20$。你需要找到一个合理的 $\text{int}\to \text{string}$ 的映射 $g(x)$，求出 $\operatorname{Hash}(g(x),b,m)$。

保证 $\text{int}\to \text{string}$ 的映射 $g(x)$ 的 $\text{string}$ 字符集为全体大写拉丁字母和全体小写拉丁字母。

Format

Input

一行，三个整数，$t,b,m$。

接下来 $t$ 行，每行一个整数 $x$。

Output

$t$ 行，每行一个 Hash 值。

Samples

20 53 97
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8
67
89
40
2
3
14
15
6
94
90
43
91
72
16
19
3
0
11
89

Limitation

对于所有测试数据，满足 $t=20$，$1\leq x\leq 20$，$53\leq b\lt 2^{31}$，$1\leq m\lt 2^{31}$。