#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
const int mod = 998244353;
int n, m, q, l[200002], r[200002];
long long a[200002], ans[200002], dp[200002][21], dp2[200002][21];
void dfs(int L, int R, vector <int> v){
	if (L >= R || v.empty()){
		return;
	}
	int mid = (L + R) >> 1;
	for (int i = L; i <= R; i++){
		for (int j = 0; j < m; j++){
			dp[i][j] = 0;
			dp2[i][j] = 0;
		}
	}
	dp[mid][0] = 1;
	for (int i = mid - 1; i >= L; i--){
		for (int j = 0; j < m; j++){
			dp[i][j] += dp[i + 1][j];
			dp[i][j] %= mod;
			dp[i][(j + a[i]) % m] += dp[i + 1][j];
			dp[i][(j + a[i]) % m] %= mod;
		}
	}
	dp2[mid - 1][0] = 1;
	for (int i = mid; i < R; i++){
		for (int j = 0; j <= m; j++){
			dp2[i][j] += dp2[i - 1][j];
			dp2[i][j] %= mod;
			dp2[i][(j + a[i]) % m] += dp2[i - 1][j];
			dp2[i][(j + a[i]) % m] %= mod;
		}
	}
	vector <int> v1, v2;
	for (auto u : v){
		if (r[u] < mid - 1){
			v1.push_back(u);
		} else if (l[u] > mid){
			v2.push_back(u);
		} else {
			if (r[u] == mid - 1){
				ans[u] = dp[l[u]][0];
			} else if (l[u] == mid){
				ans[u] = dp2[r[u]][0];
			} else {
				for (int i = 0; i < m; i++){
					ans[u] += dp[l[u]][i] * dp2[r[u]][(m - i) % m] % mod;
					ans[u] %= mod;
				}
			}
		}
	}
	dfs(L, mid, v1);
	dfs(mid, R, v2);
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector <int> v;
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> q;
	for (int i = 0; i < q; i++){
		cin >> l[i] >> r[i];
		v.push_back(i);
	}
	dfs(1, n + 1, v);
	for (int i = 0; i < q; i++){
		cout << ans[i] << "\n";
	}
	return 0;
}