Pe un șir $x_1, x_2, \dots x_k$ de numere naturale poți aplica două tipuri de operații:

$1.$ Alegi două numere $(i, j)$ cu $1 \leq i \leq j \leq k$ și fiecare valoare de la $i$ la $j$ devine $0$.
$2.$ Alegi două numere $(i, j)$ cu $1 \leq i \leq j \leq k$ și aduni $1$ la fiecare valoare de la $i$ la $j$.

De exemplu, dacă începem cu șirul $x = [1, 3, 0, 2, 3]$. Am putea, de exemplu, să aplicăm următoarea secvență de operații:

1. Aplicăm operația $1$ pentru $(2, 3)$. $x = [1, 0, 0, 2, 3]$.
2. Aplicăm operația $2$ pentru $(1, 3)$. $x = [2, 1, 1, 2, 3]$.
3. Aplicăm operația $2$ pentru $(4, 5)$. $x = [2, 1, 1, 3, 4]$.
4. Aplicăm operația $1$ pentru $(1, 3)$. $x = [0, 0, 0, 3, 4]$.

Cerință

Se dă $n$ și un șir $a_1, a_2, \dots a_n$ de numere naturale. Se dau $Q$ interogări de forma $l, r, v$. Care e numărul minim de operații pe care trebuie să le faci astfel încât $v = a_l = a_{l+1} = a_{l+2} = \dots = a_r$. După fiecare interogare, șirul $a$ se va reseta la cel inițial.

Date de intrare

Pe prima linie a fișierului de intrare egale.in se găsesc două numere întregi, $n$ și $Q$. Pe a doua linie se află șirul $a_1, a_2, \dots a_n$ de numere naturale. Pe următoarele $Q$ linii se află câte o tripletă $l, r, v$.

Date de ieșire

Pentru fiecare $i$ de la $1$ la $Q$, pe a $i$-a linie a fișierului de ieșire egale.out se va găsi un singur număr întreg, răspunsul la cea de-a $i$-a întrebare.

Restricții și precizări

• $1 \leq n, Q \leq 100 \ 000$
• $0 \leq a_i \leq 200$ pentru fiecare $i$ de la $1$ la $n$
• $1 \leq l \leq r \leq n$ și $0 \leq v \leq 200$ pentru fiecare interogare.

Exemplul 1

egale.in

11 5
1 2 1 2 1 0 5 2 3 1 6
1 4 1
1 4 2
1 11 0
1 11 4
6 9 5

egale.out

2
2
1
5
6

Explicație

Pentru prima interogare, trebuie să aflăm numărul minim de operații să facem toate elementele din șirul $[1, 2, 1, 2]$ egale cu $1$. Singurul mod în care putem face acest lucru în $2$ operații este să aplicăm operația $1$ pe tot șirul, după operația $2$ pe tot șirul.

Exemplul 2

egale.in

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

egale.out

8
10
10
4
8
3
2
5
11
2

Exemplul 3

egale.in

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

egale.out

0
1
1
0

Explicație

Acest exemplu, verifică $v = 0$ pentru fiecare interogare.

La prima interogare, deja toate elemenetele sunt $0$, deci nu mai trebuie să facem alte operații.

La a doua interogare, putem face operația $1$ pe intervalul $(1, 2)$.