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

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

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

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

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

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