Write comments with a short summary of your solution and don't copy paste it from any where.

Solve the problem given below:

Alice and Bob are playing a game. Initially, Alice has a hidden integerx

x; Bob only knows an integerN

Nsuch that1xN

1xNand he has to findx

xby asking questions. In each question, Bob must choose an integery

y(1yN

1yN), and Alice answers 'G', 'L' or 'E' based on whetherx>y

x>y,x

x

x=yrespectively.

However, to make things more interesting, they decided that Alice can lie sometimes. In particular, she cannot lie two times in a row and whenx=y

x=y(i.e. Bob foundx

x), she has to answer 'E', so lying corresponds to answering 'G' when the correct answer is 'L' or vice versa. Alice can choose to lie at any time as long as she follows these rules.

As soon as Alice answers 'E' to some question, the game ends and Bob wins. Help Bob and win the game using no more thanK

Kquestions.

Example

Grader You 5 2 L 4 G 4 G 5 E