题目描述

给定一个 $(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$ ，表示两个点的坐标分别为 $\left(x_1, y_1\right)$ 和 $\left(x_2, y_2\right)$ 。

输出格式

输出 $q$ 行，按顺序输出询问对应的答案。

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$ 。

• Subtask 1 (30 pts) : 保证 $n, q \leq 10$ 。
• Subtask 2 (20 pts) : 保证 $n \leq 10$ 。
• Subtask 3 (20 pts) : 保证 $n \leq 10^3$ 。
• Subtask 4 (20 pts) : 保证 $q=1$ 。
• Subtask 5 (10 pts)：无特殊限制。

大样例

大样例下载