Задана перестановка чисел від \(1\) до \(N\) (кожне число рівно по одному разу).
Дайте відповідь на запити "скільки серед чисел, які стоять на позиціях з \(L\) по \(R\), по величині лежать в інтервалі від \(x\) до \(y\).

Формат вхідних даних

У першому рядку лежить два натуральних числа \(N,M\) (\(1 \le N,M \le 100000\)) - кількість чисел в перестановці і кількість запитів.

У другому рядку задано \(N\) чисел - відповідна перестановка

Далі в \(M\) рядках знаходяться описи запитів. Кожен рядок містить чотири цілих числа \(L,R,x,y\) (\( 1 \le L \le R \le N , 1 \le x \le y \le N\))

Формат вихідних даних

Виведіть \(M\) рядків, кожен повинен містити єдине число - відповідь на запит

Приклад вхідних даних-1

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

Приклад вихідних даних-1

1
3