Given an $(n+1)\times (n+1)$ grid graph, where each point has coordinates $(i, j)$ with $0\leq i, j\leq n$. For each $(i, j)$:

• For $j\geq 1$, there is an undirected edge to $(i, j-1)$, and there is an undirected edge between $(i, 0)$ and $(i, n)$.
• For $i\geq 1$, there is an undirected edge to $(i-1, j)$, and there is an undirected edge between $(0, j)$ and $(n, n-j)$. Note that $j$ is connected to $n-j$ here, so you can think of this as a Klein bottle.

Given two points on the Klein bottle for each query, find the length of the shortest path between them.

Input

The first line contains two positive integers $n$ and $q$.

Each of the next $q$ lines contains four integers $x_1, y_1, x_2, y_2$, representing the coordinates of the two points $(x_1, y_1)$ and $(x_2, y_2)$.

Output

Output $q$ lines, each containing the answer to the corresponding query in order.

Examples

Input 1

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

Output 1

2
2
2
7
5

Subtasks

For $100\%$ of the data, $1\leq n\leq 10^8$, $1\leq q\leq 10^5$, and $0\leq x_1, y_1, x_2, y_2\leq n$.

For test cases $1\sim 3$, $n, q\leq 10$.

For test cases $4\sim 5$, $n\leq 10$.

For test cases $6\sim 7$, $n\leq 10^3$.

For test cases $8\sim 9$, $q=1$.

For test case $10$, there are no additional constraints.