Query \(1\) can be processed in \(O(1)\) time by flipping an element of a boolean array representing whether each cell has a tile.

However, query \(2\) naively requires “for each cell, check if it contains a tile, and repaint it if it doesn’t.” There will be at worst \(\Theta (N)\) cells whose colors change, which leads to \(\Theta(NQ)\) on its own.

---

Which operation is wasting time in this algorithm? The answer is that cells are repainted in every query. The only result we want is the final colors, so it suffices to obtain the resulting colors alone.

Among multiple possible approaches, the following one is intuitive:

• Scan the queries from the front to find whether each cell is covered by a tile in the end.
• Scan the queries form the back. When there is a painting query, paint only the cells that are not painted yet nor covered by a tile.

This way, each cell is painted a color only once. This strategy can be implemented as follows.

---

Manage a set \(S\) of cells that are not painted yet nor covered by a tile. Scan the queries from the back.

• Type \(1\)

  Change the state of the tiles. If this affects to the set \(S\), update \(S\).

• Type \(2\)

  Paint all cells in \(S\), and empty \(S\).

The time complexity is \(O(Q + N)\), assuming that insertion and deletion on a set can be done in \(O(1)\) time.

---

Sample code (PyPy)

n, q = map(int, input().split())

qry = [(2, "a")]
tile = [0] * n
for i in range(q):
    t, x = input().split()
    if t == "1":
        x = int(x) - 1
        tile[x] ^= 1
        qry.append((1, x))
    else:
        qry.append((2, x))

s = set(i for i in range(n) if tile[i] == 0)
ans = [""] * n
for t, x in reversed(qry):
    if t == 1:
        if tile[x] == 0 and ans[x] == "":
            s.remove(x)
        if tile[x] and ans[x] == "":
            s.add(x)
        tile[x] ^= 1
    else:
        for i in s:
            ans[i] = x
        s.clear()

print("".join(ans))