Distributed Matrix

The Matrix was modified to use as little energy as possible because of an energy shortage. There are $n$ Matrix nodes, numbered uniquely from $1$ to $n$. Initially, only the generator, node $1$, has energy.

Nodes that need power are connected one by one to nodes that already have power, and they receive energy from them. The connections form a power network shaped as a tree. Some nodes can fail and recover after some time. A node that is already in the network never reconnects to another node, even if a node that indirectly powers it has failed.

The unreliability of a node is the time elapsed since its last recovery. If the node has never failed, it is the time since it joined the network. The generator joins at time $0$.

You must process $m$ events. Event $i$ happens exactly $i$ seconds after the start and is one of the following types:

• ! $x_i$ $y_i$: node $y_i$ connects to node $x_i$ and starts receiving energy from it.
• - $x_i$: node $x_i$ fails and stops passing energy on.
• + $x_i$: node $x_i$, which failed earlier, recovers and passes energy on again.
• ? $x_i$ $y_i$: find how reliable the pair of nodes $x_i$ and $y_i$ is.

For a query, check whether both nodes receive energy. A node receives energy if it is connected to the network and every node on the path from the generator to it, including itself, is working. If both nodes receive energy, output the total unreliability of all nodes that the work of at least one of $x_i$ or $y_i$ depends on, that is, the nodes on the paths from the generator to them. A node shared by both paths is counted once.

The first line contains two integers $n$ and $m$ ($2 \leqslant n, m \leqslant 2 \times 10^5$), the number of nodes that need power and the number of events to process.

The $i$-th of the next $m$ lines describes the query that happens at time $i$. The query type symbol is followed by either one integer $x_i$ or two integers $x_i$ and $y_i$, separated by a space, depending on the type ($1 \leqslant x_i, y_i \leqslant n$; $x_i \neq y_i$).

It is guaranteed that in a type 1 query, node $x_i$ is already connected to the network and node $y_i$ is not. For type 2 and type 3 queries, node $x_i$ fails only if it was working before, and it recovers only after the corresponding failure.

After each type 4 query, print the answer on its own line. If at least one of $x_i$ and $y_i$ does not receive energy, print -1. Otherwise, print the sum of the unreliabilities of all nodes on the paths from the generator to $x_i$ and $y_i$.

In the first example, the failure of the third node makes the answer to the second query ? 2 3 equal to -1. The answer to the first query is $6$, because $3$, $2$, and $1$ seconds have passed since the generator, the second node, and the third node joined the network, respectively. At the third query, $7$ and $6$ seconds have passed since the generator and the second node joined. The third node recovered exactly $1$ second ago, giving the answer $14$.

In the second example, the failure of the second node makes the answer to the second query -1. The answer to the first query is calculated as in the first example. The answer to the third query is $7 + 1 + 5 = 13$.