Problem J
Popcorn Button

Caitlyn is optimizing her morning routine. First thing each morning, she heats up her breakfast in her new hextech microwave oven. Caitlyn is a very precise person. When she presses a button, she releases the button at exactly the end of the second. The button takes effect exactly at the end of this second.

Initially, the microwave is idle and has no time entered or remaining. When the microwave is idle, Caitlyn can start the microwave by entering a time with the Set Time button. To select a time, Caitlyn must press the Set Time button on the microwave, then enter the time into the microwave’s keypad, then press the Start button. Caitlyn can enter a one, two or three digit time. If Caitlyn enters a one or two digit time, the microwave will run for this many seconds. If Caitlyn enters a three digit time, the microwave will interpret the first digit as minutes and the last two digits as seconds. There are no restrictions on which digits Caitlyn can enter. For example, if Caitlyn enters Set Time-9-3-Start, the microwave will run for 93 seconds. If Caitlyn enters Set Time-6-9-3-Start, the microwave will run for 6 minutes and 93 seconds, for a total of $360 + 93 = 453$ seconds. If Caitlyn enters Set Time-0-0-0-Start, the microwave will run for 0 seconds and stop instantly. Caitlyn cannot enter more than 3 digits.

Additionally, the microwave has several preset buttons that Caitlyn can use to immediately start the microwave while the microwave is idle.

• If Caitlyn presses any digit 1 through 7 while the microwave is idle (and Set Time has not been pressed), the microwave will run for that many minutes, without Caitlyn pressing Set Time or Start. Pressing 8, 9 or 0 before pressing Set Time has no effect.

• If Caitlyn presses the Popcorn button, at the end of the second, the microwave will begin running for 2 minutes and 30 seconds.

• If Caitlyn presses the Reheat button, the microwave will begin running for 50 seconds.

• If Caitlyn presses the Potato button, the microwave will begin running for 5 minutes and 15 seconds.

• If Caitlyn presses the Add 30 Seconds button before pressing any other buttons, the microwave will begin running for 30 seconds.

No preset button except the Add 30 Seconds button have any effect when the microwave is running, idle or paused. No preset button except the digits have any effect when Caitlyn is entering a time with the Set Time button.

Caitlyn can also press the Stop button to pause the microwave while it is running. While paused, the microwave will not run, and the time will not reset.

• If Caitlyn presses the Stop button while the microwave is running, it will stop cooking at the end of the second.

• While the microwave is paused, only the Start, Add 30 Seconds and Stop buttons have any effect: pressing the Stop button resets the time to 0 seconds and cancels the cooking operation. Pressing the Start button resumes cooking with the remaining time.

• Caitlyn can run the hextech microwave without her food in it. When the microwave is not running, she can instantly insert or remove food into the microwave. She cannot insert or remove food while the microwave is running.

When the microwave is running, only the Stop and Add 30 Seconds buttons have any effect. If Caitlyn presses the Stop button when the microwave is running with $t$ seconds remaining, at the end of the second, the microwave will stop cooking with $t - 1$ seconds remaining. If Caitlyn presses the Stop button when the microwave has only one second left, this second will tick down, and the microwave will become idle instead of remaining paused with $0$ seconds. If $t > 1$, the microwave will remain paused with $t - 1$ seconds remaining.

Caitlyn can use the Add 30 Seconds whenever the microwave is running, paused or idle, but not when a time is being entered with the Set Time button. If Caitlyn presses the Add 30 Seconds button when the microwave is running with $t \leq 610$ seconds remaining, the microwave will run for this second, and at the end of the second, the microwave will have $t + 29$ seconds remaining. If Caitlyn presses the Add 30 Seconds when the microwave is running with 1 second remaining, the microwave will continue running for an additional 29 seconds. If Caitlyn presses the Add 30 Seconds button when the microwave is paused with $t \leq 609$ seconds remaining, the microwave will remain paused with $t + 30$ seconds remaining. If Caitlyn presses the Add 30 Seconds button when the microwave is idle, the microwave will begin running for 30 seconds.

The microwave can only display 3 digits. When Caitlyn presses the Add 30 Seconds button, the microwave will automatically normalize the time to 3 digits. If the resulting time would be too large to display with only 3 digits, the Add 30 Seconds button will have no effect for that second. For example, if Caitlyn hits Add 30 Seconds when the microwave is running and reads 0:99, the resulting cook time will be $99 + 29 = 128$ seconds. The microwave will display this as 2:08 (2 minutes and 8 seconds). If Caitlyn presses the Add 30 Seconds button when the microwave has 9 minutes and 71 seconds remaining or longer, the resulting time is too large to display, and the button has no effect. If Caitlyn presses the Add 30 Seconds button when the microwave is running and reads 9:70, the resulting cook time will be $9 \times 60 + 70 + 29 = 639$ seconds, and the microwave will display this as 9:99 (9 minutes and 99 seconds).

For example, to heat her food 90 seconds, Caitlyn use any one of the following strategies:

• Set Time-9-0-Start (4 seconds spent pressing buttons)

• Set Time-1-3-0-Start (5 seconds)

• 1-Add30 (2 seconds)

• Set Time-1-0-0-Start-Add30 (6 seconds)

• Add30-Add30-Add30 (3 seconds)

• Reheat (without food)-Add30-(Wait 19 seconds for microwave to count down)
  -Stop-Add30-(Put food in instantly)-Start (24 seconds)

Making Caitlyn’s life more difficult, Vi always presses the buttons too hard and breaks them. A lot of the buttons aren’t even working right now. Caitlyn can’t use any of the broken buttons to enter the time.

Caitlyn needs to heat her food today for exactly $x$ seconds. What is the minimum number of seconds for Caitlyn to enter this time into the microwave? Her time starts when she presses the first button, and ends when she presses the last button, regardless of how long the food has left.

Input

The first line contains two space-separated integers: $n$, the number of buttons that are broken ($0 \leq n \leq 15$), and $q$, the number of times Caitlyn wants to heat her food ($1 \leq q \leq 639$).

The next line contains $n$ space-separated strings, representing the button that is broken. The digit buttons are represented by a single character, 0-9, the digit of the button that is broken. This line will be empty if $n = 0$. The remaining buttons are represented by the following strings:

• settime

• popcorn

• reheat

• potato

• add30

The Stop and Start buttons are never broken.

The next line contains $q$ space-separated integers, $x_1, x_2, \ldots , x_q$ ($1 \leq x_i \leq 639$), the times Caitlyn wants to heat her food for over the next $q$ days.

Output

For each query, output one line containing a single number, the minimum number of seconds Caitlyn needs to enter the time into the microwave to cook her food exactly $x_i$ seconds. This is defined as the final time when Caitlyn presses the last button, regardless of how long the food has left to cook. If Caitlyn cannot cook her food for exactly $x_i$ seconds, output -1.

Explanation

Unless otherwise specified, in the below explanations, if Caitlyn starts the microwave, her food is assumed to be in the microwave.

To cook her food for 60 seconds, Caitlyn could use any of the three following strategies in the sample inputs:

• 1 (1 second)

• Popcorn-(wait 9 seconds)-Stop-Stop-Reheat (13 seconds)

• 2-(wait 59 seconds)-Stop (61 seconds)

To cook her food for 1 second, Caitlyn can press any preset button during the first second and then hit Stop during the second second. The microwave will remain paused and her food will have cooked for 1 second.

To cook her food for 23 seconds, Caitlyn could use any of the three following strategies in the sample inputs:

• Set Time-2-3-Start (4 seconds)

• Add30 (without food)-(wait 6 seconds)-Stop-Start (with food) (9 seconds)

• Potato-Wait 22 seconds-Stop (24 seconds)

To cook her food for 80 seconds, Caitlyn could use any of the three following strategies in the sample inputs:

• Reheat-Add30 (2 seconds)

• 4-(wait 29 seconds)-Stop-Stop-Reheat (33 seconds)

• 2 (without food)-(wait 39 seconds)-Stop-Start (with food) (42 seconds)

0 8

60 1 23 80 30 90 120 180

1
2
4
2
1
2
1
1

3 8
1 settime add30
60 1 23 80 30 90 120 180

13
2
24
33
22
32
1
1

4 8
1 settime add30 reheat
60 1 23 80 30 90 120 180

61
2
24
42
31
32
1
1

2 8
2 3
60 1 23 80 30 90 120 180

1
2
9
2
1
2
3
2