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.