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 Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 998244353;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 100111;
const int maxk = 111;
int B;
struct query {
  int l, r, id;
  query(int L = 0, int R = 0, int Id = 0) {
    l = L;
    r = R;
    id = Id;
  }
  bool operator<(const query &t) const {
    return l / B == t.l / B ? r < t.r : l < t.l;
  }
};
int n, m, q, a[maxn], all_cur[maxn], cur[maxn], ANS[maxn];
int inv[maxn * 2];
int CUR_K, L, R, CURP;
void add(int x) {
  CURP = 1ll * CURP * (all_cur[a[x]] + CUR_K - cur[a[x]]) % mod;
  cur[a[x]]++;
}
void del(int x) {
  cur[a[x]]--;
  CURP = 1ll * CURP * inv[all_cur[a[x]] + CUR_K - cur[a[x]]] % mod;
}
map<int, int> kid;
int tot, arr_k[maxk];
int getkid(int k) {
  int &id = kid[k];
  if (id == 0) id = ++tot, arr_k[id] = k;
  return id;
}
vector<query> v[maxk];
int prod[maxn];
void prework(int K) {
  CUR_K = K;
  L = 1;
  R = 0;
  CURP = 1;
  for (int i = 1; i <= m; i++) cur[i] = 0;
  prod[0] = 1;
  for (int i = 1; i <= n; i++)
    prod[i] = 1ll * (1ll * m * K + i) % mod * prod[i - 1] % mod;
}
void solve(vector<query> v) {
  if (!v.size()) return;
  B = max(1, int(n / sqrt(v.size())));
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++) {
    int l = v[i].l, r = v[i].r, id = v[i].id;
    while (L > l) add(--L);
    while (R < r) add(++R);
    while (L < l) del(L++);
    while (R > r) del(R--);
    ANS[id] = 1ll * CURP * prod[n - (r - l + 1)] % mod;
  }
}
void preworkc(int N) {
  inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = -1ll * inv[mod % i] * (mod / i) % mod;
}
int main() {
  preworkc(maxn * 2);
  n = getnum(), m = getnum(), q = getnum();
  for (int i = 1; i <= n; i++) {
    a[i] = getnum();
    all_cur[a[i]]++;
  }
  for (int i = 1; i <= q; i++) {
    int l, r, k;
    l = getnum(), r = getnum(), k = getnum();
    v[getkid(k)].push_back(query(l, r, i));
  }
  for (int i = 1; i <= tot; i++) {
    prework(arr_k[i]);
    solve(v[i]);
  }
  for (int i = 1; i <= q; i++)
    putnum((ANS[i] % mod + mod) % mod), putchar('\n');
  return 0;
}