D. a, ab, ba Strings
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a string $$$S$$$ of length $$$n$$$, consisting of the characters 'a' and 'b', and $$$q$$$ queries. There are two types of queries:

  1. replace the $$$i$$$-th character with the opposite one (that is, 'a' is changed to 'b', and 'b' is changed to 'a').
  2. check if it is possible to split the substring from the $$$l$$$-th to the $$$r$$$-th character into substrings 'a', 'ab', and 'ba'.

For each query of the second type, output the response to the query.

Input

The first line contains a single number $$$n$$$ — the length of the string ($$$1 \le n \le 100\,000$$$).

The second line contains the string $$$S$$$ itself, consisting of the characters 'a' and 'b'.

The third line contains the number $$$q$$$ — the number of queries ($$$1 \le q \le 100\,000$$$).

Each of the following $$$q$$$ lines starts with an integer $$$type$$$ — the type of query ($$$1 \le type \le 2$$$).

In the first type of queries, an integer $$$i$$$ follows ($$$1 \le i \le n$$$).

In the second type of queries, a pair of integers $$$l$$$, $$$r$$$ follows ($$$1 \le l \le r \le n$$$).

Output

For each second type of query, print 'YES' if the string can be split as described in the condition, and 'NO' otherwise.

Example
Input
7
abbabba
4
2 3 4
2 3 5
1 6
2 3 7
Output
YES
NO
YES
Note

In the first example, the substring from the first query can be represented as 'ba', the substring from the second query 'bab' cannot be split into valid substrings, after the third query the string looks like 'abbabaa', the substring from the fourth query can be split as follows: 'ba|ba|a'