B-智乃酱的子集与超集_牛客竞赛数据结构专题班前缀和练习题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

智乃酱有 ${N}$ 个物品，并且第 ${i}$ 个物品的权值为 $a_i$ ，对于一个含有 ${k}$ 个物品集合 $U=\left \{ a_{p_{1}},a_{p_{2}},a_{p_{3}}...a_{p_{k}} \right \}$ ，我们定义集合 ${U}$ 的价值为 $a_{p_{1}}\oplus a_{p_{2}}\oplus a_{p_{3}}\oplus...\oplus a_{p_{k}}$ ，其中 $\oplus$ 表示异或运算。即定义一个集合的价值为：该集合所拥有的物品权值之异或和。

现在智乃酱想问你 ${M}$ 个问题，对于每个问题他都会给你一个 ${k}$ 个物品集合 ${U}$ ，他想让你告诉她 ${U}$ 的所有子集的价值之和， ${U}$ 的所有超集的价值之和。

在本问题中，全集的定义为这 ${N}$ 个物品组成的集合。

输入描述:

第一行输入两个正整数表示智乃酱有个物品，个问题。
接下来一行个正整数表示物品的权值。
接下来行分别表示个问题。
每行第一个整数表示该查询中集合的元素个数，后面个正整数表示该集合中第个物品的编号为(下标从开始计算)。

输出描述:

输出 ${M}$ 行，每行输出两个整数，中间用空格隔开。

对于每个集合 ${U}$ ，输出 ${U}$ 的所有子集的价值之和， ${U}$ 的所有超集的价值之和。

示例1

输入

复制

输出

复制

说明

如果一个集合S2中的每一个元素都在集合S1中，且集合S1中可能包含S2中没有的元素，则集合S1就是S2的一个超集，反过来，S2是S1的子集。 S1是S2的超集

异或是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。