题目描述

给定一个长度为 $2^n$ 的二进制序列 $a$，该序列由 $0$ 和 $1$ 组成。最初序列的所有元素均为 $0$。你的任务是对该序列执行 $q$ 次操作：

1. 翻转操作：对于给定的下标 $i$，翻转 $a_i$（即将 $a_i$ 变为 $1 - a_i$）。该操作表示为 ! i。
2. 查询操作：对于给定的下标 $i$，确定所有满足 $j \subseteq i$ 的 $a_j$ 中，$1$ 的个数是奇数还是偶数。这里 $j \subseteq i$ 意味着在 $i$ 和 $j$ 的二进制表示中，$j$ 中所有为 $1$ 的位在 $i$ 中对应的位也必须是 $1$。该操作表示为 ? i。

输入格式

第一行包含两个整数 $n$ 和 $q$，表示序列的长度为 $2^n$，接下来有 $q$ 个操作。

接下来的 $q$ 行，每一行表示一个操作，可以是以下两种形式之一：

• ! i 表示一个翻转操作。
• ? i 表示一个查询操作。

输出格式

对于每个查询操作 ? i，输出一个整数：

• 如果满足条件的 $a_j$ 中 $1$ 的个数为奇数，输出 $1$。
• 如果 $1$ 的个数为偶数，输出 $0$。

样例 1

样例 1 输入

4 10
! 4
? 15
! 2
? 12
! 8
! 5
? 10
? 7
? 13
? 15

样例 1 输出

1
1
0
1
1
0

样例 2

样例 2 输入

32 10
! 772
! 34373648
? 4286562043
? 3890741199
! 18874880
! 269484552
! 1122312
? 4277131259
! 104867841
? 3087007739

样例 2 输出

1
1
1
1

附加样例 1~100

见附件下载中的 ex_subset1~100.in 与 ex_subset1~100.out。

是的，你没有看错 (＠＾◡＾)

数据范围

对于子任务 $5$，数据按照下面的规则随机生成，其中所有的随机事件彼此独立：

• 每个操作有 $50\%$ 的概率是翻转操作或查询操作。
• 翻转操作下标的每一个二进制位有 $70\%$ 的概率为 $0$，有 $30\%$ 的概率为 $1$。
• 查询操作下标的每一个二进制位有 $70\%$ 的概率为 $1$，有 $30\%$ 的概率为 $0$。