Problem J
Incredible Bartender

Edgar Chaparro.

Lars is a bartender in Scrollbar, but he is no regular bartender.

He knows incredible recipes where he can mix a little bit of this, and a little bit of that, and suddenly, he magically has a new drink. This process can even increase or decrease the total amount of liquid involved, or make drinks out of nothing. For instance, a recipe might turn $1$ dl beer and $1$ dl champagne into $3$ dl vodka. No one (least of all Lars) understands how this works, but he is able to follow these recipes consistently.

Anyway, there is no time for questions, because the bar is completely under-stocked, a bunch of customers are waiting for their drinks, and now everything depends on Lars’ ability to create drinks from seemingly nowhere to make enough of each drink to fulfil all orders.

Each recipe takes exactly $1$ minute to execute, and cannot be scaled up or down. It is no problem if Lars ends up with more drinks than required by the customers. Obviously, at no point during mixing can the amount of any drink go below $0$.

Input

The first line contains $3$ integers: the number $n$ of different drinks ($1 \leq n\leq 5$), the number $r$ of different recipes that Lars knows ($1 \leq r \leq 5$), and the amount $t$ of time he has to work in minutes ($1 \leq t \leq 15$).

Then follow $n$ lines, one for each drink, in alphabetical order. Each such line contains the name of the drink and two integers $s$ and $g$. The first integer ($0 \leq s \leq 20$, for “start”) is the initial amount and the second integer ($0 \leq g \leq 20$, for “goal”) is the amount needed to satisfy the customers, both in decilitres. At least one drink satisfies $s < g$, so Lars’ intervention is necessary. The name of each drink consists of at most $20$ lower-case letters from the English alphabet.

Then follow $r$ lines, one for each recipe, indexed $1,\ldots , r$. Each recipe contains $d$ pairs, each pair consists of an integer amount $a$ and one of the $n$ drinks. For example, the recipe “$-1$ vodka $-1$ champagne $+3$ beer” means that $1$ dl vodka and $1$ dl champagne can be used to create $3$ dl beer. In general, a negative amount $a<0$ means that the recipe consumes that amount of the specified drink, and a positive amount $a>0$ means that the recipe creates that amount. The amounts satisfy $-10\leq a \leq 10$ and $a\neq 0$. Each recipe mentions at least one drink; no recipe mentions the same drink twice; the drinks within a recipe are in alphabetical order; each recipe creates at least one type of drink (but does not have to consume anything).

Output

The output should be a list of recipes that Lars can follow in the given order to satisfy all customers. The list should be given as a single line of recipe indices separated by spaces. If there are multiple valid solutions, print any of them.

If it is impossible for Lars to produce the required amount of drinks, print “sad customers”.

3 3 6
beer 1 3
champagne 1 3
vodka 2 3
+3 beer -1 champagne -1 vodka
-1 beer +3 champagne -1 vodka
-1 beer -1 champagne +3 vodka

1 2 3 1 2 3

3 3 5
beer 1 3
champagne 1 3
vodka 2 3
+3 beer -1 champagne -1 vodka
-1 beer +3 champagne -1 vodka
-1 beer -1 champagne +3 vodka

sad customers

3 3 6
beer 1 3
champagne 1 3
vodka 1 3
+3 beer -1 champagne -1 vodka
-1 beer +3 champagne -1 vodka
-1 beer -1 champagne +3 vodka

sad customers

3 3 12
carrotjuice 1 3
darknstormy 1 3
princessmaker 1 3
+10 carrotjuice -1 darknstormy -1 princessmaker
-2 carrotjuice +2 darknstormy
-2 darknstormy +1 princessmaker

1 2 2 3 2 2 2 1 2 3 3 3

1 1 5
cokezero 0 3
+1 cokezero

1 1 1

5 1 3
gin 10 0
ginfizz 0 9
lemonjuice 12 2
simplesyrup 5 0
soda 20 0
-5 gin +10 ginfizz -3 lemonjuice -1 simplesyrup -2 soda

1

5 2 6
blacksun 0 3
orangesoda 16 4
porter 10 5
shandy 1 3
tequila 10 2
+2 blacksun -1 porter -1 tequila
-2 orangesoda -1 porter +1 shandy

2 1 2 1