The Warmest Path

In a dormitory building, there are n locations and several roads connecting them. Initially, Little R is not familiar with any road. As time goes by, he gradually discovers roads. When a road is discovered, its two endpoints, its unique temperature t and its length d are revealed. Note that all roads have distinct temperatures.

Little R needs to travel from one location to another. For each journey, he desires to take the warmest path. The definition of the warmest path is as follows. Given a path with a set of roads, sort the temperatures of the roads in increasing order to get a sequence. Among all possible simple paths (i.e. no repeated roads) between two locations, the warmest path is the one whose sorted temperature sequence is lexicographically maximum. Here, the lexicographical order is defined differently: for two distinct sequences \(a\) and \(b\), if \(a\) is a prefix of \(b\), then \(a\) is considered larger. In particular, the empty sequence is regarded as the maximum.

It can be proven that due to the uniqueness of road temperatures, the warmest path is unique if it exists. Your task is: for each journey query, using the roads discovered so far, output the total length of the warmest path. If the current discovered roads do not connect the two locations, output -1. Note that if the start and destination are the same, the path is empty and its total length is 0.

Hint: In an undirected graph with unique edge weights, the warmest path between any two vertices is the unique path between them in the maximum spanning forest of the graph. A maximum spanning tree can be computed by sorting edges in descending order of their temperatures and performing a union‐find.

Mathematical formulation:

Given a sequence of road temperatures on a path \(a = (a_1, a_2, \ldots, a_k)\) sorted in increasing order, for two distinct sequences \(a\) and \(b\), we define \(a > b\) if either:
    1. There exists an index \(i\) such that \(a_j = b_j\) for all \(j  b_i\), or
    2. \(a\) is a prefix of \(b\) (in which case \(a\) is considered larger).
Note that the empty sequence is maximum.

inputFormat

The input starts with a line containing two integers n and q (1 ≤ n, q ≤ 10^5, for example), where n is the number of locations and q is the number of events.

Each of the following q lines is in one of the following two formats:

• A u v t d — a road is discovered connecting locations u and v with temperature t and length d. All temperatures t are distinct.
• Q s e — query the warmest path from location s to location e.

There is at least one query in the input. Note that the roads discovered are cumulative.

outputFormat

For each query (lines beginning with Q), output a single integer in a separate line. This integer is the total length of the warmest path from the start to the destination location using the roads discovered so far, or -1 if no such path exists. Note that if s equals e, output 0.

sample

5 7
A 1 2 10 5
A 2 3 20 10
Q 1 3
A 1 3 15 7
Q 1 3
A 4 5 30 3
Q 3 5

15
7
-1