31465번 - 초콜릿 종류 맞히기

문제

초콜릿 종류 맞히기는 다음과 같이 진행된다.

먼저 크기가 $N\times N$인 정사각형 모양의 틀과 여러 종류의 초콜릿을 준비하고, 틀의 각 칸에 초콜릿을 하나씩 넣는다. 초콜릿의 종류는 하나의 알파벳 대문자로 나타낼 수 있다.

그리고 종이에 초콜릿 틀을 어떻게 움직일지 미리 적는다. 틀을 움직이는 방법은 시계 방향으로 90ドル$도 회전(R), 반시계 방향으로 90ドル$도 회전(L), 가로 방향으로 뒤집기(H), 세로 방향으로 뒤집기(V)가 있다. 이러한 명령의 나열은 길이 $M$의 문자열 $S$로 나타낼 수 있다.

이렇게 두 가지가 준비되었으면, 한 사람이 두 정수 $r$과 $c$를 외친다. 다른 사람은 초콜릿 틀을 $S$에 의해 움직인 결과에서 $r$행 $c$열에 오는 초콜릿의 종류를 맞히면 된다.

코코는 이 게임에서 코코 대신 초콜릿의 종류를 맞혀주는 로봇을 만들었다. 이에 맞서 한별이는 $S$의 $l$번째에서 $r$번째까지의 명령을 모두 명령 $x$로 바꿀 수 있는 로봇을 만들어 왔다. 코코의 로봇이 한별이의 로봇을 이길 수 있도록 새로운 프로그램을 만들어 주자.

입력

첫 번째 줄에는 정수 $N$의 값이 주어진다. $(1\le N\le 1,円 000)$

다음 줄부터 $N$줄에 걸쳐서 초콜릿 틀의 상태가 주어진다. 각 줄에는 $N$개의 알파벳 대문자가 공백 없이 주어진다.

그다음 줄에는 정수 $M$의 값이 주어진다. $(1\le M\le 500,円 000)$

그다음 줄에는 초콜릿 틀을 움직이는 명령의 나열 $S$가 공백 없이 주어진다. $S$는 R, L, H, V로만 이루어진 길이 $M$의 문자열이다.

그다음 줄에는 쿼리의 개수 $Q$가 주어진다. $(1\le Q\le 500,円 000)$

그다음 줄부터 $Q$줄에 걸쳐서, 각 줄에 하나의 쿼리가 주어진다. 쿼리의 종류는 다음과 같다.

• 1 r c: 초콜릿 틀을 현재의 $S$대로 움직였을 때 $r$행 $c$열의 초콜릿의 종류를 한 줄에 출력한다. $(1\le r,c\le N)$
• 2 l r x: $S$의 $i$번째 명령을 $S_i$라고 할 때, $l$ 이상 $r$ 이하의 모든 정수 $i$에 대해 $S_i$를 $x$로 바꾼다. $(1\le l\le r\le M;$ $x$는 R, L, H, V 중 하나$)$

1번 쿼리는 하나 이상 주어진다.

출력

각각의 1번 쿼리에 대한 답을 각 줄에 출력한다.

제한

힌트