No testdata at current.

Background

$moo\;moo\;moo$ ......

Description

本题共 $T$ 次询问。

$\,\color{blue}moo\,$有2个长度为 $N$ 的数列 $a$, $b$ 。

首先$\,\color{blue}moo\,$会给 $a$ 赋初始值，接着会对这2个数组进行 $K$ 次操作。具体为：

1. $b_i = \left( \sum_{j=1}^i a_j \right)\bmod P$
2. $a=b$

请你计算出经过 $K$ 次操作后 $a$ 的第 $x$ 项。

Format

Input

$N\;K\;P\;T$

$a_1\;a_2\;a_3\;...\;a_N$

$x_1\;x_2\;x_3\;...\;x_T$

Output

$a_{x_1}\;a_{x_2}\;a_{x_3}\;...\;a_{x_T}$

Samples

5 1 11 1
1 2 3 4 5
5

4

Limitation

$1 \le N \le 10^5$

$0 \le K \le 10^3$

$2 \le P \le 10^9$

$\lvert a_i \rvert \le 10^9$