Capital of the Conquered Kingdoms

On planet X there are \(n\) countries, each occupying one city numbered from \(1\) to \(n\). Initially, no two cities from different countries are connected by a road. However, wars are frequent: if country A defeats country B, then country B ceases to exist and its territory becomes part of country A. To strengthen his rule, the king of country A builds a road between one city of country A and one city of country B (the chosen cities are specified, with one belonging to the winning country and the other to the defeated one).

Each country chooses its capital from among its cities. The capital is defined as the city which minimizes the sum of distances from it to every other city in that country (the distance is the number of roads one must traverse). In case of a tie, the city with the smallest number is chosen.

You are given a sequence of events on planet X. There are three types of events:

• A x y: A war event. Two countries fight; the winning country (which contains city x) conquers the country that contains city y and a road is built between city x and city y.
• Q x: Query the capital of the country that city x currently belongs to.
• Xor: Query the XOR of the capital cities (their numbers) of all current countries.

Initially, each country consists of a single city (so its own capital). After merging, the connections form a tree structure. When a merge occurs, the new capital is re‐computed over all cities in the resulting country.

Note: In every war event A x y, it is guaranteed that one of the cities belongs to the winning country and the other belongs to the defeated country.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q \leq 1000)\), representing the number of cities (countries) and the number of events, respectively. The following \(q\) lines each contain an event in one of the three formats:

• A x y
• Q x
• Xor

It is guaranteed that the events are valid, and in an event of type A x y, the city \(x\) is from the winning country and \(y\) is from the defeated country.

outputFormat

For each event of type Q or Xor, output the corresponding answer on a new line. For a query Q x, output the capital of the country containing city \(x\). For a query Xor, output the XOR of all current countries' capitals.

sample

3 3
Q 1
A 1 2
Q 2

1
1