Description

elfnt wants to practice his English vocabulary, so Momo designed a word guessing game (AKA The hang man game) for him.

The rules are as follows:

• elfnt has exactly $k$ chances to perform operations.

• In each chance, he may choose one of the following operations:

• check c

  • Check if the letter c exists in the hidden word. (uppercase)
  • If yes, reveal all occurrences of c in the word.
  • If not, nothing happens.
  • After executing this operation, print the current revealed word status (letters + _).

• guess word

  • Guess that the hidden word is exactly word.
  • If the guess is correct, print You win and terminate the game.
  • Otherwise, print Wrong.

• chance

  • Display the number of remaining chances.
  • This operation does NOT consume a chance.

• hint

  • Reveal the leftmost unrevealed letter in the word.
  • If the same letter appears elsewhere, reveal all of them at once.
  • This operation can only be used once in the entire game.
  • If used more than once, output Already used (does NOT consume a chance).
  • If the entire word has already been fully revealed, using hint still consumes the one-time chance (if not used) but does not reveal anything new.
  • After executing this operation, print the current revealed word status (letters + _).

• Each valid operation (check, guess, or first-time hint) consumes one chance.
• The operation chance and repeated hint do not consume any chance.
• If all $k$ chances are consumed without guessing the correct word, output You lose and terminate.

Input

• The first line contains an integer $n$ — the length of the hidden word.
• The second line contains an integer $k$ — the number of chances elfnt has.
• The third line contains the hidden word consisting of $n$ uppercase English letters.
• Starting from the fourth line, each subsequent line describes an operation until the game ends.
• Each operation is one of the following forms:
  • check c
  • guess word
  • hint
  • chance

Constraints

• $1 \le n \le 1000$
• $1 \le k \le 2000$
• The chance and repeated hint operations does not exceed $2000$ times.
• The hidden word contains only uppercase English letters (A–Z).

Subtasks

1. (Testcases 1–4) No hint operation.
2. (Testcases 5–6) No additional constraints.

Output

Follow the rules strictly:

• After a check or valid hint, print the status. (letters + _).
• After a guess, print You win if correct and terminate immediately; otherwise print Wrong.
• After a chance command, print the remaining number of chances (without consuming any).
• If hint is repeated, print Already used (without consuming a chance).
• When all chances are consumed without winning, print You lose.

Sample Input  Download

Sample Output  Download

Tags

Discuss