Problem Statement

There are $N$ squares arranged in a horizontal row, numbered square $1$ to square $N$ from left to right. Colors are represented by lowercase English letters.

Initially, the color of every square is a, and nothing is placed on any square.

You are given $Q$ queries; process them in the given order. Each query is of one of the following two types:

• 1 X : If no tile is placed on square $X$, place a tile on it; if a tile is placed on it, remove it.
• 2 C : Change the color of every square on which no tile is placed to $C$.

Find the color of each square after processing all queries (regardless of whether a tile is placed on it).

Constraints

• $1 \le N,Q \le 3\times 10^5$
• Each query is of type $1$ or type $2$.
• In type-$1$ queries, $X$ is an integer satisfying $1 \le X \le N$.
• In type-$2$ queries, $C$ is a single lowercase English letter.

Input

The input is given from Standard Input in the following format:

• $N$ $Q$
• $\mathrm{query}_1$
• $\vdots$
• $\mathrm{query}_Q$

Each query $\mathrm{query}_i ~ (1 \le i \le Q)$ is given in the form

• 1 X

or

• 2 C

Output

Output the final colors of the squares as a string of length $N$, concatenated from left to right.

3 5
1 2
2 b
1 1
1 2
2 c

bcc

We represent the state of tiles as a string formed by concatenating, from left to right, # if a tile is placed and . otherwise.

The queries change the colors of the squares and the state of tiles as follows. The initial state is aaa and ....

• Processing the $1$-st query places a tile on square $2$. The state becomes aaa and .#..
• Processing the $2$-nd query changes the color of the squares without tiles to b. The state becomes bab and .#..
• Processing the $3$-rd query places a tile on square $1$. The state becomes bab and ##..
• Processing the $4$-th query removes the tile on square $2$. The state becomes bab and #...
• Processing the $5$-th query changes the color of the squares without tiles to c. The state becomes bcc and #...

Thus, output bcc. A tile remains placed on square $1$, but even in that case, output the color of the square.

10 15
1 8
2 m
1 3
1 10
2 q
1 6
1 10
2 d
1 1
2 z
1 9
2 f
1 4
1 7
2 k

dkmfkqfazk

• Source: AtCoder ABC 477 D