Description

Killer of Pig Kingdom is a turn-based card game involving three types of roles: Master Pig (MP), Loyal Pig (ZP), and Rebel Pig (AP). Each game has exactly one Master Pig, while there can be multiple Loyal Pigs and Rebel Pigs. Each pig plays one role.

Game Objective: Master Pig (MP): Eliminate all Rebel Pigs while staying alive. Loyal Pig (ZP): Protect the Master Pig at all costs; the victory condition is the same as the Master Pig's. * Rebel Pig (AP): Kill the Master Pig.

Game Process: At the start of the game, each player has 4 cards in hand. The maximum health and initial health are both 4. The game begins with the Master Pig, and players take turns in counter-clockwise order (in the data, this follows the order $1, 2, 3, \dots, n, 1, \dots$).

Each player's turn consists of 4 phases: Draw Phase: Draw two cards from the top of the deck and place them at the rightmost end of the hand. Play Phase: You may use 0 to any number of cards. Each time you use a card, you must use the leftmost usable card. Of course, the following rules must be satisfied: 1. If you do not have a Pig-Brother Crossbow, you can only use one "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 Introduction: Each card is represented by a letter indicating its type.

• Basic Cards:

  • 『Peach (P)』: During your turn, if your current health is less than your maximum health, you may use a Peach to restore 1 health point; otherwise, it cannot be used. A Peach can only be used on yourself. Outside of your turn, if your health drops to 0 or lower, you may also use it.
  • 『Kill (K)』: During your turn, use it on a character other than yourself within your attack range. If not countered by a "Dodge", it deals 1 damage. Regardless of whether you have a weapon, the attack range of a "Kill" is 1.
  • 『Dodge (D)』: When you are attacked by a "Kill", you may discard a "Dodge" to negate the effect of the "Kill".

• Strategy Cards:

  • 『Duel (F)』: During the play phase, use it on any character other than yourself. The target character goes first, and both parties take turns discarding a "Kill". The first party unable to discard a "Kill" takes 1 damage, and the other party is considered the source of this damage.
  • 『Southern Pig Invasion (N)』: During the play phase, use it on all characters except yourself. Starting from the player to your left and proceeding counter-clockwise, each character must discard a "Kill" or take 1 damage.
  • 『Arrow Rain (W)』: Similar to "Southern Pig Invasion", but characters must discard a "Dodge" instead of a "Kill".
  • 『Nullification (J)』: Negates the effect of a strategy card before it takes effect. Each time a strategy card is about to take effect, starting from the pig who used the strategy card, players get the opportunity to use "Nullification" in counter-clockwise order.
    • Effect: When used against a "Duel", the duel is invalidated and discarded. When used against "Southern Pig Invasion" or "Arrow Rain", it can only be used when the effect reaches a specific character; the current character does not need to discard a card and takes no damage (it only affects one character). When used against "Nullification", the target "Nullification" is invalidated.

• Equipment Cards:

  • 『Pig-Brother Crossbow (Z)』: Weapon, attack range 1. During the play phase, you may use any number of "Kill" cards. Only one weapon can be equipped at a time. If you already have a weapon, equipping a new one will discard the old one.

Special Events and Concepts: Damage Source: The source of damage for "Kill", "Southern Pig Invasion", and "Arrow Rain" is the pig who used the card. The source of damage for a "Duel" is as described above. Distance: The distance between two pigs is defined as the number of pigs between them in counter-clockwise order + 1. Initially, the distance between 1 and 2 is 1, but the distance between 2 and 1 is $n-1$. Note that the death of a character changes the distances between some pigs. Player Death: If a player's health drops to 0 or lower and they do not have enough "Peach" cards to restore their health to 1, they die. Upon death, all their cards (equipment and hand) are discarded. Rewards and Penalties: When a Rebel Pig dies, the last source of damage (even if it was another Rebel Pig) immediately draws three cards. When a Loyal Pig dies, if the last source of damage was the Master Pig, the Master Pig discards all their equipment and hand cards. *Note: Once the victory condition is met, the game ends immediately, so even if a player would draw 3 cards or has cards left to use, they do not execute those actions.

Behaviors: Show Favor: Use "Nullification" to block "Southern Pig Invasion", "Arrow Rain", or "Duel"; use "Nullification" to negate "Show Hostility". Show Hostility: Use "Kill" or "Duel" on a character; use "Nullification" to negate "Show Favor". Jump Loyal: Act to reveal yourself as a Loyal Pig. This means showing favor to the Master Pig or a pig already revealed as Loyal, or showing hostility to a pig already revealed as Rebel. Jump Rebel: Act to reveal yourself as a Rebel Pig. This means showing hostility to the Master Pig or a pig already revealed as Loyal, or showing favor to a pig already revealed as Rebel. Loyal Pigs never jump Rebel, and Rebel Pigs never jump Loyal. Both Loyal and Rebel pigs will jump if they can.

Action Guidelines: Common: If a character has a "Peach" and is not at full health, they will always use it. They will always use "Southern Pig Invasion" or "Arrow Rain" if they have them. They will always equip equipment. When attacked by a "Kill", they will always discard a "Dodge" if they have one. When responding to "Southern Pig Invasion" or "Arrow Rain", they will always discard a "Kill"/"Dodge" if they have one. They will never show favor to a pig whose identity is not yet revealed (including themselves). Master Pig: Considers pigs who have not revealed their identity, or who have caused damage to the Master Pig using "Southern Pig Invasion"/"Arrow Rain" (if no damage is dealt, it doesn't count; note that "potential rebel" does not mean identity is revealed), as "potential rebels". If they reveal their identity later, the Master Pig re-evaluates them. For each type of "Show Hostility", the Master Pig targets the first "potential rebel" or revealed Rebel Pig in counter-clockwise order; if none, they do not show hostility. During a "Duel", they will spare no effort to discard "Kill" cards. If they can show favor to a revealed Loyal Pig or themselves, they will. If they can show hostility to a revealed Rebel Pig, they will. Loyal Pig: For each type of "Show Hostility", they target the first revealed Rebel Pig in counter-clockwise order; if none, they do not show hostility. During a "Duel", if the opponent is the Master Pig, they will not discard a "Kill"; otherwise, they will spare no effort to discard "Kill" cards. If they have the opportunity to show favor to the Master Pig or a revealed Loyal Pig, they will. Rebel Pig: For each type of "Show Hostility", if they have the opportunity, they target the Master Pig; otherwise, they target the first revealed Loyal Pig in counter-clockwise order; if none, they do not show hostility. During a "Duel", they will spare no effort to discard "Kill" cards. If they have the opportunity to show favor to a revealed Rebel Pig, they will.

Input

The first line contains two positive integers $n$ ($2 \le n \le 5$) and $m$ ($m \le 2000$), representing the number of players and the number of cards in the deck, respectively. The data guarantees there are enough cards. The next $n$ lines each contain 5 strings, describing the role and the initial 4 hand cards for the $i$-th pig. The pig numbered 1 is always the Master Pig. The next line contains $m$ strings, describing each card in order from the top of the deck to the bottom. All adjacent strings are strictly separated by 1 space, and there is no extra space at the end of the line.

Output

The first line contains a string representing the game result. If the Master Pig wins, output "MP", otherwise output "FP". The data guarantees the game will always end. The next $n$ lines describe the hand cards of the $i$-th pig (note that only the hand cards need to be output). Output the cards in order from left to right, separated by a space, with no extra space at the end of the line. If the pig is dead, simply output "DEAD". Note that if there are no hand cards, output an empty line.

Examples

Input 1

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

Output 1

FP
DEAD
DEAD
J J J J J D

Note 1

In the first round, the Master Pig has no target to show hostility towards. Next, the Loyal Pig uses 3 "Southern Pig Invasion" cards; the Master Pig loses 3 health and considers that character a "potential rebel". Although the 3rd character has a "Nullification", because they have not revealed their identity, they cannot use it on themselves and lose 3 health. In the next round, the Rebel Pig has no cards to play. Then, the Master Pig erupts against the "potential rebel", using 4 "Duel" cards. The Loyal Pig dies, and the Master Pig discards all cards. Finally, the Rebel Pig draws a "Kill" and kills the Master Pig to win.