Not magic,but logic.

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

Description

He(Harry) pulled open the next door, both of them hardly daring to look at what came next - but there was nothing very frightening in here, just a table with seven differently shaped bottles standing on it in a line.
'Snape's,' said Harry. 'What do we have to do?'
They stepped over the threshold and immediately a fire sprang up beind them in the doorway. It wasn't ordinary fire either; it was purple. At the same instant, black flames shot up in the doorway leading onwards.They were trapped.
'Look!' Hermione seized a roll of paper lying next to the bottles. Harry looked over her shoulder to read it:


Danger lies before you, while safety lies behind,

Two of us will help you, whichever you would find,

One among us seven will let you move ahead,

Another will transport the drinker back instead,

Some among our number hold only nettle wine,

And others are killers, waiting hidden in line.

Choose, unless you wish to stay here for evermore,

To help you in your choice, we give you these clues:



Now,they must make a choice, could you help them?
However, we call the bottle who can take you ahead A,and the bottle who can take you back is named B.

Input

The first line of the input is three integer N,M,P. It means there is N bottles of wine, M bottles of poison and P clues.(0<=N,M<=100,0<P<=1000)
Next P line would be one of these four:

No. i from left/right is safe/dangrous .
All wine/poison have a wine/poison on the left/right .
The A/B have a wine/poison/A/B on the left and a wine/poison/A/B on the right .
No. i from left/right cannot take you back/ahead .

Output

Output will have only one line:
If you are sure where A and B is, just tell Harry their number from left.
If you aren't sure, you only can say: 'God help them.'
If you find that's impossible, just say: 'That's impossible.'

Sample Input

2 4 6 All wine have a poison on the left . The B have a poison on the left and a poison on the right . The A have a wine on the left and a poison on the right . No. 4 from right is safe . No. 4 from left is safe . No. 2 from right cannot take you back .

Sample Output

5 2
Hint
Both PBPWAPPW and PBPWAPWP are possible solutions,where 'P' means poison and 'W' means wine.But however,we know where A and B are.

Hint

JGShining

Source

Gardon-DYGG Contest 1

提交代码