Men in Black

Everybody knows that men in black protect our Earth from alien cockroaches and other vermin. They track all movements of our alien foes and friends and control their actions. But recently, the government has learned about men in black and decided to track all their movements.

There are several agents. Each agent has several characteristics: accuracy, intelligence, walking speed, experience, and driving skill. All characteristics are real numbers ranging from $0$ to $1$. Also, each agent has a code letter from $A$ to $Z$, since his name is top secret. When a new agent joins the organization, he is assigned the letter closest to the first letter of his name that is not assigned to any agent. If there are several such letters, the one which comes first lexicographically is chosen. For example, if there are already agents $J$, $K$, and $L$ in the organization, and an agent named Killer joins, he gets the letter $I$.

Men in black have several cars that agents use in their work. The speed of an agent when driving is equal to his driving skill. However, some cars require the agent to have a driving skill greater than or equal to a predefined value. Each car has a maximum distance it can travel before becoming unusable.

There are several kinds of alien monsters in the universe that men in black fight. An agent can kill a monster if his experience and intelligence are greater than or equal to some predefined values for this kind of monster. Each kind of monster has an evasiveness value, and depending on the agent's accuracy, it can take different amounts of time to kill a monster. A killed monster gives the agent who killed it some experience.

There are four types of quests that men in black perform:

1. **Delivery quest** — Get from the office to the destination point and back. For such quests, the distance from the office to the destination point is given. 2. **Kill the monster quest** — Get to the monster, kill it, and get back. For such a quest, you are given the distance to the monster and its kind. The time that an agent with accuracy $a$ needs to kill a monster with evasiveness $e$ is equal to $e/a$. The agent receives (1-x) \cdot m / \max x experience, where $x$ is the agent's experience, $m$ is the experience value associated with this kind of monster, and $\max x$ is the maximal possible experience. The agent's accuracy increases by (1-a) \cdot e / \max e where $\max e$ is the maximal possible evasiveness of monsters. 3. **Investigation quest** — Get to the point where the investigation is needed, perform it, get back. For such a quest, you are given the distance to the investigation point and the minimal intelligence required. The time needed to perform the investigation by an agent with intelligence $i$ is $\min t/i$, where $\min t$ is the minimal required time for the investigation. After completing the investigation, the agent receives (1-x) \cdot i / \min t experience (where $x$ is the agent's experience before the operation). His intelligence increases by (1-i) \cdot i / \min t. 4. **Negotiations quest** — Get to the point of negotiations, discuss, and get back. You are given the distance from the office to the negotiations point and the minimal experience required. The time needed for an agent with experience $x$ to complete the discussion is $\min t/x$, where $\min t$ is the minimal required time. After negotiations, the agent receives (1-x) \cdot x / \min t additional experience.

Each quest can be performed by one or two agents. If two agents perform the same quest, after it their characteristics change as if each of them completed the quest alone. An agent can walk to the quest location or drive there. If the car breaks while the agent is driving, he must continue on foot for the remainder of the journey. If the quest is performed by two agents, they can use the same car to get there.

The following algorithm is used to choose an agent or a pair of agents to perform a quest:

- The agent (or pair) who would complete the quest in the shortest time is chosen. - If several possibilities exist: 1. One agent is preferred over a pair of agents. 2. Among agents, the one with the smallest letter is chosen; for pairs, the ordered pairs of letters are compared. 3. Agents always choose a car that allows them to perform the quest in the shortest time. If the time is the same without a car, the car is not used. 4. If several cars provide the same quest time, the car with the lexicographically smallest ID is chosen.

All quests are performed as soon as they can be. If multiple quests are available, the one that was received first is performed first.

After the agent completes a quest where he had to walk, his walking speed increases by (1-s) \cdot d / \max d, where $s$ is his walking speed before the quest, $d$ is the distance he walked, and $\max d$ is the maximal possible walking distance. If the agent was driving for any distance, his driving skill increases by (1-z) \cdot d / \max d, where $z$ is the agent's driving skill before the quest, and $d$ is the distance driven.

For pairs, the following rules are used when performing a quest: - Walking speed: minimum of the agents' walking speeds. - Driving skill: maximum of the agents' driving skills. - Accuracy: (a_1 + a_2)/2. - Experience: 1 - (1-e_1)(1-e_2). - Intelligence: 1 - (1-i_1)(1-i_2).

The following events can happen: receiving a new quest, arrival of a new agent, purchase of a new car.

If an agent's experience becomes greater than or equal to the retirement experience, the agent leaves the organization immediately after completing his last quest. His letter becomes free and can be assigned to a new agent. There are never more than $26$ agents in the agency at any time.

All time intervals in this problem are in minutes and rounded to the nearest minute (standard rules). For example, the driving, walking (when a car breaks), and killing a monster intervals must be rounded independently.