The Bridge on the River Delta

In the mystical land of Midsommer, there is a river called \(\delta\) where deep purple acid flows dangerously. Surrounding the river are several islands connected by bridges, each with its own danger factor. Detective Richard Hradecki, both an investigator and a crime novelist, needs your help to determine the safest route between two islands. Here, the safest path is defined as the one in which the maximum danger factor over all bridges is minimized. If no such path exists, you must report \(-1\).

You will process a sequence of events:

• Add event: An event of the form A u v w indicates that a new bridge connecting islands u and v has been built with danger factor \(w\).
• Destroy event: An event of the form D u v indicates that an existing bridge between islands u and v is destroyed.
• Query event: An event of the form Q u v asks you to determine the safest path from island u to island v; that is, the path whose bridges have the smallest possible maximum danger factor.

Process each event in the given order. For each query event, output the minimal maximum danger factor encountered on any path from u to v. If no path exists, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(q\) where \(n\) is the number of islands and \(q\) is the number of events to process.

Each of the next \(q\) lines contains an event in one of the following formats:

• A u v w: Add a bridge between islands \(u\) and \(v\) with danger factor \(w\).
• D u v: Destroy the existing bridge between islands \(u\) and \(v\). It is guaranteed that such a bridge exists when this event occurs.
• Q u v: Query for the safest path from island \(u\) to island \(v\).

outputFormat

For each query event (lines starting with Q), output a single line containing the minimal maximum danger factor along any path from island \(u\) to island \(v\). If no path exists, output \(-1\).

sample

4 6
A 1 2 10
A 2 3 5
Q 1 3
A 3 4 7
Q 1 4
D 2 3
Q 1 3

10
10
-1