题目描述

广场站着一排人，在观看着挟持小男孩的愤怒司教的演说，一共有 $n$ 个，编号为 $1$ 到 $n$ ，第 $i$ 个人的编号为 $i$ 。
第 $i$ 个人，有一个恐惧程度值为 $ai$ 。如果 $[l,r]$ 的人被愤怒司教使用权能链接，那么对于 $l\leq i\leq j\leq r$ ，便会产生 $(\sum{i=l}^{r}{a_i}) \bmod p$ 那么多的恐惧总值，其中 $p$ 是给定的一个常数。
为了更好的应战愤怒司教，现在有 $q$ 个询问，每个询问给定区间 $[l,r]$ ，请你找出对于任意 $l\leq i\leq j\leq r$ ， $[i,j]$ 产生恐惧总值的最小值。

输入格式

第一行两个正整数表示 $n$，$p$ 。
接下来一行，$n$ 个整数，表示序列 $a$ 。
接下来一行一个正整数表示询问个数 $q$ 。
接下来 $q$ 行，每行两个正整数 $l$，$r$ 表示一次询问。

输出格式

$q$ 行每行一个整数表示答案。

样例

input

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

output

1
0
2

数据范围与提示

• 对于 $100\%$ 的数据， $2 \leq p \leq n $ 。
• 所有 $a_i$ 均在 $[0,p-1]$ 中等概率随机生成。
• 每个测试点有一个对应的常数 $len$ ，对于每组询问，其有 $\frac{3}{4}$ 的概率满足条件 $1$ ，$\frac{1}{4}$ 的概率满足条件 $2$。
  • 条件 $1$ ：被询问区间的区间大小 $\leq len$。
  • 条件 $2$ ：被询问区间的区间大小$\gt len$。
• 被询问区间的区间大小 $x$ 在满足条件情况下等概率随机生成，然后等概率随机生成符合条件的右端点，相减得到左端点。