Shopping Mania

Limits 1s, 256 MB · Interactive

Shapla and Jui have entered the final round of Shopping Mania, an annual shopping game played by two players. The rules of the game are described below:

1. There are $n$ items with prices $p_1, p_2, \dots, p_n$. There is also a constant value $k$, denoted as Maximum Skips in a Row. These values are made known to the players at the very beginning.

2. The host presents an item. The items are presented one by one and item $i$ is only presented when all the items before it i.e. the items numbered $1, 2, \dots, i-1$ are purchased by any of the players.

3. The player who has the turn decides whether to purchase this item or skip it in this turn. An item can only be skipped when there was at least one purchase made by any of the players in the last $k$ turns or if the game hasn’t been played for $k$ turns yet.

   • If the item is purchased, the item is added to the player’s cart.

     • If it was the last item i.e. $n$’th item, the game ends.

     • Otherwise, the host presents the next item. Turn changes to the other player. And the game continues from Step-3 again.

   • If the item can be skipped and is skipped in this turn by the current player, the turn changes to the other player, and the game continues from Step-3.

4. When the game ends, the prices of the items in each players’ cart are summed up and the player with the biggest sum wins the game. If both of them an equal sum of prices in their carts, both are declared winners.

Shapla won the toss and can decide who has the first turn. Can you advise Shapla whether to go first or second and in each of her turns whether to purchase or skip the current item so that she eventually wins?

Interaction

This is an interactive problem. The judge will play as Jui opposing you. Please refer to the Notes section for help on interactive problems.

There will be two integers $n,k$ on the first line of input. The next line follows with $n$ space separated integers $p_1, p_2, \dots, p_n$.

Now you must output “first” or “second” (without the quotes) to indicate if Shapla should have the first turn or not.

• In each of Shapla’s turns, you must output “purchase” or “skip” (both without the quotes, and you can only output “skip” if it’s valid) on a line.

• In each of Jui’s turns, the judge will output “purchase” or “skip” on a line as well. You can be assured that the judge output will be valid. You must input this line.

• When any player $x$ purchases current item $i$, there will be a line of input with the text “$x$ purchased item $i$”. You must input this line. However, this line is only for convenience and you may not do anything with it.

The game ends when $n$ purchases have been made and your program must quit immediately. You will get an “Accepted” verdict if Shapla and you have won this game or a “Wrong Answer” if you haven’t. If your program doesn’t quit and expect further inputs, it might get all sorts of verdicts excluding “Accepted” and including “Idleness limit exceeded”.

Please note that any invalid output from your program will result in a “Wrong Answer” verdict as well. Do refer to the sample interaction for better understanding.

Sample Interaction

Inputs are shown on the left and your outputs are shown on the right. Note that on line 11, Jui had no other option but to purchase item 3, since in the last $k =3$ turns there were no purchases made.

Constraints & Scoring

For all sub-tasks:

• $1 \le p_i \le 10^5$.

Sub-tasks:

1. Sub-task 1 (14 points):

   • $2 \le n \le 3$

   • $0 \le k \le 1$.

2. Sub-task 2 (6 points):

   • $2 \le n \le 10^4$

   • $k = 0$.

3. Sub-task 3 (80 points):

   • $2 \le n \le 10^4$

   • $0 \le k \le 50$.

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems