Recently, the ACM/ICPC team of Marjar University decided to choose some new members from freshmen to take part in the ACM/ICPC competitions of the next season. As a traditional elite university in ACM/ICPC, there is no doubt that application forms will fill up the mailbox. To constitute some powerful teams, coaches of the ACM/ICPC team decided to use a system to score all applicants, the rules are described as below. Please note that the score of an applicant is measured by pts, which is short for "points".

1. Of course, the number of solved ACM/ICPC problems of a applicant is important. Proudly, Marjar University have a best online judge system called Marjar Online Judge System V2.0, and in short, MOJ. All solved problems in MOJ of a applicant will be scored under these rules:

• (1) The problems in a set, called MaoMao Selection, will be counted as 2.5 pts for a problem.
• (2) The problems from Old Surgeon Contest, will be counted as 1.5 pts for a problem.

There is no problem in MaoMao Selection from Old Surgeon Contest.

• (3) Besides the problem from MaoMao Selection and Old Surgeon Contest, if the problem‘s id is a prime, then it will be counted as 1 pts.
• (4) If a solved problem doesn‘t meet above three condition, then it will be counted as 0.3 pts.

2. Competitions also show the strength of an applicant. Marjar University holds the ACM/ICPC competition of whole school once a year. To get some pts from the competition, an applicant should fulfill rules as below:

• The member of a team will be counted as 36 pts if the team won first prize in the competition.
• The member of a team will be counted as 27 pts if the team won second prize in the competition.
• The member of a team will be counted as 18 pts if the team won third prize in the competition.
• Otherwise, 0 pts will be counted.

3. We all know that some websites held problem solving contest regularly, such as JapanJam, ZacaiForces and so on. The registered member of JapanJam will have a rating after each contest held by it. Coaches thinks that the third highest rating in JapanJam of an applicant is good to show his/her ability, so the scoring formula is:

Here r is the third highest rating in JapanJam of an applicant.

4. And most importantly - if the applicant is a girl, then the score will be added by 33 pts.

The system is so complicated that it becomes a huge problem for coaches when calculating the score of all applicants. Please help coaches to choose the best M applicants!

Input

There are multiple test cases.

The first line of input is an integer T (1 ≤ T ≤ 10), indicating the number of test cases.

For each test case, first line contains two integers N (1 ≤ N ≤ 500) - the number of applicants and M (1 ≤ M ≤ N) - the number of members coaches want to choose.

The following line contains an integer R followed by R (0 ≤ R ≤ 500) numbers, indicating the id of R problems in MaoMao Selection.

And then the following line contains an integer S (0 ≤ S ≤ 500) followed by S numbers, indicating the id of S problems from Old Surgeon Contest.

The following line contains an integer Q (0 ≤ Q ≤ 500) - There are Q teams took part in Marjar University‘s competition.

Following Q lines, each line contains a string - team name and one integer - prize the team get. More specifically, 1 means first prize, 2 means second prize, 3 means third prize, and 0 means no prize.

In the end of each test case, there are N parts. In each part, first line contains two strings - the applicant‘s name and his/her team name in Marjar University‘s competition, a char sex - M for male, F for female and two integers P (0 ≤ P ≤ 1000) - the number of problem the applicant solved, C (0 ≤ C ≤ 1000) - the number of competitions the applicant have taken part in JapanJam.

The following line contains P integers, indicating the id of the solved problems of this applicant.

And, the following line contains C integers, means the rating for C competitions the applicant have taken part in.

We promise:

• The problems‘ id in MaoMao Selection, Old Surgeon Contest and applicant‘s solving list are distinct, and all of them have 4 digits (such as 1010).
• All names don‘t contain spaces, and length of each name is less than 30.
• All ratings are non-negative integers and less than 3500.

Output

For each test case, output M lines, means that M applicants and their scores. Please output these informations by sorting scores in descending order. If two applicants have the same rating, then sort their names in alphabet order. The score should be rounded to 3 decimal points.

Sample Input

15 33 1001 1002 10034 1004 1005 1006 10073MagicGirl!!! 3Sister‘s_noise 2NexusHD+NexusHD 1Edward EKaDiYaKanWen M 5 31001 1003 1005 1007 10091800 1800 1800FScarlet MagicGirl!!! F 3 51004 1005 10071300 1400 1500 1600 1700A NexusHD+NexusHD M 0 0B None F 0 0IamMM Sister‘s_noise M 15 11001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 10153000

Sample Output

FScarlet 60.000IamMM 44.300A 36.000

/** @Author: lyuc* @Date:   2017-04-15 17:39:24* @Last Modified by:   lyuc* @Last Modified time: 2017-04-16 15:56:46*//*题意：题目太长导致，三个英语渣没翻译明白题目。    大致意思就是给你选手算分的方式，然后让你输出排名前三的选手    给出你 n m 选手数量，输出排名前m的选手    然后给出你两个OJ的题目序号    第一个是MaoMao Selection    第二个是Old Surgeon Contest    然后是给你获奖队伍的数量    接着是获得前三等奖的队伍名称以及奖的等级    接着给出n各选手的信息    姓名 队伍名 性别 OJ做题的数量 参加比赛的数量    然后是：        OJ做题的编号        参加比赛获得分数    算分的规则：    1.        如果你所在的队伍获得一等奖，那么你+36分        如果你所在的队伍获得二等奖，那么你+27分        如果你所在的队伍获得一等奖，那么你+18分    2.        女选手+33分    3.        在MaoMao Selection做的题目+2.5分        在Old Surgeon Contest做的题目+1.5分        不在这两个OJ但是题目序号是素数的+1分        其余的题目+0.3分    4.        你参加的比赛场次如果大于等于三场        那么取分数第三高的分数        加上max(0, (r - 1200) / 100) * 1.5分数*/#include <bits/stdc++.h>#define ll long long#define INF 0x3f3f3f3f#define pb push_back#define exp 1e-6using namespace std; struct People{    string name;//人名    string team;//队名    string sex;//性别    double score;//分数    int testnum;//参加比赛的数目    double testscore[1010];//参加比赛的分数    bool operator < (const People & other) const{//从大到小排序        return score-other.score>exp;    }}people[505];struct Team{    string name;//队伍名    int rank;//名词}team[505];int t;int n,m;//选手人数，需要输出的前几名int mao[505];//存储mao OJ的题目int maonum;//mao OJ题目的数量int sur[505];//存储sur OJ的题目int surnum;//sur OJ题目的数量int prizenum;//获奖队伍数int num;//oj的做题数目bool Prime(int x){//判断题号是否为素数    for(int i=2;i*i<=x;i++)        if(x%i==0)            return false;    return true;}double getscore(int x){//判断该题号的得分    for(int i=0;i<maonum;i++){        if(x==mao[i])            return 2.5;    }    for(int i=0;i<surnum;i++){        if(x==sur[i])            return 1.5;    }    if(Prime(x))         return 1;    else        return 0.3;}double getteam(string x){    for(int i=0;i<prizenum;i++){        if(x==team[i].name){            if(team[i].rank==1)                return 36;            else if(team[i].rank==2)                return 27;            else if(team[i].rank==3)                return 18;        }    }    return 0;}bool cmp(double a,double b){    return a>b;}int main(){    // freopen("in.txt","r",stdin);    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&m);        //输入两个oj的题目        scanf("%d",&maonum);        for(int i=0;i<maonum;i++){            scanf("%d",&mao[i]);        }        scanf("%d",&surnum);        for(int i=0;i<surnum;i++){            scanf("%d",&sur[i]);        }        //输入获奖名单        scanf("%d",&prizenum);        for(int i=0;i<prizenum;i++){            cin>>team[i].name>>team[i].rank;        }        for(int i=0;i<n;i++){            cin>>people[i].name>>people[i].team>>people[i].sex;            scanf("%d%d",&num,&people[i].testnum);            people[i].score=0;            //OJ得分            for(int j=0;j<num;j++){                int x;                scanf("%d",&x);                people[i].score+=getscore(x);            }            for(int j=0;j<people[i].testnum;j++){                scanf("%lf",&people[i].testscore[j]);            }            //女生加分            if(people[i].sex=="F")                people[i].score+=33;            //团队加分            people[i].score+=getteam(people[i].team);                        //大赛加分            if(people[i].testnum>=3){                sort(people[i].testscore,people[i].testscore+people[i].testnum,cmp);                people[i].score+=max(0.0,(people[i].testscore[2]-1200)/100)*1.5;            }        }        sort(people,people+n);        for(int i=0;i<m;i++){            cout<<people[i].name;            printf(" %.3lf\n",people[i].score);        }    }    return 0;}

ZOJ 3705 Applications