E. PalTree
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Wonderland offers a wide range of beautiful landscapes, one of them being the one from the jungle of palindromic trees. In this jungle there is a lot of diversification in terms of creatures, many of them being interested in solving problems with ... palindromes.

A problem which has been declared NP-complete in the jungle is the following one: you are given a 1-indexed lowercase string $$$S$$$ of length $$$N$$$ and $$$Q$$$ operations of four types. The operations are the following:

  1. You are given a number $$$K$$$ ($$$1 \leq K \leq 10^9$$$). Left-permute subsequently $$$K$$$ times the string $$$S$$$. (e.g. 'abcd' will become 'bcda' for $$$K=1$$$ and 'cdab' for $$$K=2$$$)
  2. You are given a number $$$K$$$ ($$$1 \leq K \leq 10^9$$$). Right-permute subsequently $$$K$$$ times the string $$$S$$$. (e.g. 'abcd' will become 'dabc' for $$$K=1$$$ and 'cdab' for $$$K=2$$$)
  3. You are given a position $$$P$$$ ($$$1 \leq P \leq N$$$) and a lowercase character $$$C$$$. The character on the $$$P$$$-th position from $$$S$$$ becomes $$$C$$$.
  4. You are given a position $$$P$$$ ($$$1 \leq P \leq N$$$). What is the length of the longest palindrome centered in $$$P$$$? Let's assume that the answer is $$$L$$$. If $$$L$$$ is odd, the position $$$P$$$ has to represent the unique center of the palindrome of length $$$L$$$ you found. However, if $$$L$$$ is even, position $$$P$$$ might represent any of the two possible centers of the palindrome of length $$$L$$$ you found.

Can you prove to the jungle that this problem is actually in P?

Input

The first line of the input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the length of $$$S$$$.

The second line of the input will contain the lowercase string $$$S$$$, having the length $$$N$$$.

The third line of the input will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), the number of operations.

The next $$$Q$$$ lines will contain a query of type $$$1$$$, $$$2$$$, $$$3$$$ or $$$4$$$. The format is as follows:

  • $$$1$$$ $$$K$$$
  • $$$2$$$ $$$K$$$
  • $$$3$$$ $$$P$$$ $$$C$$$
  • $$$4$$$ $$$P$$$
Output

The output will contain $$$Q_4$$$ lines, where $$$Q_4$$$ is the number of operations of type $$$4$$$. Each of these lines will contain an integer, the maximum length of the palindrome found.

Example
Input
5
xxxxu
15
2 5
1 2
3 4 y
2 9
1 8
2 3
3 5 m
4 3
4 5
4 2
4 4
3 4 r
2 5
2 6
3 4 a
Output
1
1
1
1