Nlogonian people are very excited about the event that will occur in the next year: the Cheese-rolling World Cup Nlogonia 2013! The event is organized by the Modern Cheeserolling Association (MCA or ACM, as spelled in Nlogonish) every four years, and this will be the first time that such an event is held in Nlogonia.

The project, however, is still being worked on. ACM didn’t announce the list of host cities yet, but, instead, it announced how the cities will be chosen. It’s worth mentioning that Nlogonia was attacked by some kind of giant cannon in 2009, so the facilities in the cities are damaged and can’t be fully considered (at least not now). Instead, a city will be chosen according to how easy its name is pronounced.

Let’s define the pronunciation power (pp) of a city name S as the sum of the lengths of all its palindromic contiguous substrings with even positive length. For example, consider the name abbaxx. Its substrings with even positive length are {ab, bb, ba, ax, xx, abba, bbax, baxx, abbaxx}. Of these, the palindromic ones are {bb, xx, abba} and thus pp(abbaxx) = |bb| + |xx| + |abba| = 8. Repeated substrings should be considered as many times as they occur (so pp(aaa) = |aa| + |aa| = 4, since aa occurs twice). Also, letter comparisons are case insensitive (so pp(aBbAxX) = 8, too), since the pronunciation is independent of the letter case.

Nlogonia has N cities. Let K be a number given by ACM. The cities whose names have a pronunciation power equal or greater than the K th unique highest power of all N cities will be chosen. Notice that it’s possible to choose more than K cities. For example, consider K = 3 and N = 6 cities whose names have the powers 2, 4, 4, 8, 8 and 16. The first 3 unique higher powers are 16, 8 and 4, so all cities except the first one will be chosen.

The 2009 cannon attack also damaged the roads between the cities. There’are only M one-way roads available to use in Nlogonia (if a road connects city A to B, it can’t be used to go from B to A). Also, due the damages made by the cannon, each road has a traffic flow limit. Nlogonia’s capital is the only city with an airport, so all the foreign people will come to Nlogonia via the capital and go to the host cities using the road network cited above. Your task is to help the Nlogonian people know the list of cities that will be chosen, and, for each one, know what is the maximum traffic flow possible from the capital to the city, so they know if the roads will handle the traffic well during the event. During the World Cup, each match will be played in a different date and city, so consider the chosen cities independently (in other words, calculate the flow between the capital and the first chosen city as if it was the only chosen one; then do the same with the second chosen one, and so on).

Input

The input will consist of one or more test cases. Each test case starts with a line containing three integers N (1 ≤ N ≤ 200), M (1 ≤ M ≤ N (N − 1)) and K(1 ≤ K ≤ 10). The cities are numbered from 0 to N − 1, and the capital is the city number 0.

Each of the N next lines contains the names of the cities, in increasing order of their numbers. Each name will contain only upper and lower case English letters, and its length will not exceed 30000. Each of the M next lines will describe the road network of the country. Each line will be in the form A B C (0 ≤ A, B < N, A = B, 1 ≤ C ≤ 109 ) and indicates a road connecting city A to city B with traffic flow limit C. There won’t be more than one road connecting a pair of cities in the same direction, and it will always be possible to go from the capital to any other city.

The last test case will be followed by a line containg three zeros.

Output

For each test case, print one line with k - the number of chosen cities. Then, print k lines in the format n (pp) f , where n is a city name, pp is its pronunciation power and f is the maximum flow from the capital to the city. Print the cities in increasing order of their numbers. Also, if the capital is a chosen city, use f = 0. You may assume that k ≤ 2K for each test case.

Example

Input:
3 4 2
Curitiba
LalLal
Idappadi
0 1 2
2 1 1
0 2 3
1 2 6
4 5 3
heeymacarena
haay
abbaxx
ddxdd
0 3 20
0 2 10
2 3 5
3 1 10
2 1 20
0 0 0

Output:
2
LalLal (12) 3
Idappadi (20) 5
4
heeymacarena (2) 0
haay (2) 20
abbaxx (8) 10
ddxdd (4) 25