Jasiu 喜欢和朋友们玩跳房子游戏。他们决定对游戏规则进行一些改进。起初，人行道上画了 $N$ 个方格，一个接一个地排列。方格从左到右依次编号为 $1$ 及以上。某些方格上放有单个鹅卵石。每个玩家选择一个起始方格，以及一个大于 $1$ 的整数 $K$。然后，从选定的方格开始，每次跳过 $K$ 个方格，直到跳出第 $N$ 个方格为止。玩家的得分等于跳跃过程中所经过的带有鹅卵石的方格数量。现在轮到 Jasiu 了，他非常想获得尽可能多的分数。已知鹅卵石的位置，请计算他能获得的最大分数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^6$)，表示方格的数量。第二行包含一个长度为 $N$ 的字符串，由字符 . 和/或 # 组成。如果第 $i$ 个字符是 #，则表示第 $i$ 号方格上有一个鹅卵石，否则该方格为空。

输出格式

第一行（也是唯一一行）应包含一个整数，表示 Jasiu 可以获得的最大分数。

样例

输入格式 1

8
#..#...#

输出格式 1

2

输入格式 2

6
####..

输出格式 2

2

输入格式 3

9
#.#..#..#

输出格式 3

3

2014 年的初中生现在已成为参加算法竞赛的专业人士，我们期望他们能解决更具挑战性的任务。在我们的版本中，鹅卵石的布局不再是一成不变的——我们从一个拥有 $n$ 个方格的空人行道开始，孩子们在游戏过程中会不断添加或移除鹅卵石。在人行道上的每一次变动后，Jasiu 都想知道他能获得的最大游戏分数是多少。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10\,000\,000, 1 \le q \le 1\,000\,000$)，分别表示人行道上的方格数量和需要考虑的事件数量。

接下来的 $q$ 行包含事件描述；第 $i$ 行包含一个整数 $a_i$ ($1 \le a_i \le n$)，表示第 $i$ 个事件是在方格 $a_i$ 上添加一个鹅卵石（如果那里还没有鹅卵石）或从方格 $a_i$ 上移除一个鹅卵石（如果那里有鹅卵石）。

输出格式

输出应包含恰好 $q$ 行；第 $i$ 行应包含一个整数，表示在第 $i$ 个事件发生后 Jasiu 可以获得的最大分数。

样例

输入格式 1

9 10
1
4
8
2
3
8
6
9
2
4

输出格式 1

1
2
2
3
3
2
3
3
3
3

说明

样例说明：在前三次事件之后，我们得到了原始任务中的第一种（左侧）情况（多了一个第九个方格，它是空的，因此不影响得分）。在接下来的三次事件之后，我们得到了第二种（中间）情况，最后得到了第三种（右侧）情况。