There is an undirected graph $G$, where each node has a weight and each edge has a color. This undirected graph satisfies the following two conditions:

1. For any node, there are at most two incident edges of the same color.
2. There are no monochromatic cycles in the graph (a monochromatic cycle is a cycle formed by edges of the same color).

You need to support the following three operations on this graph:

1. Modify the weight of a node.
2. Modify the color of an edge.
3. Query the maximum weight of nodes on all possible simple paths between node $u$ and node $v$ in the subgraph formed by edges of color $c$.

Input

The first line contains four positive integers $N, M, C, K$, where $N$ is the number of nodes, $M$ is the number of edges, $C$ is the number of edge colors, and $K$ is the number of operations.

The next $N$ lines each contain a positive integer $v_i$, representing the weight of node $i$.

The following $M$ lines each contain three positive integers $u, v, w$, representing an edge connecting node $u$ and node $v$ with color $w$. It is guaranteed that $1 \le u, v \le N$, $0 \le w < C$, $u \neq v$, and there is at most one edge between any two nodes (regardless of color).

The last $K$ lines each represent an operation. The first integer $k$ in each line indicates the operation type:

1. $k = 0$ is a node weight modification operation, followed by two positive integers $x$ and $y$, indicating that the weight $v_x$ of node $x$ is changed to $y$.
2. $k = 1$ is an edge color modification operation, followed by three positive integers $u, v$, and $w$, indicating that the color of the edge connecting node $u$ and node $v$ is changed to $w$. It is guaranteed that $0 \le w < C$.
3. $k = 2$ is a query operation, followed by three positive integers $c, u$, and $v$, indicating a query for the maximum weight of nodes on all possible simple paths between node $u$ and node $v$ consisting only of edges of color $c$. If there is no path between $u$ and $v$ consisting of edges of color $c$, output "-1".

Output

The output contains several lines, each corresponding to an operation:

1. For node weight modification operations, no output is required.
2. For edge color modification operations, output as follows: a) If there is no edge connecting node $u$ and node $v$, output "No such edge.". b) If the modification would violate condition 1, do not modify the color and output "Error 1.". c) If the modification would violate condition 2, do not modify the color and output "Error 2.". d) Otherwise, the color is successfully modified; output "Success.". If multiple conditions are violated, output the first one that applies (e.g., if both b and c are violated, only output "Error 1.").
3. For query operations, output a single integer.

Constraints

• For 30% of the data: $N \le 1000, M \le 10000, C \le 10, K \le 1000$.
• For another 20% of the data: $N \le 10000, M \le 100000, C = 1, K \le 100000$.
• For 100% of the data: $N \le 10000, M \le 100000, C \le 10, K \le 100000$.

Examples

Input 1

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

Output 1

4
Success.
Error 2.
-1
Error 1.
5

Note

Color 0 is represented by solid lines, and color 1 is represented by dashed lines. The path from node 1 to node 4 using only color 0 edges is $1 - 2 - 4$, so $\max\{v_1, v_2, v_4\} = \max\{1, 2, 4\} = 4$. Changing the edge between node 1 and node 2 to color 1 is successful, output "Success.".

Changing the edge between node 4 and node 3 to color 1 would create a cycle of color 1 ($1 - 2 - 4 - 3 - 1$), violating condition 2, so the change is rejected and "Error 2." is output. There is no path between node 1 and node 4 using only color 0 edges, so output "-1". Changing the edge between node 2 and node 3 to color 1 would result in node 2 having three incident edges of color 1, violating condition 1, so the change is rejected and "Error 1." is output. The weight of node 2 is changed to 5. The path from node 1 to node 4 using only color 1 edges is $1 - 2 - 4$, so $\max\{v_1, v_2, v_4\} = \max\{1, 5, 4\} = 5$.