A Strange Regulation

Thanks to cryptography, we can encrypt a message so that no one other than the intended recipient can read it. An encrypted message is useless, however, if it never actually reaches its recipient. Today, computer networks are the most common way to deliver such messages. In this problem we study a problem that network providers must solve. Because the messages are already encrypted, you no longer need to worry about network security itself.

The network cables connecting the servers are owned by different companies. A newly enacted anti-monopoly law states that no company may own more than two cables at any single server. To avoid wasting resources, it also states that no company may own a redundant cable. That is, if any one of a company's cables were removed, the two servers it connected must become disconnected when using only that company's cables. In other words, the cables owned by a single company never form a cycle. Because companies constantly buy and sell cables, enforcing this rule is very hard. Your task is to write a program that helps enforce it!

The input contains several test cases. The first line of each test case has four space-separated integers N, M, C, T. N is the number of servers (1 ≤ N ≤ 8000), M is the number of cables (0 ≤ M ≤ 100000), C is the number of companies (1 ≤ C ≤ 100), and T is the number of cable transactions (0 ≤ T ≤ 100000).

The next M lines describe the cables. Each line has three space-separated integers Sj1, Sj2, Kj. Sj1 and Sj2 are the two servers the cable connects (1 ≤ Sj1 < Sj2 ≤ N), and Kj is the company that initially owns that cable. There is at most one cable between any pair of servers. The initial state satisfies the rule: each company owns at most two cables at any server, and the cables owned by any single company form no cycle.

The next T lines each contain three integers Si1, Si2, Ki describing a transaction. This means company Ki (1 ≤ Ki ≤ C) wants to buy the cable between servers Si1 and Si2.

After the last test case, a line with four zeros is given, marking the end of the input.

For each test case, print T lines giving the result of each transaction. The possible results are:

• No such cable. : there is no cable between the two servers.
• Already owned. : company Ki already owns that cable.
• Forbidden: monopoly. : company Ki already owns two cables at server Si1 or at server Si2.
• Forbidden: redundant. : company Ki owns at most one cable at each of Si1 and Si2, but transferring ownership of this cable would make Ki's cables form a cycle.
• Sold. : none of the above restrictions apply. In this case ownership of the cable between Si1 and Si2 passes to company Ki and is reflected in later transactions.

Separate the output of consecutive test cases with a single blank line.