感谢密码学，我们能够加密消息，使得除了预期的接收者之外，没有人能够阅读它们。然而，如果加密的消息实际上无法送达接收者，它们就毫无用处。如今，计算机网络是发送此类消息最典型的方式。在这个问题中，我们将研究网络提供商必须解决的问题。记住：由于消息是加密的，我们不再需要关心网络隐私。

连接计算机（服务器）的网络电缆属于不同的公司。一项新的反垄断法规规定，任何公司在每个服务器上拥有的电缆不能超过两条。此外，为了避免浪费资源，还有一项法律规定，任何单一公司拥有的电缆系统不能是冗余的，即拆除其中任何一条电缆都会导致原本相连的某两个服务器断开连接（即该公司拥有的电缆不能成环）。由于各公司一直在买卖电缆，因此执行这些规定是相当困难的。你的任务是编写一个程序来实现这一监管。

输入格式

输入包含多个实例。每个实例的第一行包含四个由空格分隔的整数 $N$、$M$、$C$ 和 $T$ —— 分别表示服务器的数量（$1 \le N \le 8000$）、电缆的数量（$0 \le M \le 100000$）、公司的数量（$1 \le C \le 100$）以及电缆买卖交易的数量（$0 \le T \le 100000$）。

接下来的 $M$ 行描述电缆。每行包含三个由空格分隔的整数 $S_{j1}$、$S_{j2}$ 和 $K_j$，表示由该电缆连接的服务器编号 $S_{j1}$ 和 $S_{j2}$（$1 \le S_{j1} < S_{j2} \le N$）以及最初拥有该电缆的公司编号 $K_j$（$1 \le K_j \le C$）。对于每对服务器，最多只有一条电缆连接它们。初始状态满足上述规定，即每个公司在每个服务器上最多拥有两条与之相连的电缆，且任何单一公司拥有的电缆系统均无环。

最后，接下来的 $T$ 行中，每行包含整数 $S_{i1}$、$S_{i2}$ 和 $K_i$，描述一次交易，其中公司 $K_i$（$1 \le K_i \le C$）试图购买服务器 $S_{i1}$ 和 $S_{i2}$（$1 \le S_{i1} < S_{i2} \le N$）之间的电缆。

最后一个实例后面紧跟一行，包含四个零。

输出格式

对于每个输入实例，输出 $T$ 行，描述交易的结果。

可能的结果有：

• "No such cable."：如果该对服务器之间没有电缆连接。
• "Already owned."：如果该电缆已被公司 $K_i$ 拥有。
• "Forbidden: monopoly."：如果公司 $K_i$ 在 $S_{i1}$ 或 $S_{i2}$ 处已经拥有两条电缆。
• "Forbidden: redundant."：如果 $K_i$ 在 $S_{i1}$ 和 $S_{i2}$ 的每一个处最多拥有一条电缆，但授予所有权会使 $K_i$ 拥有的电缆产生环。
• "Sold."：如果以上限制均不适用。在这种情况下，为了后续交易，该 $S_{i1}$ 和 $S_{i2}$ 之间的电缆所有权将变更为 $K_i$。

在每个实例之后打印一个空行。

样例

输入样例 1

4 5 3 5
1 2 1
2 3 1
3 4 2
1 4 2
1 3 3
1 2 3
1 2 3
1 4 3
2 3 3
2 4 3
2 1 1 1
1 2 1
1 2 1
0 0 0 0

输出样例 1

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

Already owned.