{"raw_statement":[{"iden":"problem statement","content":"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)$.\nYou 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.\n\n*   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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $0 \\leq a_i,\\ b_i,\\ c_i,\\ d_i < N$\n*   $(a_i,\\ b_i) \\neq (c_i,\\ d_i)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$a_1$ $b_1$ $c_1$ $d_1$\n$a_2$ $b_2$ $c_2$ $d_2$\n$\\vdots$\n$a_Q$ $b_Q$ $c_Q$ $d_Q$"},{"iden":"sample input 1","content":"3 3\n0 0 1 2\n2 0 0 0\n1 1 2 2"},{"iden":"sample output 1","content":"6\n4\n4\n\nThe first query adds an edge between $(0,\\ 0),\\ (1,\\ 2)$, between $(1,\\ 1),\\ (2,\\ 0)$, and between $(2,\\ 2),\\ (0,\\ 1)$, changing the number of connected components from $9$ to $6$."},{"iden":"sample input 2","content":"4 3\n0 0 2 2\n2 3 1 2\n1 1 3 3"},{"iden":"sample output 2","content":"14\n11\n11\n\nThe graph after queries may not be simple."},{"iden":"sample input 3","content":"6 5\n0 0 1 1\n1 2 3 4\n1 1 5 3\n2 0 1 5\n5 0 3 3"},{"iden":"sample output 3","content":"31\n27\n21\n21\n19"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}