Problem: In "The Man in the High Castle" world, there are m different film endings. 

Abendsen owns a storage and a shelf. At first, he has n ordered films on the shelf. In the i-th month he will do:

  1. Empty the storage.
  2. Put k_i ⋅ m films into the storage, k_i films for each ending.
  3. He will think about a question: if he puts all the films from the shelf into the storage, then randomly picks n films (from all the films in the storage) and rearranges them on the shelf, what is the probability that sequence of endings in [l_i, r_i] on the shelf will not be changed? Notice, he just thinks about this question, so the shelf will not actually be changed.



Answer all Abendsen's questions.

Let the probability be fraction P_i. Let's say that the total number of ways to take n films from the storage for i-th month is A_i, so P_i ⋅ A_i is always an integer. Print for each month P_i ⋅ A_i \pmod {998244353}.

998244353 is a prime number and it is equal to 119 ⋅ 2^{23} + 1.

It is guaranteed that there will be only no more than 100 different k values.

Input

The first line contains three integers n, m, and q (1 ≤ n, m, q ≤ 10^5, n+q≤ 10^5) — the number of films on the shelf initially, the number of endings, and the number of months.

The second line contains n integers e_1, e_2, …, e_n (1≤ e_i≤ m) — the ending of the i-th film on the shelf.

Each of the next q lines contains three integers l_i, r_i, and k_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ k_i ≤ 10^5) — the i-th query.

It is guaranteed that there will be only no more than 100 different k values.

Output

Print the answer for each question in a separate line.

Examples

Input

6 4 4
1 2 3 4 4 4
1 4 0
1 3 2
1 4 2
1 5 2


Output

6
26730
12150
4860


Input

5 5 3
1 2 3 4 5
1 2 100000
1 4 4
3 5 5


Output

494942218
13125
151632

Note

In the first sample in the second query, after adding 2 ⋅ m films into the storage, the storage will look like this: \{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4\}.

There are 26730 total ways of choosing the films so that e_l, e_{l+1}, …, e_r will not be changed, for example, [1, 2, 3, 2, 2] and [1, 2, 3, 4, 3] are such ways.

There are 2162160 total ways of choosing the films, so you're asked to print (26730/2162160 ⋅ 2162160) mod 998244353 = 26730.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using cat = long long;
struct query {
  int l, r, K, id;
  bool operator<(const query& Q) const { return r < Q.r; }
};
cat pw(cat a, cat e, cat mod) {
  if (e <= 0) return 1;
  cat x = pw(a, e / 2, mod);
  x = x * x % mod;
  if (e & 1) x = x * a % mod;
  return x;
}
struct fin {
  vector<int> T;
  fin(int N) : T(N + 10, 0) {}
  int lastone(int x) { return x & (x ^ (x - 1)); }
  void put(int pos, int val) {
    for (int i = pos + 1; i < (int)T.size(); i += lastone(i)) T[i] += val;
  }
  int get(int pos) {
    int ret = 0;
    for (int i = pos + 1; i > 0; i -= lastone(i)) ret += T[i];
    return ret;
  }
};
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  map<int, vector<int> > queries_by_K;
  vector<query> QV(Q);
  for (int i = 0; i < Q; i++) {
    cin >> QV[i].l >> QV[i].r >> QV[i].K;
    QV[i].id = i;
    QV[i].l--;
  }
  sort(begin(QV), end(QV));
  for (int i = 0; i < Q; i++) queries_by_K[QV[i].K].push_back(i);
  int X = 300;
  vector<int> rare, common;
  vector<vector<int> > elems_by_occ(M);
  for (int i = 0; i < N; i++) elems_by_occ[--A[i]].push_back(i);
  for (int i = 0; i < M; i++) {
    if ((int)elems_by_occ[i].size() >= X)
      common.push_back(i);
    else
      rare.push_back(i);
  }
  cat mod = 998244353;
  vector<cat> ans(Q, 1);
  for (auto it = queries_by_K.begin(); it != queries_by_K.end(); it++) {
    cat K = it->first;
    vector<cat> cnt(N + 1, 1);
    for (int i = 1; i <= N; i++) cnt[i] = cnt[i - 1] * (M * K % mod + i) % mod;
    for (auto jt = it->second.begin(); jt != it->second.end(); jt++) {
      query q_cur = QV[*jt];
      ans[q_cur.id] = ans[q_cur.id] * cnt[N - (q_cur.r - q_cur.l)] % mod;
    }
  }
  for (int i = 0; i < (int)common.size(); i++) {
    int e = common[i];
    vector<int> cnt(N + 1, 0);
    for (auto it = elems_by_occ[e].begin(); it != elems_by_occ[e].end(); it++)
      cnt[(*it) + 1]++;
    for (int j = 1; j <= N; j++) cnt[j] += cnt[j - 1];
    vector<cat> prod(cnt[N] + 1, 1);
    for (auto it = queries_by_K.begin(); it != queries_by_K.end(); it++) {
      int K = it->first;
      for (int j = cnt[N]; j > 0; j--) prod[j - 1] = prod[j] * (K + j) % mod;
      for (auto jt = it->second.begin(); jt != it->second.end(); jt++) {
        query q_cur = QV[*jt];
        int cnt_cur = cnt[q_cur.r] - cnt[q_cur.l];
        ans[q_cur.id] = ans[q_cur.id] * prod[cnt[N] - cnt_cur] % mod;
      }
    }
  }
  int MX = 110000;
  vector<vector<cat> > invfac_pw(MX + 1, vector<cat>(20, 1));
  for (int i = 1; i <= MX; i++)
    invfac_pw[i][0] = invfac_pw[i - 1][0] * pw(i, mod - 2, mod) % mod;
  for (int i = 0; i <= MX; i++)
    for (int j = 1; j < 20; j++)
      invfac_pw[i][j] = invfac_pw[i][j - 1] * invfac_pw[i][j - 1] % mod;
  for (auto it = queries_by_K.begin(); it != queries_by_K.end(); it++) {
    int K = it->first;
    cat prodc = 1;
    vector<cat> fac(K + X + 1, 1);
    for (int i = 1; i <= K + X; i++) fac[i] = i * fac[i - 1] % mod;
    for (auto jt = rare.begin(); jt != rare.end(); jt++)
      prodc = prodc * fac[K + elems_by_occ[*jt].size()] % mod;
    for (auto jt = it->second.begin(); jt != it->second.end(); jt++)
      ans[QV[*jt].id] = ans[QV[*jt].id] * prodc % mod;
  }
  vector<vector<int> > cnt_occ(Q, vector<int>(X, 0));
  vector<fin> F(X, fin(N));
  vector<int> Fsum(X, 0);
  for (auto it = rare.begin(); it != rare.end(); it++)
    for (int i = 0; i < (int)elems_by_occ[*it].size(); i++) {
      Fsum[i]++;
      F[i].put(elems_by_occ[*it][i], 1);
    }
  int a = 0;
  vector<int> b(M, 0);
  for (int i = 0; i < N; i++) {
    if ((int)elems_by_occ[A[i]].size() < X) {
      int x = A[i], sz = elems_by_occ[A[i]].size();
      for (int j = 0; j < sz; j++) {
        F[j].put(elems_by_occ[x][(b[x] + j) % sz], -1);
        Fsum[j]--;
      }
      b[x]++;
      for (int j = 0; j < sz; j++) {
        F[j].put(elems_by_occ[x][(b[x] + j) % sz], 1);
        Fsum[j]++;
      }
    }
    while (a < Q && QV[a].r == i + 1) {
      for (int j = 0; j < X; j++)
        cnt_occ[a][j] = Fsum[j] - F[j].get(QV[a].r - 1) + F[j].get(QV[a].l - 1);
      a++;
    }
  }
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j <= X - 2; j++) cnt_occ[i][j] -= cnt_occ[i][j + 1];
    int zero = rare.size();
    for (int j = X - 1; j > 0; j--) {
      cnt_occ[i][j] = cnt_occ[i][j - 1];
      zero -= cnt_occ[i][j];
    }
    cnt_occ[i][0] = zero;
  }
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j < X; j++) {
      int x = QV[i].K + j;
      int e = cnt_occ[i][j];
      for (int k = 0; k < 20; k++) {
        if (e == 0) break;
        if ((e >> k) & 1) {
          ans[QV[i].id] = ans[QV[i].id] * invfac_pw[x][k] % mod;
          e -= 1 << k;
        }
      }
    }
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
  return 0;
}