자원

특정 게임에서는 건물을 짓기 위해 플레이어가 자원을 모아야 한다. 철과 석탄은 여러 광산에서 나는 원자재이며, 제련해서 강철로 만들 수도 있다. 광산에는 등급이 있고, 업그레이드해서 생산 속도를 높일 수 있다. 각 광산은 시간당 정확히 10번, 즉 6분마다 한 번 자원을 생산한다. 1레벨 광산은 시간당 10개, 즉 6분마다 1개를 생산하고, 10레벨 광산은 시간당 100개, 즉 6분마다 10개를 생산한다. 광산 레벨이 하나 오를 때마다 생산량이 시간당 10개씩 늘어나므로, 3레벨 광산은 시간당 30개, 8레벨 광산은 시간당 80개를 생산한다. 광산의 최고 레벨은 10이며, 10레벨을 넘어서는 업그레이드할 수 없다.

강철 1개는 철 3개와 석탄 1개로 만든다. 강철로 바꾸는 데는 시간이 걸리지 않으며, 자원이 준비되는 즉시 할 수 있다.

업그레이드 중인 광산은 자원을 생산하지 않는다. 업그레이드에는 시간이 걸리고, 같은 종류의 광산은 한 번에 하나만 업그레이드할 수 있다. 예를 들어 철 광산과 석탄 광산은 동시에 업그레이드할 수 있지만, 철 광산 두 개는 동시에 업그레이드할 수 없다. 업그레이드가 끝나면 같은 종류의 다른 광산이 바로 업그레이드를 시작할 수 있다.

광산 업그레이드와 소요 시간:

건설 요청은 받은 순서대로 처리하며, 우선순위도 같은 순서를 따른다. 요청이 A, B, C 순서로 들어왔다면 건설 시작 시각은 A ≤ B ≤ C를 만족해야 한다. A가 가능한 한 빨리 시작하는 것이 가장 중요하고, 그다음이 B, 마지막이 C이다. 각 건설 요청을 시작할 수 있는 가장 이른 시각을 구하라.

첫 줄에는 테스트 케이스 수 T (1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스는 자원 정보와 건설 요청으로 구성된다. 자원 정보는 두 줄이며, 첫 줄은 철, 둘째 줄은 석탄에 대한 정보다. 각 줄에는 해당 자원의 보유량, 그 자원을 생산하는 광산 수, 각 광산의 레벨이 주어진다. 자원마다 광산은 최대 10개다.

자원 정보 두 줄 다음에는 보유한 강철의 양을 나타내는 한 줄이 주어진다.

다음 줄에는 건설 요청 수가 주어지며, 최대 10개다. 각 건설 요청은 건물 종류와, 그 건물을 짓는 데 필요한 철, 석탄, 강철의 양을 정수 3개로 나타낸 것이다. 건물 종류는 a-z로 이루어진 1자 이상 20자 이하의 문자열이다.

모든 양(초기 철, 석탄, 강철, 그리고 건물마다 필요한 철, 석탄, 강철)은 0 ≤ Q ≤ 50,000 범위에 있다.

각 건설 요청마다 B began construction at H:MM:SS 형식으로 한 줄씩 출력한다. B는 건물 종류이고, H:MM:SS는 게임 시작부터 그 건물의 건설이 시작되기까지 걸린 시간을 시, 분, 초로 나타낸 것이다. 시, 분, 초는 0이어도 항상 출력하며, 분과 초는 두 자리가 되도록 앞을 0으로 채운다.