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>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,tree-vectorize")
#pragma GCC target("popcnt,sse3,sse4.1,sse4.2,avx,tune=native")
using namespace std;
using namespace rel_ops;
using ll = int64_t;
using Pii = pair<int, int>;
using ull = uint64_t;
using Vi = vector<int>;
void run();
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  run();
  return 0;
}
ll modInv(ll a, ll m) {
  if (a == 1) return 1;
  return ((a - modInv(m % a, a)) * m + 1) / a;
}
constexpr int MOD = 998244353;
int n, m, q;
struct Query {
  int begin, end, k, answer, ord;
  bool operator<(const Query& r) const {
    if (k != r.k) return k < r.k;
    return ord < r.ord;
  }
};
vector<Query> queries;
Vi pattern, inPattern, counts;
int ansUp, ansDown, mult1;
int lastK = -1, lastBegin, lastEnd;
void addElem(int e) {
  ansUp = (ll(ansUp) * counts[e]--) % MOD;
  ansDown = (ll(ansDown) * mult1--) % MOD;
}
void delElem(int e) {
  ansUp = (ll(ansUp) * ++mult1) % MOD;
  ansDown = (ll(ansDown) * ++counts[e]) % MOD;
}
int handle(int begin, int end, int k) {
  if (lastK != k) {
    lastK = k;
    lastBegin = begin;
    lastEnd = begin;
    ansDown = ansUp = 1;
    mult1 = (ll(m) * k) % MOD;
    for (int i = (0); i < (n); i++) {
      mult1 += 1;
      ansUp = (ll(ansUp) * mult1) % MOD;
    }
    for (int i = (0); i < (m); i++) counts[i] = (inPattern[i] + k) % MOD;
  }
  while (lastBegin > begin) addElem(pattern[--lastBegin]);
  while (lastEnd < end) addElem(pattern[lastEnd++]);
  while (lastBegin < begin) delElem(pattern[lastBegin++]);
  while (lastEnd > end) delElem(pattern[--lastEnd]);
  ll ans = (ll(ansUp) * modInv(ansDown, MOD)) % MOD;
  if (ans < 0) ans += MOD;
  return ans;
}
ll hilbert(ll first, ll second, ll s, ll c = 0) {
  if (s <= 1) return c;
  s /= 2;
  c *= 4;
  if (second < s)
    return hilbert(first & (s - 1), second, s, c + (first >= s) + 1);
  if (first < s) return hilbert(2 * s - second - 1, s - first - 1, s, c);
  return hilbert(second - s, first - s, s, c + 3);
}
void run() {
  cin >> n >> m >> q;
  int moSize = 1;
  while (moSize < n) moSize *= 2;
  pattern.resize(n);
  inPattern.resize(m);
  counts.resize(m);
  for (auto& p : (pattern)) {
    cin >> p;
    p--;
    inPattern[p]++;
  }
  queries.resize(q);
  for (auto& p : (queries)) {
    cin >> p.begin >> p.end >> p.k;
    p.begin--;
    p.ord = hilbert(p.begin, p.end, moSize);
  }
  Vi sorted(q);
  iota((sorted).begin(), (sorted).end(), 0);
  sort((sorted).begin(), (sorted).end(),
       [](ll l, ll r) { return queries[l] < queries[r]; });
  for (auto& i : (sorted)) {
    auto& p = queries[i];
    p.answer = handle(p.begin, p.end, p.k);
  }
  for (auto& p : (queries)) cout << p.answer << '\n';
}