Илья сидит в зале ожидания аэропорта города Мегаполиса и скучает, наблюдая за тем, как его рейс вновь и вновь задерживается. Чтобы скрасить время, он решил достать лист бумаги и ручку и порешать какие-нибудь задачи.
Илья нарисовал на листочке сетку из n × n клеток и отметил на ней n клеток, никакие две из которых не находятся в одной строке или в одном столбце. Он называет прямоугольники со сторонами, проходящими по линиям сетки, среди углов которых есть ровно две отмеченные клетки, интересными. На поле есть ровно n·(n - 1) / 2 интересных прямоугольников.
Илья выбрал q прямоугольников со сторонами, проходящими по линиям сетки поля (не обязательно являющихся интересными), после чего решил посчитать для каждого из выбранных прямоугольников степень интересности. Степенью интересности выбранного прямоугольника назовём количество интересных прямоугольников, которые имеют в пересечении с заданным хотя бы одну клетку.
Теперь Илья уже не уверен, что успеет справиться с поставленной задачей до отлёта. Вам дано описание отмеченных клеток и выбранных прямоугольников, помогите Илье определить степень интересности каждого из выбранных прямоугольников.
В первой строке находятся два целых числа n и q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) размер поля и число выбранных прямоугольников.
Во второй строке содержатся n чисел p1, p2, ..., pn, разделённых пробелами (1 ≤ pi ≤ n, все pi различны), задающие клетки, отмеченные Ильёй. А именно, pi — это номер строки клетки, отмеченной в столбце i. Строки пронумерованы от 1 до n снизу вверх, столбцы пронумерованы от 1 до n слева направо.
В следующих q строках содержатся описания выбранных прямоугольников. Каждый прямоугольник задаётся четвёркой чисел l, d, r, u (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ u ≤ n), где l и r — номера самого левого и самого правого столбца в прямоугольнике, а d и u — номера самой нижней и самой верхней строки.
Для каждого из отмеченных прямоугольников выведите степень его интересности в отдельной строке.
2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2
1
1
1
4 2
1 3 2 4
4 1 4 4
1 1 2 3
3
5
В первом тестовом примере существует только один интересный прямоугольник, занимающий всё поле. Поэтому ответ на любой запрос равен 1.
Во втором тестовом примере для первого запроса 3 интересных прямоугольника, пересекающие данный, расположены так:
А 5 интересных прямоугольников, пересекающие данный, во втором запросе расположены так:
