AT_abc477_d [ABC477D] Masking Tape

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).

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 the final colors of the squares as a string of length $ N $ , concatenated from left to right.

### Sample Explanation 1 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. ### 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.