Dany jest graf siatkowy o wymiarach $(n+1)\times (n+1)$, w którym każdy punkt ma współrzędne $(i,j)$, gdzie $0\leq i,j\leq n$. Dla każdego punktu $(i, j)$:

• Dla $j\geq 1$ istnieje krawędź dwukierunkowa do $(i,j-1)$, a także krawędź dwukierunkowa między $(i,0)$ oraz $(i,n)$.
• Dla $i\geq 1$ istnieje krawędź dwukierunkowa do $(i-1,j)$, a także krawędź dwukierunkowa między $(0,j)$ a $(n, n-j)$ (uwaga: $j$ łączy się z $n-j$). Można to interpretować jako butelkę Kleina.

Dla każdej pary punktów na butelce Kleina należy wyznaczyć długość najkrótszej ścieżki między nimi.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite dodatnie $n$ oraz $q$.

W kolejnych $q$ liniach znajdują się cztery liczby całkowite $x_1, y_1, x_2, y_2$, oznaczające współrzędne dwóch punktów $(x_1, y_1)$ oraz $(x_2, y_2)$.

Wyjście

Dla każdego zapytania należy wypisać w osobnej linii długość najkrótszej ścieżki.

Przykład

Przykład 1

Wejście

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

Wyjście

2
2
2
7
5

Podzadania

Dla $100\%$ danych wejściowych spełnione są warunki: $1\leq n\leq 10^8$, $1\leq q\leq 10^5$ oraz $0\leq x_1,y_1,x_2,y_2\leq n$.

Dla testów $1\sim 3$ zachodzi $n,q\leq 10$.

Dla testów $4\sim 5$ zachodzi $n\leq 10$.

Dla testów $6\sim 7$ zachodzi $n\leq 10^3$.

Dla testów $8\sim 9$ zachodzi $q=1$.

Dla testu $10$ brak dodatkowych ograniczeń.