With the magnification of the Energy Crisis, Chemists have decided to re-examine the existing procedures of preparation of various Chemical Substances.

As part of this Project, they list all the elements that they commonly find as raw material (Initial Reactants), and the ones that they intend to produce (Final Products). They also prepare an extensive list of the various known reactions/processes that are used to convert one substance to another.

One major issue that they find is that the Initiation of many reactions needs absurdly large amounts of energy. They wish to keep low the activation energies used in the new procedures.

Knowing all this, they now attempt to find out such methods of preparing the target substances:

1. in which the highest value of activation energy needed by any of the reactions that make up the path, in any of the methods, does not exceed a given upper value,
2. which minimizes the Total reactions/procedures performed in All the (Initial Reactant) → (Final Product) conversions.

Each substance, on being given a specific amount of energy, converts into some other substance. The formed substance is unique for a particular value of Energy. The process of creating each successive Target Substance (Final Product) starts from one of the Source Substances Only, and leaves no by-products.

Your task is to find the minimum value of upper bound such that all final products are obtainable with that upper bound and for this minimum value, find out the minimum number of conversions to get all the final products.

Note: None of the procedures are Reversible, unless explicitly stated. Also, if a procedure Is reversible, the Energy requirement may or may not be same. You may assume that there is a limitless supply of the Initial Reactants.

Input

The first line contains an integer t which is the number of test cases. Each test case begins with a line containing three integers : number of Initial reactants (S), Final Products (D) and the total number of elements (N). Then S+D lines follow, first S lines contain IDs of Initial reactant (0 based) and next D lines contain ID's of Final products (0 based). Then follows a line containing an integer R which is number of reactions possible. Then follow R lines, each containing three integers, the Substance (S), the converted substance (C) and the activation energy (A) units required for the reaction. 0 ≤ S, C < n.

Output

For each test case, output in a different line, 2 integers (a, b) separated by spaces where a is the minimum upper value and b is the minimum number of conversions required for corresponding a. In case that all final products are not obtainable for any value of upper bound, Print a single line with message "Excessive Energy.".

Example

Input:
1
2 2 6
1
3
0
3
6
1 2 2
2 4 3
4 5 1
4 2 2
3 0 4
5 0 1

Output:
3 4

Constraints and Limits

N ≤ 10000. S ≤ N, D ≤ N, R < 100000. 0 < A < 1000000000

---

hide comments

	:D: 2016-12-03 17:59:19 Auto re: the correct answer if '1 4'. That means you should consider all (Initial Reactant) --> (Final Product) operations as separate. You can't reuse intermediate products between different final products.
	:D: 2011-03-10 11:07:44 What is the answer for: 1 1 2 4 1 2 3 3 1 0 1 0 2 1 0 3 1 Is it '1 4' or '1 3'?