Problem Statement

There is an undirected graph with $N^2$ vertices. Initially, it has no edges. For each pair of integers $(i,\ j)$ such that $0 \leq i,\ j < N$, the graph has a corresponding vertex called $(i,\ j)$.

You will get $Q$ queries, which should be processed in order. The $i$-th query, which gives you four integers $a_i,\ b_i,\ c_i,\ d_i$, is as follows.

• For each $k$ $(0 \leq k < N)$, add an edge between two vertices $((a_i+k) \bmod N,\ (b_i+k) \bmod N)$ and $((c_i+k) \bmod N,\ (d_i+k) \bmod N)$. Then, print the current number of connected components in the graph.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq a_i,\ b_i,\ c_i,\ d_i < N$
• $(a_i,\ b_i) \neq (c_i,\ d_i)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
\vdots
a_Q b_Q c_Q d_Q

Output

Print $Q$ lines. The $i$-th line should contain the number of connected components in the graph at the $i$-th query.