코코는 3가지 종류의 초콜릿을 삼각형 모양으로 배열하여 방의 한쪽 벽을 장식하려고 한다. 구체적인 방법은 다음과 같다.

• 먼저 맨 아랫줄을 임의의 초콜릿으로 채운다.
• 그 윗줄부터는 각 칸의 바로 아래에 있는 두 개의 초콜릿을 보고 다음과 같은 방법으로 종류를 결정한다.
  • 두 초콜릿이 같은 종류이면, 그 종류의 초콜릿을 놓는다. (예: 화이트 초콜릿 2개의 위에는 화이트 초콜릿을 놓는다.)
  • 두 초콜릿이 다른 종류이면, 둘 다 아닌 종류의 초콜릿을 놓는다. (예: 민트 초콜릿과 화이트 초콜릿 위에는 다크 초콜릿을 놓는다.)

아래는 위 규칙에 따라 초콜릿 장식을 완성한 예시이다.

맨 아랫줄의 디자인을 아직 결정하지 못한 코코는 초콜릿을 하나씩 바꿔가면서 고민하고 있다. 코코가 초콜릿을 하나 바꿀 때마다 맨 위에 올 초콜릿이 무엇인지 알려주자.

Input

첫 줄에는 맨 아랫줄을 구성하는 초콜릿의 개수 $N$이 주어진다. ($1 \le N \le 500\;000$)

다음 줄에는 $N$개의 초콜릿의 종류를 나타내는 길이 $N$의 문자열이 주어진다. 화이트 초콜릿은 W, 다크 초콜릿은 D, 민트 초콜릿은 M으로 주어진다.

그다음 줄에는 코코가 초콜릿을 바꾸는 횟수 $Q$가 주어진다. ($1 \le Q \le 500\;000$)

다음 $Q$줄에는 각 줄마다 바꿀 초콜릿의 위치 $i$와 초콜릿의 종류 $c$가 주어진다. ($1 \le i \le N$, $c$는 W, D, M 중 하나) 모든 변경 사항은 누적된다.

Output

첫 줄에는 처음 상태에서 맨 위에 올 초콜릿의 종류를 출력한다.

다음 $Q$줄에는 코코가 초콜릿을 하나 바꿀 때마다 맨 위에 올 초콜릿의 종류를 출력한다.

Examples

Input 1

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

Output 1

M
D
M
D
W
D