Вася виписав на дошці у якомусь порядку усі числа від \textbf{1} до \textbf{N}, кожне число рівно по одному разу. Кількість чисел виявилась досить великою, тому Вася не може окинути поглядом усі числа. Проте йому потрібно усе-таки уявляти цю послідовність, тому він написав програму, яка відповідає на питання - скільки среди чисел, які стоять на позиціях з \textbf{x} по \textbf{y}, по величині лежать в інтервалі від \textbf{k} до \textbf{l}. Зробіть те ж саме. \InputFile У першому рядку лежить два натуральних числа - \textbf{1} ≤ \textbf{N} ≤ \textbf{100000} - кількість чисел, які виписав Вася, і \textbf{1} ≤ \textbf{M }≤ \textbf{100000} - кількість запитань, які Вася хоче задати програмі. У другому рядку задано \textbf{N} чисел - послідовність цілих чисел, виписаних Васею. Далі в \textbf{M} рядках знаходяться описи запитань. Кожен рядок містить чотири цілих числа \textbf{1} ≤ \textbf{x} ≤ \textbf{y} ≤ \textbf{N} и \textbf{1} ≤ \textbf{k} ≤ \textbf{l} ≤ \textbf{N}. \OutputFile Виведіть \textbf{M} рядків, кожен повинен містити єдине число - відповідь Васине запитання.