Marisa needs to pick mushrooms in a forest. The forest can be represented as a straight line with $n$ positions from $1$ to $n$. At position $i$ in the forest, a type of mushroom $a_i$ grows.
There are $q$ days. On the $i$-th day, she will stand at position $p_i$. She wants to pick mushrooms of types $l_i$ to $r_i$, one of each type if it exists. Instead of moving physically, she can use mushroom-picking magic. If she is standing at position $x$, she can pick a mushroom at position $y$ at a cost of $|x - y|$.
For each day, help her calculate the minimum cost to pick the mushrooms.
### Input
- The first line contains two integers $n$ and $q$.
- The second line contains $n$ integers $a_i$.
- The next $q$ lines each contain three integers $p_i$, $l_i$, and $r_i$.
### Output
- For each day, calculate the minimum cost for Marisa to pick the mushrooms.
### Constraints
- $1 \leq n, q \leq 2 \times 10^5$.
- $1 \leq l, r, p, a_i \leq n$.
### Example
Input:
```
5 4
1 5 3 1 3
3 3 4
4 2 5
3 1 3
5 2 5
```
Output:
```
0
3
1
3
```
### Subtasks
- $30\\%$ of the tests have $1 \leq n, q \leq 1000$.
- $10\\%$ of the tests have $a_i = i$.
- $30\\%$ of the tests have $\forall i \; l_i=1, r_i=n$.
- The remaining $20\\%$ have no additional constraints.
