题目描述

给定一个序列 $a_{1_1},a_{1_2},a_{1_3},...,a_{1_n}$，要求依次生成完整的序列 $a$，规则如下：

对于 $2 \le i \le n,a_{i_1}=a_{{i-1}_1}$。

对于 $2 \le i,j \le n,a_{i_j}=(a_{i_{j-1}}+a_{{i-1}_j}) \times k$。

现在有 $q$ 次询问，每次给定 $x,y$，求 $a_{x_y}$ 的值。为了避免答案过大，额外给定 $p$，每次输出时对 $p$ 取余。

输入格式

一共 $q+2$ 行。

第一行，三个整数 $n,k,q,p$，用空格隔开。

第二行，一个序列 $a_{1_1},a_{1_2},a_{1_3},...,a_{1_n}$，用空格隔开。

接下来 $q$ 行，每行两个数 $x,y$，用空格隔开。

输出格式

一共 $q$ 行。

对于输入的每一次询问，输出单独的一行，即 $a_{x_y} \operatorname{mod} p$ 的值。

样例 #1

样例输入 #1

5 2 3 114514
6 9 8 1 4
1 5
2 3
4 4

样例输出 #1

316
296
11808

提示

对于 $100\%$ 的数据，$1 \le n,q \le 4 \times 10^5,1 \le k,p,a_{1_i} \le 10^8,1 \le x,y \le n$。