You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现有一个位数组（Bitset）容器，支持以下操作：设置某位的值、翻转某位的值、查询某位的值、按位与操作、按位或操作、按位异或操作和统计置位位数。你需要实现这个位数组，并处理可能的边界情况。具体规则如下：

1. 设置操作：将指定位设置为指定值（0或1）。
2. 翻转操作：将指定位的值取反（0变1，1变0）。
3. 查询操作：获取指定位的值。
4. 与操作：将当前位数组与另一个位数组按位与，并更新当前位数组。
5. 或操作：将当前位数组与另一个位数组按位或，并更新当前位数组。
6. 异或操作：将当前位数组与另一个位数组按位异或，并更新当前位数组。
7. 统计操作：返回位数组中值为1的位的数量。

操作完成后，需输出最终位数组的二进制表示（从最高位到最低位）。

输入格式

• 第一行输入两个整数n（1 ≤ n ≤ 1000000）和q（1 ≤ q ≤ 1000000），分别表示位数组的长度和操作的总次数。
• 初始时，位数组的所有位均为0。
• 接下来q行，每行表示一次操作，格式如下：
  • 设置操作：1 pos val（将位置pos的位设置为val，val为0或1，位置从0开始）。
  • 翻转操作：2 pos（将位置pos的位翻转）。
  • 查询操作：3 pos（查询位置pos的位的值）。
  • 与操作：4 s（将当前位数组与二进制字符串s按位与，s的长度为n）。
  • 或操作：5 s（将当前位数组与二进制字符串s按位或，s的长度为n）。
  • 异或操作：6 s（将当前位数组与二进制字符串s按位异或，s的长度为n）。
  • 统计操作：7（返回位数组中值为1的位的数量）。

输出格式

• 对于每次查询操作（操作3），输出一行：
  • 若位置合法，输出该位的值（0或1）；
• 若位置不合法，输出-1。
• 对于每次统计操作（操作7），输出一行整数，表示位数组中值为1的位的数量。
• 所有操作完成后，输出一行：
  • 位数组的二进制表示（从最高位到最低位）。若位数组为空，输出空行。

样例 1 输入

5 6
1 2 1
2 3
4 01010
7
3 3
5 01100

样例 1 输出

1
1
01100

样例说明

1. 初始状态：位数组为00000。
2. 设置操作：将位置2的位设置为1，位数组变为00100。
3. 翻转操作：将位置3的位翻转，位数组变为00110。
4. 与操作：与二进制字符串01010按位与，结果为00010。
5. 统计操作：值为1的位有1个，输出1。
6. 查询操作：位置3的位为0，输出0。
7. 或操作：与二进制字符串01100按位或，结果为01110。
8. 最终输出：位数组的二进制表示为01110。

测试点约束

• 位数组长度 n ≤ 1000000。
• 操作次数 q ≤ 1000000。
• 所有位置pos满足0 ≤ pos < n。
• 所有二进制字符串s的长度均为n。
• 注意：字符串第一位是最高位
• 4、5、6操作最多总共出现一次

提示

• 位运算：熟悉按位与、或、异或的运算规则。
• 边界检查：所有涉及位置的操作需检查位置是否合法。
• 高效实现：统计操作的时间复杂度应为O(n)。