Dynamic Farm Connectivity

Farmer John operates \(N\) farms (\(1 \le N \le 10^5\)) numbered from 1 to \(N\). Initially, no roads connect any two farms and every farm is actively producing milk.

Due to an ever–changing economy, Farmer John performs \(Q\) update operations (\(0 \le Q \le 2\cdot10^5\)). There are three types of operations:

• D x: Deactivate an active farm \(x\), so that it stops producing milk.
• A x y: Add a road between two active farms \(x\) and \(y\).
• R e: Remove the road that was added in the \(e\)th addition operation (i.e. when \(e=1\) it refers to the very first added road).

A farm \(x\) is called related if either:

• Farm \(x\) is active (i.e. it is still producing milk), or
• There is a series of roads connecting \(x\) to another active farm.

Your task is: for each farm \(x\) (\(1 \le x \le N\)), find the maximum update index \(i\) (where \(0\le i\le Q\)) such that after performing the first \(i\) operations, farm \(x\) is related. Note that update index \(0\) represents the initial state before any updates.

Input Format:

inputFormat

The first line contains two integers \(N\) and \(Q\). Each of the following \(Q\) lines contains one update operation in one of the following formats:

• D x
• A x y
• R e

It is guaranteed that for each operation:

• For an operation D x, farm \(x\) is active at that moment.
• For an operation A x y, both \(x\) and \(y\) are active at that moment.
• For an operation R e, the \(e\)th addition operation was previously performed and not yet removed.

outputFormat

Output \(N\) integers separated by spaces (or newlines), where the \(i\)th integer is the maximum update index \(i\) (\(0 \le i \le Q\)) such that after applying that many updates the farm \(i\) is related.

sample

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

5 5 5 5