题目内容

给定一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ ，和一个整数 $m$ ，你需要回答 $q$ 次询问，每一次询问给定一个 $x$ ，随后，按照下方步骤进行一元二次函数的构造：

1.初始化 $a=0,b=0,c=0$ 。

2.遍历序列 $a_1,a_2,...,a_n$ ，每次遍历将 $a_i$ 累加到 $a、b、c$ 三个值中的其中任意一个值上。

3.保证 $a、b、c$ 都要被至少累加一次。

于是你构造出了一个二次函数 $f(x)=a·x^2+b·x+c$ 。对于每一个询问，请你计算出最大的 $f(x)$ $mod$ $m$ (注意，是取模后的最大值)。

注意，每一次询问构造独立，互不干扰。

输入描述

第一次输入三个整数 $n,m,q(n=3;2≤m≤648;1≤q≤100)$ 。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^6)$ 。

第三行输入 $q$ 个整数 $x_1,x_2,...,x_q(0≤x_i≤10^6)$ 。

输出描述

对于每一个询问，输出一个整数，表示 $f(x)$ $mod$ $m$ 的最大值。

样例1

输入

3 4 2
1 2 5
2 0

输出

3 2