{"raw_statement":[{"iden":"background","content":"搬运自 <http://czoj.com.cn/p/955>。数据为民间数据。"},{"iden":"statement","content":"小 Y 有一个 $n\\times n$ 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第 $1,3,5\\cdots$ 个格子是白色，第 $2,4,6\\cdots$ 个格子是黑色，第二行第 $2,4,6\\cdots$ 个格子是白色，第 $1,3,5\\cdots$ 个格子是黑色，如下图所示。\n\n\n$$\n\\def\\b{\\color{ff}\\rule{10px}{10px}\\kern{1px}}\n\\def\\w{\\color{white}\\rule{10px}{10px}\\kern{1px}}\n\\def\\bg{\\color{black}\\rule{33.5px}{33.5px}}\n\\def\\eps{\\\\[-39.5px]}\n\\def\\ep{\\\\[-5.5px]}\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\b\\w\\b\\ep\n\\w\\b\\w\n\\end{aligned}\n$$\n\n小 Y 会进行 $q$ 次操作，每次操作会将某一行或者某一列的所有格子的颜色反转，即白色格子变成黑色格子，黑色格子变成白色格子。\n\n小 Y 想知道，在每次操作之后，一共有多少个同颜色（全黑或全白）的连通区域。这里联通指的是**四连通**，即两个格子之间有边相邻才算联通。\n\n"},{"iden":"input","content":"第 $1$ 行 $2$ 个正整数 $n,q$，表示棋盘的大小和操作的次数。\n\n第 $2$ 到 $q+1$ 行每行 $2$ 个正整数 $\\text{opt}_i,a_i$，若 $\\text{opt}_i=1$ 则表示反转的是行，$\\text{opt}_i=2$ 则表示反转的是列，$a_i$ 表示反转的是第几行（列）。"},{"iden":"output","content":"输出 $q$ 行每行一个整数，表示在经过该次操作后，一共有多少个同颜色的联通区域。\n\n"},{"iden":"note","content":"### 样例 $\\textbf 1$ 解释\n$$\n\\def\\b{\\color{ff}\\rule{10px}{10px}\\kern{1px}}\n\\def\\w{\\color{white}\\rule{10px}{10px}\\kern{1px}}\n\\def\\bg{\\color{black}\\rule{33.5px}{33.5px}}\n\\def\\eps{\\\\[-39.5px]}\n\\def\\ep{\\\\[-5.5px]}\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\b\\w\\b\\ep\n\\w\\b\\w\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\w\\ep\n\\w\\b\\w\\ep\n\\w\\b\\w\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\b\\ep\n\\w\\b\\b\\ep\n\\w\\b\\b\n\\end{aligned}\n\\to\n\\begin{aligned}\n\\bg\\eps\n\\w\\b\\b\\ep\n\\b\\w\\w\\ep\n\\w\\b\\b\n\\end{aligned}\n$$\n\n### 数据范围\n对于所有数据，$1≤q, n≤10^5, 1≤\\text{opt}_i≤2, 1≤a_i≤n$。\n\n|测试点编号|$n$|$q$|特殊性质|\n|:-:|:-:|:-:|:-:|\n|$1\\sim4$|$\\le 4$|$\\le 10$|无|\n|$5\\sim6$|$\\le10^5$|$=1$|无|\n|$7\\sim9$|$\\le10^5$|$\\le10^5$|$\\alpha$|\n|$10$|$\\le10^5$|$\\le10^5$|无|\n\n- 特殊性质 $\\alpha$：保证同一个测试点所有的 $\\text{opt}_i$ 均相等。"}],"translated_statement":null,"sample_group":[["3 3\n1 2\n2 3\n1 2","3\n2\n6"],["100000 1\n1 1","9999900000"],["15000 5\n1 90\n1 1231\n1 91\n1 1233\n1 1232","224970000\n224940000\n224940000\n224910000\n224940000"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}