Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Background

The spherical elf pl launched Slay before taking the ABC contest. At this moment, the coach came in, so he had to pretend to be working on data structures.

Problem Description

Given a sequence $a$ of length $n$, you need to support $m$ operations of the following type: let $x$ be the $k$-th smallest value in the interval $l \sim r$, and find the number of elements equal to $x$ in the interval.

Input Format

The first line contains two integers $n, m$, representing the length of the sequence and the number of subsequent operations respectively.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, describing the sequence.

The next $m$ lines each contain three integers in the format l r k.

Output Format

For each query, output a single line with an integer representing the answer to that query.

Samples

5 3
3 1 4 1 5
1 3 2
2 5 3
1 5 1

1
1
2

Data Range

$1\le n,m\le2\times10^5$，$1\le a_i\le 10^9$，$1\le l\le r\le n$，$1\le k\le r-l+1$.