D - Masking Tape Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個のマスが横一列に並んでおり、左から順にマス 1 からマス N までの番号がついています。色は英小文字で表されます。

はじめ、すべてのマスの色は a で、各マスには何も置かれていません。

Q 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 2 種類のいずれかです。

  • 1 X : マス X にタイルが置かれていなければタイルを置き、置かれていれば取り除く。

  • 2 C : タイルが置かれていないすべてのマスの色を C に変更する。

すべてのクエリを処理した後の各マスの色を（タイルが置かれているかどうかにかかわらず）求めてください。

制約

  • 1 \le N,Q \le 3\times 10^5
  • 各クエリはタイプ 1 またはタイプ 2 のいずれか
  • タイプ 1 のクエリにおいて、X は 1 \le X \le N を満たす整数
  • タイプ 2 のクエリにおいて、C は英小文字 1 文字

入力

入力は以下の形式で標準入力から与えられる。

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

各クエリ \mathrm{query}_i ~ (1 \le i \le Q) は

1 X

または、

2 C

の形で与えられる。

出力

最終的な各マスの色を、左から順につなげた長さ N の文字列として出力せよ。

入力例 1

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

出力例 1

bcc

タイルの状態について、置かれているならば #、 そうでないならば . として左から順につなげた文字列で表現をすることにします。

クエリによって、以下のようにマスの色・タイルの状態が変化します。はじめの状態は aaa と ... です。

  • 1 つ目のクエリを処理すると、マス 2 にタイルが置かれる。状態は aaa と .#. となる。
  • 2 つ目のクエリを処理すると、タイルの置かれていないマスの色が b に変更される。状態は bab と .#. となる。
  • 3 つ目のクエリを処理すると、マス 1 にタイルが置かれる。状態は bab と ##. となる。
  • 4 つ目のクエリを処理すると、マス 2 のタイルが取り除かれる。状態は bab と #.. となる。
  • 5 つ目のクエリを処理すると、タイルの置かれていないマスの色が c に変更される。状態は bcc と #.. となる。

よって bcc と出力してください。マス 1 にはタイルが置かれたままですが、その場合であってもマスの色を出力します。

入力例 2

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

出力例 2

dkmfkqfazk

Score : 400 points

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.

Sample Input 1

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

Sample Output 1

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.

Sample Input 2

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

Sample Output 2

dkmfkqfazk