착신 전환

현대의 사무실 전화 시스템은 걸려 온 전화를 자동으로 다른 번호로 전환(포워딩)할 수 있습니다. 예를 들어 어떤 직원이 휴가를 떠나면, 자신의 내선으로 걸려 오는 모든 전화가 동료에게 전달되도록 설정해 둘 수 있습니다. 이 문제에서는 그러한 착신 전환을 추적하는 시스템을 시뮬레이션합니다.

회사의 모든 전화기는 네 자리 내선 번호를 가집니다. 착신 전환을 설정하려는 직원은 다음 정보를 입력합니다.

• 자신의 내선 번호(출발지, source)
• 전환을 시작할 시각(time)
• 전환이 지속되는 길이(지속 시간, duration)
• 전화를 전달할 내선 번호(도착지, target)

규칙은 다음과 같습니다.

• 모든 내선 번호는 정확히 네 자리입니다.
• 내선 번호 0000과 9999는 특수 용도로 예약되어 있어, 직원이 입력하는 정보로는 사용되지 않습니다.
• 시각은 1시간 단위의 정수로 기록하며, 매년 마지막 날 자정에 0000으로 시작하는 시계를 기준으로 합니다. 따라서 시각은 0000 이상 8784($366 \times 24$) 이하의 정수입니다. 시스템은 매년 초에 완전히 초기화됩니다.
• 시작 시각이 $X$, 지속 시간이 $Y$인 전환 규칙은 $X \le T \le X + Y$를 만족하는 모든 시각 $T$에서 유효합니다(양쪽 끝 포함).

직원들은 항상 올바른 형식으로 요청을 입력합니다. 형식을 지키고, 연말을 넘기는 요청을 하지 않으며, 같은 내선에 대해 시간이 겹치는 두 요청을 입력하지 않습니다. 따라서 어느 시각에나 한 내선 번호에는 유효한 전환 규칙이 최대 하나만 존재합니다.

그럼에도 전환이 고리(순환)를 이룰 수 있습니다. 예를 들어 A가 B로, B가 C로, C가 다시 A로 전환하도록 설정하면, 이 셋 중 누구에게 전화를 걸어도 전화가 영원히 전달됩니다. 이를 처리하기 위해, 걸려 온 내선에서 전환 사슬을 따라가다가 이미 지나온 내선을 다시 만나면(즉 사슬이 순환에 빠지면), 그 전화는 특별한 막다른 내선 9999로 연결됩니다.

첫 줄에 시뮬레이션할, 서로 독립적인 착신 전환 시스템의 개수 $N$($1 \le N \le 10$)이 주어집니다.

각 시스템은 두 부분으로 기술됩니다.

먼저 0개에서 100개까지의 전환 요청이 한 줄에 하나씩 주어지며, 각 줄은 출발지 시작시각 지속시간 도착지 형식(네 자리 수 네 개)입니다. 요청은 접수된 순서대로 나열됩니다. 첫 번째 필드가 0000인 줄이 이 부분의 끝을 나타냅니다.

이어서 한 개 이상의 전화가 한 줄에 하나씩 주어지며, 각 줄은 시각 내선번호 형식이고 시각에 대해 감소하지 않는(오름차순) 순서로 나열됩니다. 각 줄은 해당 시각에 해당 내선번호로 전화가 걸려 왔음을 뜻합니다. 첫 번째 필드가 9000인 줄이 이 부분의 끝을 나타냅니다.

각 시스템에 대해 순서대로, 먼저 그 시스템의 번호 N(1, 2, ...)을 이용해 SYSTEM N 줄을 출력합니다. 그다음, 해당 시스템으로 걸려 온 각 전화에 대해 입력 순서대로 다음 형식의 줄을 하나씩 출력합니다.

AT tttt CALL TO eeee RINGS rrrr

여기서 tttt는 전화가 걸려 온 시각, eeee는 처음 건 내선 번호, rrrr는 전화가 최종적으로 울리는 내선 번호입니다. eeee에서 시작해 유효한 전환 규칙을 따라갑니다. 사슬이 더 이상 유효한 전환이 없는 내선에 도달하면 그 내선이 울립니다. 사슬이 순환에 빠지면 그 전화는 9999에서 울립니다. 네 개의 값은 모두 네 자리로 출력합니다.