The chocolate guessing game proceeds as follows:

First, an $N \times N$ square frame and several types of chocolates are prepared, and one chocolate is placed in each cell of the frame. Each type of chocolate can be represented by a single uppercase English letter.

Next, the sequence of movements for the chocolate frame is written down on paper. The methods for moving the frame are: rotating $90$ degrees clockwise (R), rotating $90$ degrees counter-clockwise (L), flipping horizontally (H), and flipping vertically (V). This sequence of commands can be represented as a string $S$ of length $M$.

Once these two are prepared, one person calls out two integers $r$ and $c$. The other person must guess the type of chocolate located at row $r$, column $c$ after the chocolate frame has been moved according to $S$.

(todo: Add example explanation with figures)

Coco has built a robot that guesses the type of chocolate for her. In response, Hanbyeol has built a robot that can change all commands from the $l$-th to the $r$-th position in $S$ to a command $x$. Let's create a new program so that Coco's robot can defeat Hanbyeol's robot.

Input

The first line contains an integer $N$. $(1 \le N \le 1\,000)$

The next $N$ lines describe the state of the chocolate frame. Each line contains $N$ uppercase English letters without spaces.

The next line contains an integer $M$. $(1 \le M \le 500\,000)$

The next line contains the sequence of commands $S$ for moving the chocolate frame, given as a string of length $M$ consisting only of R, L, H, and V, without spaces.

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

The following $Q$ lines each contain a query. The types of queries are as follows:

• 1 r c: Output the type of chocolate at row $r$, column $c$ when the chocolate frame is moved according to the current $S$. $(1 \le r, c \le N)$
• 2 l r x: Let $S_i$ be the $i$-th command of $S$. Change $S_i$ to $x$ for all integers $i$ such that $l \le i \le r$. $(1 \le l \le r \le M;$ $x$ is one of R, L, H, V$)$

There is at least one type 1 query.

Output

For each type 1 query, output the answer on a new line.

Examples

Input 1

3
ABC
DEF
GHI
4
RHLV
4
1 1 1
2 3 4 R
2 2 3 L
1 3 3

Output 1

A
I