One day, AwD went to play in the forest, and upon returning, he told zhangzy, "I discovered many moving trees!" zhangzy replied, "What is so strange about that? I can maintain the structure of any tree with my fingers."

A few days later, AwD went to play in the desert, and upon returning, he told zhangzy, "I discovered many moving cacti!" zhangzy replied, "What is so strange about that? I can maintain the structure of any cactus with my toes."

A few more days later, AwD went to play on a basketball court, and upon returning, he told zhangzy, "I discovered many moving k-FCs!" zhangzy replied, "What is so strange about that? I can maintain the structure of any k-FC without doing anything at all."

AwD was very depressed, so he turned to you for help. Please help him.

If every edge in an undirected connected graph belongs to at most $k$ simple cycles, we call it a k-FC.

If every connected component of an undirected graph is a k-FC and there are no self-loops, we call it a basketball court.

To prove that you can indeed maintain a k-FC, we give you $n$ nodes, labeled from $1$ to $n$.

Initially, there are no edges, and each node $i$ has a non-negative weight $w_i$. Perform one of the following operations each time:

• link v u w: Add an edge with weight $w$ between nodes $v$ and $u$.
  • $1 \leq v, u \leq n$ and $w$ is a positive integer. It is guaranteed that the graph remains a basketball court after the operation.
  • Output ok after performing this operation.
• cut v u w: Remove an edge with weight $w$ between nodes $v$ and $u$.
  • $1 \leq v, u \leq n$ and $w$ is a positive integer. It is guaranteed that the graph remains a basketball court after the operation.
  • Output ok after performing this operation (if there are multiple edges with weight $w$, remove any one of them).
• query1 v u: Query the shortest path information between node $v$ and node $u$.
  • $1 \leq v, u \leq n$.
  • Output two space-separated integers $\min, \sigma$, representing the minimum node weight and the sum of node weights on the shortest path, respectively.
  • If there is no path, output $\min=-1, \sigma=-1$.
  • If the shortest path is not unique, output $\min=-2, \sigma=-2$.
• query2 v u: Query information about the sub-k-FC $u$ rooted at node $v$.
  • $1 \leq v, u \leq n$.
  • The sub-k-FC $u$ rooted at node $v$ is defined as the connected component containing $u$ after removing all edges on all simple paths between $v$ and $u$.
  • Output two space-separated integers $\min, \sigma$, representing the minimum node weight and the sum of node weights in the sub-k-FC $u$, respectively.
  • If $v$ and $u$ are not connected, output $\min=-1, \sigma=-1$.
• add1 v u d: Add $d$ to the weight of every node on the shortest path between node $v$ and node $u$.
  • $1 \leq v, u \leq n$ and $d$ is a positive integer.
  • If a path exists and the shortest path is unique, output ok.
  • Otherwise, the operation is invalid; do not perform it and output failed.
• add2 v u d: Add $d$ to the weight of every node in the sub-k-FC $u$ rooted at node $v$.
  • $1 \leq v, u \leq n$ and $d$ is a positive integer.
  • If $v$ and $u$ are in the same connected component, output ok.
  • Otherwise, the operation is invalid; do not perform it and output failed.

Note: As is well known, k-FC is an abbreviation for k-Factors Cactus.

Input

The first line contains an integer $T$ representing the test set ID.

The second line contains three space-separated positive integers $n, m, k$, representing $n$ nodes, $m$ operations, and that each edge belongs to at most $k$ simple cycles.

The next line contains $n$ positive integers, where the $i$-th integer is $w_i$.

The next $m$ lines each represent an operation.

Output

For each operation, output the corresponding result.

Examples

Input 1

0
11 23 4
10 5 11 7 8 14 30 3 16 20 19
link 1 2 5
link 2 3 3
link 3 4 7
link 4 5 8
link 2 6 10
link 6 7 15
link 4 7 3
link 6 8 9
link 6 8 6
link 7 9 12
link 9 11 10
link 7 10 4
link 9 10 8
query1 6 11
query1 2 10
query2 8 7
add1 8 5 100
query1 1 7
query2 8 7
add2 11 7 1000
query1 8 3
add2 3 2 2333
query1 1 5

Output 1

ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
ok
-2 -2
5 73
16 85
ok
5 263
16 185
ok
1005 4233
ok
1011 9907

Subtasks

There are 18 test sets in total:

Special Property A: link and cut operations occur before all other operations.

Special Property B: No query2, add1, or add2 operations.

Special Property C: No query2 or add2 operations.

$1 \leq n \leq 50000$; $1 \leq m \leq 250000$.

It is guaranteed that $w$ in link and cut operations satisfies $1 \leq w \leq 10000$, so calculations involving edge weights will not exceed the range of a 32-bit signed integer.

It is guaranteed that the initial $w_i$ does not exceed $10^9$, and the sum of $d$ in all add1 and add2 operations does not exceed $10^9$.