Poor Cinderella! Her cruel stepmother has found a really demonic plan to get rid of her. Recently she bought many bags of beans that were cursed by an evil mage. Then she told Cinderella that these beans would be her only food for the next months. Of course eating cursed beans in larger quantities is fatal for a human. Desperate, Cinderella asked the good fairy for help. The good fairy cast a counterspell on the bags, removing the curse and making the beans edible again. But even the fairy's magical powers were not sufficient to break the curse completely -- the beans in one of the bags remained cursed.
The problem is that Cinderella doesn't know which bag contains the cursed beans. However, she knows that a cursed bean weighs more than an edible one. A normal bean weighs 1 gram; a cursed one weighs 2 grams. In the kitchen Cinderella found a digital scale, which can measure any weight up to 1717 grams. (If the total weight of the items on the scale is greater, the scale will still show 1717 grams.) Help poor Cinderella find the cursed bag! You can assume that each bag contains at least 1717 and at most 100 000 beans.
In the easy test case there are 80 bags. The hard case has 10 000 bags.
In each submit, you may either use the scale or report the cursed bag. Using the scale works as follows: You open some of the bags, take some beans, place them on the scale and read their total weight.
Each submit should begin with either the word "WEIGHT" or "ANSWER" according to the action you want to perform.
"WEIGHT" must be followed by one or more pairs of numbers "X Y", where X is the number of the bag and Y is the positive number of beans taken from that particular bag. Bags are numbered consecutively beginning with 1. The list of pairs must be terminated by the pair "0 0". All numbers should be separated by whitespaces. Our reply will contain the total weight of these beans.
Example:
WEIGHT 1 2 3 4 0 0
We are weighing two beans from the bag number 1 and four beans from the bag number 3.
"ANSWER" must be followed by exactly one number -- the number of the bag with cursed beans. Our reply will indicate whether your choice was correct.
Example:
ANSWER 5
Remember that you have only 10 submits and each submit adds precious minutes to your total time!