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>
const int P = 998244353;
inline int mul(const int &a, const int &b) { return 1ll * a * b % P; }
inline int sub(int a, const int &b) {
  a -= b;
  return (a < 0) ? a + P : a;
}
inline int add(int a, const int &b) {
  a += b;
  return (a >= P) ? a - P : a;
}
int qsm(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a);
    b >>= 1;
  }
  return ans;
}
int n, m, q, pos[200010], a[200010], cnt[200010], tot[200010], top, inv[200010],
    _mul[200010], k;
int ans[200010];
struct point {
  int l, r, k, ord;
} num[200010];
bool cmp1(point a, point b) { return a.k < b.k; }
bool cmp2(point a, point b) {
  return (pos[a.l] < pos[b.l]) ||
         (pos[a.l] == pos[b.l] &&
          ((a.r != b.r) ? (a.r < b.r) ^ (pos[a.l] & 1) : (a.ord < b.ord)));
}
int nl, nr, nowans;
void addl() {
  --nl;
  nowans = mul(nowans, cnt[a[nl]]--);
}
void addr() {
  ++nr;
  nowans = mul(nowans, cnt[a[nr]]--);
}
void dell() {
  nowans = mul(nowans, inv[++cnt[a[nl]]]);
  ++nl;
}
void delr() {
  nowans = mul(nowans, inv[++cnt[a[nr]]]);
  --nr;
}
void solve(int l, int r) {
  _mul[0] = 1;
  for (int i = 1, start = (1ll * num[l].k * m + n) % P; i <= n; i++, start--)
    _mul[i] = mul(_mul[i - 1], start);
  int bl = std::max((int)((double)n / sqrt(r - l + 1)), 1);
  for (int i = 1; i <= n; i++) pos[i] = (i - 1) / bl + 1;
  for (int i = 1; i <= m; i++) cnt[i] = tot[i] + num[l].k;
  std::sort(num + l, num + r + 1, cmp2);
  nl = 1, nr = 0, nowans = 1;
  for (int i = l; i <= r; i++) {
    while (nl > num[i].l) addl();
    while (nr < num[i].r) addr();
    while (nl < num[i].l) dell();
    while (nr > num[i].r) delr();
    ans[num[i].ord] =
        mul(mul(nowans, qsm(_mul[num[i].r - num[i].l + 1], P - 2)), _mul[n]);
  }
}
int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
void write(int x) {
  if (x > 9) write(x / 10);
  putchar((x % 10) + '0');
}
int main() {
  n = read(), m = read(), q = read();
  for (int i = 1; i <= n; i++) ++tot[a[i] = read()];
  for (int i = 1; i <= q; i++)
    num[i].l = read(), num[i].r = read(), num[i].k = read(), num[i].ord = i;
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= 200000; i++) inv[i] = mul(P - P / i, inv[P % i]);
  std::sort(num + 1, num + q + 1, cmp1);
  for (int i = 1, last = 1; i <= q; i++) {
    if (i == q || (num[i].k != num[i + 1].k)) {
      solve(last, i);
      last = i + 1;
    }
  }
  for (int i = 1; i <= q; i++) write(ans[i]), putchar('\n');
}