Two types of queries
/

## Data Structures, Disjoint Data Structures

Problem
Editorial
Analytics

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.

SAMPLE INPUT
10
vwuhjdbgzp
4
1 a b
2
1 w z
2
SAMPLE OUTPUT
5
4
Explanation

After the first query, a can be converted to b.

In the second query, all the pairs cost 1 unit for making the palindrome.

After the third query, w can be converted into z or vice-versa with zero cost.

In the fourth query, since z can be converted to w in 0 cost, total cost is equal to 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...