E. Adnan and the Burned drivers
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Adnan is training the ARC team in NCD, but he wants to challenge them, so he started burning their drivers.

The team has $$$N$$$ drivers. Each driver has a lowercase Latin letter written on it. A segment of drivers from $$$L$$$ to $$$R$$$ can be used to move the robot if this segment is palindrome. When Adnan burns a driver, he changes the letter to any other letter he wants.

A segment of letters is considered palindrome if it can be read the same way from right and left. For example, $$$aa$$$, $$$abcba$$$, and $$$mmm$$$ are palindromes. But $$$mma$$$ and $$$aama$$$ aren't.

You will be given $$$E$$$ events in order; these events are of two kinds:

$$$1$$$ $$$i$$$ $$$c$$$: Adnan will burn the $$$i_{th}$$$ driver to change its letter to the char $$$c$$$.

$$$2$$$ $$$l$$$ $$$r$$$: The ARC team will use the segment [$$$l$$$,$$$r$$$], print "Adnan Wins" if this segment is palindrome, and "ARCNCD!" otherwise.

Input

First line of input will be $$$T$$$, number of test cases

Each test case begins with two numbers $$$N, E$$$ the number of drivers, and the number of events.

Followed by a string of length $$$N$$$ consisting of only lowercase Latin letters.

Next $$$E$$$ lines contains $$$3$$$ space separated integers, the queries as described above.

$$$ 1 \le N, E \le 10^5$$$

It's guaranteed there is at least one query of the second type.

Output

For every query of the second type, print "Adnan Wins" or "ARCNCD!"

Example
Input
1
7 5
adaersd
1 5 a
2 3 5
2 1 6
1 1 d
2 1 2
Output
Adnan Wins
ARCNCD!
Adnan Wins