Given a sequence $a$ of length $n$. There are $q$ queries, each given by $l, r, k$. Find the number of pairs $(l', r')$ such that $l \leq l' \leq r' \leq r$ and $\operatorname{mex}(\{a_{l'}, a_{l'+1}, \dots, a_{r'}\}) = k$.

Input

The first line contains two integers $n$ and $q$.

The next line contains $n$ integers, representing the sequence $a$.

The next $q$ lines each contain three integers $l, r, k$.

Output

For each query, output a single integer on a new line representing the answer.

Examples

Input 1

10 10
0 0 4 1 1 3 0 4 6 1
2 2 1
4 10 2
1 4 0
4 8 0
4 4 1
1 6 0
5 8 0
2 10 3
3 9 6
1 4 0

Output 1

1
10
3
7
0
10
4
0
0
3

Subtasks

For $10\%$ of the data, $n, q \leq 1\,000$.

For $100\%$ of the data, $1 \leq n, q \leq 230\,000$, $0 \leq a_i, k \leq 10^9$.

Note

1. No memory limit was provided during the contest; it is set to 1 GB on QOJ.