#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000 + 5;
const int P = 998244353;

int N, M, Q;
int a[MAX_N];
struct Query {
    int l, r, ans;
} q[MAX_N];
int fl[MAX_N][22], fr[MAX_N][22];

void solve(int l, int r, vector<int> &qi) {
    if (l == r || qi.empty()) return;
    int m = l + r >> 1;
    for (int j = 0; j < M; j ++) fl[m + 1][j] = 0;
    for (int j = 0; j < M; j ++) fr[m][j] = 0;
    fl[m + 1][0] = fr[m][0] = 1;
    for (int i = m; i >= l; i --) {
        for (int j = 0, jj = a[i]; j < M; j ++, jj ++, jj = jj < M ? jj : 0) {
            fl[i][jj] = fl[i + 1][jj] + fl[i + 1][j];
        }
    }
    for (int i = m + 1; i <= r; i ++) {
        for (int j = 0, jj = a[i]; j < M; j ++, jj ++, jj = jj < M ? jj : 0) {
            fr[i][jj] = fr[i - 1][jj] + fr[i - 1][j];
        }
    }
    vector<int> ql, qr;
    for (int i: qi) {
        if (q[i].r < m) {
            ql.push_back(i);
        } else if (q[i].l > m + 1) {
            qr.push_back(i);
        } else {
            int *f1 = fl[q[i].l], *f2 = fr[q[i].r], &ans = q[i].ans;
            for (int j = 0; j < M; j ++) {
                ans = (ans + 1ll * f1[j] * f2[j ? M - j : 0]) % P;
            }
        }
    }
    solve(l, m, ql);
    solve(m + 1, r, qr);
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &Q);
    vector<int> qi;
    for (int i = 1; i <= Q; i ++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        qi.push_back(i);
    }
    solve(1, N, qi);
    for (int i = 1; i <= Q; i ++) {
        printf("%d\n", q[i].ans);
    }
    return 0;
}