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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXZ = 447;
const int MAXTYPE = 100000;
const int MAXQ = 100000;
const int MAXK = 100;
const int MAXKVAL = 100000;
const int MOD = 998244353;
struct Q {
  int b, l, r, k, id;
};
bool operator<(const Q &u, const Q &v) {
  if (u.b != v.b) return u.b < v.b;
  return u.b % 2 == 0 ? u.r < v.r : u.r > v.r;
}
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
int n, ntype, nq;
int type[MAXN];
Q q[MAXQ];
int ans[MAXQ];
int inv[MAXKVAL + MAXN + 1];
int fac[MAXKVAL + MAXN + 1];
int ifac[MAXKVAL + MAXN + 1];
int tmp[MAXN >= MAXTYPE ? MAXN : MAXTYPE], ntmp;
int zval[MAXZ], nz;
int tz[MAXTYPE];
int tcnt[MAXTYPE];
int freq[MAXZ][MAXN + 1];
bool incur[MAXZ][MAXN + 1];
pair<int, int> cur[3 * MAXN];
int ncur;
int kval[MAXK], nk;
int kfalling[MAXK][MAXN + 1];
void mod(int idx, int by) {
  --freq[tz[type[idx]]][tcnt[type[idx]]];
  tcnt[type[idx]] += by;
  ++freq[tz[type[idx]]][tcnt[type[idx]]];
  if (tcnt[type[idx]] != 0 && !incur[tz[type[idx]]][tcnt[type[idx]]])
    cur[ncur++] = make_pair(tz[type[idx]], tcnt[type[idx]]),
    incur[tz[type[idx]]][tcnt[type[idx]]] = true;
}
int calc(int k) {
  int nncur = 0;
  for (int i = (0); i < (ncur); ++i)
    if (freq[cur[i].first][cur[i].second] == 0)
      incur[cur[i].first][cur[i].second] = false;
    else
      cur[nncur++] = cur[i];
  ncur = nncur;
  int ret = 1;
  for (int i = (0); i < (ncur); ++i) {
    int have = zval[cur[i].first], need = cur[i].second,
        exp = freq[cur[i].first][cur[i].second];
    ret = (long long)ret *
          pw((long long)fac[k + have] * ifac[k + have - need] % MOD, exp) % MOD;
  }
  return ret;
}
void solve() {
  inv[1] = 1;
  for (int i = (2); i <= (MAXKVAL + MAXN); ++i)
    inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
  fac[0] = 1;
  for (int i = (1); i <= (MAXKVAL + MAXN); ++i)
    fac[i] = (long long)fac[i - 1] * i % MOD;
  ifac[0] = 1;
  for (int i = (1); i <= (MAXKVAL + MAXN); ++i)
    ifac[i] = (long long)ifac[i - 1] * inv[i] % MOD;
  for (int i = (0); i < (ntype); ++i) tcnt[i] = 0;
  for (int i = (0); i < (n); ++i) ++tcnt[type[i]];
  ntmp = 0;
  for (int i = (0); i < (ntype); ++i)
    if (tcnt[i] != 0) tmp[ntmp++] = tcnt[i];
  sort(tmp, tmp + ntmp);
  ntmp = unique(tmp, tmp + ntmp) - tmp;
  assert(ntmp <= MAXZ);
  nz = ntmp;
  for (int i = (0); i < (nz); ++i) zval[i] = tmp[i];
  for (int i = (0); i < (ntype); ++i)
    tz[i] = tcnt[i] == 0 ? -1 : lower_bound(zval, zval + nz, tcnt[i]) - zval;
  ntmp = 0;
  for (int i = (0); i < (nq); ++i) tmp[ntmp++] = q[i].k;
  sort(tmp, tmp + ntmp);
  ntmp = unique(tmp, tmp + ntmp) - tmp;
  assert(ntmp <= MAXK);
  nk = ntmp;
  for (int i = (0); i < (nk); ++i) kval[i] = tmp[i];
  for (int i = (0); i < (nk); ++i) {
    kfalling[i][0] = 1;
    for (int j = (0); j < (n); ++j)
      kfalling[i][j + 1] = (long long)kfalling[i][j] *
                           ((long long)kval[i] * ntype % MOD + j + 1) % MOD;
  }
  int bsz = sqrt(1.0 * n);
  for (int i = (0); i < (nq); ++i) q[i].b = q[i].l / bsz;
  sort(q, q + nq);
  int l = 0, r = 0;
  ncur = 0;
  for (int i = (0); i < (ntype); ++i) tcnt[i] = 0;
  for (int i = (0); i < (nz); ++i)
    for (int j = (0); j <= (n); ++j) freq[i][j] = 0, incur[i][j] = false;
  for (int i = (0); i < (ntype); ++i)
    if (tz[i] != -1) ++freq[tz[i]][tcnt[i]];
  for (int i = (0); i < (nq); ++i) {
    while (l > q[i].l) mod(--l, +1);
    while (r < q[i].r) mod(r++, +1);
    while (l < q[i].l) mod(l++, -1);
    while (r > q[i].r) mod(--r, -1);
    int k = q[i].k, kid = lower_bound(kval, kval + nk, k) - kval;
    int a = calc(k);
    int b = (long long)kfalling[kid][n - (r - l)];
    ans[q[i].id] = (long long)a * b % MOD;
  }
}
void run() {
  scanf("%d%d%d", &n, &ntype, &nq);
  for (int i = (0); i < (n); ++i) scanf("%d", &type[i]), --type[i];
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k), --q[i].l, q[i].id = i;
  solve();
  for (int i = (0); i < (nq); ++i) printf("%d\n", ans[i]);
}
void stress() {
  n = MAXN;
  ntype = MAXTYPE;
  nq = MAXQ;
  for (int i = (0); i < (n); ++i) type[i] = rand() % ntype;
  for (int i = (0); i < (nq); ++i) {
    q[i].l = rand() % n, q[i].r = rand() % n, q[i].k = rand() % MAXK,
    q[i].id = i;
    if (q[i].l > q[i].r) swap(q[i].l, q[i].r);
    ++q[i].r;
  }
  solve();
  printf(".");
}
int main() {
  run();
  return 0;
}