题目背景

这里本来应该有一个绝妙的题目背景，可惜位置太小写不下了。

题目描述

给定一个数轴，你初始时位于原点。

每一单位时间内，你将分别以 $\frac{1}{4}, \frac{1}{2}, \frac{1}{4}$ 的概率向左移动一个单位长度、不动、向右移动一个单位长度。

有 $T$ 次询问，每次询问给定 $n$，求 $n$ 个单位时间后后位移大小（即所在位置坐标的绝对值）的期望对 $p$ 取模的结果。

实现细节

请在提交源代码前添加 #include "pilgrimage.h"。

你需要实现以下函数：

void init (int o, int p);

• $o$：表示该测试点所属的子任务编号，特别地，对于样例有 $o = 0$。
• $p$：表示该测试点的模数。

该函数在每个测试点内只会被调用一次，早于任何一次 ask 调用。

int ask (long long n);

• $n$：表示一次询问的时间长度。
• 该函数需要返回一个 $[0, p)$ 范围内的整数表示答案。

评测程序示例

评测程序示例按照以下格式读入输入数据：

• 第 $1$ 行：$o ~ T ~ p$，其中 $o$ 表示该测试点所属的子任务编号。
• 第 $2 + i$（$0 \le i < T$）行：$n[i]$。

评测程序示例首先调用 init，然后按照 $i = 0, 1, \dots, T - 1$ 的顺序调用 ask：$n = n[i]$。

评测程序示例按照以下格式输出：

第 $1 + i$（$0 \le i < T$）行：一个 $[0, p)$ 范围内的整数，表示第 $i$ 次调用 ask 返回的结果。

样例

样例输入

0 9 999983
1
2
3
4
5
12
2999
999999
1000000000000000000

样例输出

499992
749988
937485
593741
292965
279604
703253
798000
771553

样例解释

以 $n = 2$ 为例，有以下 $9$ 种情况：

• 第一个单位时间内向左，第二个单位时间内向左，最终位于 $-2$，概率为 $\frac{1}{16}$。
• 第一个单位时间内向左，第二个单位时间内不动，最终位于 $-1$，概率为 $\frac{1}{8}$。
• 第一个单位时间内向左，第二个单位时间内向右，最终位于 $0$，概率为 $\frac{1}{16}$。
• 第一个单位时间内不动，第二个单位时间内向左，最终位于 $-1$，概率为 $\frac{1}{8}$。
• 第一个单位时间内不动，第二个单位时间内不动，最终位于 $0$，概率为 $\frac{1}{4}$。
• 第一个单位时间内不动，第二个单位时间内向右，最终位于 $1$，概率为 $\frac{1}{8}$。
• 第一个单位时间内向右，第二个单位时间内向左，最终位于 $0$，概率为 $\frac{1}{16}$。
• 第一个单位时间内向右，第二个单位时间内不动，最终位于 $1$，概率为 $\frac{1}{8}$。
• 第一个单位时间内向右，第二个单位时间内向右，最终位于 $2$，概率为 $\frac{1}{16}$。

故期望为 $\lvert -2 \rvert \times \frac{1}{16} + \lvert -1 \rvert \times \frac{1}{8} + \dots + \lvert 2 \rvert \times \frac{1}{16} = \frac{3}{4}$，在模 $999983$ 意义下即为 $749988$。

数据范围

对于所有测试数据，满足 $3 \le p \le 10 ^ 6$，$1 \le T \le 10 ^ 6$，$1 \le n \le 10 ^ {18}$，保证 $p$ 为奇数。

每个子任务的具体限制如下表所示：

• 特殊性质 A：$p$ 是素数。
• 特殊性质 B：$p = p_1 \times p_2 \times \dots \times p_k$，其中 $p_1, p_2, \dots, p_k$ 是两两不同的素数。