题目描述

威利是一只蜘蛛，它曾经住在佩特罗博士的化学实验室里。它常常在实验室的管道里闲逛，有时还会进入空的管道。一天晚上，它在一根管道里睡着了。第二天早上，佩特罗博士来到实验室。他在打开阀门让管道充满热水时没有注意到威利。与此同时，斯坦利这只灰色的老鼠意识到即将发生的事情。时间紧迫！斯坦利拼命跑到阀门处，想在威利被热水淹没之前关掉它，但……唉！他没能及时赶到！

可怜的威利在热水中被煮沸了，但它的记忆仍然留在我们心中。尽管斯坦利尽力了，我们想编写一个程序，以纪念威利，计算斯坦利在博士打开阀门时开始跑时，他还有多少时间可以拯救威利。

为了简化问题，假设管道都是直径为 1 厘米的垂直圆柱体。每个管道的顶部是开放的，底部是封闭的。有些管道通过特殊的水平管道（称为连接管）相互连接。连接管的流量很大，但在任何给定时间，连接管内的水体积可以忽略不计。水从其中一个管道的顶部以每秒 $0.25\pi \, \text{cm}^3$ 的恒定速率进入，并从底部开始填满管道，直到水流到达一个连接管，然后水平流动并开始填满连接的管道。根据基础物理知识，如果两个管道通过连接管相连，且水面高于连接点，那么当我们试图填满其中一个管道时，两个管道中的水位会保持一致。在这种情况下，水会以进水速率的一半分别填满每个管道。例如，考虑以下配置：

首先，左侧管道的下部 2 厘米以全速被水填满，然后，右侧管道的下部 3 厘米被填满，之后，两个管道的上部以半速并行填满。对于上述配置，输出是 9 秒。

假设水流速度非常快，以至于水流下落的时间可以忽略不计。目标水位总是假设比指定的水位稍高一些。例如，如果我们将目标点设置为上图左侧管道的 4 厘米处，水到达该目标点的经过时间假设为 5 秒（而不是 2 秒）。另外请注意，如果水到达管道顶部（假设在水平位置 $x$），它不会从管道中溢出，直到连接的管道中低于水平位置 $x$ 的空隙被填满（如果可以填满，即水位达到连接管）。注意，可能有一些连接管位于水平位置 $x$，水会从这些连接管进入。在所有这些空隙被填满后，水位不会再进一步上升。

输入

为了描述位置，我们假设坐标以 $(x, y)$ 表示，原点位于所有管道和连接管的左上角（注意 $y$ 坐标向下增加）。所有坐标都是 0 到 100（含）之间的整数。

输入文件的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量，随后是每个测试用例的输入数据。每个测试用例的第一行是一个整数 $p$（$1 \leq p \leq 20$），表示管道的数量，随后是 $p$ 行，每行描述一个管道。每行管道描述包含三个数字。前两个是管道左上角的 $(x, y)$ 坐标，第三个数字是管道的高度（至少 1 厘米，最多 20 厘米）。注意，每个管道的直径为 1 厘米。

在描述管道的输入数据之后，有一行包含一个整数 $l$，表示连接管的数量（$0 \leq l \leq 50$）。之后是 $l$ 行，每行描述一个连接管。每行连接管描述包含 3 个整数。前两个是连接管左端点的 $(x, y)$ 坐标，第三个是连接管的长度（至少 1 厘米，最多 20 厘米）。假设连接管的宽度为零。

每个测试用例的最后一行包含两个数字。第一个是目标管道的编号（从 1 开始，按测试数据中出现的顺序）。第二行是目标管道中水位的期望 $y$ 值（注意指定的水平可能完全超出管道范围）。

你可以假设以下关于输入的内容：

• 水从第一个管道进入。
• 没有连接管穿过管道。
• 没有两个连接管具有相同的 $y$ 坐标。
• 没有两个管道具有相同的左上角 $x$ 坐标。
• 每个连接管的两个端点都连接到管道。

输出

输出应包含恰好 $t$ 行，中间没有空行，每行对应一个测试用例。每行输出应包含水到达目标管道中目标水位所需的时间（一个整数）。如果在某个特定测试用例中，水永远无法到达目标水位，则该行应包含字符串 No Solution。

输入数据 1

1
2
2 0 6
5 1 6
1
3 4 2
2 2

输出数据 1

9

来源

德黑兰 2001