윌리 추모 프로그램

거미 윌리는 페트로 박사의 화학 실험실에 살면서 실험실의 관들 사이를 돌아다니고, 가끔은 비어 있는 관 안에서 쉬곤 했습니다. 어느 날 밤 윌리는 관 안에 들어가 있다가 잠이 들었습니다. 다음 날 아침, 페트로 박사는 윌리를 알아채지 못한 채 관을 뜨거운 물로 채우기 위해 밸브를 열었습니다. 회색 쥐 스탠리는 무슨 일이 벌어질지 눈치채고 밸브에 제때 닿으려고 있는 힘껏 달렸지만, 끝내 이르지 못했고 가엾은 윌리는 뜨거운 물에 삶기고 말았습니다.

윌리를 기리며, 우리는 박사가 밸브를 연 바로 그 순간에 스탠이 달리기 시작했다고 가정할 때, 스탠에게 윌리를 구할 시간이 얼마나 있었는지를 계산하는 프로그램을 작성하려고 합니다.

문제를 단순화하기 위해, 모든 관은 지름 1 cm의 수직 원기둥이며 위쪽은 열려 있고 아래쪽은 막혀 있다고 가정합니다. 일부 관들은 링크(link) 라고 부르는 수평 관으로 서로 연결되어 있습니다. 링크는 유량 용량은 매우 크지만 매우 가늘어서, 그 안에 들어 있는 물의 부피는 항상 무시할 수 있습니다.

물은 지정된 한 관의 위쪽으로 일정한 속도 $0.25\pi\ \mathrm{cm}^3/\mathrm{sec}$ 로 들어와 그 관을 아래에서부터 채웁니다. 수면이 어떤 링크에 도달하면 물은 그 링크를 통해 수평으로 흘러 연결된 관을 채우기 시작합니다. 기초 물리에서 알 수 있듯이, 두 관이 연결되어 있고 수면이 연결 링크보다 위에 있으면 두 관의 수위는 채워지는 동안 항상 같게 유지되며, 이때 각 관은 들어오는 물의 절반 속도로 채워집니다.

예를 들어 아래 구성을 살펴봅시다.

먼저 왼쪽 관의 아래 2 cm가 최대 속도로 채워지고, 그다음 오른쪽 관의 아래 3 cm가 채워지며, 그 후에는 두 관의 윗부분이 절반 속도로 함께 채워집니다. 프로그램은 관과 링크의 구성, 그리고 어느 한 관에서의 목표 수위(그림의 굵은 점선)가 주어졌을 때, 물이 그 목표 수위에 도달하는 데 걸리는 시간을 구해야 합니다. 위 구성에서 답은 9초입니다.

물은 매우 빠르게 떨어지므로 물이 떨어지는 데 걸리는 시간은 무시한다고 가정합니다. 목표 수위는 언제나 지정된 위치보다 아주 조금 위에 있는 것으로 간주합니다. 예를 들어 위 그림의 왼쪽 관에서 목표를 높이 4로 설정하면, 그 목표에 도달하는 데 걸리는 시간은 (2가 아니라) 5입니다. 또한 물이 어떤 관의 꼭대기(높이 $x$라고 하자)에 도달하더라도, 높이 $x$ 아래에 있으면서 아직 채울 수 있는 연결된 관의 빈 공간이 모두 채워지기 전까지는 관 밖으로 넘치지 않습니다(높이 $x$에 물이 들어가는 링크가 있을 수도 있습니다). 그러한 빈 공간이 모두 채워진 뒤에는 수위가 더 이상 올라가지 않습니다.

위치는 모든 관과 링크의 좌상단을 원점으로 하는 좌표 $(x, y)$ 로 나타내며, $y$ 는 아래로 갈수록 커집니다. 모든 좌표는 0 이상 100 이하의 정수입니다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 10$) 가 주어지고, 이어서 각 테스트 케이스의 데이터가 주어집니다. 각 테스트 케이스의 첫 줄에는 관의 수 $p$ ($1 \le p \le 20$) 가 주어지고, 이어지는 $p$ 개의 줄이 각각 하나의 관을 나타냅니다. 각 관의 줄에는 정수 세 개가 있으며, 앞의 두 개는 관의 좌상단 모서리 좌표 $(x, y)$ 이고 세 번째는 관의 높이(최소 1 cm, 최대 20 cm)입니다. 모든 관의 지름은 1 cm입니다.

관 데이터 다음에는 링크의 수 $l$ ($0 \le l \le 50$) 가 한 줄에 주어지고, 이어지는 $l$ 개의 줄이 각각 하나의 링크를 나타냅니다. 각 링크의 줄에는 정수 세 개가 있으며, 앞의 두 개는 링크의 왼쪽 끝점 좌표 $(x, y)$ 이고 세 번째는 링크의 길이(최소 1 cm, 최대 20 cm)입니다. 링크의 폭은 0으로 간주합니다.

각 테스트 케이스의 마지막 줄에는 정수 두 개가 있습니다. 첫 번째는 목표 관의 번호(관은 입력에 나타난 순서대로 1부터 번호가 매겨집니다)이고, 두 번째는 그 관에서 물의 목표 수위에 해당하는 $y$ 값입니다(이 수위는 관을 완전히 벗어나 있을 수도 있습니다).

입력에 대해 다음을 가정할 수 있습니다.

• 물은 첫 번째 관으로 들어옵니다.
• 어떤 링크도 관을 가로지르지 않습니다.
• 두 링크가 같은 $y$ 좌표를 가지지 않습니다.
• 두 관이 같은 좌상단 $x$ 좌표를 가지지 않습니다.
• 모든 링크의 양 끝점은 관에 연결되어 있습니다.

각 테스트 케이스마다, 목표 관에서 물이 목표 수위에 도달하는 데 걸리는 시간(정수)을 정확히 한 줄에 출력합니다. 어떤 테스트 케이스에서 물이 목표 수위에 결코 도달하지 못하면, 그 줄에는 대신 No Solution 을 출력합니다. 각 줄은 순서대로, 사이에 빈 줄 없이 출력합니다.