요금 청구표

통신에서는 전화번호에 따라 서로 다른 요율이나 요금제가 적용될 수 있다. 한 통신사는 각 통화에 어떤 요금제를 적용할지 결정하는 요금 청구표를 관리한다.

모든 전화번호는 정확히 11자리 숫자로 이루어진다. 기존 청구표는 n개의 줄로 이루어지며, 각 줄은 번호 접두사의 범위를 A - B 형태로 적고 그 뒤에 요금제 이름을 적는다. 이 줄은 앞자리가 그 범위 안에 드는 모든 전화번호와 일치한다. 예를 들어 7919 - 921 줄은 7919, 7920, 7921 중 하나로 시작하는 모든 전화번호와 일치한다.

어떤 통화의 요금제는 청구표를 위에서 아래로 읽어 내려가며 처음으로 일치하는 줄이 결정한다. 어떤 줄과도 일치하지 않으면 그 번호는 유효하지 않으며 요금제가 필요 없다. 한 줄은 특수 요금제 이름 invalid를 사용해 번호를 유효하지 않다고 표시할 수도 있다. 같은 요금제 이름이 서로 매우 다른 번호를 나타내는 여러 줄에 나타날 수도 있다.

기존 청구표에는 불필요한 항목이 있을 수 있어, 통신사는 더 깔끔한 표를 원한다. 새 표는 범위 없이 단순 접두사만으로 이루어진 목록이며, 각 접두사에 요금제 이름이 붙는다. 그리고 표 안의 어떤 접두사도 다른 접두사의 접두사가 되지 않는다. 그러면 한 번의 사전식 조회만으로 임의의 전화번호의 요금제를 알 수 있다. 요금제 invalid는 새 표에 나타나서는 안 된다. 유효하지 않은 번호는 일치하는 접두사가 없는 번호로 정의되기 때문이다. 기존 표의 결정을 정확히 똑같이 재현하는 모든 표 가운데, 줄 수가 가장 적은 표 하나를 출력하라.

첫째 줄에 정수 n (1 ≤ n ≤ 100)이 주어진다. 기존 청구표의 줄 수이다.

다음 n개의 각 줄은 하나의 규칙을 공백으로 구분된 네 개의 토큰으로 나타낸다: 접두사 A, 빼기 기호 -, 접두사 B, 그리고 요금제 이름. 각 접두사는 1자리에서 11자리 숫자로 이루어지고, 각 요금제 이름은 1자에서 20자의 소문자 알파벳으로 이루어진다.

A와 B의 자릿수를 각각 |A|, |B|로 쓴다. 접두사는 1 ≤ |B| ≤ |A| ≤ 11을 만족하며, A의 마지막 |B|자리를 문자열로 볼 때 사전식으로 B보다 작거나 같다. 이 규칙은 앞의 |A| − |B|자리가 A의 앞 |A| − |B|자리와 같고, 그다음 |B|자리가 A의 마지막 |B|자리와 B 사이(양 끝 포함)에 있는 모든 전화번호와 일치한다.

첫째 줄에 정수 k를 출력한다. 새 표가 기존 표를 정확히 나타내기 위해 필요한 최소 줄 수이다.

그다음 k개의 줄에 새 표를 접두사의 사전식 순서로 출력한다. 각 줄은 공백으로 구분된 두 토큰, 즉 접두사(숫자 한 자리 이상)와 그 요금제 이름으로 이루어진다.

모든 전화번호가 유효하지 않다면 숫자 0 하나만 출력한다.