F. Semi Palindrome
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdelaleem, while working on his problem set, has exhausted all his ideas and couldn't come up with more problems. Consequently, he is seeking help from his friend Salah. However, Salah insists that his problems are typically somewhat difficult and may not suit the community's level. Despite this, Abdelaleem tries to convince him that the community at Shorouk Academy is improving and has some talented individuals. Thus, he challenges Salah that there are people who can solve his problems. Salah, wishing for the improvement of the community's skill level, agrees not to propose a difficult problem and suggests a moderately challenging one instead.

The proposed problem is as follows:

You are given a string $$$s$$$ consisting of lowercase English letters with size $$$n$$$. Additionally, there are some queries on this string:

1. $$$i, c$$$ $$$( 1 \leq i \leq n )$$$ - You are asked to change the $$$i$$$-th character in the string $$$s$$$ to $$$c$$$.

2. $$$l, r$$$ $$$( 1 \leq l \leq r \leq n )$$$ - You are given a range and asked if it is possible to change at most one character within this range to make it a palindrome. If you can achieve this, print "YES"; otherwise, print "NO".

Can you solve this problem, or will it lead to Abdelaleem's frustration and Salah's mockery?

Input

The first line contains integer $$$T$$$ the number of test cases.

For each test case:

The first line of each test case contains the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains a string $$$s$$$ with lowercase English letters.

The third line contains $$$q$$$ ($$$1\leq q \leq 10^5$$$).

Then $$$q$$$ lines each line one of two types of queries:

  1. $$$i, c$$$ $$$( 1 \leq i \leq n )$$$ - You are asked to change the $$$i$$$-th character in the string $$$s$$$ to $$$c$$$.
  2. $$$l, r$$$ $$$( 1 \leq l \leq r \leq n )$$$ - You are given a range and asked if it is possible to change at most one character within this range to make it a palindrome.
Output

For each test case output for each type $$$2$$$ query "YES" or "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as positive answers.

Examples
Input
1
10
madamrasha
7
2 1 5
2 4 7
1 6 a
2 6 10
2 3 6
1 2 s
2 2 8
Output
YES
YES
YES
NO
YES
Input
1
6
zvaoqb
4
2 3 6
2 1 5
1 3 n
2 5 6
Output
NO
NO
YES