给定一个大小为 $2^n \times 2^n$ 的矩阵，初始时所有单元格均为白色。单元格的颜色可以是黑色或白色。

我们定义矩阵的“价格”如下： 1. 如果矩阵仅由一种颜色组成，则价格为 1 个硬币； 2. 否则，将矩阵平分为 4 个大小相等的子矩阵，该矩阵的价格为这 4 个子矩阵的价格之和加上 1 个硬币。

你需要处理 $q$ 次查询。每次查询给出一个行号或列号 $x$，你需要翻转该行或该列中所有单元格的颜色（即：如果单元格是白色，则变为黑色；如果单元格是黑色，则变为白色），并计算翻转后矩阵的价格。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($0 \le n \le 20, 1 \le q \le 10^6$)，其中 $n$ 表示矩阵的大小为 $2^n \times 2^n$，$q$ 表示查询次数。

接下来的 $q$ 行，每行包含两个整数 $t$ 和 $x$ ($0 \le t \le 1, 1 \le x \le 2^n$)。如果 $t = 0$，则翻转第 $x$ 行；否则，翻转第 $x$ 列。

输出格式

对于每次查询，输出矩阵的价格。

样例

输入格式 1

2 7
1 3
0 2
1 1
1 4
0 4
0 3
1 1

输出格式 1

13
17
21
17
21
17
13

说明

在样例中，每次查询后矩阵的状态如下：