The Willy Memorial Program

Willy the spider used to live in the chemistry laboratory of Dr. Petro, wandering among the lab's pipes and sometimes resting inside the empty ones. One night, while he was inside a pipe, he fell asleep. The next morning Dr. Petro came in and, without noticing Willy, opened a valve to fill the pipes with hot water. Stanley the gray mouse realized what was about to happen and ran as hard as he could to reach the valve in time, but he couldn't make it, and poor Willy was boiled.

In Willy's memory, we want to write a program that computes how much time Stan had to rescue him, assuming Stan started running exactly when the doctor opened the valve.

To simplify the problem, assume every pipe is a vertical cylinder of diameter 1 cm, open at the top and closed at the bottom. Some pipes are joined by horizontal pipes called links. Links have very high flow capacity, but are so thin that the volume of water inside them is always negligible.

Water enters the top of one designated pipe at a constant rate of $0.25\pi\ \mathrm{cm}^3/\mathrm{sec}$ and fills that pipe from the bottom up, until the surface reaches a link, through which the water flows horizontally and starts filling the connected pipe. By elementary physics, if two pipes are connected and the water surface is above the connecting link, the level in both pipes stays equal as they fill; in that case each pipe fills at half of the incoming rate.

As an example, consider the configuration below:

First, the lower 2 cm of the left pipe fills at full rate, then the lower 3 cm of the right pipe fills, and after that the upper parts of the two pipes fill together at half rate. Given a configuration of pipes and links and a target level in one of the pipes (the heavy dotted line in the figure), the program must report how long it takes for the water to reach that target level. For the configuration above, the answer is 9 seconds.

Assume the water falls very rapidly, so the time needed for it to fall can be neglected. The target level is always considered to be a tiny bit above the specified level. For instance, if we set the target to level 4 in the left pipe above, the elapsed time to reach it is 5 (not 2). Also note that when the water reaches the top of a pipe (say at level $x$), it does not pour out of the pipe until every empty space in connected pipes below level $x$ that can still be filled has been filled (there may also be links at level $x$ through which water enters). After all such spaces are filled, the water level does not rise any further.

To describe positions we use coordinates $(x, y)$ with the origin at the top-left of all pipes and links (note that $y$ increases downward). All coordinates are integers between 0 and 100, inclusive.

The first line contains a single integer $t$ ($1 \le t \le 10$), the number of test cases, followed by the data for each test case. The first line of each test case is $p$ ($1 \le p \le 20$), the number of pipes, followed by $p$ lines, each describing one pipe. Each pipe line contains three integers: the $(x, y)$ coordinates of the pipe's upper-left corner and the pipe's height (at least 1 cm and at most 20 cm). Every pipe has diameter 1 cm.

After the pipe data comes a line with a single integer $l$ ($0 \le l \le 50$), the number of links, followed by $l$ lines describing the links. Each link line contains three integers: the $(x, y)$ coordinates of the link's left endpoint and the link's length (at least 1 cm and at most 20 cm). Links have zero width.

The last line of each test case contains two integers: the index of the target pipe (pipes are numbered from 1, in the order they appear in the input) and the desired $y$ value for the water level in that pipe (this level may lie entirely outside the pipe).

You may assume the following about the input:

• The water enters the first pipe.
• No link crosses a pipe.
• No two links have the same $y$ coordinate.
• No two pipes have the same upper-left $x$ coordinate.
• Both endpoints of every link are attached to pipes.

For each test case, print exactly one line with the time (an integer) required for the water to reach the target level in the target pipe. If in a given test case the water never reaches the target level, print No Solution on that line instead. Print the lines in order, with no blank lines between them.