#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "settings/debug.cpp" #define _GLIBCXX_DEBUG #else #define Debug(...) void(0) #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); ++i) #include<atcoder/modint> using mint = atcoder::modint998244353; int main() { int n, m, q; cin >> n >> m >> q; vector<int> a(n); rep(i, n) cin >> a[i]; vector<mint> sum(n + 1, 0); rep(i, n) sum[i + 1] = sum[i] * m + (a[i] - 1); while (q--) { int l, r; cin >> l >> r; --l; cout << (sum[r] - sum[l] * mint(m).pow(r - l) + 1).val() << endl; } return 0; }