It was supposed to be a quiet night. Bajzek was sitting in front of the monitors, guarding the building. He worked at the Bajtocki Central Bank. The job was not very interesting, but the pay was decent, so Bajzek did not complain. Suddenly, he noticed that the signal from one of the cameras was distorted. He decided to check it. When he arrived at the scene, he saw flames bursting from one of the rooms.

"I must check on the vault..." thought Bajzek and ran to the floor above, where the room with the money was located. "I need to move them to a safe place," he muttered under his breath, but after a moment he realized that he could not just pack up all the banknotes and carry them away.

The money in the vault is arranged in $n$ stacks. Each stack contains a certain number of bundles of banknotes. One of the stacks, however, is different: it contains fake banknotes filled with ink that explodes when it leaves the vault. This is one of the famous security measures of the Bajtocki Central Bank. A fake bundle of banknotes is slightly heavier than a real one: it weighs 101 grams, while a real one weighs 100 grams. Only one stack contains fake bundles of banknotes; this stack does not contain any real bundles.

In the corner of the vault stands a very precise electronic scale, which allows you to find the weight of any set of bundles. Unfortunately, it works very slowly, and there is not much time.

Write a program that communicates with the library used to operate the scale to find the stack of fake banknotes by performing the minimum number of weighings.

Interaction

To use the library, you must include the following at the beginning of your program:

#include "skalib.h"

The library provides the following functions:

• inicjuj() This function provides information about the contents of the vault. It returns a vector containing $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le n \le 1\,000\,000$, $1 \le a_i \le 10^9$). The number $a_i$ denotes the number of bundles of banknotes in the $i$-th stack.

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

• waz(p) This function performs a weighing. Its argument is a vector containing exactly $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le a_i$). The number $p_i$ denotes the number of bundles of banknotes from the $i$-th stack that Bajzek is to place on the scale. The function returns the weight of the placed money in grams.

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

• odpowiedz(k) This function informs the library that the stack numbered $k$ ($1 \le k \le n$) contains the fake bundles of banknotes. Calling this function terminates your program.

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

Your program must not read any data (neither from standard input nor from files). It also must not write anything to files or to standard output. It may write to the standard diagnostic output (stderr), but remember that this consumes precious time.

Examples

Example 1

inicjuj() -> [1, 2]
waz([1, 0]) -> 101
odpowiedz(1)

Note

In the example above, $n = 2$, $a_1 = 1$, $a_2 = 2$. By calling waz([1, 0]), Bajzek places one bundle from the first stack on the scale. Its weight is 101, so it is fake (if the second stack contained fake bundles, the weight would be 100). Finally, the program calls odpowiedz(1). This sequence is correct and uses the minimum number of calls to waz.

Constraints

The test cases are divided into the following subtasks:

Subtasks

Let $W$ denote the minimum number of weighings needed to find the fake stack. If your program correctly finds the stack using at most $W$ calls to the waz function, it will receive 100% of the points for the test. If your program correctly finds the stack by calling this function $W + 1$ times, it will receive 50% of the points for the test, and if it calls it $W + 2$ times, it will receive 25% of the points for the test.

If your program does not find the fake stack or uses the waz function at least $W + 3$ times, it will receive 0 points for the test.

Implementation Details

A sample incorrect solution along with a sample library can be found in the dlazaw folder. The library reads data from standard input in the following format:

• First line: number of stacks $n$ and the number $k$ of the fake stack ($1 \le k \le n$).
• Second line: sizes of the stacks $a_1, \dots, a_n$.

When the odpowiedz function is called, the library prints information about whether the contestant's program correctly detected the fake stack and the number of weighings performed. In particular, the sample library does not check if the number of weighings performed was minimal.

When compiling, ensure that the files skalib.h and skalib.cpp are in the same folder as your solution. The compilation command is as follows:

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

A sample makefile is also provided, which generates the executable ska.e from ska.cpp using the command:

make