给定一个 $(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)$ 到 $\boldsymbol {(n, n-j)}$ 有一条双向边，注意这里 $\boldsymbol j$ 连接到 $\boldsymbol{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

样例 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$，无特殊限制。