Migrated from Lutece 1944 Letter Kingdom

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

One day, you had a dream. In the dream, you got trapped in the Letter Kingdom. Two soldiers caught you, and brought you to the front of the king.

The king asked you: "Are you a programmer?"

You answered: "Yes."

The king said: Our Letter Kingdom is going to hold the $233^{rd}$ National Day ceremony, now we need to check our traffic network, and I appoint you to be the commander of this event. Our country has $n$ cities, numbered by the first $n$ uppercase letters, for example the first city named $A$, the second city named $B$, and so on. Due to the lack of money, every city only has one directed road to another city. The army will arrange for $m$ soldiers to walk between these cities. The soldiers are numbered from $1$ to $m$. I will tell you the initial position of each soldier, and then issue three types of orders:

1. Interval Move: Given two integers $l$ and $r$, the soldiers numbered between $[l, r]$ walk along the only directed road from the current city to another city (we'll call it $Moving\ Operation$).

2. Multiple Move: Given an integer $x$, the soldiers whose number is a multiple of $x$ ($id$ mod $x = 0$) do $Moving\ Operation$.

3. Commander Report: Given an integer $p$, please tell me which city the soldier numbered $p$ located in.

Since you are a smart person, can you complete this task?

Input

The first line consists of two integers $n$ and $m$, which represent the amounts of city and soldier.

The second line is a $n$-length string. The $i^{th}$ letter in the string represents the directed road's leading city from the $i^{th}$ city. It's guaranteed that the $i^{th}$ letter in the string differs from the $i^{th}$ letter in the alphabet, and the string only consists of uppercase letters.

The third line is a $m$-length string. The $i^{th}$ letter in the string represents the $i^{th}$ soldier's initial city. The string also only consists of uppercase letters.

The fourth line consists of an integer $q$, which represent the number of king's orders.

Following $q$ lines, the first part of the line is an integer $op$.

If $op = 1$, then input two integers $l$ and $r$, which represent the soldiers numbered between $[l,r]$ do $Moving\ Operation$.

If $op = 2$, then input an integer $x$, which represents the soldiers whose number is a multiple of $x$ do $Moving\ Operation$.

If $op = 3$, then input an integer $p$, you should output where the soldier numbered $p$ located in.

Its guaranteed there is at least one order that $op = 3$.

• $1 \leq n \leq 26$
• $1 \leq m \leq 200000$
• $1 \leq q \leq 200000$

Output

For each order that $op = 3$, output the position of the soldier.

Samples

5 6
DAEEA
AEDCBA
7
1 1 4
2 2
3 4
2 3
1 3 6
2 1
3 6

A
D

Resources

2018 Guangdong Collegiate Programming Contest