这是一个平静的夜晚。Bajzek 坐在监视器前，守护着大楼。他在巴伊特中央银行（Bajtocki Bank Centralny）工作。这份工作虽然没什么意思，但薪水还算体面，所以 Bajzek 并没有抱怨。突然，他注意到其中一个摄像头的信号受到了干扰。他决定去查看一下。当他到达现场时，看到其中一个房间里冒出了火焰。

“我得去检查一下金库……”Bajzek 心想，于是跑到了楼上存放钱财的房间。“我得把它们转移到安全的地方，”他喃喃自语，但片刻后他意识到，他不能就这样简单地把所有的钞票打包带走……

金库里的钱被堆成了 $n$ 堆。每一堆都包含一定数量的钞票捆。然而，其中有一堆与众不同：它包含着装满油漆的假钞，一旦离开金库就会爆炸。这是巴伊特中央银行著名的安全措施之一。假钞捆比真钞捆稍微重一点：它重 $101$ 克，而真钞捆重 $100$ 克。只有一堆包含假钞捆；这一堆里不包含任何真钞捆。

金库角落里有一台非常精密的电子秤，可以称出任意一组钞票捆的重量。遗憾的是，它的工作速度非常慢，而且时间紧迫。

请编写一个与称重库进行交互的程序，通过执行最少次数的称重来找到装有假钞的那一堆。

交互

要使用该库，必须在程序开头包含：

#include "skalib.h"

该库提供以下函数：

• inicjuj() 该函数提供有关金库内容的信息。它返回一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的向量 ($1 \le n \le 1\,000\,000$, $1 \le a_i \le 10^9$)。数字 $a_i$ 表示第 $i$ 堆中钞票捆的数量。

  • C++: vector<int> inicjuj();

• waz(p) 该函数执行一次称重。其参数是一个包含恰好 $n$ 个整数 $p_1, p_2, \dots, p_n$ 的向量 ($0 \le p_i \le a_i$)。数字 $p_i$ 表示 Bajzek 要放到秤上的第 $i$ 堆钞票捆的数量。函数返回所放钞票的总重量（以克为单位）。

  • C++: long long waz(const vector<int>& p);

• odpowiedz(k) 该函数用于向库报告第 $k$ 堆 ($1 \le k \le n$) 包含假钞捆。调用此函数将结束你的程序。

  • C++: void odpowiedz(int k);

你的程序不得读取任何数据（无论是从标准输入还是从文件）。它也不得向文件或标准输出写入任何内容。它可以向标准错误输出（stderr）写入内容，但请记住，这会消耗宝贵的时间。

样例

下表展示了函数调用的示例序列。

上述程序运行是正确的。它使用了最少次数的 waz 函数调用，因此将获得满分。

评分

设 $W$ 为找到假钞堆所需的最小称重次数。如果你的程序在调用 waz 函数不超过 $W$ 次的情况下正确找到了假钞堆，则该测试点得 100% 的分数。如果你的程序在调用该函数 $W + 1$ 次后正确找到，则得 50% 的分数；如果调用 $W + 2$ 次，则得 25% 的分数。

如果你的程序未能找到假钞堆，或者调用 waz 函数的次数达到或超过 $W + 3$ 次，则该测试点得 0 分。

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。

实验

一个错误的示例解决方案以及示例库位于 dlazaw 文件夹中。该库从标准输入读取以下格式的数据：

• 第一行：堆的数量 $n$ 以及假钞堆的编号 $k$ ($1 \le k \le n$)，
• 第二行：各堆的大小 $a_1, \dots, a_n$。

当调用 odpowiedz 函数时，库会输出选手程序是否正确检测到了假钞堆，以及执行的称重次数。特别需要注意的是，示例库不会检查称重次数是否为最小值。

编译时，请确保 skalib.h 和 skalib.cpp 文件与你的解决方案位于同一文件夹中。编译命令如下：

g++ -O3 -static skalib.cpp ska.cpp -std=c++17

此外还提供了一个示例 makefile，可以通过以下命令从 ska.cpp 生成可执行文件 ska.e：

make