일련번호

한 제조사가 일련번호 표를 정렬된 상태로 관리한다. 표의 각 행은 연속된 일련번호 구간 하나와, 그 구간에 대한 두 가지 정보인 상태 코드(status code)와 이관 코드(transfer code)를 담는다. 표는 네 개의 열로 이루어지며, 순서대로 시작 일련번호, 끝 일련번호, 상태 코드, 이관 코드이다.

일련번호와 이관 코드는 $1$ 이상 $2^{31}-1$ 이하의 정수이다($2^{31}-1 = 2147483647$). 상태 코드는 한 글자짜리 대문자이다. 표는 일련번호가 증가하는 순서로 정렬되어 있고, 구간끼리 서로 겹치지 않으며, 모든 일련번호에 대해 표는 항상 가장 최근에 기록된 정보(상태 코드와 이관 코드)를 반영한다.

예를 들어 일련번호 100,000개를 상태 A, 이관 코드 1로 생성했다고 하자. 이들은 한 행으로 표현할 수 있다:

1 100000 A 1

이는 동일한 100,000개의 행을 각각 저장하는 것보다 훨씬 효율적이다. 어려움은 이미 정의된 구간 안의 일부 일련번호에 다른 상태 코드나 이관 코드를 부여해야 할 때 생긴다. 예를 들어 일련번호 12345를 상태 B로 바꿔야 한다면, 위의 행은 세 개의 행으로 나뉜다:

1 12344 A 1
12345 12345 B 1
12346 100000 A 1

이어서 12000부터 12999까지의 모든 일련번호의 이관 코드를 2로 바꾸면 다음과 같다:

1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1

이제 10000부터 100000까지의 모든 일련번호를 상태 C, 이관 코드 2로 바꾸면 다음과 같다:

1 9999 A 1
10000 100000 C 2

한 번 생성된 일련번호는 삭제되지 않지만, 정의된 구간들 사이에 정의되지 않은 일련번호 구간이 존재할 수 있다. 예를 들어 1000000부터 1999999까지의 모든 일련번호를 상태 Z, 이관 코드 99로 설정하면 다음과 같다:

1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99

마지막으로, 표는 항상 최소한의 행 수로 유지된다. 즉 한 행으로 대체할 수 있는 인접한 두 행이 절대 존재하지 않는다. 인접한 두 행은 (1) 일련번호가 연속적으로 이어지고(두 번째 구간이 첫 번째 구간의 끝 바로 다음에서 시작하고), (2) 상태 코드와 이관 코드가 모두 같을 때에만 하나로 합칠 수 있다. 예를 들어 다음 표는 최소가 아니다:

1 10 A 1
11 20 A 1
21 30 B 1

처음 두 행을 하나로 합칠 수 있기 때문이다:

1 20 A 1
21 30 B 1

반면 다음 표는 처음 두 행의 이관 코드가 다르므로 이미 최소이다:

1 10 A 1
11 20 A 2
21 30 B 1

그리고 다음 표도 처음 두 행이 연속적이지 않으므로(일련번호 11이 정의되지 않음) 더 줄일 수 없다:

1 10 A 1
12 20 A 1
21 30 B 1

각 트랜잭션은 주어진 구간에 속한 모든 일련번호의 상태 코드와 이관 코드를 설정하여, 기존에 담고 있던 값을 덮어쓰고 이전에 정의되지 않았던 일련번호는 새로 정의한다. 한 테스트 케이스의 모든 트랜잭션을 주어진 순서대로 적용한 뒤, 최소 행 수로 정리된 표를 출력한다.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 케이스의 이름이 담긴 한 줄로 시작한다. 이름은 최대 80자의 문자열이다. 이름이 END이면 입력의 끝을 뜻한다.

이름 다음에는 1개부터 100개까지의 트랜잭션 줄이 오며, 각 줄은 A B S T 형식이다. 여기서 A, B, T는 1 이상 $2^{31}-1$ 이하의 정수이고, S는 대문자 한 글자이며, A ≤ B이다. 각 줄은 주어진 순서대로 적용되는 트랜잭션 하나를 기록한다. 즉 A부터 B까지의(양 끝 포함) 모든 일련번호가 상태 코드 S, 이관 코드 T로 설정된다. 한 케이스의 트랜잭션 목록은 오직 0 하나만 있는 줄로 끝난다.

각 테스트 케이스에 대해, 케이스의 이름을 한 줄에 그대로 출력하고, 이어서 그 케이스의 모든 트랜잭션을 적용한 뒤 얻어지는 최소 행 수의 일련번호 표를 출력한다. 표의 각 행은 시작 일련번호, 끝 일련번호, 상태 코드, 이관 코드를 공백 하나로 구분하여 나열한다.