题目背景
他说，如果破茧之后发现自己并不是蝴蝶，而是一只难看的蛾子，那该怎么办？
——题记
题目描述
给定一个长度为 $2^n$ 的二进制序列 $a$，该序列由 $0$ 和 $1$ 组成。最初序列的所有元素均为 $0$。你的任务是对该序列执行 $q$ 次操作：
- 翻转操作：对于给定的下标 $i$，翻转 $a_i$（即将 $a_i$ 变为 $1 - a_i$）。该操作表示为
! i。 - 查询操作：对于给定的下标 $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。
是的，你没有看错 (＠＾◡＾)
数据范围
| 子任务编号 | 子任务分值 | 测试点个数 | $ n= $ | $ q= $ | 特殊性质 |
|---|---|---|---|---|---|
| $1$ | $10$ | $8$ | $24$ | $10^6$ | 无 |
| $2$ | $10$ | $8$ | $26$ | $10^6$ | 无 |
| $3$ | $10$ | $8$ | $28$ | $10^6$ | 无 |
| $4$ | $10$ | $8$ | $30$ | $10^6$ | 无 |
| $5$ | $10$ | $8$ | $32$ | $10^6-10$ | 数据随机生成 |
| $6$ | $50$ | $20$ | $32$ | $10^6$ | 无 |
对于子任务 $5$，数据按照下面的规则随机生成，其中所有的随机事件彼此独立：
- 每个操作有 $50\%$ 的概率是翻转操作或查询操作。
- 翻转操作下标的每一个二进制位有 $70\%$ 的概率为 $0$，有 $30\%$ 的概率为 $1$。
- 查询操作下标的每一个二进制位有 $70\%$ 的概率为 $1$，有 $30\%$ 的概率为 $0$。
计分规则
假设该测试点属于一个分值 $S$ 分的子任务：
你的输出会逐行与正确输出进行比较。如果你的输出完全正确，你将获得 $S$ 分。否则，如果你的输出第一次出现错误是在第 $x$ 个操作，将使用公式 $ \left\lfloor \dfrac{x-1}{q/S} \right\rfloor $ 来计算得分。换句话说，每完整处理 $ q/S $ 次操作，你就获得 $1$ 分。
每个子任务的最终得分为其所有测试点中的最低得分。各个子任务之间相互独立，不存在任何依赖关系。