PLNDROME - Palindrome Or Not


It's English class now. So John is bored as usual. To get over his boredom he is doing a very strange thing. He writes an arbitrary string on his notebook and then keeps changing a single character of the string every time and tries to find out if the string has become a palindrome.

As John is very smart this task is very simple for him.

But how simple is it for you? Can you be as smart as the great John?

You'll have to write a code that solves the similar problem and hopefully, as fast as John.

Input

First line of the input will be an integer T (T <= 15) denoting number of test cases.

Each test case starts with an integer N (1 <= N <= 100000) denoting the length of the string.

Next line will contain the string consisting of only small letters of English alphabet (a,b,c,...,x,y,z).

Then there will be another integer M (1 <= M <= 10000) denoting number of queries.

Each query will be in the form: i x, where i will be an integer (1 <= i <= N) and x will be a character, (a <= x <= z) and it will mean that the i-th character of the string has been changed to x.

Output

First you will have to print the test case number.

Then for each query in the test case you will have to print "YES" if the given string has become a palindrome. Otherwise print "NO" (without the quotes.)

See sample input/output and explanation for details.

Sample

Input
1
11
madamimadam
6
6 z
1 a
11 b
5 z
1 b
7 z

Input
Case 1:
YES
NO
NO
NO
NO
YES

Explanation:

After the 1st query the string is: madamzmadam, which is a palindrome

After the 2nd query the string is: aadamzmadam, which is NOT a palindrome

After the 3rd query the string is: aadamzmadab, which is NOT a palindrome

After the 4th query the string is: aadazzmadab, which is NOT a palindrome

After the 5th query the string is: badazzmadab, which is NOT a palindrome

After the 6th query the string is: badazzzadab, which is a palindrome


hide comments
wisnupramoedya: 2020-03-18 13:52:25

Search for an hour and look at the output that said to print "Case %d:". After add it, I've got AC. Lol.

Nemanja Stojanovic: 2016-11-08 19:25:03

Can you take a look at submission 18134735? I just loop once through the string and it works for all examples for me and it should be fast enough?

sush_75: 2016-09-17 18:57:02

Just keep the count of differences in the characters and use that

akshayvenkat: 2016-09-16 17:31:36

My respects, sir! Great question :D AC after 9 months

nehae: 2016-09-02 22:47:31

No idea why m i gtn tle .
If possible please check Submission id 17595638 !
any piece of advice for optimising the code!?

setsuda: 2016-08-20 20:22:45

In C++, is using std::reverse too slow? 0.100s is a rather strict time limit. My submission ID is 17548321, I need help optimizing so I can deal with TLE.

Admin Deepak Baghel: 2016-06-15 23:18:56

use scanf, printf.

Last edit: 2016-06-15 23:45:52
chalarangelo: 2016-03-19 13:35:53

Is python 3 too slow for this? Anyone got any ideas as to how to optimize my code as I am getting TLE right now?

Md. Najim Ahmed: 2016-02-02 12:10:22

thelazycoder: Your code should get a TLE not WA ... its been fixed ...

thelazycoder: 2016-01-27 14:59:49

No idea why i am getting WA . Can you check Submission id 16171756 please ?

Last edit: 2016-01-29 12:59:20

Added by:Md. Najim Ahmed
Date:2015-12-05
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY