Power Tower

题号：NC229016
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牧师们想要建造一座塔来代表他们神的力量。塔通常由带电的岩石制成。它是在稀有魔法的帮助下通过悬浮塔的当前顶部并在其底部添加岩石而建造的。如果由 $\ k - 1$ 块岩石建造的顶部具有功率 $\ p$ ，并且我们想要添加带有功率 $\ w_k$ 的岩石，那么新塔的功率值将是 $\ \{w_k\}^p$ 。

岩石从最后一个添加到第一个。即对于序列 $\ w_1, ..., w_m$ 的幂值将是

塔建成后，其威力可能非常大。但是牧师仍然想获得一些关于它的信息，即他们想知道一个称为累积功率的数字，它是取模 $\ m$ 的功率的值。牧师有 $\ n$ 块石头，编号从 $\ 1$ 到 $\ n$ 。他们要求您计算如果他们用编号为 $\ l, l + 1, ..., r$ 的岩石建造这座塔，该塔将具有多少累积功率值。

输入描述:

第一行包含两个整数 和。

第二行包含个整数，这是牧师拥有的岩石的力量。

第三行包含一个整数，这是牧师向您查询的数量。

接下来行的第行包含两个整数和。

输出描述:

输出 个整数。它们中的第 个表示，如果用岩石 建造，塔将具有的累积功率量。

示例1

输入

复制

6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6

输出

复制

说明

备注:

原题链接：https://codeforces.com/problemset/problem/906/D