Train Scheduling

Elihc is a strange country occupying a long, narrow strip of land from north to south. There is only one main railway line in this country. This railway line is a straight line. It starts from the northernmost station, traverses the whole country southward, and finishes at the southernmost station.

Unfortunately, there are too many trains travelling on this railway line all the time. Long delays, even serious railway accidents are quite common here. Now, Railways Bureau of Elihc decides to solve these problems by scheduling the train in a better way, and hires you to write the program.

There are (N+1) stations on this railway line, and they are numbered from 0 to N from north to south. There are also M trains numbered from 0 to M-1. Each train has an initial station, a terminal station, expected time of departure and speed limit. Initially, it parks at its initial station. It departs at the expected time or after the expected time, and is bound for its terminal station. The train has to stop at every station on its route. Different trains may have different speed limits. During the journey, a train should always run within its own speed limit (it is allowed to run at any speed not exceeding the limit anywhere). Compared with the railway line, both stations and trains are so small that they can be regarded as points in your scheduling program.

For each pair of adjacent stations, the part of the railway line between them is called a section (stations are not included). The positions of the stations are well designed so that the length of each section is exactly S kilometer. All stations are sufficient to park any number of trains. However, due to some financial difficulties, there is just one track for each section. For safety reasons, trains running on the same section should always follow the rules below.

1. They are running in the same direction.
2. A train can catch up with, but can never pass any other trains in front of it.

An officer of Railways Bureau provides you some scheduling strategies, which you have to use in your program:

1. During scheduling, trains that are not expected to depart yet should be ignored. If a train has already arrived at its terminal station, it will be ignored forever.
2. Once a train is expected to depart from the original station, or arrives at a station except the terminal one, it stops and waits to move on the next section immediately.
3. When a train is stopping in some station, it will not start to move to the next section until (1) no running train is coming from the opposite direction on this section, and (2) No train with smaller number is stopping and waiting to move on this section from station at either end of this section.
4. A train should always run as fast as it can, without passing any train in front running on the same section.

Now, please help Railways Bureau to schedule the trains and figure out when each train will reach its terminal station.

There are several test cases in the input.

The first line contains an integer C (1 ≤ C ≤ 10) -- the number of test cases.

Each test case begins with three integers N, M, S (1 ≤ N ≤ 10, 1 ≤ M ≤ 10, 1 ≤ S ≤ 1000), indicating the number of stations, the number of trains and the length of section (in kilometer).

Then M lines follow, describing trains from number 0 to M-1 in order, one per line. Each line contains four integers O, T, E, L (0 ≤ O ≤ N, 0 ≤ T ≤ N, O ≠ T, 0 ≤ E ≤ 10000, 1 ≤ L ≤ S), indicate that this train travels from station O to station T, expected to depart at minute E, and its speed limit is L kilometer per minute.

For each test case, output the arrival time (in minute) of each train one per line, in ascending order of train number. Your answers should be rounded up to the nearest integer.

2
1 3 100
0 1 0 5
0 1 20 5
1 0 0 5
2 2 100
0 2 0 4
0 2 2 5

20
40
60
50
50

In the first test case:
At minute 0, both train 0 and train 2 are expected to depart and waiting to move to the same section. According to our strategies, train 0 starts to go and train 2 has to stay in station 1 while train 0 is running on the section. At minute 20, train 0 arrives at its terminal station. At this time, both train 1 and train 2 are waiting to move to the same section. Then train 1 starts to go and poor train 2 has to keep waiting again.

In the second test case:
Train 0 departs at minute 0 and runs straight forward to its terminal station. The case of train 1 is quite complicated. Train 1 departs at minute 2 and catches up with train 0 at minute 10. Since train 1 should never pass train 0 on the section, it has to follow train 0. Both of them arrive at station 1 at minute 25. Then, train 0 starts first (because of the smaller number), and train 1 has to follow train 0 again.

2014ACM/ICPC亚洲区广州站-重现赛（感谢华工和北大）