ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Mobile Life

Time limit: 2.0 second
Memory limit: 64 MB
The Sunny Town keeps pace with modern technologies. Not much time has passed since cellular communication was introduced in the town, yet Shpuntik and Vintik have already designed their own mobile phone with a built-in location transmitter. With this phone, no one of the Mites (especially Neznaika) will get lost, because Vintik and Shpuntik will be able to know his location. Now the new phone must be tested. It is decided to carry out the testing in the following way. Shpuntik goes around the town with the phone and writes down its readings on a piece of paper. All of this time Vintik is at the workshop and traces Shpuntik's travel watching a special monitor. When Shpuntik is back, they compare their records. But there's one problem: Shpuntik's record is a list of lines with the phone's readings, and Vintik has a list of numbers describing Shpuntik's travel. Write a program that generates Shpuntik's list using Vintik's list under the assumption that the system works correctly.
The mobile phone that undergoes testing has a chromatic indicator of the signal's power and shows the identier of the current cell. The indicator can show seven dierent colors, namely, the colors of a rainbow. Violet corresponds to the strongest signal and red means that the signal is vanishing and the phone may become disconnected any moment.
If the distance between the phone and a base station is less then a certain value, then the signal is ideal (which corresponds to the violet color of the indicator). This threshold distance may be dierent for dierent stations. If the phone is moved away from a base station further than the threshold distance, then the indicator goes indigo, then blue, green, and so on, until it becomes red and not changes anymore as the signal decreases further. The indicator's color changes each time the signal's power falls 2 decibels. The signal's power depends only on the distance from a base station and is in inverse proportion to this distance. For example, when the distance increases two times, then the power decreases also two times.
The phone selects a base station according to the following rules:
  1. When the phone is being turned on, it selects a station with the strongest signal. If there are several such stations, then the station with the minimal (with respect to the lexicographic order) name of the cell is selected among them.
  2. The phone stays connected to the same station until its signal goes red; then it switches to the search mode and tries to select a new station.
  3. The phone is in the search mode until it finds a station whose signal's level is enough for turning the indicator any color excepting red. If there are several such stations, then the phone uses the same selection rule as in the case of turning on.
Shpuntik writes down the phone's readings in the following format:
  1. Power on. CELL_ID:<cell's_name>, SIGNAL_LEVEL:<indicator's_color>
    — the phone is on.
  2. Cell changed. CELL_ID:<cell's_name>, SIGNAL_LEVEL:<indicator's_color>
    — the change of a base station.
  3. Signal changed. SIGNAL_LEVEL:<indicator's_color>
    — the change of the indicator's color.
Even if the phone instantly switches over to another station, Shpuntik nevertheless writes down the line registering the occurrence of the red indication in the previous cell.
A comment for those who are not familiar with decibels: a decibel is a logarithmic quantity characterizing ratios of values. If signal A has power Wa and signal B has power Wb, then the power of signal B differs from the power of signal A by 10 · log10(Wb/Wa) decibels. When one compares not powers, but, say, voltages, then another formula is used: 20 · log10(Ub/Ua), but Vintik and Shpuntik use the first one.


The first line contains the number of base stations in the Sunny Town: N (1 ≤ N ≤ 100). Then there are N lines describing the cells. Each of these lines is of the following form: Xc Yc Rc Sc. The integer numbers Xc and Yc are the coordinates of a base station.The integer number Rc is its threshold distance within which the station's signal is shown by the violet color of the indicator. Sc is a string without spaces of length not exceeding 50, which is the name of the cell.
The (N+2)-nd line contains a number M, which is the number of linear segments of Shpuntik's route. The following M lines contain 4 integer numbers each: Xs, Ys, Xe, Ye. They are the coordinates of the beginning and of the end of a segment; −10000 ≤ Xc, Yc,Xs, Ys, Xe, Ye ≤ 10000, 0 < Rc ≤ 10000, 1 ≤ M ≤ 1000.
It is guaranteed that Shpuntik's motion is continuous, which means that the end of each segment coincides with the beginning of the following one. Also, we assume that at the points where the segments join, Shpuntik's phone never changed cells and that for each of the stations the curves of change of the signal's level do not pass through these points. And he never went at a tangent to that curves.


Correct Shpuntik's list.


0 0 1 Romashka
0 10 1 Lutik
10 10 2 Znaika
10 0 1 Children
5 5 -5 -5
-5 -5 5 5
Signal changed. SIGNAL_LEVEL:RED
Cell changed. CELL_ID:Romashka, SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:GREEN
Problem Author: Eugene Krokhalev
Problem Source: The Ural State University Championship, October 29, 2005
To submit the solution for this problem go to the Problem set: 1415. Mobile Life