主厨金东贤自称可以制作五花八门的酱料。事实果真如此吗？你作为烹饪比赛的评委，打算测量金东贤主厨制作酱料的能力。

比赛现场有 $N$ 种食材。每种食材编号为 $0,1,\dots,N-1$。金东贤主厨能够制作的酱料由其中 $2$ 种或 $3$ 种食材组成。对于任意两个不同的酱料，它们所包含的食材集合不能完全相同（但可以有部分食材重合）。

数学上，主厨能够制作的酱料构成一个集合 $X$。$X$ 的每个元素 $S$ 都是 $\{0,1,\dots,N-1\}$ 的子集，且 $|S|$ 为 $2$ 或 $3$。根据集合的一般定义，集合中不存在重复元素。

作为评委，你需要求出主厨可以制作的酱料总数 $|X|$。虽然不会直接给出关于 $X$ 的信息，但你可以通过盲测来获得相关信息。

盲测按如下方式进行：

• 你可以选择食材集合 $\{0,1,\dots,N-1\}$ 的一个子集 $Y$ 放入锅中交给主厨。但由于锅的容量有限，一次最多只能放入 $\lceil \frac{N}{2} \rceil + 1$ 种食材，即必须满足 $|Y| \le \lceil \frac{N}{2} \rceil + 1$。其中 $\lceil t \rceil$ 表示不小于实数 $t$ 的最小整数。
• 主厨会告诉你，仅使用锅中食材可以制作多少种酱料。也就是说，你将得到 $f(Y) = |\{S \in X \mid S \subseteq Y\}|$。

你的目标是在尽可能少的盲测次数下，准确求出 $|X|$。

实现细节

你需要实现以下函数：

int solve(int N)

• 参数：$N$，食材的数量。
• 该函数需要返回 $|X|$。
• 该函数只会被调用一次。

函数内部，你可以调用以下函数。

int query(vector<int> Y)

• $Y$ 的每个元素表示一个食材编号。
• $Y$ 中的元素必须互不相同。
• 必须满足 $0 \le Y[i] \le N - 1$（$0 \le i \le |Y|-1$）。
• 必须满足 $|Y| \le \lceil \frac{N}{2} \rceil + 1$。
• 该函数返回 $f(Y) = |\{S \in X \mid S \subseteq Y\}|$。
• 在每个测试用例中，该函数最多可以调用 $3000$ 次。

限制

• $6 \le N \le 1000$
• $1 \le |X| \le 50000$
• 对所有 $S \in X$，有 $|S| \in \{2,3\}$。
• 本题中的评测器不是自适应（adaptive）的，即集合 $X$ 在调用 solve 之前已经固定。

子任务

评分方式

若在某个子任务中，你的程序在任一测试用例上未能正确返回 $|X|$，则该子任务得分为 $0$。

若在某个子任务的所有测试用例中都正确返回 $|X|$，则该子任务得分按如下规则计算。

设该子任务所有测试用例中使用的查询次数（query 调用次数）的最大值为 $Q$。

子任务 1, 2

• 若 $Q \le 3000$，则获得该子任务分值的 $100\%$。

子任务 3, 4

• 若 $Q \le 41$，则获得该子任务分值的 $100\%$。
• 若 $41 < Q \le 3000$，则获得该子任务分值乘以
  $0.5 + \frac{2Q}{41}$ 的比例。

样例数据

设 $N=6$，主厨能够制作的酱料为 $X = \{\{0,1\}, \{2,3,4\}\}$，因此 $|X|=2$。

锅的最大容量为 $\lceil \frac{6}{2} \rceil + 1 = 4$。

评测器首先调用：

solve(6)

选手代码可以进行如下交互：

query({0,1,2});
query({2,3,4});
query({0,2,3,5});

由于 $\{0,1\} \subseteq \{0,1,2\}$ 且 $\{2,3,4\} \not\subseteq \{0,1,2\}$，因此 query({0,1,2}) 返回 $1$。

由于 $\{0,1\} \not\subseteq \{2,3,4\}$ 且 $\{2,3,4\} \subseteq \{2,3,4\}$，因此 query({2,3,4}) 返回 $1$。

因为 $\{0,2,3,5\}$ 不包含 $X$ 中的任何元素，因此 query({0,2,3,5}) 返回 $0$。

最终，选手在 solve(6) 中返回 $2$，提交正确答案。

实现细节

样例评测器的输入格式如下：

• 第 1 行：$N$
• 第 2 行：$K$（即 $|X|$）
• 对于所有 $0 \le i < K$：
  • 第 $3+i$ 行：$L\ a_0\ a_1\ \dots\ a_{L-1}$
    • $2 \le L \le 3$
    • $0 \le a_j \le N-1$
    • $a_0,a_1,\dots,a_{L-1}$ 互不相同
    • $\{a_0,a_1,\dots,a_{L-1}\} \in X$

样例评测器输出格式如下：

• 第 1 行：solve 函数返回的值
• 第 2 行：query 函数被调用的次数