White, Dark, Mint Chocolate

Coco wants to decorate one wall of a room with three kinds of chocolate arranged in a triangle. The procedure is as follows.

• First, fill the bottom row with chocolates of any kinds.
• For each row above, look at the two chocolates directly below each cell and choose the kind as follows.
  • If the two chocolates are the same kind, place a chocolate of that kind. (Example: above two white chocolates, place a white chocolate.)
  • If the two chocolates are different kinds, place a chocolate of the kind that is neither of them. (Example: above a mint chocolate and a white chocolate, place a dark chocolate.)

The finished decoration is shown below.

Coco has not yet decided the design of the bottom row, so Coco changes one chocolate at a time and considers the result. Each time Coco changes a chocolate, report the kind of chocolate on the top.

The first line contains the number of chocolates $N$ in the bottom row. ($1\le N\le 500 000$)

The next line contains a string of length $N$ that gives the kinds of the $N$ chocolates. White chocolate is W, dark chocolate is D, and mint chocolate is M.

The next line contains the number of changes $Q$. ($1\le Q\le 500 000$)

Each of the next $Q$ lines contains a position $i$ of the chocolate to change and the new kind $c$. ($1\le i\le N$, $c$ is one of W, D, M) All changes accumulate.

On the first line, print the kind of the top chocolate for the initial state.

On each of the next $Q$ lines, print the kind of the top chocolate after each change.