#97jvzi. 高效制冷模块（freeze）

时间限制：2 s       空间限制：512 MiB       标签： 缺题解 

算法难度等级：0       思维难度等级：0       实现难度等级：0

麦哲伦有 $n$ 个无人机，第 $i$ 个无人机有一个正整数参数 $a_i$，其中 $a_i\in[1,\ m]$。

麦哲伦每次会使用 $[l,\ r]$ 范围内的无人机进行高效制冷。她需要手动配置 $b_l,\ b_{l+1},\ \cdots,\ b_r$，使得 $b_i=a_i$，才可以启动高效制冷模块。

但由于无人机实在是太多了，配置的过程很容易出错，因此她改进了配置系统，现在只需要序列 $a_l,\ a_{l+1},\ \cdots,\ a_r$ 和 $b_l,\ b_{l+1},\ \cdots,\ b_r$ 的最长公共子序列的长度恰好为 $r-l$，就可以启动高效制冷模块。

为了保证无人机的正常运行，$b_i$ 也必须是 $[1,\ m]$ 范围中的正整数。

麦哲伦想知道，对于每一次的高效制冷，她有多少种配置序列 $b_l,\ b_{l+1},\ \cdots,\ b_r$ 的方式。两种配置方式 $b,\ c$ 不同，当且仅当存在 $i\in[l,\ r]$，使得 $b_i\neq c_i$。

由于答案太大了，她只想知道答案对 $998244353$ 取模后的结果。

输入格式

从文件 freeze.in 中读入数据。

第一行三个整数 $n,\ m,\ q$，分别表示无人机的个数、参数的范围和高效制冷的次数。

第二行 $n$ 个正整数，表示每个无人机的参数 $a_1,\ a_2,\ \cdots,\ a_n$。

接下来 $q$ 行，每行两个正整数 $l,\ r$，表示一次高效制冷所选的无人机范围。

输出格式

输出到文件 freeze.out 中。

对于每次高效制冷，输出一行一个整数，表示答案。

3 3 3
1 1 1
1 1
1 2
1 3

2
4
6

样例 1 解释

对于第一次高效制冷，$\{2\},\ \{3\}$ 两个序列满足要求。 对于第二次高效制冷，$\{1,2\},\ \{1,3\},\ \{2,1\},\ \{3,1\}$ 四个序列满足要求。 对于第三次高效制冷，$\{1,1,2\},\ \{1,1,3\},\ \{1,2,1\},\ \{1,3,1\},\ \{2,1,1\},\ \{3,1,1\}$ 六个序列满足要求。

10 9 1
1 2 1 3 1 4 5 6 7 8
1 10

789

数据范围

对于 $100\%$ 的数据，满足 $1\leq l\leq r\leq n\leq 5\times 10^5$，$2\leq m\leq 10^9$，$1\leq q\leq 2\times 10^6$。