Rikka is running with her every cell to the hall where the contest will be held.
Well, EC Final is growing bigger and bigger... Thus more and more computers have been connected into the weak 2000W main wires. Heat is accumulating 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 observing.
"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$. Since a $k$-level node has a power limit twice of a $(k -1)$-level one, Rikka could merge two adjacent $k$-level nodes into a $(k + 1)$-level one if $k < m$. She can also remove any node at any time from the circuitry while the order of rest nodes remains.
The volunteers have $q$ queries in total. Each query contains a segment $[ l, r ]$ and an integer level $k$. Rikka needs to count how many sub-segments of the assigned segment (i.e. a segment $[ x, y ]$ such that $l <= x <= y <= r$) can provide a $k$-level node, which means it is possible to turn circuitry sequence $[ x, y ]$ into a single $k$-level node by merging adjacent nodes at the same level and removing nodes, where these two types of operations can be performed multiple times in any order. Notice that the level must be exactly $k$ rather than higher or lower.
The first line contains three integers $n, m, q med (1 <= n, m, q <= 2 times 10^5)$, the length of the circuitry sequence, the maximal level and the number of queries, respectively.
The second line contains $n$ integers $A_1, A_2, \\dots, A_n med (1 <= A_i <= m)$, the levels of nodes in order.
Each of the following $q$ lines contains three integers $l, r, k med (1 <= l <= r <= n, 1 <= k <= m)$, describing a query.
Multiple integers in the same line are separated by spaces.
Output $q$ lines; each contains one integer, the answer to that query.
## Input
The first line contains three integers $n, m, q med (1 <= n, m, q <= 2 times 10^5)$, the length of the circuitry sequence, the maximal level and the number of queries, respectively.The second line contains $n$ integers $A_1, A_2, \\dots, A_n med (1 <= A_i <= m)$, the levels of nodes in order.Each of the following $q$ lines contains three integers $l, r, k med (1 <= l <= r <= n, 1 <= k <= m)$, describing a query.Multiple integers in the same line are separated by spaces.
## Output
Output $q$ lines; each contains one integer, the answer to that query.
[samples]
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ denote the length of the sequence, maximum level, and number of queries, respectively.
Let $ A = (A_1, A_2, \dots, A_n) $ be a sequence where $ A_i \in \{1, 2, \dots, m\} $ represents the level of the $ i $-th node.
**Operation Rules**
A contiguous sub-segment $ [x, y] $ can be reduced to a single node of level $ k $ if and only if:
- The segment can be transformed via any sequence of:
(1) Merging two adjacent nodes of level $ j < m $ into one node of level $ j+1 $,
(2) Removing any node (deleting it without affecting adjacency of others).
- The resulting single node has level **exactly** $ k $, not higher or lower.
**Key Insight**
A contiguous sub-segment can be reduced to level $ k $ if and only if:
- The sum of $ 2^{A_i - 1} $ over all nodes in the segment equals $ 2^{k - 1} $.
This follows because merging two level-$ j $ nodes produces a level-$ (j+1) $ node (equivalent to $ 2 \cdot 2^{j-1} = 2^j $), and removals correspond to omitting terms — so the total power must sum exactly to $ 2^{k-1} $.
**Constraints**
1. $ 1 \leq n, m, q \leq 2 \times 10^5 $
2. $ 1 \leq A_i \leq m $ for all $ i \in \{1, \dots, n\} $
3. For each query: $ 1 \leq l \leq r \leq n $, $ 1 \leq k \leq m $
**Objective**
For each query $ (l, r, k) $, compute the number of contiguous sub-segments $ [x, y] $ such that:
$$ l \leq x \leq y \leq r \quad \text{and} \quad \sum_{i=x}^{y} 2^{A_i - 1} = 2^{k - 1} $$