Distinguished Polish mathematician Stanislaw Ulam proposed a two-person game. Player A chooses an integer number x from the set X=(0,1,...,2047). Player B has to find out which number was chosen by A. In order to do this he can ask questions in the form: "Is number x an element of the set Y?", where Y is any subset of X. Player A answers "TAK" (which means "YES" in Polish) or "NIE" ("NO" in Polish). Moreover he can lie at most once. Your task is to invent and implement a strategy for player B, which allows him to find the number chosen by A, using the minimal number of questions.

Example

Consider the Ulam's game for the set X={0,1,2,3}. Analyse the following sequence of questions and answers:
B: Is x in the set {0,1}?
A: TAK
B: Is x in the set {0}?
A: TAK

At that moment player B is not sure if 0 is the number chosen by A, since the second answer may be a lie.
B: Is x in the set {0}?
A: NIE

B doesn't know which of the two previous answers was correct.

B: Is x in the set {0}?
A: NIE

Player B knows that 0 is not the number he looks for. The first answer had to be correct, so the number chosen by A is 1.

B: x=1.

Task

Your task is to implement a strategy of asking questions, that allows player B to find the number x, using the minimal number of questions. Player A will be simulated by a program delivered by organizers. You have to implement a module containing the following procedures (functions in case of C/C++ languages):

• nowa_gra - this procedure will be called at the beginning of a game; this is the only moment when you can initialize your data structures;
• daj_pytanie - this procedure is used for asking a question; it should place proper values into the table pytanie described in the next paragraph;
• analizuj_odpowiedz - this procedure should read an answer to the last question from the global variable (described below) and analyse this answer; if owing to the analysis the number x can be identified, the procedure should signal it, i.e. it has to assign correct values to appropriate global variables.

The supervising program will call the procedure nowa_gra first and then it will repeat the following actions:

• calling the procedure daj_pytanie,
• answering a question,
• calling the procedure analizuj_odpowiedz

Note: Do not assume that the program simulating player A fixes the number x before starting a game. It can adjust it during the game to force your program to ask maximal number of questions. Obviously after the game it cannot be possible to prove that player A has lain more than once. Thus, you should try to minimize the number of questions which your program would have to ask in the worst case.

Communication

The communication between your module and the supervising program is provided by global variables. The question "Is x an element of Y?" is represented in procedure daj_pytanie by value of the table pytanie of type array[0..2047] of Boolean (in case of C/C++: char pytanie[2048]). The number i is an element of Y if and only if pytanie[i]=TAK, where TAK is a constant valued to TRUE in case of Pascal and a macro valued to 1 in case of C/C++ (similarly NIE is defined as FALSE in case of Pascal and 0 in case of C/C++). The answer to the question is put into the global variable odpowiedz of type Boolean (in case of C/C++ it has type char); odpowiedz = TAK if and only if the answer is positive. When your program finds the number x the procedure analizuj_odpowiedz should assign the value TAK to the variable wiem, which is of type Boolean (in case of C/C++ it has type char). The number you found should be assigned to variable x. Assigning values to variables wiem and x finishes the game. If the answer is wrong then player B loses.

Directory and files

Pascal programmers should prepare their solution in the directory C:\GRAPAS, C/C++ programmers - in the directory C:\GRAC. In the directory C:\GRAPAS (C:\GRAC) you will find the following files:

• gramod.pas (gramod.h i gramod.c) - a module containing basic definitions and declarations of global variables;
• gra.pas - a frame of a playing module; you should complete this file with definitions of functions nowa_gra, daj_pytanie and analizuj_odpowiedz (for C/C++ programmers headers of the functions are in the file gra.h, you have to write the file gra.c with definitions of these functions);
• rywal.pas (rywal.c) - an example of a supervising program using you module; it allows you to check if your unit meets the specification.

Output

The result of your work should be exactly one file: gra.pas or gra.c written to a diskette.

Notes for C/C++ programmers

C and C++ programmers have to compile multifile program. To do this it is necessary to create a project (chose New Project from Menu Project), and then add (with the Insert key) to this project all the files *.c. From this moment commands Make and Build compile and link all the files of the project.