在这个游戏中，玩家需要获取资源来建造建筑物。铁和煤是来自不同矿山的原材料，也可以精炼成钢。矿山有不同的等级，可以通过升级来提高生产率。每个矿山每小时精确生产 10 次资源，即每六分钟生产一次。一级矿山每小时生产 10 个单位，即每六分钟生产 1 个单位；十级矿山每小时生产 100 个单位，即每六分钟生产 10 个单位。矿山每提升一级，每小时产量增加 10 个单位，因此三级矿山每小时生产 30 个单位，八级矿山每小时生产 80 个单位。矿山的最高等级为 10 级；矿山不能升级超过 10 级。

精炼钢由原材料铁和煤制成。1 个钢需要 3 个铁和 1 个煤。转换为钢不需要时间，并且可以在资源可用时立即完成。

当矿山正在升级时，它不生产任何资源。升级矿山需要时间，并且每种类型的矿山在同一时间只能有一个进行升级，例如铁矿和煤矿可以同时升级，但两个铁矿不能同时升级。一旦升级完成，同类型的另一个矿山可以立即开始升级。

矿山升级及所需时间：

你需要确定每个建造请求最早可以开始的时间。建造请求必须按照接收到的顺序进行处理，并按该顺序给予优先级。如果有 $A$、$B$ 和 $C$ 的请求（按此顺序接收），则建造时间必须满足 $A \leq B \leq C$。最重要的是 $A$ 尽可能早地开始，其次是 $B$ 尽可能早地开始，最后是 $C$ 尽可能早地开始。

输入格式

第一行表示测试用例的数量 $T$ ($1 \leq T \leq 50$)。

每个测试用例包含资源数据，随后是建造请求。资源数据以两行输入开始。第一行用于铁，第二行用于煤。每行资源数据包含手头原材料的数量、生产该资源的矿山数量，以及各矿山的等级。每种原材料的矿山不超过 10 个。

两行资源数据之后是单行输入，列出手头钢资源的数量。

下一行标识建造请求的数量。建造请求不超过 10 个。每个建造请求列出建筑类型，后跟建造它所需的资源要求。每个建筑类型为 1 到 20 个字符，由 a-z 组成，后跟 3 个整数，分别代表建造该建筑所需的铁、煤和钢。

所有数量（初始铁、煤、钢以及每个建筑所需的铁、煤、钢）均在 $0 \leq Q \leq 50\,000$ 的范围内。

输出格式

对于每个建造请求，输出一行格式为 B began construction at H:MM:SS 的内容，其中 B 是建筑类型，H:MM:SS 是从游戏开始到该建筑开始建造所经过的时间，以小时、分钟和秒表示。小时、分钟和秒总是会被打印出来，即使为零，分钟和秒会补零至 2 位。

样例

输入格式 1

1
3 2 1 1
2 2 1 1
1
2
hospital 5 5 5
factory 1 1 0

输出格式 1

hospital began construction at 0:36:00
factory began construction at 0:42:00