High School Programming League Problems Archive

Julia and Robert are going to spend some time on vacation in a faraway skiing resort of their dreams. Unfortunately, their free time and funds are very limited (so typical, isn't it?).

Still, since the vacation resort has already been booked in advance, they must arrange the trip there and back. I will do it. - said Robert, and after a few minutes of browsing the web he proudly presented their itinerary. This is too expensive, we cannot afford it! - complained Julia, looking at it - let me try.

Julia's suggestion for their trip was much cheaper, but unfortunately their travel would take up too much time. This is completely unacceptable - said Robert.

After some discussion, they have decided to approach the problem as follows:

1. They cannot spend more than k$ on travel.
2. They want to travel along the shortest possible way, as long as the first condition is true.

Having the above in mind, Julia and Robert have decided to ask you for help. First, they would like to solve the simplified case in which arrival/departure times are not taken into account, and all transport connections between points are bidirectional.

Input

In the first line, you are given start and end - the names of the starting and the destination points, respectively. In the next line, you are given: k <= 10⁹ - the maximum travel cost and m<= 4 * 10⁶ - the number of connections. Each of the following m lines contains:

code name₁ name₂ cost time

describing the connection from place name₁ to place name₂ and the cost and time corresponding to i.

The number of different names is <= 10⁶; cost_i <= 1000; time_i <= 10⁶. You can assume that there is always a path which fulfills the criteria, for which the total time does not exceed 10⁹. 

Names used in the description are sequences of at most 32 characters of the Latin alphabet written in both lower and upper case.

Output

First output c, the number of connections which you will use in your solution. In the following c lines output: code - the code of the i-th connection, and in the final line: total_cost total_time (the total cost and time of the whole travel).

Scoring

For each test case: score = some_constant - total_time if total_cost <= k or 0 otherwise, where the some_constant is a test case specific positive integer.

The number of points given in the ranking is scaled so that it is equal to 10 for the contestant whose solution has the highest score, and is proportionally less for all solutions with lower scores.

Example 1

Input:

Wilamowo Burszewo
7 5
aA Wilamowo Boleszyn 6 2
KRC Wilamowo Burszewo 8 3
SsRS Boleszyn Burszewo 2 4
bbb Wilamowo Boleszyn 4 6
adsK Wilamowo Burszewo 5 12
Output:
2
bbb
SsRS
6 10

Score:
If the some_constant is equal to 12
then the score is equal to 12-10=2 points.

More information about test cases

Note

For the first weeks of the series all submissions to this problem will be visible to all users and tested on 5 data sets only.

For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on all 10 data sets. (Earlier solutions will also be extended to all 10 data sets.)