Nlogonian people is 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