Coco wants to decorate one wall of her room by arranging three types of chocolates in a triangle. The specific method is as follows:

• First, fill the bottom row with chocolates of your choice.
• For each subsequent row above, determine the type of chocolate for each cell based on the two chocolates directly below it:
  • If the two chocolates are the same type, place a chocolate of that same type. (e.g., place a white chocolate above two white chocolates.)
  • If the two chocolates are different types, place a chocolate of the third type. (e.g., place a dark chocolate above a mint chocolate and a white chocolate.)

Below is an example of a completed chocolate decoration following these rules.

Coco has not yet decided on the design of the bottom row and is considering changing the chocolates one by one. For every change Coco makes, tell her what the chocolate at the very top will be.

Input

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$ representing the types of the $N$ chocolates. White chocolate is given as W, dark chocolate as D, and mint chocolate as M.

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

The following $Q$ lines each contain the position $i$ of the chocolate to change and the type of chocolate $c$. ($1 \le i \le N$, $c$ is one of W, D, M) All changes are cumulative.

Output

The first line should output the type of the chocolate at the top in the initial state.

The next $Q$ lines should output the type of the chocolate at the top after each of Coco's changes.

Examples

Input 1

9
WDMMDDWMM
5
1 M
4 D
8 W
7 M
5 M

Output 1

M
D
M
D
W
D