Desperate Fire Survive

Rikka is running with her every cell to the hall where the contest will be held.

Well, EC Final is growing bigger and bigger. More and more computers are connected to the weak 2000W main wires, and heat builds up in every row.

When Rikka enters the hall, she finds LCR there rearranging the wires with the volunteers. However, the girl might not be able to do anything helpful but observe.

"Listen. We have no time to calculate parameters for the new circuit. Are you good at data structures? Help us, please..."

The circuitry is a sequence of $n$ nodes, where there are $m$ possible levels of nodes in total, numbered from $1$ to $m$. A $k$-level node has a power limit twice that of a $(k-1)$-level node, so Rikka can merge two adjacent $k$-level nodes into a $(k+1)$-level node if $k < m$. She can also remove any node at any time from the circuitry, and the order of the remaining nodes stays the same.

The volunteers have $q$ queries in total. Each query gives a segment $[l,r]$ and an integer level $k$. Rikka needs to count how many sub-segments of the given segment (that is, segments $[x, y]$ with $l \le x \le y \le r$) can provide a $k$-level node. A sub-segment $[x, y]$ provides a $k$-level node if it is possible to turn the sequence $[x, y]$ into a single $k$-level node by merging adjacent nodes at the same level and removing nodes. These two operations can be performed any number of times in any order. The level must be exactly $k$, not higher or lower.

The first line contains three integers $n$, $m$, $q$ ($1 \le n, m, q \le 2 \times 10^5$), the length of the circuitry sequence, the maximal level, and the number of queries.

The second line contains $n$ integers $A_1, A_2, \dots, A_n$ ($1 \le A_i \le m$), the levels of the nodes in order.

Each of the following $q$ lines contains three integers $l$, $r$, $k$ ($1 \le l \le r \le n$, $1 \le k \le m$), describing a query. The integers in a line are separated by spaces.

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.