$(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$ に接続されることに注意せよ。したがって、これはクラインの壺とみなすことができる。

クラインの壺上の2点が与えられるたびに、それらの間の最短路の長さを求めよ。

入力

1行目に2つの正整数 $n, q$ が与えられる。

続く $q$ 行の各行には4つの整数 $x_1, y_1, x_2, y_2$ が与えられ、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

小課題

すべてのデータにおいて、$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$：特別な制約はない。