{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEverybody knows that men in black protect our Earth from alien cockroaches \r\nand other vermin. They track all movements of our alien foes and friends\r\nand control their actions. But recently the government has learned\r\nabout men in black and decided to track all their movements.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are several agents. Each agent has several characteristics:\r\naccuracy, intelligence, walking speed, experience, driving skill.\r\nAll characteristics are real numbers ranging from 0 to 1. \r\nAlso each agent has a code letter \"A\" to \"Z\", since his name\r\nis top secret. When the new agent comes to the organization\r\nhe is assigned a letter closest to the first letter of the agent name,\r\nthat is not assigned to any agent. If\r\nthere are several such letters, the one which goes first lexicographically\r\nis chosen. For example, if there are already agents \"J\", \"K\" and \"L\"\r\nin the organization, and the agent with the name \"Killer\"\r\ncomes, he gets the letter \"I\".\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eMen in black have several cars that agents use in their work.\r\nThe speed of the agent when driving is equal to his driving skill.\r\nBut some cars require the agent that drives it to have a\r\ndriving skill greater or equal to some predefined value.\r\nEach car has some distance that it can pass before it can\r\nno longer be used.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are several kinds of alien monsters in the universe that \r\nmen in black fight with. The agent can kill a monster if\r\nhis experience and his intelligence are greater or equal\r\nto some predefined values for this kind of monster. Each \r\nkind of monster has evasiveness, and depending on the \r\nagent\u0027s accuracy it can take different time to kill a monster.\r\nA killed monster gives the agent who has killed him\r\nsome experience.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are four types of quests that men in black perform.\r\n\r\n\u003col\u003e\r\n\u003cli\u003e \r\n Delivery quest\u0026nbsp;— get from the office to the \r\n destination point and back. For such quests the distance\r\n from the office to the destination point is given.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n Kill the monster quest\u0026nbsp;— get to the monster, kill him,\r\n get back. For such a quest you are given a distance to the\r\n monster and its kind. The time that an agent with accuracy\r\n \u003ci\u003ea\u003c/i\u003e needs to kill a monster with evasiveness \u003ci\u003ee\u003c/i\u003e is equal to \u003ci\u003ee\u003c/i\u003e/\u003ci\u003ea\u003c/i\u003e.\r\n The agent gets (1−\u003ci\u003ex\u003c/i\u003e)·\u003ci\u003em\u003c/i\u003e/\u003ci\u003emaxx\u003c/i\u003e experience,\r\n here \u003ci\u003ex\u003c/i\u003e is the experience of the agent, \r\n \u003ci\u003em\u003c/i\u003e is some experience value that is associated with this\r\n kind of monster, and \u003ci\u003emaxx\u003c/i\u003e is the theoretically \r\n maximal experience value. Agent\u0027s\r\n accuracy increases by (1−\u003ci\u003ea\u003c/i\u003e)·\u003ci\u003ee\u003c/i\u003e/\u003ci\u003emaxe\u003c/i\u003e where \u003ci\u003emaxe\u003c/i\u003e\r\n is the maximal theoretically possible evasiveness of monsters.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n Investigation\u0026nbsp;— get to the point where the investigation\r\n is needed, perform it, get back. For such a quest you are\r\n given a distance to the investigation point, and the minimal\r\n intelligence required to perform the investigation.\r\n The time needed to perform an investigation by an agent\r\n with intelligence \u003ci\u003ei\u003c/i\u003e is \u003ci\u003emint\u003c/i\u003e/\u003ci\u003ei\u003c/i\u003e where \u003ci\u003emint\u003c/i\u003e is the minimum\r\n time required to perform this investigation. After completing\r\n the investigation the agent gets (1−\u003ci\u003ex\u003c/i\u003e)·\u003ci\u003ei\u003c/i\u003e/\u003ci\u003emint\u003c/i\u003e experience,\r\n where \u003ci\u003ex\u003c/i\u003e is the agent\u0027s experience before the operation.\r\n His intelligence increases by (1−\u003ci\u003ei\u003c/i\u003e)·\u003ci\u003ei\u003c/i\u003e/\u003ci\u003emint\u003c/i\u003e.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n Negotiations\u0026nbsp;— get to the point of negotiations, discuss\r\n hot issues, get back. You are given the distance from the office\r\n to the negotiations point, and the minimal experience of an\r\n agent that can take part in negotiations. The time needed\r\n for an agent with experience \u003ci\u003ex\u003c/i\u003e \r\n to complete the discussion is equal \u003ci\u003emint\u003c/i\u003e/\u003ci\u003ex\u003c/i\u003e\r\n where \u003ci\u003emint\u003c/i\u003e is the minimum time needed. After the negotiations\r\n the agent gets (1−\u003ci\u003ex\u003c/i\u003e)·\u003ci\u003ex\u003c/i\u003e/\u003ci\u003emint\u003c/i\u003e additional experience.\r\n\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEach quest can be performed by one or two agents. If two agents\r\nperform the same quest, after it their characteristics change as if each\r\nof them completed this quest alone. An agent can walk to the location\r\nwhere the quest must be performed, or drive there. If the car\r\nbreaks while the agent is driving, he must continue to walk\r\nto the location he was driving to. If the quest is performed\r\nby two agents, they can use the same car to get to its location.\r\n\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following algorithm is used to choose an agent or a pair of \r\nagents to perform the quest. An agent (a pair of agents) is chosen\r\nthat would perform the quest in the shortest time. If there are\r\nseveral possibilities, the following tie breaking rules are used.\r\nIf it is possible to choose one agent or a pair of agents, one\r\nagent is chosen. If there are two candidate agents, the one who has \r\nthe smaller letter assigned is chosen (for pairs of agents\r\nthe ordered pairs of letters are compared). \u003cb\u003eAgents always choose a car \r\nin such a way to perform their quest in the shortest time.\u003c/b\u003e If the quest\r\nis completed without using a car within the same time, the car\r\nis not used. If there are several cars available \r\n\u003cb\u003ewith the same quest performing time\u003c/b\u003e, the car with\r\nthe lexicographically smaller id is chosen.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll quests are performed as soon as they can be performed.\r\nIf there are several quests available, the one that was\r\nreceived earlier is performed first.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAfter the agent completed the quest where he had to walk,\r\nhis walking speed increases by (1−\u003ci\u003es\u003c/i\u003e)·\u003ci\u003ed\u003c/i\u003e/\u003ci\u003emaxd\u003c/i\u003e where\r\n\u003ci\u003es\u003c/i\u003e is his walking speed before the quest, \u003ci\u003ed\u003c/i\u003e is the distance\r\nhe walked while performing the quest, \u003ci\u003emaxd\u003c/i\u003e is the maximal\r\npossible walking distance. If the agent was driving\r\na car for some distance, his driving skill increases by \r\n(1−\u003ci\u003ez\u003c/i\u003e)·\u003ci\u003ed\u003c/i\u003e/\u003ci\u003emaxd\u003c/i\u003e where \u003ci\u003ez\u003c/i\u003e is the driving skill of the agent\r\nbefore the quest, \u003cb\u003e\u003ci\u003ed\u003c/i\u003e is the distance he drove while performing the quest\u003c/b\u003e.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eWhen the pair of agents perform the quest, the characteristics\r\nof the pair are calculated using the following algorithm.\r\nPair\u0027s walking speed is minimum of agents\u0027 walking speeds, \r\npair\u0027s driving skill is maximum of agents\u0027 driving skills,\r\npair\u0027s accuracy is (\u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e+\u003ci\u003ea\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e)/2,\r\npair\u0027s experience is 1−(1−\u003ci\u003ee\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e)·(1−\u003ci\u003ee\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e), pair\u0027s\r\nintelligence is 1−(1−\u003ci\u003ei\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e)·(1−\u003ci\u003ei\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e).\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following events can happen: new quest can be received,\r\nnew agent can come, new car can be bought.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf the agent\u0027s experience becomes greater or equal to \r\nsome predefined value called retirement experience,\r\nthe agent gets tired and leaves the organization \r\n\u003cb\u003eimmediately after finishing his last quest\u003c/b\u003e.\r\n\u003cb\u003eHis letter becomes free and a new agent can get it from that moment.\r\nIt is guaranteed that at each moment there are no more than 26 agents in the agency,\r\nno more than 50 non-broken cars,\r\nand no more than 50 received but not yet started quests.\u003c/b\u003e\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll time intervals in this problem are measured in minutes,\r\nall time interval lengths are rounded to the closest minute, standard\r\nrounding rules are used. \u003cb\u003eFor example, the intervals when \r\nan agent drives a car, when he walks after the car is broken, \r\nwhen he kills a monster must be rounded separately.\u003c/b\u003e\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll numbers and words in the input are separated by \r\nspaces and/or line feeds.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe input contains:\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e\r\n The number of agents (at most 26) followed by\r\n the description of agents. Each agent is described by\r\n his name, accuracy, walking speed, intelligence,\r\n experience, driving skill, and the letter he is assigned.\r\n All assigned letters are different. Experience\r\n of each agent is less than the retirement experience.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n The number of car types (at most 50), after that\r\n for each car type: the minimal required driving skill to\r\n drive the car of this type, the distance the car of this\r\n type can run before breaking, the name of the type.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n The number of cars (at most 50), after that for each car:\r\n its type, current distance passed (not exceeding the maximal\r\n distance for cars of this type), its id.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n The number of monster kinds (at most 50), after that for\r\n each monster kind: the minimal experience needed to kill\r\n a monster of this kind, minimal intelligence needed to kill\r\n a monster of this kind, evasiveness of monsters of this kind,\r\n experience value associated with monsters of this kind,\r\n and the name of this kind.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n Maximal walking distance, maximal monsters evasiveness,\r\n maximal experience for monster killing, retirement experience.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n The number of events in the organization (at most 2000).\r\n After that for each event the time it occurs and:\r\n \u003cul\u003e\r\n \u003cli\u003e\r\n For a new agent coming to the organization:\r\n \"newagent\", followed by agent\u0027s name, his\r\n accuracy, walking speed, intelligence, experience, driving\r\n skill. The number of agents never exceeds 26.\r\n \u003c/li\u003e\u003cli\u003e\r\n For a new car bought: \r\n \"newcar\" followed by the type of the car,\r\n its current distance passed, its id.\r\n \u003c/li\u003e\u003cli\u003e\r\n For a delivery quest: \r\n \"quest run\" followed by the distance from the office\r\n to the destination point.\r\n \u003c/li\u003e\u003cli\u003e\r\n For a kill the monster quest: \r\n \"quest kill\" followed by the distance from the office\r\n to the monster and the monster type.\r\n \u003c/li\u003e\u003cli\u003e\r\n For an investigation quest: \r\n \"quest findout\" followed by the distance from the office,\r\n the minimal required intelligence and the minimal investigation \r\n time.\r\n \u003c/li\u003e\u003cli\u003e\r\n For a negotiations quest: \r\n \"quest talk\" followed by the distance from the office,\r\n the minimal required experience and the minimal discussion\r\n time.\r\n \u003c/li\u003e\r\n \u003c/ul\u003e\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll characteristics are floating point numbers ranging from 0 to 1 (not inclusive) \u003cb\u003ewith no more than 2 digits after decimal point\u003c/b\u003e.\r\n\u003cb\u003eMinimal required characteristics for quests might be equal to zero.\u003c/b\u003e\r\nAll other numbers are positive integers and do not exceed 10\u003csup\u003e6\u003c/sup\u003e.\r\nAll agent names, car type names, monster kind names, and car ids\r\ncontain only letters of the English alphabet \u003cb\u003eand digits\u003c/b\u003e, \u003cb\u003ethe lengths of\u003c/b\u003e the names\r\ndo not exceed 10. All names and ids are different. All events\r\nare sorted by the time of occurrence, all times are different.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput all interesting moments to the output in the following format:\r\n\"dddd:hh:mm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026lt;description\u0026gt;\", where \"dddd:hh:mm\" are day, hour and \r\nminute when the interesting event occurs.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following moments are interesting \u003cb\u003e(pay attention to the order)\u003c/b\u003e:\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \"MIB bought a car of class \u0026lt;car type\u0026gt;.\" \u003c/li\u003e\r\n\u003cli\u003e \"Car \u0026lt;id\u0026gt; was broken.\" \u003c/li\u003e\r\n\u003cli\u003e \"Agent \u0026lt;letter1\u0026gt;[ and agent \u0026lt;letter2\u0026gt;] killed monster \u0026lt;monster kind\u0026gt;.\" \u003c/li\u003e\r\n\u003cli\u003e \"Agent \u0026lt;letter1\u0026gt;[ and agent \u0026lt;letter2\u0026gt;] finished quest \u0026lt;number\u0026gt;.\" \u003c/li\u003e\r\n\u003cli\u003e \"Agent \u0026lt;letter\u0026gt; has tired.\" \u003c/li\u003e\r\n\u003cli\u003e \"New agent \u0026lt;name\u0026gt; got a letter \u0026lt;letter\u0026gt;.\" \u003c/li\u003e\r\n\u003cli\u003e \"Agent \u0026lt;letter1\u0026gt;[ and agent \u0026lt;letter2\u0026gt;] started quest \u0026lt;number\u0026gt;[ using car \u0026lt;car id\u0026gt;].\" \u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAll quests are numbered starting from 1 in order they are received.\r\nIf several interesting events occur simultaneously, they\r\nmust be listed in the same order they are described above.\r\n\u003cb\u003eIf several interesting events of the same type occur \r\nsimultaneously, they must be listed in lexicographic order.\u003c/b\u003e\r\n\u003cb\u003eIf two agents perform the quest they must be listed in the \r\nmessages in the order of their code letters.\u003c/b\u003e\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003e\u003cb\u003eIt is guaranteed that all quests can be performed by men in black before 10000 day since beginning.\u003c/b\u003e\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\nJames 0.8 0.7 0.75 0.5 0.85 J\r\n\r\n1\r\n0.4 100 mibLexus\r\n\r\n2\r\nmibLexus 0 pq123bu\r\nmibLexus 12 ab891ah\r\n\r\n1\r\n0.2 0.3 18 100 cockroach\r\n\r\n200 20 200 0.95\r\n\r\n4\r\n10 newagent Klint 0.9 0.8 0.5 0.7 0.86\r\n20 quest run 48\r\n30 newcar mibLexus 47 aa890bu\r\n43 quest kill 100 cockroach\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0000:00:10 New agent Klint got a letter K.\r\n0000:00:20 Agent J started quest 1 using car pq123bu.\r\n0000:00:30 MIB bought a car of class mibLexus.\r\n0000:00:43 Agent K started quest 2 using car ab891ah.\r\n0000:02:12 Agent J finished quest 1.\r\n0000:02:25 Car ab891ah was broken.\r\n0000:03:00 Agent K killed monster cockroach.\r\n0000:05:05 Agent K finished quest 2.\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}