B'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: 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 cdot A_i is always an integer. Print for each month P_i cdot A_i pmod {998244353} . 998244353 is a prime number and it is equal to 119 cdot 2^{23} + 1 . It is guaranteed that there will be only no more than 100 different k values. The first line contains three integers n , m , and q ( 1 <= n, m, q <= 10^5 , n+q <= 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, ldots, e_n ( 1 <= q e_i <= q 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. Print the answer for each question in a separate line. In the first sample in the second query, after adding 2 cdot 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}, ldots, 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 ( frac{26730}{2162160} cdot 2162160) mod 998244353 = 26730 . '...