Farmer John operates a collection of NN farms (1≤N≤1051≤N≤105), conveniently numbered 1…N1…N. Initially, there are no roads connecting these farms to each-other, and each farm is actively producing milk.Due to the dynamic nature of the economy, Farmer John needs to make changes to his farms according to a series of QQ update operations (0≤Q≤2⋅1050≤Q≤2⋅105). Update operations come in three possible forms:

• (D x) Deactivate an active farm xx, so it no longer produces milk.
• (A x y) Add a road between two active farms xx and yy.
• (R e) Remove the eeth road that was previously added (e=1e=1 is the first road that was added).

A farm xx that is actively producing milk, or that can reach another active farm via a series of roads, is called a "relevant" farm. For each farm xx, please calculate the maximum ii (0≤i≤Q0≤i≤Q) such that xx is relevant after the ii-th update.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN and QQ. The next QQ lines each contain an update of one of the following forms:

D x
A x y
R e

It is guaranteed that for updates of type R, ee is at most the number of roads that have been added so far, and no two updates of type R have the same value of ee.

OUTPUT FORMAT (print output to the terminal / stdout):

Please output NN lines, each containing an integer in the range 0…Q0…Q.

SAMPLE INPUT:

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

SAMPLE OUTPUT:

7
8
6
9
9

In this example, roads are removed in the order (2,3),(1,2),(2,4)(2,3),(1,2),(2,4).

• Farm 11 is relevant just before (1,2)(1,2) is removed.
• Farm 22 is relevant just before (2,4)(2,4) is removed.
• Farm 33 is relevant just before (2,3)(2,3) is removed.
• Farms 44 and 55 are still active after all queries. Therefore they both stay relevant, and the output for both should be QQ.

SCORING:

• Tests 2 through 5 satisfy N≤103N≤103, Q≤2⋅103Q≤2⋅103
• Test cases 6 through 20 satisfy no additional constraints.