Subsequence Sum Query

You are given a sequence of integers. For each query, you need to compute the sum (modulo \(p\)) of all distinct sums generated by the subsequences of a subarray defined by the interval \([l,r]\). Here, a subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements (the empty subsequence is also considered).

More formally, for an interval \([l,r]\), let \(S\) be the set of all sums of subsequences of \(a_l,a_{l+1},\ldots,a_r\). Your task is to output \(\left(\sum_{x\in S} x\right) \bmod p\).

inputFormat

The first line contains three integers \(n\), \(q\), and \(p\) \((1\le n,q\le 20,\ 1\le p\le 10^9)\), representing the number of elements in the sequence, the number of queries, and the modulo value, respectively.

The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\) that make up the sequence.

Each of the following \(q\) lines contains two integers \(l\) and \(r\) \((1\le l\le r\le n)\) representing a query interval.

outputFormat

For each query, output one line containing the result: the sum of all distinct subsequence sums modulo \(p\).

sample

3 2 100
1 2 3
1 2
2 3

6
10