이상한 규정

암호화 기술 덕분에 우리는 의도한 수신자만 메시지를 읽을 수 있도록 메시지를 암호화할 수 있다. 하지만 암호화된 메시지도 수신자에게 실제로 전달되지 않으면 쓸모가 없다. 오늘날 이러한 메시지를 전달하는 가장 흔한 방법은 컴퓨터 네트워크이다. 이 문제에서는 네트워크 공급자들이 풀어야 하는 문제를 다룬다. 메시지는 이미 암호화되어 있으므로 네트워크 보안 자체는 신경 쓰지 않아도 된다.

서버들을 잇는 네트워크 케이블은 여러 회사가 나누어 소유한다. 새로 제정된 독점 금지법에 따르면, 어떤 회사도 한 서버에 케이블을 2개보다 많이 소유할 수 없다. 또한 자원 낭비를 막기 위해, 어떤 회사도 불필요한 케이블을 소유해서는 안 된다. 즉, 한 회사가 소유한 케이블 중 어느 하나를 없앴을 때 그 케이블이 잇던 두 서버가 (그 회사가 가진 케이블만으로는) 서로 연결이 끊어져야 한다. 다시 말해, 한 회사가 소유한 케이블들은 사이클을 이루지 않는다. 회사들이 케이블을 끊임없이 사고팔기 때문에 이 규정을 지키도록 관리하기는 매우 어렵다. 당신이 할 일은 이 규정의 시행을 돕는 프로그램을 작성하는 것이다.

입력은 여러 개의 예시로 이루어진다. 각 예시의 첫 줄에는 공백으로 구분된 네 정수 N, M, C, T가 주어진다. N은 서버의 수(1 ≤ N ≤ 8000), M은 케이블의 수(0 ≤ M ≤ 100000), C는 회사의 수(1 ≤ C ≤ 100), T는 케이블 거래의 수(0 ≤ T ≤ 100000)이다.

이어지는 M개의 줄은 각 케이블을 설명한다. 각 줄에는 공백으로 구분된 세 정수 Sj1, Sj2, Kj가 주어진다. Sj1과 Sj2는 그 케이블이 잇는 두 서버의 번호이며(1 ≤ Sj1 < Sj2 ≤ N), Kj는 그 케이블을 처음 소유한 회사의 번호이다. 서로 다른 두 서버 사이에는 케이블이 최대 하나만 존재한다. 처음 상태는 규정을 만족한다. 즉, 각 회사는 어느 서버에서도 케이블을 최대 2개까지만 소유하며, 한 회사가 소유한 케이블들은 사이클을 이루지 않는다.

이어지는 T개의 줄에는 각 거래를 나타내는 세 정수 Si1, Si2, Ki가 주어진다. 이는 회사 Ki(1 ≤ Ki ≤ C)가 서버 Si1과 Si2를 잇는 케이블을 사려 한다는 뜻이다.

마지막 예시 다음 줄에는 네 개의 0이 주어지며, 이는 입력의 끝을 나타낸다.

각 예시에 대해, 거래의 결과를 나타내는 T개의 줄을 출력한다. 각 거래의 결과로 가능한 출력은 다음과 같다.

• No such cable. : 두 서버를 잇는 케이블이 존재하지 않을 때
• Already owned. : 회사 Ki가 이미 그 케이블을 소유하고 있을 때
• Forbidden: monopoly. : 회사 Ki가 이미 서버 Si1 또는 Si2에서 케이블 2개를 소유하고 있을 때
• Forbidden: redundant. : 회사 Ki가 서버 Si1과 Si2에서 각각 케이블을 최대 1개만 소유하고 있지만, 이 케이블의 소유권을 넘기면 Ki가 소유한 케이블들이 사이클을 이루게 될 때
• Sold. : 위의 어떤 제한에도 걸리지 않을 때. 이 경우 서버 Si1과 Si2를 잇는 케이블의 소유권이 회사 Ki에게 넘어가며, 이후 거래에도 반영된다.

서로 다른 예시의 출력은 빈 줄 하나로 구분한다.