The Three Kingdoms kill the surrounding areas -------- explanation of the pig Kingdom kill problem

[SDOI2010] Pig national slaughter

Title Description

Game background

《 Pig national slaughter 》 It is a multi - pig round game , Altogether $3$ Roles ： Main pig , Zhongzhu , Anti pig . The main pig of each game has and only $1$ only , There can be many loyal pigs and anti pigs , Each pig plays $1$ Roles .

Game purpose

Main pig / $\text{MP}$： Destroy all anti pigs while you are alive .
Zhongzhu / $\text{ZP}$： Do anything to protect the main pig , The winning conditions are the same as those of the main pig .
Anti pig / $\text{FP}$： Kill the main pig .

The process of the game

At the beginning of the game , Every player will have $4$ card , And both the upper limit of physical strength and the initial physical strength are $4$ .

At the beginning of the game , Start with the main pig , In a counterclockwise direction （ In the data, it is from... According to the number $1,2,3\dots n,1\dots$ The order of ） Act in turn .

Each player's own turn can be divided into 2 Stages ：

• Touch stage ： Touch from the top of the deck $2$ card , Put them on the far right of the hand in turn ;
• The licensing stage ： You can play any card , Each time you play a card, use the leftmost card that can be used . Of course , The following rules must be met ：
  1. If there is no brother pig crossbow , Each playing stage can only use $1$ Time 「 kill 」 To attack ;
  2. Any card that is used is discarded （ Weapons are equipment ）; Discarded cards can no longer be used , That is, it has nothing to do with the game .

Introduction to various cards

For each hand $1$ A letter means , The letters represent the type of cards .

Basic cards

• 『 peach / $\text{P}$』 In your own turn , If your physical strength is not equal to your maximum physical strength , So use $1$ A peach can complement itself $1$ A little physical strength , Otherwise, do not use peaches ; Peaches can only be used for themselves ; Outside your own turn , If your own blood becomes $0$ Or lower , You can also use .

• 『 kill / $\text{K}$』 In your own turn , For those within the attack range other than yourself $1$ Name role use . If not 『 Flash 』 offset , Cause $1$ Point injury . With or without weapons , The range of attack is $1$.

• 『 Flash / $\text{D}$』 When you are attacked by a killer , Can be discarded $1$ Zhang flashed to counteract the effect of disinfection and sterilization .

Brocade bag

• 『 duel / $\text{F}$』 The licensing stage , For anything except yourself $1$ Name role use , Start with the target character , Discard yourself and the target character in turn $1$ Zhang sha , First of all, the party that can not be killed and abandoned is $1$ Point injury , The other party regards this as the source of the injury .

• 『 The southern pig invades / $\text{N}$』 The licensing stage , Use for all characters except you , The settlement starts from the user's next home in anticlockwise order , Unless discarded $1$ Zhang sha , Otherwise, you will be $1$ Point injury .

• 『 Thousands have been / $\text{W}$』 Similar to the southern pig invasion , But the thing to discard is not to kill but to flash .

• 『 With no chink in one's armour / $\text{J}$』 Counteract the effect of the target's brocade bag before it takes effect . Every time $1$ When zhangjinbao is about to take effect , Start with the pig who uses this brocade bag , In counterclockwise order , In turn get the opportunity to use impeccable ; effect ： For dueling , The duel is invalid and discarded ; It is used when Southern pigs invade or ten thousand arrows are fired at once , It can only be used when the settlement reaches a certain role , The current character does not need to discard cards and will not take damage （ Only on $1$ Characters produce effects ）; Used when impeccable , The invulnerability of being a target is nullified .

Equipment card

• 『 Brother pig's Crossbow / $\text{Z}$』 weapons , Attack range $1$ , You can use any card to kill in the card playing stage ; At most, you can only install at the same time $1$ Put the weapon ; If you already have $1$ Put the weapon , Then if we load weapons later , Will discard the previous weapons to install the present weapons .

Special events and concept explanation

• Source of injury ： kill 、 The southern pig invades 、 The damage source of the ten thousand arrows is the pig using this card , The damage sources of duel are as follows ;

• distance ： The distance between two pigs is defined as the number of pigs separated in a counterclockwise direction $+1$ . At the beginning $1$ and $2$ The distance to $1$ , however $2$ and $1$ The distance is $n-1$ . Note that the death of a character will cause some changes in pig distance ;

• Players die ： If the player's strength drops to $0$ Or lower , And I don't have enough peaches in my hands to make my physical strength return to $1$ , Then you die , All cards after death （ Equipment area , Hand area ） Abandoned ;

• Reward and punishment ： When the anti pig dies , The last source of damage （ Even anti pig ） Touch immediately $3$ card . When Zhongzhu dies , If the last source of injury is the main pig , So all the equipment cards of the main pig 、 The hand is discarded .

Be careful ： Once the winning conditions are met , The game ends immediately , So even if you touch $3$ Cards or cards can be used without execution .

Now? , We already know the role of each pig 、 Hand , And the initial situation of the deck , And assume that each character will play according to the following code of conduct , All you have to do is tell the pig iPig The final result .

Several behaviors

• Be courteous ： Use impeccable to block the invasion of Nanzhu 、 Thousands have been 、 duel ; Use impeccable counterattack table hostility ;
• Show hostility ： Use kill on a character 、 duel ; Use impeccable counteraction to pay attention ;
• Tiaozhong ： That is to say, you are a loyal pig through actions . Jumping loyalty is to pay attention to the main pig or a pig that has jumped loyalty , Or hostile to a pig that has jumped backwards ;
• Jump back ： That is to say, you are anti pig through actions . The act of jumping back is to show hostility to the main pig or to a pig that has jumped out of loyalty , Or pay attention to a pig that has jumped backwards .

Be careful ： Loyal pigs don't jump backwards , Anti pig will not jump loyalty ; Whether it's loyal or anti pig , If you can jump, you will jump .

The code of conduct

Generality

• If each character has a peach in his hand and his HP is not full , Then it must be eaten ;
• There is a southern pig invasion 、 Thousands have been 、 Must use ; If you have equipment, you must have it ;
• When killed , If there is a flash, it must be discarded ;
• In response to the invasion of Southern pigs or the simultaneous launching of ten thousand arrows , There are murders / Flash must be discarded ;
• Will not be courteous to unidentified pigs （ Including myself ）.

characteristic

• Main pig ：
  • The main pig will think 「 No identity jump , And invade with southern pigs / A pig that causes damage to itself by firing ten thousand arrows at once 」 yes class Anti pig （ It doesn't count if it doesn't hurt , Note that the anti pig does not identify itself ）, If you jump later , Then the main pig will know this pig again ;
  • For every way of expressing hostility , For the first anti pig or skipped anti pig table that can be executed in the counterclockwise direction ; without , Then don't show hostility ;
  • During the duel, I will spare no effort to discard the kill ;
  • If you can be courteous to a pig or yourself who is already loyal , Then you must offer ; If you can be hostile to a pig that has jumped backwards , Then it must be .
• Zhongzhu ：
  • For every way of expressing hostility , Yes 「 The first pig that can be executed anticlockwise has jumped backwards 」 surface , without , Then don't show hostility ;
  • In a duel , If the other side is the main pig , Then we will not abandon killing , otherwise , Will spare no effort to abandon killing ;
  • If you have the opportunity to be courteous to the main pig or the pig who has jumped into loyalty , Then you must offer .
• Anti pig ：
  • For every way of expressing hostility , If there is a chance, the main pig table , otherwise , Yes 「 The first pig that can be executed in an anticlockwise direction 」 surface , without , Then don't show hostility ;
  • During the duel, I will spare no effort to discard the kill ;
  • If there is a chance to be courteous to the pig who has jumped back , Then you must offer .

Be limited to iPig Only use P++ Language writing A + B, He asked you to use Pigcal (Pascal)、P or P++ (C++) Language to help him predict the final result .

Input format

The first line of the input file contains two positive integers $ n $ $ (2 \leqslant n \leqslant 10) $ and $m$ $ (m \leqslant 2000) $, Represents the number of players and the number of cards in the stack . There are enough data guarantee boards .

Next $n$ That's ok , Each row $5$ A string , In turn, they represent the pairs of $i$ Pig's role and initial $4 $ Description of a hand . The number is $1$ It must be the main pig .

The next line , altogether $m$ A string , Describe each card from the top of the stack to the bottom of the stack .

Be careful ： All two adjacent strings are strictly used $1$ Space between , There is no extra space at the end of the line .

Output format

The first row of the output data contains a string representing the game result . If the main pig wins , Then output $\text{MP}$ , Otherwise output $\text{FP}$ . Data guarantees that the game will end .

Next $n$ That's ok , The first $i$ The line is right $i$ Description of a pig's hand （ Note that you only need to output your hand ）, Output cards from left to right in the order of hand , Two adjacent cards use $1$ Space between , There is no extra space at the end of the line . If the pig is dead , So just output $\text{DEAD}$ that will do .

Be careful ： If you want to output a hand without a hand , Then just output $1$ Empty rows .

Due to data problems , If the deck is empty , According to each draw, the last card is drawn .

Examples #1

The sample 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

Sample output #1

FP
DEAD
DEAD
J J J J J J D

Tips

Sample explanation

The first round ：

• The main pig has no target to show hostility ;
• Next, Zhongzhu used $3$ Zhang Nan pig invades , The main pig fell $3$ A little physical strength , And that the role is anti - pig ,$3$ No. 1 character is impeccable in spite of his hands , But because I didn't identify myself , So you can't use it for yourself , Just drop it $3$ A little physical strength ;

Next round ：

• Anti pig has no card to play ;
• Then the main pig broke out against the anti pig , Use $4$ Zhang duels , Loyal pig dies , As a result, the main pig discarded all cards ;
• Come down and touch the pig $1$ Zhang Sha directly kills the main pig and wins .

The subtasks

altogether $20$ Group test data , Each point $5$ branch .

$10\%$ There is no gold medal in the data , in addition $20\%$ The data is not impeccable .

Answer key

Big big big big big big big big simulation ！！！！！！

The problem is very simple , Just simulate it once

I just WA More than ten times

First store the player information of the structure

struct Player{
    
	int s,nxt,lst;                                   // physical strength , The previous player and the next player 
	string id;                                       //MP Main pig ,ZP Zhongzhu ,FP Anti pig 
	int cl;                                          // Number of cards in hand  
	char c[MAXCARD];                                 //P peach ,K kill ,D Flash ,F duel ,N The southern pig invades ,W Thousands have been ,J With no chink in one's armour 
	bool f;                                          //1 It means to equip various brothers' crossbows ,0 conversely  
	bool dead;                                       //0 Means alive ,1 Death  
}player[MAXPLAYER];

Touch the card

int m,cl = 1;                                        // The number of cards in the stack , Number of cards touched now  
char card[MAXCARD];  
void mp(int x){
                                          // Touch the card  
	if(cl > m)
		player[x].c[++player[x].cl] = card[m];       //2000 Not enough cards 
	else
		player[x].c[++player[x].cl] = card[cl];	
	cl++;
}

Input and initialization

cin >> n >> m;
for(int i=1;i<=n;i++){
    
	cin >> player[i].id;
	for(int j=1;j<=4;j++) cin >> player[i].c[j];
	if(player[i].id == "FP") fz++;
	player[i].s = player[i].cl = 4;
	player[i].f = false;
	player[i].dead = false;
	player[i].nxt = i+1; player[i].lst = i-1;
}
player[1].lst = n; player[n].nxt = 1;
for(int i=1;i<=m;i++) cin >> card[i];
sf[1] = "MP"; for(int i=2;i<=n;i++) sf[i] = "U";// In the eyes of the main pig ,U = unknown

Output

if(player[1].dead) cout << "FP\n";// Without the main pig, the anti pig wins 
else cout << "MP\n";
for(int i=1;i<=n;i++){
    
    if(player[i].dead) cout << "DEAD\n";
    else{
    
        for(int j=1;j<=player[i].cl;j++)
            if(player[i].c[j] != 'U' && player[i].c[j] != ' ')
                cout << player[i].c[j] << " ";
        cout <<"\n";
    }
} 

10 pts

Let's do it without the brocade bag

It should be noted that

You can only kill once without brother Zhu's crossbow

Anti pig will only attack the main pig and loyal pig

The main pig will only attack anti pig and anti pig

Loyal pigs only attack anti pigs

After the attack ( Show hostility ) Will expose your identity

The main program

bool ed;// Indicates whether the game is over 
void slove(){
    
	char nc;//now_card
	ed = (fz == 0);// There is no anti thief in a game. The game ends directly 
	if(ed) return;
	for(int i=1;i;i=player[i].nxt){
    
		mp(i); mp(i);// Each person touches two cards first 
		bool k = true; // Judge whether you can use overkill 
		for(int j=1;j<=player[i].cl;j++){
    
			nc = player[i].c[j];
			if(nc == 'U') continue;
			if(player[i].dead) break;
			if(nc == 'P'){
    // If you are not satisfied with your blood, you can return it directly 
				if(player[i].s != 4) player[i].s++,player[i].c[j] = 'U';
				continue;
			}
			else if(nc == 'K'){
    
				if(!k && !player[i].f) continue;// I have used the crossbow to kill and have no brother pig 
				if(player[i].id == "MP" && sf[player[i].nxt] != "FP" && sf[player[i].nxt] != "LFP") continue;// The main pig will only attack anti pig and anti pig 
				if(player[i].id == "ZP" && sf[player[i].nxt] != "FP") continue;// Loyal pigs only attack anti pigs 
				if(player[i].id == "FP" && sf[player[i].nxt] != "MP" && sf[player[i].nxt] != "ZP") continue;// Anti pig will only attack the main pig and loyal pig 
				player[i].c[j] = 'U';
				kil(i,player[i].nxt);
				sf[i] = player[i].id;
				k = false;
				if(ed) return;
				continue;
			}
			else if(nc == 'Z'){
    /// Equip brother pig crossbow 
				player[i].f = true;
				player[i].c[j] = 'U';
				j = 0;// Because there may be a killer ahead , So we have to look again 
				continue;
            }
		)
	}
}

kill

void kil(int x,int y){
                                    // kill  
	for(int i=1;i<=player[y].cl;i++)
		if(player[y].c[i] == 'D'){
    // If there is a flash, flash 
			player[y].c[i] = 'U';
			return;
		}
	player[y].s--;
	if(!player[y].s) js(x,y);// Remember to judge whether anyone died 
}

Judge to kill

void js(int x,int y){
                                     // Judge to kill  
	for(int i=1;i<=player[y].cl;i++)
		if(player[y].c[i] == 'P'){
    // If there are peaches, blood will return 
			player[y].c[i] = 'U';
			player[y].s++;
			return;
		}
	player[y].dead = 1;// There is no peach 
	player[player[y].lst].nxt = player[y].nxt;// The death of one player will change the position of other players 
	player[player[y].nxt].lst = player[y].lst;
	if(y == 1){
    ed = true; return;}// The main pig is gone , Anti pig victory 
	if(player[y].id == "FP") fz--;
	if(!fz){
    ed = true;return;}// The anti pig is gone , The main pig wins 
	if(player[y].id == "FP"){
    mp(x);mp(x);mp(x);}// Kill the anti pig and touch three cards 
	if(player[x].id == "MP" && player[y].id == "ZP") player[x].cl = 0,player[x].f = false;
    // The main pig kills the loyal pig and discards the card , equipment 
}

Just stay with me

30 pts

Let's not be faultless , Make other brocade bags

Remember to judge whether the game is over after each damage attack

Note that the identity will not be exposed after the South pig invasion and the ten thousand arrows are used

The main program

bool ed;// Indicates whether the game is over 
void slove(){
    
	char nc;//now_card
	ed = (fz == 0);// There is no anti thief in a game. The game ends directly 
	if(ed) return;
	for(int i=1;i;i=player[i].nxt){
    
		mp(i); mp(i);// Each person touches two cards first 
		bool k = true; // Judge whether you can use overkill 
		for(int j=1;j<=player[i].cl;j++){
    
			nc = player[i].c[j];
			if(nc == 'U') continue;
			if(player[i].dead) break;
			if(nc == 'P'){
    // If you are not satisfied with your blood, you can return it directly 
				if(player[i].s != 4) player[i].s++,player[i].c[j] = 'U';
				continue;
			}
			else if(nc == 'K'){
    
				if(!k && !player[i].f) continue;// I have used the crossbow to kill and have no brother pig 
				if(player[i].id == "MP" && sf[player[i].nxt] != "FP" && sf[player[i].nxt] != "LFP") continue;// The main pig will only attack anti pig and anti pig 
				if(player[i].id == "ZP" && sf[player[i].nxt] != "FP") continue;// Loyal pigs only attack anti pigs 
				if(player[i].id == "FP" && sf[player[i].nxt] != "MP" && sf[player[i].nxt] != "ZP") continue;// Anti pig will only attack the main pig and loyal pig 
				player[i].c[j] = 'U';
				kil(i,player[i].nxt);
				sf[i] = player[i].id;
				k = false;
				if(ed) return;
				continue;
			}
			else if(nc == 'Z'){
    /// Equip brother pig crossbow 
				player[i].f = true;
				player[i].c[j] = 'U';
				j = 0;// Because there may be a killer ahead , So we have to look again , The same below 
				continue;
            }
            else if(nc == 'W'){
    // Thousands have been 
				wjqf(i);
				player[i].c[j] = 'U';
				if(ed) return;
				j=0;
				continue;
			}
			else if(nc == 'N'){
    
				nzrq(i);
				player[i].c[j] = 'U';
				if(ed) return;
				j=0;
				continue;
			}
            else if(nc == 'F'){
    
				if(player[i].id == "FP"){
    
					player[i].c[j] = 'U';
					jd(i,1);// Anti pig will show hostility to the main pig 
					sf[i] = player[i].id;
					if(ed) return;
					j=0;
					continue;
				}
				for(int k=player[i].nxt;k!=i;k=player[k].nxt){
    
					if(player[i].id == "MP" && (sf[k] == "FP" || sf[k] == "LFP") || player[i].id == "ZP" && sf[k] == "FP"){
    // Will only show hostility to the enemy 
						player[i].c[j] = 'U';
						jd(i,k);
						sf[i] = player[i].id;// After expressing hostility, his identity was exposed 
						if(ed) return;
						j=0;
						break;
					}
				}
				continue;
			}
		)
	}
}

The southern pig invades

Imitate according to the question

void nzrq(int x){
                                         // The southern pig invades  
	for(int i=player[x].nxt;i!=x;i=player[i].nxt){
    
		int j;
		for(j=1;j<=player[i].cl;j++){
    
			if(player[i].c[j] == 'K'){
    
				player[i].c[j] = 'U';
				break;
			}
		}
		if(j > player[i].cl){
    
			player[i].s--;
			if(!player[i].s) js(x,i);
			if(i == 1 && sf[x] == "U") sf[x] = "LFP";
			if(ed) return;
		}
	}
}

Thousands have been

It's almost the same as the southern pig invasion , Only the function name and one letter are missing

void wjqf(int x){
                                         // Thousands have been  
	for(int i=player[x].nxt;i!=x;i=player[i].nxt){
    
		int j;
		for(j=1;j<=player[i].cl;j++){
    
			if(player[i].c[j] == 'D'){
    
				player[i].c[j] = 'U';
				break;
			}
		}
		if(j > player[i].cl){
    
			player[i].s--;
			if(i == 1 && sf[x] == "U") sf[x] = "LFP";
			if(!player[i].s) js(x,i);
			if(ed) return;
		}
	}
}

duel

void jd(int x,int y){
                                     // duel  
	if(wxkj(x,y,1)) return;
	if(x == 1 && player[y].id == "ZP"){
    
        // Notice that the loyal pig will only bleed if beaten by the main pig 
		player[y].s--;
		if(!player[y].s) js(x,y);
		return;
	}
	int j,k;
	j = k = 1;
	while(true){
    
		for(;j<=player[y].cl;j++)// Pay attention to the opposite side first, not yourself 
			if(player[y].c[j] == 'K') break;
		if(j > player[y].cl){
    
			player[y].s--;
			if(!player[y].s) js(x,y);
			return;
		}
		else player[y].c[j] = 'U';
		for(;k<=player[x].cl;k++)
			if(player[x].c[k] == 'K') break;
		if(k > player[x].cl){
    
			player[x].s--;
			if(!player[x].s) js(y,x);// Don't write backwards 
			return;
		}
		else player[x].c[k] = 'U';
	}
}

100 pts

The next is the most difficult and impeccable

There are two scenarios

The first kind of impeccability is used to counteract impeccability

The second is the opposite

You can use something like $dfs$ Realization

With no chink in one's armour

bool wxkj(int x,int y,bool z){
                             // With no chink in one's armour  z：0 It is impeccable  
	int i = x;
	while(true){
    
		if(z){
    
			if(player[i].id == sf[y] || (player[i].id == "MP" && sf[y] == "ZP") || (player[i].id == "ZP" && sf[y] == "MP"))// Arrive for your teammates 
				for(int j=1;j<=player[i].cl;j++)
					if(player[i].c[j] == 'J'){
    
						player[i].c[j] = 'U';
						sf[i] = player[i].id;
						return !wxkj(i,x,0);
					}
		}
		else{
    
			if((sf[x] == "FP" && (player[i].id == "MP" || player[i].id == "ZP")) || (player[i].id == "FP" && (sf[x] == "MP" || sf[x] == "ZP")))// Remove the invulnerability of the enemy 
				 for(int j=1;j<=player[i].cl;j++)
					if(player[i].c[j] == 'J'){
    
						player[i].c[j] = 'U';
						sf[i] = player[i].id;
						return !wxkj(i,x,0);
					}
			
		}
		i = player[i].nxt;
		if(i == x) break;
	}
	return false; 
}

Complete code

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int MAXPLAYER = 15;
const int MAXCARD = 2100;
int n;                                               // Number of players  
struct Player{
    
	int s,nxt,lst;                                   // physical strength 
	string id;                                       //MP Main pig ,ZP Zhongzhu ,FP Anti pig 
	int cl;                                          // Number of cards in hand  
	char c[MAXCARD];                                 //P peach ,K kill ,D Flash ,F duel ,N The southern pig invades ,W Thousands have been ,J With no chink in one's armour 
	bool f;                                          //1 It means to equip various brothers' crossbows ,0 conversely  
	bool dead;                                       //0 Means alive ,1 Death  
}player[MAXPLAYER];
bool ed = false;
int m,cl = 1;                                        // The number of cards in the stack , Number of cards touched now  
char card[MAXCARD];                                  // Cards in the stack 
string sf[MAXPLAYER];                                // Identity in the eyes of the main pig  
int fz;                                              // Anti thief number  
void mp(int x){
                                          // Touch the card  
	if(cl > m){
    
		player[x].c[++player[x].cl] = card[m];
	}
	else{
    
		player[x].c[++player[x].cl] = card[cl];	
	}
	cl++;
}
void js(int x,int y){
                                     // Judge to kill  
	for(int i=1;i<=player[y].cl;i++)
		if(player[y].c[i] == 'P'){
    
			player[y].c[i] = 'U';
			player[y].s++;
			return;
		}
	player[y].dead = 1;
	player[player[y].lst].nxt = player[y].nxt;
	player[player[y].nxt].lst = player[y].lst;
	if(y == 1){
    ed = true; return;}
	if(player[y].id == "FP") fz--;
	if(!fz){
    ed = true;return;}
	if(player[y].id == "FP"){
    mp(x);mp(x);mp(x);}
	if(player[x].id == "MP" && player[y].id == "ZP") player[x].cl = 0,player[x].f = false;
}
void kil(int x,int y){
                                    // kill  
	for(int i=1;i<=player[y].cl;i++)
		if(player[y].c[i] == 'D'){
    
			player[y].c[i] = 'U';
			return;
		}
	player[y].s--;
	if(!player[y].s) js(x,y);
}
bool wxkj(int x,int y,bool z){
                             // With no chink in one's armour  z：0 It is impeccable  
	int i = x;
	while(true){
    
		if(z){
    
			if(player[i].id == sf[y] || (player[i].id == "MP" && sf[y] == "ZP") || (player[i].id == "ZP" && sf[y] == "MP"))
				for(int j=1;j<=player[i].cl;j++)
					if(player[i].c[j] == 'J'){
    
						player[i].c[j] = 'U';
						sf[i] = player[i].id;
						return !wxkj(i,x,0);
					}
		}
		else{
    
			if((sf[x] == "FP" && (player[i].id == "MP" || player[i].id == "ZP")) || (player[i].id == "FP" && (sf[x] == "MP" || sf[x] == "ZP")))
				 for(int j=1;j<=player[i].cl;j++)
					if(player[i].c[j] == 'J'){
    
						player[i].c[j] = 'U';
						sf[i] = player[i].id;
						return !wxkj(i,x,0);
					}
			
		}
		i = player[i].nxt;
		if(i == x) break;
	}
	return false; 
}
void nzrq(int x){
                                         // The southern pig invades  
	for(int i=player[x].nxt;i!=x;i=player[i].nxt){
    
		if(wxkj(x,i,1)) continue;
		int j;
		for(j=1;j<=player[i].cl;j++){
    
			if(player[i].c[j] == 'K'){
    
				player[i].c[j] = 'U';
				break;
			}
		}
		if(j > player[i].cl){
    
			player[i].s--;
			if(!player[i].s) js(x,i);
			if(i == 1 && sf[x] == "U") sf[x] = "LFP";
			if(ed) return;
		}
	}
}
void wjqf(int x){
                                         // Thousands have been  
	for(int i=player[x].nxt;i!=x;i=player[i].nxt){
    
		if(wxkj(x,i,1)) continue;
		int j;
		for(j=1;j<=player[i].cl;j++){
    
			if(player[i].c[j] == 'D'){
    
				player[i].c[j] = 'U';
				break;
			}
		}
		if(j > player[i].cl){
    
			player[i].s--;
			if(i == 1 && sf[x] == "U") sf[x] = "LFP";
			if(!player[i].s) js(x,i);
			if(ed) return;
		}
	}
}
void jd(int x,int y){
                                     // duel  
	if(wxkj(x,y,1)) return;
	if(x == 1 && player[y].id == "ZP"){
    
		player[y].s--;
		if(!player[y].s) js(x,y);
		return;
	}
	int j,k;
	j = k = 1;
	while(true){
    
		for(;j<=player[y].cl;j++)
			if(player[y].c[j] == 'K')
				break;
		if(j > player[y].cl){
    
			player[y].s--;
			if(!player[y].s) js(x,y);
			return;
		}
		else player[y].c[j] = 'U';
		for(;k<=player[x].cl;k++)
			if(player[x].c[k] == 'K')
				break;
		if(k > player[x].cl){
    
			player[x].s--;
			if(!player[x].s) js(y,x);
			return;
		}
		else player[x].c[k] = 'U';
	}
}
void slove(){
    
	char nc;
	ed = (fz == 0);
	if(ed) return;
	for(int i=1;i;i=player[i].nxt){
    
		mp(i); mp(i);
		bool k = true; // Judge whether you can use overkill 
		for(int j=1;j<=player[i].cl;j++){
    
			nc = player[i].c[j];
			if(nc == 'U') continue;
			if(player[i].dead) break;
			if(nc == 'P'){
    
				if(player[i].s != 4) player[i].s++,player[i].c[j] = 'U';
				continue;
			}
			else if(nc == 'K'){
    
				if(!k && !player[i].f) continue;
				if(player[i].id == "MP" && sf[player[i].nxt] != "FP" && sf[player[i].nxt] != "LFP") continue;
				if(player[i].id == "ZP" && sf[player[i].nxt] != "FP") continue;
				if(player[i].id == "FP" && sf[player[i].nxt] != "MP" && sf[player[i].nxt] != "ZP") continue;
				player[i].c[j] = 'U';
				kil(i,player[i].nxt);
				sf[i] = player[i].id;
				k = false;
				if(ed) return;
				continue;
			}
			else if(nc == 'Z'){
    
				player[i].f = true;
				player[i].c[j] = 'U';
				j = 0;
				continue;
			}
			else if(nc == 'W'){
    
				wjqf(i);
				player[i].c[j] = 'U';
				if(ed) return;
				j=0;
				continue;
			}
			else if(nc == 'N'){
    
				nzrq(i);
				player[i].c[j] = 'U';
				if(ed) return;
				j=0;
				continue;
			}
			else if(nc == 'F'){
    
				if(player[i].id == "FP"){
    
					player[i].c[j] = 'U';
					jd(i,1);
					sf[i] = player[i].id;
					if(ed) return;
					j=0;
					continue;
				}
				for(int k=player[i].nxt;k!=i;k=player[k].nxt){
    
					if(player[i].id == "MP" && (sf[k] == "FP" || sf[k] == "LFP") || player[i].id == "ZP" && sf[k] == "FP"){
    
						player[i].c[j] = 'U';
						jd(i,k);
						sf[i] = player[i].id;
						if(ed) return;
						j=0;
						break;
					}
				}
				continue;
			}
		} 
	}
}
int main(){
    
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
    
		cin >> player[i].id;
		for(int j=1;j<=4;j++) cin >> player[i].c[j];
		if(player[i].id == "FP") fz++;
		player[i].s = player[i].cl = 4;
		player[i].f = false;
		player[i].dead = false;
		player[i].nxt = i+1; player[i].lst = i-1;
	}
	player[1].lst = n; player[n].nxt = 1;
	for(int i=1;i<=m;i++) cin >> card[i];
	sf[1] = "MP"; for(int i=2;i<=n;i++) sf[i] = "U";
	slove();
	if(player[1].dead) cout << "FP\n";
	else cout << "MP\n";
	for(int i=1;i<=n;i++){
    
		if(player[i].dead) cout << "DEAD\n";
		else{
    
			for(int j=1;j<=player[i].cl;j++)
				if(player[i].c[j] != 'U' && player[i].c[j] != ' ')
					cout << player[i].c[j] << " ";
			cout <<"\n";
		}
	} 
	return 0;
}

then