Guess the number P67099


Statement
 

pdf   zip

thehtml

Alfredo and Beatriz are playing the well known game “Guess the number”. Alfredo has thought a number between 1 and 500, and Beatriz has 10 attempts to guess it. For each attempt of Beatriz, Alfredo has to answer “greater” (if Beatriz said a number less than the one that Alfredo thought) or “less” (if the said number was greater).

Your task in this problem is the following one: assuming that Beatriz has already done 9 attempts, none of them has been succesful, you must find out if these attempts are enough to find out the number thought by Alfredo (and, therefore, Beatriz will guess in the tenth attempt if she says that number) or if, otherwise, it could be many possible answers.

Input

The input contains in a line the number n of cases. n lines follow, each one of them describes a case. A case is formed by 9 pairs g a, separated by spaces, where g is a number between 1 and 500 proposed by Beatriz and a is the answer that Alfredo gave: the signal ‘+’ indicates that the answer of Alfredo is “Greater”, while the signal ‘-’ indicates “Less”.

Alfredo never lies nor is wrong in his answers.

Output The output consists of n lines, each one of them gives the solution of a case. Your program must print the number in a line if you can certainly know the number thought by Alfredo. Otherwise, it must print ‘?’ in a line (Follow the format of the instances).

Public test cases
  • Input

    6
    250 - 125 - 65 - 40 - 21 - 8 - 4 - 2 - 2 -
    250 - 125 - 65 - 40 - 21 - 8 - 4 - 3 - 3 -
    250 - 125 - 62 - 31 + 46 - 38 + 34 + 40 + 43 -
    250 - 125 - 62 - 31 - 15 - 7 + 11 - 9 - 10 -
    250 - 125 - 62 - 31 - 15 - 7 + 11 - 9 + 9 +
    250 - 125 - 62 - 31 - 15 - 7 + 11 + 17 - 14 -
    
    
    

    Output

    1
    ?
    ?
    8
    10
    ?
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python