You are given two strings and consist of lowercase letters. The length of and are both .

You have to perform queries. Each query has one of three types:

• - change to ( is a lowercase letter).
• - change each to the next character in lexicographic order. For example, change the letter to , to , ... , to .
• - calculate the length of the longest common prefix of two strings and .

Definition of the length of the longest common prefix: For two strings and , the length of the longest common prefix is the max index , so that .

输入描述:

The first line contains two integers  and  — the length of two strings and the number of queries.
The second line and third line contain two strings  and  of length  .
Next  lines contain queries (one per line), each query has one of three types described above.
It is guaranteed that there is at least one query of the third type.

输出描述:

For each third type of query, output an integer representing the length of the longest common prefix of strings  and  .

6 5
aazaaa
abcbaa
3
2 2 4
3
1 3 c
3

1
2
6