题目描述

这是一个交互题。

给定平面上 $n$ 个点 $A_i = (x_i, y_i)$，已知所有 $x_i$ 互不相同，且所有 $y_i$ 也互不相同。你的任务是绘制连接这 $n$ 个点的折线。

折线由一个从 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$ 定义。折线包含 $n-1$ 个线段，第一个线段连接点 $A_{p_1}$ 和 $A_{p_2}$，第二个线段连接点 $A_{p_2}$ 和 $A_{p_3}$，……，最后一个线段连接点 $A_{p_{n-1}}$ 和 $A_{p_n}$。注意，线段之间可能相交。

折线的锐度定义为满足 $2 \leq i \leq n-1$ 的编号 $i$ 的数量，其中角 $\angle A_{p_{i-1}} A_{p_i} A_{p_{i+1}}$ 是锐角，即严格小于 $90^{\circ}$。

你需要解决以下四个任务：

1. 找到一条折线，使其锐度达到可能的最大值。
2. 给定整数 $c$，找到一条折线，其锐度 $\leq c$。
3. 给定整数 $c$，回答 $q$ 个查询，每个查询由一个整数 $k_i$ $(c \leq k_i \leq n - c)$ 组成。在第 $i$ 个查询中，构建一条锐度恰好为 $k_i$ 的折线。
4. 给定整数 $c$，对于从 $c$ 到 $n - c$ 的每个 $k$，构建一条锐度恰好为 $k$ 的折线 $p^{(k)}$。作为答案，提供 $n - 2c + 1$ 个数字 $\text{hash}\left(p^{(c)}\right), \text{hash}\left(p^{(c+1)}\right), \ldots, \text{hash}\left(p^{(n-c)}\right)$，其中 $\text{hash}(p) = \left( \sum_{i=1}^{n} p_i b^{i-1} \right) \bmod m$ 是排列 $p$ 的多项式哈希，参数为 $b = 10^{6} + 3$ 和 $m = 10^{9} + 7$。然后，回答 $q$ 个查询，每个查询由一个整数 $k_i$ $(c \leq k_i \leq n - c)$ 组成。在第 $i$ 个查询中，提供折线 $p^{(k_i)}$，其锐度必须恰好为 $k_i$，且哈希值必须与之前提供的 $\text{hash}\left(p^{(k_i)}\right)$ 一致。注意，查询将在提供哈希值之后出现。

保证在给定限制下，答案始终存在。

交互方式

第一行包含两个整数 $\text{task}$ 和 $\text{group}$ $(1 \leq \text{task} \leq 4, 0 \leq \text{group} \leq 21)$，分别表示需要解决的任务编号和子任务编号。

第二行包含一个整数 $n$ $(3 \leq n \leq 80000)$，表示平面上的点数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ $(|x_i|, |y_i| \leq 10^{9})$，表示点的坐标。保证所有 $x_i$ 互不相同，所有 $y_i$ 也互不相同。

如果 $\text{task} = 1$，输入数据到此结束，你需要输出一个排列，使其锐度达到最大可能值。交互到此结束。

如果 $\text{task} \neq 1$，下一行包含一个整数 $c$ $(2 \leq c \leq \frac{n}{2})$。

如果 $\text{task} = 2$，输入数据到此结束，你需要输出一个排列，其锐度 $\leq c$。交互到此结束。

如果 $\text{task} = 4$，你的程序需要输出 $n - 2c + 1$ 个整数 $\text{hash}\left(p^{(c)}\right), \text{hash}\left(p^{(c+1)}\right), \ldots, \text{hash}\left(p^{(n-c)}\right)$，其中 $0 \leq \text{hash}\left(p^{(i)}\right) < 10^{9} + 7$。注意，如果 $\text{task} = 3$，不需要执行此操作。

后续交互仅在 $\text{task} = 3$ 或 $\text{task} = 4$ 时进行。

下一行包含一个整数 $q$ $(1 \leq q \leq 50)$，表示查询数量。

随后有 $q$ 行，每行包含一个查询 $k_i$ $(c \leq k_i \leq n - c)$。作为回答，你需要在单独的一行中输出一个排列，该排列的锐度必须恰好为 $k_i$。如果 $\text{task} = 4$，该排列的哈希值必须与之前提供的哈希值一致。

注意：由于这是交互题，请确保在输出每行后添加换行符，并清空输出流缓冲区。

1 0
4
2 3
1 8
4 2
0 0

3 2 4 1

2 0
5
-2 0
-1 -1
0 1
2 -2
3 -3
2

5 4 3 1 2

3 0
6
0 0
1 1
2 2
3 -3
4 -2
5 -1
2
3
2

3

4

1 2 3 4 5 6

4 5 6 1 3 2

6 2 4 3 5 1

4 0
5
-2 -1
-1 1
1 6
0 -3
2 0
2

2
2

3

534735187 776162084


4 5 1 2 3

1 3 2 5 4

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	任务类型 ($\text{task}$)	$n$ 限制	$c$ 限制	附加限制	子任务依赖	备注
$1$	$8$	$1$	$n \leq 20000$		$x_i < x_{i+1}$，$y_i < y_{i+1}$
$2$	$6$		$n \leq 10$		点坐标随机生成
$3$	$5$		$n \leq 1000$			$2$
$4$	$5$		$n \leq 20000$			$2 \sim 3$
$5$	$6$					$1 \sim 4$
$6$	$17$	$2$	$n = 80000$	$c = 800$
$7$	$7$	$3$			$x_i < x_{i+1}$，$y_i < y_{i+1}$
$8$	$4$		$n = 50$	$c = 25$	点坐标随机生成
$9$	$4$		$n = 200$	$c = 80$
$10$	$4$		$n = 1000$	$c = 300$
$11$	$3$		$n = 5000$	$c = 600$
$12$	$3$		$n = 80000$	$c = 35000$
$13$	$3$			$c = 5000$		$12$
$14$	$3$			$c = 2000$		$12 \sim 13$
$15$	$2$			$c = 800$		$7, 12 \sim 14$
$16$	$6$	$4$			$x_i < x_{i+1}$，$y_i < y_{i+1}$
$17$	$3$		$n = 5000$	$c = 600$	点坐标随机生成
$18$	$3$		$n = 80000$	$c = 35000$
$19$	$3$			$c = 5000$		$18$
$20$	$3$			$c = 2000$		$18 \sim 19$
$21$	$2$			$c = 800$		$16, 18 \sim 20$