시너그 생명체

과학자들이 새로운 종류의 미세 생명체를 발견하고 이를 시너그(synnerg) 라고 이름 붙였습니다. 시너그에 대해 알려진 사실은 몇 가지뿐입니다.

• 시너그의 종류는 두 가지 이상입니다.
• 갓 태어난 시너그는 모두 같은 수명을 가집니다. 이 문제에서 갓 태어난 시너그의 수명은 1 입니다.
• 인접한 두 시너그는 하나의 새로운 시너그로 통합(unify) 될 수 있습니다. 종류 $A$ 인 시너그와 종류 $B$ 인 시너그가 통합되면, 수명이 $(\text{수명}(A) + \text{수명}(B)) \times f$ 인 목표 시너그가 됩니다. 여기서 $f$ 는 증폭 계수입니다. 목표 종류는 두 근원 종류와 다를 수 있습니다. 통합은 정해진 규칙 집합을 따르며, 각 규칙은 목표 종류, 두 근원 종류, 증폭 계수 $f$ 를 지정합니다. 규칙은 근원의 순서에 영향을 받지 않습니다. 근원이 $p$ 와 $q$ 인 규칙은 인접한 쌍에서 $p$ 와 $q$ 가 어느 쪽에 있든 적용됩니다.

규칙의 예시는 다음과 같습니다.

두 개 이상의 갓 태어난 시너그를 수열로 늘어놓으면, 각 시너그는 왼쪽 또는 오른쪽 이웃과 통합하여 수열을 더 짧게 만들 수 있습니다. 통합은 재귀적으로 반복되며, 같은 수열이라도 통합하는 방법이 여러 가지일 수 있고 그에 따라 수명이 달라집니다.

통합 단계의 예시는 다음과 같습니다.

첫 번째 예시에서 갓 태어난 수열 a a b b(수명 1 1 1 1)는 규칙 1과 3으로 aa[a a] bb[b b] 로 통합되며, aa 의 수명은 $2 = (1 + 1) \times 1$, bb 의 수명은 $6 = (1 + 1) \times 3$ 입니다. 이어서 aa bb 는 규칙 4로 x[aa bb] 로 통합되고 그 수명은 $16 = (2 + 6) \times 2$ 입니다.

두 번째 예시에서는 같은 갓 태어난 수열이 규칙 2와 3으로 AA[a a] bb[b b] 로 통합되며 수명은 각각 $34 = (1 + 1) \times 17$ 과 $6 = (1 + 1) \times 3$ 입니다. 이 수열은 하나의 시너그로 완전히 통합되지는 않았지만 더 이상 통합할 수 없으므로 최종 상태이며, 이때의 AA 는 위에서 완전히 통합된 x 보다 더 긴 수명을 가집니다.

갓 태어난 수열이 주어질 때, 수열의 어떤 연속된 부분을 완전히 통합하여 만들 수 있는 시너그 중 가능한 최대 수명 을 가지는 모든 시너그를 찾으세요. 그 부분은 수열 전체일 수도 있고 일부(부분 수열)일 수도 있으며, 결과가 완전히 통합될 필요는 없습니다. 입력의 어떤 연속된 구간을 단계별로 통합하여 하나의 시너그로 만들 수 있으면 그 시너그는 생성 가능 합니다. 수명은 통합 순서에 따라 달라지므로, 각 (종류, 구간)에 대해 얻을 수 있는 가장 큰 수명을 취합니다. 그리고 전체 최댓값과 같은 수명을 가지는 모든 시너그를 출력하세요.

입력은 빈 줄 하나로 구분되는 두 부분으로 이루어집니다.

1부 — 통합 규칙. 각 줄은 하나의 규칙이며, 공백으로 구분된 네 개의 필드로 이루어집니다: 목표 종류, 근원 종류 #1, 근원 종류 #2, 증폭 계수. 각 종류는 최대 20자의 영숫자 문자열입니다. 증폭 계수는 100 이하의 양의 정수입니다.

2부 — 수열. 각 줄은 하나의 갓 태어난 수열이며, 공백으로 구분된 시너그 종류들로 이루어집니다. 수열의 모든 시너그는 수명 1인 갓 태어난 상태로 시작합니다.

빈 줄(또는 입력의 끝)이 수열 목록의 종료를 나타냅니다.

각 입력 수열마다 두 부분을 출력합니다.

• 먼저 최대 수명을 가지는 시너그의 개수, 공백, 그 최대 수명을 한 줄에 출력합니다.
• 이어서 해 하나마다 한 줄씩 출력합니다. 각 줄은 공백으로 구분된 세 필드로 이루어집니다: 시너그 종류, 수열에서의 시작 위치, 끝 위치(둘 다 1부터 시작하며 양 끝 포함). 해는 시작 위치, 그다음 끝 위치, 그다음 종류 순으로 오름차순 정렬합니다. 두 위치 비교는 수치 비교이고, 종류 비교는 사전식(ASCII) 순서입니다.

예시는 위의 6개 규칙과 5개의 수열을 사용합니다.

• a a b b 의 경우, 위치 1부터 4까지를 x[aa[a a] bb[b b]] 로 완전히 통합할 수 있고 그 수명은 $16 = ((1+1)\times 1 + (1+1)\times 3) \times 2$ 이지만, 이는 위치 1부터 2까지의 AA[a a] 가 가지는 34 보다 작으므로 답은 AA 1 2 입니다.
• a a b b a 의 경우 두 개의 해가 있습니다: 위치 1부터 2까지의 AA 와 위치 1부터 5까지의 x 로, 둘 다 수명 34입니다.
• a a b b a a 의 경우 해는 하나입니다: 위치 1부터 6까지의 x 로 수명 70입니다.
• c 를 포함한 수열에서는 규칙 6(근원 c 와 a 로부터 목표 c)이 순서에 영향을 받지 않는다는 점을 기억하세요. 인접한 c 와 a 가 어느 순서로 있든 적용됩니다.