题目描述

因为正值圆周率日，Sashka 决定复习一下数学知识，尤其是圆周率与素数之间的联系。她有一个长度为 N 的排列：

P_0, P_1, ..., P_{N-1}

它是集合 {1, 2, ..., N} 的一个排列。她想找出这个排列中所有素数所在的位置，但她自己做不到，于是向你求助。

不过，Sashka 并不会把整个排列直接告诉你。相反，她只愿意回答你若干次如下形式的问题：

对于 0 <= A, B < N，是否有 P_A | P_B ？

也就是判断 P_A 是否整除 P_B。

你的任务是：在尽可能少地调用上述询问接口的前提下，找出排列中所有素数所在的位置。

---

实现要求

你需要实现如下函数：

std::vector<int> solve(int N);

评测时，这个函数会在每个测试中被调用 T 次，每次对应一个随机生成的排列，且它们的 N 相同。

你的函数需要返回排列中所有素数所在的位置，返回顺序任意。

为此，你可以调用评测器提供的函数：

bool query(int A, int B);

其中：

• A：候选除数所在的位置
• B：候选被除数所在的位置

返回值：

• 若 P_A 整除 P_B，返回 true
• 否则返回 false

---

关于素数

一个正整数是素数，当且仅当它恰好有两个正因数。

---

子任务

本题共有 2 个子任务。每个子任务只包含一个测试，但该测试中会生成 T 个随机排列。

子任务	分值	N	T	Q_target	C_score
1	20	10^3	100	175000	0.42
2	80	10^4		1000000	0.52

只有当一个子任务中的所有排列都被正确识别时，才能获得该子任务分数；最终得分还要乘以下文定义的测试结果系数。

---

评分方式

设：

• Q_target 和 C_score 为上表给定常数
• Q_contestant 为你的程序在该测试中，平均每个排列调用 query 的次数

则该测试的得分系数 r 为：

r = min(1.0, max(0.0, 1.0 - C_score * (Q_contestant - Q_target) / Q_target))

于是，该子任务的最终得分为：

子任务分值 × r

要获得正分，必须满足：

• 子任务 1：Q_contestant < 591667
• 子任务 2：Q_contestant < 2923077

---

交互示例

你的程序

solve(3)
query(0, 1)
query(0, 2)
return {1, 2}

评测器

return true
return true

你的程序

solve(3)
query(0, 1)
query(1, 2)
return {0, 1}

评测器

return false
return false

说明：为了演示，设 N = 3，T = 2。
第一组排列为 1, 2, 3，第二组排列为 2, 3, 1。

---

本地评测器

输入格式

• 第 1 行：三个整数 T, N, R
  • T：排列个数
  • N：每个排列的长度
  • R：运行模式
• 当 R = 1 时：
  • 本地评测器会自行随机生成排列
  • 你的程序应在第一行输出一个整数 S，作为随机数种子
• 当 R = 2 时：
  • 接下来第 2 行到第 1 + T 行，每行给出一个 {1, 2, ..., N} 的排列

输出格式

• 第 1 行：若某个排列未被正确识别，则输出错误信息； 否则输出所有子测试中平均每个排列的询问次数

---