I. Текстовый редактор 2
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Нехотя, тыкая пальцами в кнопки на клавиатуре, Вася выдавливает из себя скудные мысли по поводу того, о чем же думал Андрей Болконский, глядя на небо Аустерлица... Ну как объяснить учительнице по литературе, что Вася не собирается становиться писателем, а хочет стать программистом. Поэтому программу он напишет с удовольствием, а вот сочинение дается ему с трудом.

Пока Вася думал о том, как выудить из себя очередное предложение, ему в голову пришел неожиданный вопрос: а какое наименьшее количество нажатий на кнопки ему нужно сделать, чтобы переместить курсор из одной позиции в другую?

Опишем его вопрос более формально: для набора текста Вася использует текстовый редактор. Он уже написал n строчек, в i-й строке написано ai символов (включая пробелы). Если в некоторой строке записано k символов, то всего в этой строке существует (k + 1) позиция, в которой может находиться курсор: перед каким-то символом или после всех символов (в конце строки). Таким образом, положение курсора задается парой чисел (r, c), где r — номер строки, а c — позиция курсора в ней (позиции нумеруются с единицы от начала строки).

Для перемещения курсора Вася не использует мышь. Он использует клавиши «Вверх», «Вниз», «Вправо» и «Влево». При нажатии на каждую из этих клавиш курсор перемещается следующим образом. Пусть до нажатия соответствующей клавиши курсор находился в позиции (r, c), тогда после нажатия клавиши:

  • «Вверх»: если курсор находился в первой строке (r = 1), то он не перемещается. Иначе он перемещается на предыдущую строку (с номером r - 1) в ту же позицию. При этом, если предыдущая строка короткая, то есть курсор не может находиться в ней в позиции c, то курсор перемещается на последнюю позицию строки с номером r - 1;
  • «Вниз»: если курсор находился в последней строке (r = n), то он не перемещается. Иначе он перемещается на следующую строку (с номером r + 1) в ту же позицию. При этом, если следующая строка короткая, то есть курсор не может находиться в ней в позиции c, то курсор перемещается на последнюю позицию строки с номером r + 1;
  • «Вправо»: если курсор может переместиться вправо в текущей строке (c < ar + 1), то он перемещается вправо (в позицию c + 1). Иначе он находится в конце строки. Если текущая строка является последней в файле (r = n), курсор при нажатии клавиши «Вправо» никуда не перемещается. Иначе, он перемещается в самую левую позицию в следующей строке (с номером r + 1).
  • «Влево»: если курсор может переместиться влево в текущей строке (c > 1), то он перемещается влево (в позицию c - 1). Иначе он находится в начале строки. Если текущая строка является первой в файле (r = 1), курсор при нажатии клавиши «Влево» никуда не перемещается. Иначе, он перемещается в самую правую позицию в предыдущей строке (с номером r - 1).

Вам задано количество строк в текстовом файле и количество символов, записанное в каждой строке этого файла. Вам требуется ответить на m запросов. Для каждого запроса найдите наименьшее количество нажатий описанных выше клавиш, требуемое для того, чтобы переместить курсор из положения (r1, c1) в положение (r2, c2).

Входные данные

Входные данные состоят из нескольких тестовых наборов. Описание каждого тестового набора начинается со строки, содержащей два целых числа n и m (1 ≤ n ≤ 106, 1 ≤ m ≤ 10). Во второй строке записано n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109), разделенных одиночными пробелами. Каждая из следующих m строк содержит по четыре целых числа r1, c1, r2, c2 (1 ≤ r1, r2 ≤ n, 1 ≤ c1 ≤ ar1 + 1, 1 ≤ c2 ≤ ar2 + 1).

Выходные данные

Для каждого тестового набора выведите его порядковый номер и ответы на запросы. Для каждого запроса выведите наименьшее количество нажатий, требуемое для того, чтобы переместить курсор из положения (r1, c1) в положение (r2, c2).

Примеры
Входные данные
4 1
2 1 6 4
3 5 4 2
5 2
3 5 4 3 6
2 1 5 6
1 1 5 7
Выходные данные
Case 1: 3
Case 2: 7 9