Description

小云最近在学习「最大权重独立集（Maximum-Weight Independent Set, MWIS）」的算法。

根据定义，一张无向图里的顶点子集合 $I$ 要被称作「独立集」的话，需要满足 $I$ 集合中任两个顶点在原图上皆互不相邻的条件。而「最大权重独立集」则是所有可能的「独立集」中，点权重总和最大的一组。

今天小云发现，假如这张无向图是一条链（Chain）的话，那要找到「最大权重独立集」变得超级简单！他向小成分享这件事之后，小成却反问:「那你知道怎么有效率地回答一条链上面的『区间最大权重独立集询问』吗？」

经过一番研究后，小云发现，即使在不知道链上每个节点的具体权重下，也能找到它的最大权重独立集，甚至能用来解决区间询问。于是，他列了以下这道难题给小成：

「给定一条包含 $n$ 个顶点编号为 $1, 2, \ldots, n$ 的链（chain），其中对于任何的 $1 \leq i < n$，顶点 $i$ 与顶点 $i+1$ 之间皆有一条无向边，且对于任何 $1 \leq i \leq n$，顶点 $i$ 的权重为一个正整数 $w_i$，请回答 $q$ 个『区间最大权重独立集询问 (Range MWIS Query)』。」

「在区间最大权重独立集询问中，对于满足 $1 \leq l \leq r \leq n$ 的任意区间，你必须回答我顶点 $l, l + 1, \ldots, r$ 之间的最大权重独立集是什么。」

小云接着补充。

「当然，在一无所知的情况下不可能解决这个问题，所以我允许你执行数次『权重和比较询问』：任选两个顶点的子集，我会告诉你哪一个子集的顶点权重和比较大。」

请协助小成，在执行尽量少次『顶点子集权重比较』的情况下，回答所有待询问区间里的最大权重独立集！

实现细节

你需要实现两个函数 init() 与 range_MWIS_query()：

void init(int n);

• 对于每一组测试数据，正式评分程序会调用你实现的 init() 函数恰好 $1$ 次。
• $n$ 代表顶点的数量。

std::vector<int> range_MWIS_query(int l, int r);

• 对于每一组测试数据，正式评分程序会调用你实现的 range_MWIS_query() 函数恰好 $q$ 次。
• 保证在调用完 init() 后才会调用此函数。
• range_MWIS_query() 需要返回一个数组 $x_1, x_2, \ldots, x_m$。
• 数组 $x$ 代表了该询问区间的最大权重独立集包含的顶点编号。
• 对于所有 $1\le i \le m$，皆须保证 $l \leq x_i \leq r$。
• 对于所有 $1\le i < j \le m$，皆须保证 $|x_i - x_j| > 1$。

此外，在实现时可以调用 compare_subsets() 这个函数。

bool compare_subsets(const std::vector<int>& a, const std::vector<int>& b);

• $a$ 是一个数组，其描述了 $\{1, 2, \ldots, n\}$ 的子集。
• $b$ 是一个数组，其描述了 $\{1, 2, \ldots, n\}$ 的子集。
• $a$ 内不能有重复的数字。
• $b$ 内不能有重复的数字。
• 若集合 $a$ 内的顶点的权重和比集合 $b$ 小，则该函数会返回布尔值 true，否则会返回布尔值 false。
• 示例评分程序内的 compare_subsets() 实现与实际评分程序内的实现完全相同。

交互范例

一个可能被评为 Accepted 的交互例子显示如下：

评分程序端	参赛者端
调用 init( $5$ )。
	调用 compare_subsets( $[1]$, $[2]$ )。
返回 true。
	调用 compare_subsets( $[3]$, $[4]$ )。
返回 false。
	返回 void()
调用 range_MWIS_query($2, 5$)
	调用 compare_subsets( $[2, 5]$, $[1, 3, 5]$ )。
返回 true。
	返回 $[2, 4]$
调用 range_MWIS_query($1, 5$)
	返回 $[1, 3, 5]$

Input Format

示例评分程序采用以下格式输入：

$$\begin{aligned} &n \ q \\ &w_1 \ w_2 \ \ldots \ w_n \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_q \ r_q \end{aligned}$$

请注意，正式的评分程序一定不会采用以上格式输入。请不要自行处理输入输出。

Output Format

示例评分程序首先调用 init($n$)，接着示例评分程序会调用 $q$ 次 range_MWIS_query($l_i, r_i$)。接着，若示例评分程序检测到从 init 或 range_MWIS_query 对 compare_subsets 的调用有任何不合法，此程序将输出

Wrong Answer: msg

后并终止程序执行，其中 $msg$ 为下列其中之一的错误信息：

• Invalid vertex number: v: 你的程序传入 compare_subsets 的集合中有不介于 $1\sim n$ 之间的数字 $v$。
• Duplicate vertex numbers: v: 你的程序传入 compare_subsets 的集合中有重复的数字 $v$。

否则，示例评分程序将会以下列格式印在标准输出中：

$$\begin{aligned} &m_1 \\ &x_{1, 1} \ x_{1, 2} \ \ldots \ x_{1, m_1} \\ &m_2 \\ &x_{2, 1} \ x_{2, 2} \ \ldots \ x_{2, m_2} \\ &\vdots \\ &m_q \\ &x_{q, 1} \ x_{q, 2} \ \ldots \ x_{q, m_q} \\ &\text{Accepted:} \ Q_{init} \ Q_{query} \end{aligned}$$

其中，

• $m_i$ 为第 $i$ 次调用 range_MWIS_query() 时你返回的数组长度。
• $x_{i, j}$ 为第 $i$ 次调用 range_MWIS_query() 时你返回的数组的第 $j$ 项。
• $Q_{init}$ 与 $Q_{query}$ 为根据你的程序调用 compare_subsets 的次数得来的数值，详细定义请见评分说明栏位。

Hint

对于每一组测试数据，若你的程序在函数 init() 中调用 compare_subsets 的次数为 $x$、在第 $i$ 次 range_MWIS_query() 中调用 compare_subsets 的次数为 $y_i$，则定义 $Q_{init}$ 与 $Q_{query}$ 为：

$$\begin{cases} Q_{init} = \left\lceil \displaystyle\frac{x}{n} \right\rceil\\ Q_{query} = \displaystyle\max_{1 \leq i \leq q} y_i \end{cases}$$

根据 $Q_{init}$ 与 $Q_{query}$，你将得到两个分数比重 $W_{init}$ 与 $W_{query}$：

$$W_{init} = \begin{cases} 1.0 & \text{ 若 $Q_{init}\le 3$；}\\ 1.0 - 0.07 \cdot (Q_{init} - 3) & \text{ 若 $3 < Q_{init} \le 10$；}\\ 0.5 - 0.04 \cdot (Q_{init} - 10) & \text{ 若 $10 < Q_{init} \le 20$；}\\ 0 & \text{ 若 $Q_{init} > 20$。} \end{cases}$$$$W_{query} = \begin{cases} 1.0 & \text{ 若 $Q_{query}\le 1$；}\\ 1.0 - 0.1 \cdot (Q_{query} - 1) & \text{ 若 $1 < Q_{query} \le 10$；}\\ 0 & \text{ 若 $Q_{query} > 10$。} \end{cases}$$

你的最终比重 $W$ 会是两者相乘，也就是：

$$W = W_{init}\cdot W_{query}$$

本题共有 3 组子任务，条件限制如下所示。 每一组可有一或多组测试数据，你在该子任务的得分为所有测试数据中分数比重 $W$ 的最小值，乘以该子任务的总分。

子任务	分数	额外输入限制
1	16	$l = 1$。
2	11	对于所有询问的区间 $[l, r]$，区间 $[1, r]$ 的最大权重独立集唯一且不包含顶点 $l + 1$。
3	73	无额外限制。

数据范围

• $1\leq n\le2000$
• $1\leq q\le2000$
• $1\leq l\leq r\leq n$