On the evening of 3 August 1492, Christopher Columbus departed from Palos de la Frontera with a few ships, starting a serious of voyages of finding a new route to India. As you know, just in those voyages, Columbus discovered the America continent which he thought was India.
Because the ships are not large enough and there are seldom harbors in his route, Columbus had to buy food and other necessary things from savages. Gold coins were the most popular currency in the world at that time and savages also accept them. Columbus wanted to buy N kinds of goods from savages, and each kind of goods has a price in gold coins. Columbus brought enough glass beads with him, because he knew that for savages, a glass bead is as valuable as a gold coin. Columbus could buy an item he need only in four ways below:
There are several test cases.
The first line in the input is an integer T indicating the number of test cases (0 < T <= 10).
For each test case:
The first line contains an integer N, meaning there are N kinds of goods (0 < N <= 20). These N kinds are numbered from 1 to N.
Then N lines follow, each contains two integers Q and P, meaning that the price of the goods of kind Q is P. (0 < Q <= N, 0 < P <= 30)
The next line is a integer M (0 < M <= 20), meaning there are M "bargains".
Then M lines follow, each contains three integers N1, N2 and R, meaning that you can get an item of kind N2 by paying an item of kind N1 plus R gold coins. It's guaranteed that the goods of kind N1 is cheaper than the goods of kind N2 and R is none negative and less than the price difference between the goods of kind N2 and kind N1. Please note that R could be zero.
For each test case:
Please output N lines at first. Each line contains two integers n and p, meaning that the "actual price" of the goods of kind n is p gold coins. These N lines should be in the ascending order of kind No..
Then output a line containing an integer m, indicating that there are m kinds of goods whose "actual price" is equal to the sum of "actual price" of other two kinds.
1 4 1 4 2 9 3 5 4 13 2 1 2 3 3 4 6
1 3 2 6 3 4 4 10 1