Дан граф-сетка размера $(n+1)\times (n+1)$, где координаты каждой точки $(i,j)$ удовлетворяют условиям $0\leq i,j\leq n$. Для каждой точки $(i, j)$ выполняются следующие условия:

• Для $j\geq 1$ существует двустороннее ребро до $(i,j-1)$, а также существует двустороннее ребро между $(i,0)$ и $(i,n)$.
• Для $i\geq 1$ существует двустороннее ребро до $(i-1,j)$, а также существует двустороннее ребро между $(0,j)$ и $(n, n-j)$, обратите внимание, что $j$ соединяется с $n-j$. Таким образом, это можно представить как бутылку Клейна.

Для каждого запроса, состоящего из двух точек на этой поверхности, необходимо найти длину кратчайшего пути между ними.

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

В первой строке заданы два целых положительных числа $n$ и $q$.

Далее следуют $q$ строк, каждая из которых содержит четыре целых числа $x_1, y_1, x_2, y_2$, обозначающих координаты двух точек $(x_1, y_1)$ и $(x_2, y_2)$.

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

Выведите $q$ строк, содержащих ответы на соответствующие запросы в том же порядке.

Примеры

Пример 1

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

10 5
1 9 10 1
7 4 5 4
1 1 3 1
6 6 0 2
10 2 6 1

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

2
2
2
7
5

Подзадачи

Для $100\%$ данных гарантируется, что $1\leq n\leq 10^8$, $1\leq q\leq 10^5$, $0\leq x_1,y_1,x_2,y_2\leq n$.

Для тестов $1\sim 3$ гарантируется, что $n,q\leq 10$.

Для тестов $4\sim 5$ гарантируется, что $n\leq 10$.

Для тестов $6\sim 7$ гарантируется, что $n\leq 10^3$.

Для тестов $8\sim 9$ гарантируется, что $q=1$.

Для теста $10$ нет дополнительных ограничений.