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;
const int N = 2e5 + 2;
const int L = 1e5;
const int mod = 998244353;
const int K = 102;
const int magic = 320;
void add(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}
void sub(int &x, int y) {
  x -= y;
  if (x < 0) {
    x += mod;
  }
}
int mul(int x, int y) { return (1ll * x * y) % mod; }
int binpow(int x, int y) {
  int tich = 1;
  while (y) {
    if (y & 1) {
      tich = mul(tich, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return tich;
}
struct query {
  int grp, l, r, k, idx;
};
bool cmp(query x, query y) {
  if (x.grp != y.grp) {
    return x.grp < y.grp;
  }
  return x.r < y.r;
}
int ar[N], cnt1[N], cnt[N], fact[K][N], now = 0, ans[N], cnt_sub[N], fact1[N],
                                        invfact[N], tich[K];
query que[N];
set<int> lis;
map<int, int> owo;
void add_v(int x) {
  cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L]--;
  if (cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L] == 0) {
    lis.erase(cnt[ar[x]] - cnt1[ar[x]]);
  }
  cnt1[ar[x]]++;
  cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L]++;
  if (cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L] == 1) {
    lis.insert(cnt[ar[x]] - cnt1[ar[x]]);
  }
}
void sub_v(int x) {
  cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L]--;
  if (cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L] == 0) {
    lis.erase(cnt[ar[x]] - cnt1[ar[x]]);
  }
  cnt1[ar[x]]--;
  cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L]++;
  if (cnt_sub[cnt[ar[x]] - cnt1[ar[x]] + L] == 1) {
    lis.insert(cnt[ar[x]] - cnt1[ar[x]]);
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q, i, j, k, l, r;
  cin >> n >> m >> q;
  for (i = 1; i <= n; i++) {
    cin >> ar[i];
    cnt[ar[i]]++;
  }
  fact1[0] = 1;
  for (i = 1; i <= 2 * L; i++) {
    fact1[i] = mul(fact1[i - 1], i);
  }
  invfact[2 * L] = binpow(fact1[2 * L], mod - 2);
  for (i = 2 * L; i > 0; i--) {
    invfact[i - 1] = mul(invfact[i], i);
  }
  for (i = 1; i <= q; i++) {
    cin >> que[i].l >> que[i].r >> que[i].k;
    que[i].idx = i;
    que[i].grp = (que[i].l + magic - 1) / magic;
    if (!owo.count(que[i].k)) {
      now++;
      owo[que[i].k] = now;
      fact[now][0] = tich[now] = 1;
      for (j = 1; j <= n; j++) {
        fact[now][j] = mul(fact[now][j - 1], mul(que[i].k, m) + j);
      }
      for (j = 1; j <= m; j++) {
        tich[now] = mul(tich[now], fact1[que[i].k + cnt[j]]);
      }
    }
  }
  for (i = 1; i <= m; i++) {
    cnt_sub[cnt[i] + L]++;
    if (cnt_sub[cnt[i] + L] == 1) {
      lis.insert(cnt[i]);
    }
  }
  j = 1, k = 0;
  sort(que + 1, que + 1 + q, cmp);
  set<int>::iterator ite;
  for (i = 1; i <= q; i++) {
    while (k < que[i].r) {
      k++;
      add_v(k);
    }
    while (j > que[i].l) {
      j--;
      add_v(j);
    }
    while (k > que[i].r) {
      sub_v(k);
      k--;
    }
    while (j < que[i].l) {
      sub_v(j);
      j++;
    }
    ans[que[i].idx] = mul(fact[owo[que[i].k]][n - (que[i].r - que[i].l + 1)],
                          tich[owo[que[i].k]]);
    for (ite = lis.begin(); ite != lis.end(); ite++) {
      l = *ite;
      ans[que[i].idx] =
          mul(ans[que[i].idx], binpow(invfact[que[i].k + l], cnt_sub[l + L]));
    }
  }
  for (i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
}