Bajtek and Bajtyna, young and madly in love, have found themselves in quite a predicament. The evil wizard Bitocy has kidnapped Bajtyna, hoping for a hefty ransom. Bajtek, however, does not give up — he is not very wealthy, so he decided to rescue his beloved. Bitocy does not like hand-to-hand combat, so he proposed a different solution to the whole situation. If the young man guesses which floor of the tower his beloved is imprisoned on, the wizard will set her free.

There are many floors — they are numbered from $1$ to $n$. The only help for Bajtek can be questions asked to the wizard. The questions must be of the form "Is Bajtyna above/below floor $x$?". Of course, Bajtek can choose exactly one of the words "above" or "below", and also freely set the number $x$. Bitocy always answers such a question truthfully, but he demands a payment of $a$ bajtalars if the answer is "yes", or $b$ bajtalars if the answer is "no". Well, if Bajtek becomes too poor and Bitocy becomes excessively rich, Bajtyna might decide to stay with the wizard...

Bajtek is wondering what questions to ask. Unfortunately, Bajtyna hears the entire conversation, i.e., Bajtek's subsequent questions and Bitocy's answers, and she is a very frugal person. If Bajtek spends even one bajtalar more than is (in the worst case) necessary to determine her location, she will be mortally offended and leave with Bitocy. More precisely, if at any moment of the conversation it can be deduced that from that moment on, regardless of Bitocy's further answers, Bajtek can guess Bajtyna's location by spending no more than $K$ bajtalars, and from that moment on Bajtek spends an amount greater than $K$, his chances with Bajtyna will drop to zero (points for a given test). Help Bajtek!

Interaction

You should implement a program that solves Bajtek's problem using the provided library (simulating the wizard Bitocy). To use the library, you must include the following in your program:

• C/C++: #include "poslib.h"
• Pascal: uses poslib;

The library provides three procedures and functions:

• inicjuj — provides the number of floors $n$ and the costs $a$ and $b$. It should be used exactly once, at the very beginning of the program's execution.
  • C/C++: void inicjuj(int *n, int *a, int *b);
  • Pascal: procedure inicjuj(var n, a, b: longint);
• pytaj — the character c denotes the type of question ('W' for above or 'N' for below), and x is the floor number. The result of the function is the boolean value of the wizard's answer. Your program can use this function any number of times.
  • C/C++: int pytaj(char c, int x); (0 means false, and 1 means true),
  • Pascal: function pytaj(c: char; x: longint): boolean;
• odpowiedz — using this procedure/function, you provide the floor number where Bajtyna is located. It should be used exactly once. Its execution will terminate your program.
  • C/C++: void odpowiedz(int wynik);
  • Pascal: procedure odpowiedz(wynik: longint);

Your program must not open any files or use standard input and output. The solution will be compiled with the library using the following commands:

• C: gcc -O2 -static poslib.c pos.c -lm
• C++: g++ -O2 -static poslib.c pos.cpp -lm
• Pascal: ppc386 -O2 -XS -Xt pos.pas

In the /home/zawodnik/rozw/lib directory, you can find example library files and non-optimal solutions illustrating how to use them. For the compilation commands above to work, the library files should be located in the current directory.

Constraints

You may assume that $1 \leqslant n \leqslant 10^9$ and $1 \leqslant a, b \leqslant 10\,000$.

Examples

Example 1

The above interaction sequence is correct, but non-optimal, so the program would not receive points for such a test. In particular, a well-written program is able to ask questions for the data $n = 5$, $a = 1$, $b = 2$ in such a way as to spend at most 4 bajtalars in every case.