OpenKattis
National University of Singapore

What's In It For Me?

Pekka has started preparing for the beautiful summer on the beaches along the great Finnish lakes. He has started his yearly spring diet. Although the diet is very strict and boring, it has given Pekka fruitful results for the last $10$ years as well as an increased interest in the food he eats. He always reads the ingredient list of a food item before he puts it into his basket in the grocery store. He has a hard time getting a full overview of how much of each ingredient he actually puts in his body and would like your help to figure it out.

The ingredient list on a food item always lists all the ingredients, but it seldom tells you how much is used of each one of the single ingredients. It will often tell you how much is used for some of the ingredients. The ingredients list is always sorted from the ingredient with the most content to the ingredient with the least content.

Input

The first line of the input consists of a single integer $N$ indicating the number of ingredients in the thing Pekka wants to eat.
Each of the next $N$ lines describe one ingredient, and consist of one word $I$ and one number $P$, describing the name of the ingredient and the percentage of the ingredient in this piece of food – if known, otherwise it is a ’?’.
The $N$ ingredients are listed in the order on the package of the food item.

Output

For each test case, output a list of ingredients, one line for each ingredient, in the same order as they were given in the input. Each line should consist of an ingredient name $I$, and two non-negative integers $L$ and $H$, describing the minimal and maximal possible quantity of the ingredient in the actual food item.

Limits

  • $1 \leq N \leq 1000$.

  • $1 \leq \operatorname {len}(I) \leq 100$.

  • $P$ is an integer if the percentage of this ingredient is known, or a $?$ if it is not known.

  • If $P$ is known: $0 \leq P \leq 100$.

  • $0 \leq \sum (P) \leq 100$.

  • $I$ consists of the letters from A-Z and a-z.

  • Each ingredient name $I$ is unique.

  • It is guaranteed that there exists a solution.

Sample Input 1 Sample Output 1
4
Strawberries 60
Sugar ?
Water 10
Thickener ?
Strawberries 60 60
Sugar 20 30
Water 10 10
Thickener 0 10