阿尔贝托和比阿特丽斯两兄妹必须一起吃菠菜披萨。不过,他们都不喜欢吃菠菜,所以他们都想尽量少吃。
披萨具有严格凸多边形的形状,$$$n$$$ 顶点位于平面的整数坐标 $$$(x_1, y_1), \, (x_2, y_2), \, \dots, \, (x_n, y_n)$$$ 处。
兄弟姐妹决定按照以下方式吃披萨:轮流从阿尔贝托开始,每个兄弟姐妹选择披萨剩余部分的一个顶点,并吃掉由其两个相邻边确定的三角形。这样,在第一个 $$$n - 3$$$ 的每一圈之后,披萨都会少一个顶点。游戏在第 $$$(n - 2)$$$ 回合后结束,此时所有披萨都已吃完。
假设阿尔贝托和比阿特丽斯选择最佳吃的披萨,哪一个兄弟姐妹能吃掉最多一半的披萨?您应该找到一个有这样做策略的兄弟姐妹,并帮助他们适当地选择切片。请注意,如果阿尔贝托和比阿特丽斯选择最佳切片,他们最终可能会吃掉一半的区域。
输入
第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 100$$$) — 顶点数。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — 代表披萨初始形状的多边形第 $$$i$$$ 顶点的坐标。
保证多边形是严格凸的,并且其顶点按逆时针顺序给出。
互动
首先,您应该打印一行,其中包含字符串 $$$\texttt{Alberto}$$$ 或字符串 $$$\texttt{Beatrice}$$$ — 您将帮助赢得的兄弟姐妹。
然后,在接下来的 $$$n - 2$$$ 轮中,您将与法官轮流选择一片披萨并将其取出,如果您选择帮助阿尔贝托,则从您开始,或者如果您选择帮助比阿特丽斯,则从法官开始。
- 当轮到你的时候,打印一行包含一个之前没有选择过的整数 $$$p$$$ ($$$1 \leq p \leq n$$$) ,表示你想吃掉位于 $$$(x_p, y_p)$$$ 处的顶点确定的切片。
- 轮到裁判时,读取一个整数$$$q$$$ ($$$1 \leq q \leq n$$$),表示对方吃掉位于$$$(x_q, y_q)$$$处的顶点确定的切片。保证 $$$q$$$ 之前没有被选择过。
如果您的交互之一格式错误,则交互器会立即终止,并且您的程序会收到判决 $$$\texttt{WRONG-ANSWER}$$$。否则,如果最后您的玩家最多吃掉了一半的披萨,您将收到 $$$\texttt{CORRECT}$$$,否则您将收到 $$$\texttt{WRONG-ANSWER}$$$。
打印一行后,不要忘记结束该行并刷新输出。否则,您将得到判决$$$\texttt{TIMELIMIT}$$$。要刷新输出,请使用:
- C 中的 $$$\texttt{fflush(stdout)}$$$;
- C++ 中的 $$$\texttt{fflush(stdout)}$$$、$$$\texttt{cout <}\texttt{<lush}$$$ 或 $$$\texttt{cout.flush()}$$$;
- Java 和 Kotlin 中的 $$$\texttt{System.out.flush()}$$$;
- Python 中的 $$$\texttt{sys.stdout.flush()}$$$。
示例
输入 #1
4 0 0 6 1 5 3 1 4
输出 #1
-
输入 #2
6 0 0 2 0 3 2 2 4 0 4 -1 2
输出 #2
-
输入 #3
7 0 0 2 0 5 2 4 5 1 5 -1 4 -1 2
输出 #3
-
注意
在第一个示例中,披萨的面积为 $$$15$$$。通过吃顶点 $$$2$$$ 周围(面积 $$$6.5$$$)或顶点 $$$3$$$ 周围(面积 $$$3.5$$$)周围的切片,Alberto 可以吃掉不到一半的披萨。
在第二个样本中,可以证明,如果两个玩家吃得最佳,他们将恰好吃掉一半的披萨。因此,可以选择帮助阿尔贝托或贝阿特丽斯。
在第三个样本中,可以表明只有 Beatrice 有最多吃掉一半披萨的策略。以下是有效交互的示例(读取输入后):
$$$$$$ \begin{array}{|c|c|c|} \hline \textbf{参赛者} & \textbf{裁判} & \textbf{解释} \\ \hline \texttt{Beatrice} & & \text{参赛者将帮助 Beatrice} \\ \hline & \texttt{7} & \text{Alberto 吃掉三角形顶点 $6$、$7$、$1$ 和面积 $1$} \\ \hline \texttt{2} & & \text{Beatrice 吃掉顶点 $1$、$2$、$3$ 和面积 $2$的三角形} \\ \hline & \texttt{5} & \text{Alberto 吃掉顶点 $4$、$5$、$6$ 和面积 $1.5$的三角形} \\ \hline \texttt{4} & & \text{Beatrice 吃掉了顶点为 $3$、$4$、$6$ 且面积为 $8$的三角形} \\ \hline & \texttt{6} & \text{Alberto 吃掉了顶点为 $3$、$6$、$1$ 且面积为 $11$的三角形} \\ \hline \end{array} $$$$$$ Alberto 吃掉的总面积为$$$13.5$$$,Beatrice吃掉的总面积是$$$10$$$,不到整个披萨面积的一半。在这个交互示例中,参赛者和评委执行的动作可能不是最佳的。该过程如下图所示: