B'Anya received a string s of length n brought from Rome. The string s consists of lowercase Latin letters and at first glance does not raise any suspicions. An instruction was attached to the string. Start of the instruction. A palindrome is a string that reads the same from left to right and right to left. For example, the strings "anna", "aboba", "level" are palindromes, while the strings "gorilla", "banan", "off" are not. A substring [l ldots r] of string s is a string s_l s_{l+1} ldots s_{r-1} s_r . For example, the substring [4 ldots 6] of the string "generation" is the string "era". A string is called beautiful if it does not contain a substring of length at least two that is a palindrome. For example, the strings "fox", "abcdef", and "yioy" are beautiful, while the strings "xyxx", "yikjkitrb" are not. When an integer x is added to the character s_i , it is replaced x times with the next character in the alphabet, with "z" being replaced by "a". When an integer x is added to the substring [l, r] of string s , it becomes the string s_1 s_2 ldots s_{l-1} (s_l + x) (s_{l+1} + x) ldots (s_{r-1} + x) (s_r + x) s_{r+1} ldots s_n . For example, when the substring [2, 4] of the string "abazaba" is added with the number 6 , the resulting string is "ahgfaba". End of the instruction. After reading the instruction, Anya resigned herself to the fact that she has to answer m queries. The queries can be of two types: The first line contains an integer t ( 1 <= t <= 10^4 ) - the number of test cases. The descriptions of the test cases follow. The first line of each test case contains two integers n and m ( 1 <= n, m <= 2 cdot 10^5 ) - the length of the string s and the number of queries. The second line of each test case contains the string s of length n , consisting of lowercase Latin letters. The next m lines c'...