Given $$$n$$$ numbers of a permutation of $$$[0, 1, ..., n-1]$$$ $$$p_1, p_2, ..., p_n$$$.

Define a function $$$g(l, r, k)$$$ as follows:

• Define an array $$$c$$$ as: $$$c_i = \operatorname{MEX}(p[l+i:r+i])$$$ for $$$1\le i\le k$$$, where $$$p[x:y]$$$ denotes the subarray from $$$x$$$ to $$$y$$$.
• Return the sum of $$$\min(k,10^4)$$$ largest numbers from array $$$c$$$.

You are given $$$q$$$ queries of form $$$(l, r, k)$$$, print out $$$g(l, r, 1)+g(l, r, 2)+...+g(l, r, k)$$$.

Constraints:

$$$n, q \le 10^5$$$

$$$1 \le l \le r \lt n, r+k \le n$$$

Huge inspirations from 2163D2 - Diadrash (Hard Version)