Description

Game Background

"Pig Kingdom Kill" is a turn-based card game for multiple pigs. There are 3 types of roles: Main Pig (MP), Loyal Pig (ZP), and Rebel Pig (FP). In every game, there is exactly 1 MP. There can be multiple ZPs and FPs. Each pig plays exactly one role.

Game Objective

• Main Pig (MP): Eliminate all Rebel Pigs (FP) while surviving.
• Loyal Pig (ZP): Protect the Main Pig at all costs. The victory condition is the same as the MP.
• Rebel Pig (FP): Kill the Main Pig.

Game Process

At the start of the game, each player holds $4$ cards. Both the max HP and initial HP are $4$.

The game starts with the Main Pig and proceeds in counter-clockwise order (in the data, this is the order of IDs $1, 2, 3 \dots n, 1 \dots$).

Each player's turn consists of two phases:

1. Draw Phase: Draw $2$ cards from the top of the deck and place them at the rightmost end of the hand.
2. Play Phase: You may use any number of cards. When playing cards, you must always use the leftmost usable card. However, the following rules apply:
   1. Without a "Zhuge Crossbow", you can only use 1 "Kill" card to attack per Play Phase.
   2. Any card used is discarded (weapons are equipped). Discarded cards cannot be used again and are removed from the game.

Card Descriptions

Each card is represented by a single letter indicating its type.

Basic Cards

• Peach (P): During your turn, if your HP is not full, you can use a Peach to recover $1$ HP. Otherwise, it cannot be used. Peach can only be used on yourself. Exception: If your HP drops to $0$ or below during someone else's turn, you can use a Peach immediately to save yourself.
• Kill (K): During your turn, use this on any other character within your attack range. If the target does not use a "Dodge" to cancel it, they take $1$ point of damage. Regardless of weapons, the default attack range of a Kill is $1$.
• Dodge (D): When attacked by a "Kill", you may discard a Dodge to negate the effect.

Scroll Cards (Strategy Cards)

• Duel (F): During the Play Phase, use on any other character. Starting with the target, the target and the user take turns discarding a "Kill". The first side unable to discard a "Kill" takes $1$ damage. The other side is considered the source of this damage.
• South Pig Invasion (N): During the Play Phase, use on all other characters. Starting from the player to the user's right (next in turn order), proceed counter-clockwise. Unless a player discards a "Kill", they take $1$ damage.
• Archery Attack (W): Similar to South Pig Invasion, but players must discard a "Dodge" instead of a "Kill" to avoid damage.
• Unassailable / Nullification (J): Use this to negate the effect of a target scroll card before it takes effect.
  • Each time a scroll is about to take effect on a character, players (starting from the scroll user) proceed counter-clockwise, having the opportunity to use J.
  • Effect: When used against a Duel, the Duel is invalidated and discarded. When used against AOE (South Pig Invasion/Archery), it prevents the effect for one specific target (that target does not need to discard a card and takes no damage). When used against another J, it negates the previous J (re-enabling the original scroll).

Equipment Cards

• Zhuge Crossbow (Z): A weapon. Attack range is $1$. During the Play Phase, you may use any number of "Kill" cards. You may only have $1$ weapon equipped at a time. If you equip a new weapon, the old one is discarded.

Special Events and Concepts

• Damage Source: For Kill, South Pig Invasion, and Archery Attack, the source is the user of the card. For Duel, the source is the winner of the duel.
• Distance: The distance between two pigs is defined as the number of pigs between them in the counter-clockwise direction $+ 1$. Initially, the distance from $1$ to $2$ is $1$, but the distance from $2$ to $1$ is $n-1$. Note that the death of a character changes the distance between the remaining pigs.
• Player Death: If a player's HP drops to $0$ or lower and they cannot use enough Peaches to bring their HP back to $1$, they die. Upon death, all their cards (hand and equipment) are discarded.
• Rewards and Penalties:
  • When an FP dies, the source of the damage (even if it is another FP) immediately draws $3$ cards.
  • When a ZP dies, if the damage source was the MP, the MP must discard all their cards (hand and equipment).
  • Note: If the victory condition is met, the game ends immediately. No cards are drawn or discarded even if triggered.

Now, given each pig's role, initial hand, and the initial deck configuration, assume every character follows the behavior rules below. Your task is to predict the final result for iPig.

Behavior Rules

• Showing Goodwill: Using J to negate South Pig Invasion, Archery, or Duel for someone; or using J to negate a "Showing Animosity" action.
• Showing Animosity: Using K or F on a character; or using J to negate a "Showing Goodwill" action.
• Jump Loyal (Reveal as ZP): Actions that show you are a Loyalist. This involves Showing Goodwill to the MP or an already revealed ZP, or Showing Animosity to an already revealed FP.
• Jump Rebel (Reveal as FP): Actions that show you are a Rebel. This involves Showing Animosity to the MP or an already revealed ZP, or Showing Goodwill to an already revealed FP.

Note: A ZP will never Jump Rebel, and an FP will never Jump Loyal. If a pig can reveal its identity (jump), it will.

Action Logic

General (Common to all)

1. If a player has a Peach (P) and HP is not full, they will strictly use it.
2. If holding South Pig Invasion (N) or Archery (W), they will strictly use it. If holding equipment (Z), they will strictly equip it.
3. When targeted by a Kill (K), if they have a Dodge (D), they will strictly discard it.
4. When responding to South Pig Invasion (N) or Archery (W), if they have the required card (K/D), they will strictly discard it.
5. Players will never Show Goodwill to a pig whose identity is unknown (this includes themselves—logic implies they don't 'reveal' to protect themselves unless they are already known or it helps a known ally, but the specific rule provided is "Won't show goodwill to undefined identities").

Specific Role Logic

• Main Pig (MP):

  • The MP considers any pig who has caused damage to the MP using South Pig Invasion (N) or Archery (W) and has not yet revealed their identity as a "Like-Rebel" (quasi-rebel). (Zero damage doesn't count. Note: Like-Rebels have not technically revealed their identity). If this pig later reveals an identity ("Jumps"), the MP updates their view of this pig.
  • For any method of Showing Animosity: The MP targets the first Like-Rebel or Revealed FP found in the counter-clockwise direction (within range/validity). If none are found, the MP does not Show Animosity.
  • During a Duel (F), the MP discards Kills as much as possible.
  • If able to Show Goodwill to a Revealed ZP or themselves, the MP strictly does so. If able to Show Animosity to a Revealed FP, the MP strictly does so.

• Loyal Pig (ZP):

  • For any method of Showing Animosity: The ZP targets the first Revealed FP found in the counter-clockwise direction. If none, they do not Show Animosity.
  • During a Duel (F):
    • If the opponent is the MP, the ZP will not discard a Kill (voluntarily takes damage).
    • Otherwise, the ZP discards Kills as much as possible.
  • If there is a chance to Show Goodwill to the MP or a Revealed ZP, the ZP strictly does so.

• Rebel Pig (FP):

  • For any method of Showing Animosity: If able, strictly target the MP. Otherwise, target the first Revealed ZP found in the counter-clockwise direction. If neither is possible, do not Show Animosity.
  • During a Duel (F), the FP discards Kills as much as possible.
  • If there is a chance to Show Goodwill to a Revealed FP, the FP strictly does so.

Since iPig can only write "A + B" in P++, he asks you to predict the result using Pascal, C, or C++.

Input Format

The first line contains two positive integers $n$ $(2 \leqslant n \leqslant 10)$ and $m$ $(m \leqslant 2000)$, representing the number of players and the number of cards in the deck. The data guarantees the number of cards is sufficient (see note below).

The next $n$ lines each contain 5 strings, describing the $i$-th pig. The first string is the role, followed by the initial 4 cards. The pig with ID $1$ is always the MP.

The following line contains $m$ strings, describing the cards in the deck from top to bottom.

Note: All adjacent strings are strictly separated by 1 space. There are no trailing spaces at the end of lines.

Output Format

The first line contains a string representing the game result. If the Main Pig wins, output MP. Otherwise, output FP. The data guarantees the game will end.

The next $n$ lines describe the hand cards of the $i$-th pig (only output the hand cards). Output them in order from left to right, separated by 1 space. There should be no trailing spaces. If the pig is dead, output DEAD.

Note: If a pig is alive but has no cards, output a single empty line.

Due to data issues, if the draw pile becomes empty, treat it as if the last card drawn is drawn repeatedly for all subsequent draws.

3 10
MP D D F F
ZP N N N D
FP J J J J
F F D D J J F F K D

FP
DEAD
DEAD
J J J J J J D

Hint

Sample Explanation

Turn 1:

• MP: Has no target to Show Animosity to.
• ZP: Uses 3 South Pig Invasions (N).
  • MP takes 3 damage. MP now views ZP as a "Like-Rebel".
  • Player 3 (FP) has J (Nullification), but since they haven't revealed their identity, they cannot use it on themselves. They take 3 damage.
• FP: Starts turn.

Next Turn (implied flow):

• FP: Has no playable offense cards (only J).
• MP: Acts. Uses 4 Duels (F) on the ZP (who is marked as Like-Rebel).
  • ZP dies (ZP does not fight back against MP? Wait, ZP logic says "If opponent is MP, do not discard Kill". However, ZP is currently treated as Like-Rebel by MP. The ZP knows MP is MP, so ZP accepts death).
  • MP kills ZP. MP Penalty: MP discards all cards.
• FP: Acts. Draws a Kill (K). Uses it on MP. MP (HP 1, no cards) dies.
• Result: FP wins.

Subtasks

There are 20 test cases, 5 points each.

• 10% of data has no Scroll cards.
• Another 20% of data has no "Unassailable" (J) cards.