Original problem statement (in Polish) can be found here.

Archibald the Archeologist was sitting hunched at his desk, while carefully examining badly yellowed manuscript, filled with some unusual looking letters. At this point he was already sure - in South America, civilizations were present much earlier than supposed. And the evidence was right there - old, inconspicuous book, stolen in a daring stunt from the Library of Congress in Washington, described a large chunk of the history of La-Og-Mhtir people. Many pages are completely unreadable, but the following fragment survived, and it concerns the Great War with another previously uknown Ueh-Sir-Cit civilization:

... the threat from our enemies is becoming increasingly serious. It can cause the downfall of our culture. Ueh-Sir-Cits do not understand our pursuit of ideas at all, but they think that their own concepts (which are rubbish) will solve all the problems. We can't let them win!

Our newest idea for neutralizing the enemy consist in paralizing their arms industry - we hope that after stopping the production of stone combat sticks, they will cease fighting. We are of the opinion that blocking all transport between some settlements will suffice to meet our goal (for example, cutting off the access to the quarry will be a huge blow for the hilt factory).

We know all the roads between the settlements, we also chose some pairs of settlements, between which all the transport should be blocked. Some of the pairs are not that crucial though, so merely making the transport difficult (instead of making it impossible) will suffice.

We will send saboteurs into the Ueh-Sir-Cit's area. They will block or weaken some of the roads. On every path between the settlements that belong to a crucial pair, at least one road must be blocked. If a pair is not crucial, it is enough that on every path at least one road is weakened or blocked. Our planners determined the exact cost of weakening and blocking every road, we only need the sabotage plan now. We believe that thanks to our ingenuity, we will find the cheapest plan of the operation. We offer prayers to The Great Temple for the success...

Input

The first line contains a single integer t, denoting the number of testcases. (t <= 16). Then, testcases follow.

The first line of the descriptions contains three integers n, m and k (1 <= n <= 40, 1 <= m, k <= 1600), denoting the number of settlements in the Ueh-Sir-Cit's country, the number of roads, and the number of pairs of settlements, chosen by the La-Og-Mhtirs. The settlements are numbered using integers from 1 to n.

In the next m lines there are descriptions of the roads, each road in a separate line. One road is described by four integers a_i, b_i, z_i, o_i (1 <= a_i, b_i <= n, 1 <= o_i <= z_i <= 10⁶). It means that there is a two-way road between the settlement a_i and the settlement b_i, blocking that road costs z_i, and weakening that road costs o_i. The road is connecting distinct settlements, and there is at most one road between every pair of settlements.

In the next k lines there are descriptions of the pairs - two distinct integers c_i and d_i, and a single character "Z" or "O" (1 <= c_i, d_i <= n). "Z" denotes a crucial pair of settlements (in other words, you must block all the transport between the settlement c_i and the settlement d_i), "O" means a pair that is not that crucial (so it is enough to make the transport difficult). Every pair of the settlements appears on that list at most once.

Output

For every testcase you should prepare the sabotage plan. The description begins with two integers p and c (0 <= p <= m) - number of affected roads and cost of the operation. Then, the descriptions of p roads should follow. One description should consist of an integer e_i, followed by a single character "Z" or "O" (1 < e_i <= m). "Z" denotes blocking the road number e_i, according to the order from the input, counting from 1. "O" means that we should weaken the road. A road can appear at most once in the output for one testcase.

Example

Input:

1
5 5 2
1 3 100 90
3 2 100 10
3 4 100 99
4 5 100 50
5 2 100 10
1 5 Z
2 5 O

Output:

3 120
1 Z
2 O
5 O

Explanation

After blocking the road 1-3 (which costs 100), the transport from the settlement number 1 to the settlement number 5 is impossible. After weakening the roads 2-3 and 2-5 (which costs 10 for both), the transport from 2 to 5 is difficult enough. Total cost: 100+10+10 = 120.

Scoring

If the plan is correct, and the cost c is computed correctly, it is worth c/(sum of all z_i in a testcase) points. Overall score is equal to the sum of individual scores. Score for the sample output is equal 120/(100*5) = 0.24.