You are given a string str. It costs one unit of a coin to change a character at an index. Your task is to convert it into a palindrome with minimum coins. Also, you are given $q$ number of queries. The queries are of the following types:

• 1 A B
• 2

After solving the first type of query, you can convert character $A$ into character $B$ without any cost and vice versa. In the second type of query, you are required to answer the minimum cost that is required to convert the given string into a palindrome.

Note: If character $A$ can be converted to character $B$ and character $B$ can be converted to character $C$, then you can convert character $A$ to character $C$.

Input format

• The first line contains $n$ denoting the length of the string.
• The second line contains string str.
• The third line contains $q$ that denotes the number of queries.
• The next $q$ lines contain one of the mentioned queries.

Output format

For each query of type 2, print the minimum cost to convert a given string into a palindrome.

Constraints

$1 \le n \le 10^5$

$1 \le q \le 10^5$

The string consists of only lowercase letters.