Those of you who use Java (or are subscribed to SecondThread) likely know that calling Arrays.sort() on an array of primitives in Java can lead to TLE verdicts on Codeforces contests because there are some very specific cases in which quicksort runs in $$$n^2$$$ time. There are a couple solutions to this: one is to use Collections.sort() on an ArrayList. This uses mergesort and is always $$$n*log(n)$$$.

Another solution is to shandomly ruffle [aka randomly shuffle] the array before sorting so that it is very very very unlikely that it is still in some undesirable order. One way of doing this is to do the following:

shandom_ruffle(int a, int b, int[] array) {
  int bStart=b;
  while (a<bStart && b<=array.length) {
    swap(array[a], array[b]); //swap the values at indecies a and b
    a++;
    b++;
  }
}

In Java and the psuedocode above, arrays are pass-by-reference. Suppose David starts with the array $$$[1, 2, 3, 4, ... n]$$$, and calls this method $$$n$$$ times on the array, the ith time passing in $$$a_i$$$ and $$$b_i$$$. What will the array look like after these $$$n$$$ method calls?

Have you ever heard of an eer-tree? It is a very special tree that does super cool stuff with palindromes. As you would expect of such a structure, the word eer-tree is a palindrome itself. Even cooler, if we do the same thing with a treap, we get a Pear Treap! What an epic palindrome!

What's that I hear? "Pear Treap isn't actually a palindrome," you say? Nonsense! I always write a and e together as one character, so it is totally a palindrome. Anyhow, here's your palindromic treap problem, as promised:

You have a string initially containing $$$n$$$ lowercase characters. Please perform the $$$q$$$ operations (that is, please solve each query before reading the next one) of the following types:

1. Delete all characters from position $$$l$$$ to position $$$r$$$ inclusive.

2. Insert the character $$$c$$$ at position $$$p$$$. After this query, the character at position $$$p$$$ will be $$$c$$$, and all characters initially with indecies $$$\geq p$$$ will be moved one space to the right.

3. Is the substring from position $$$l$$$ to position $$$r$$$ a palindrome? A substring from $$$l$$$ to $$$r$$$ is the continuous block of characters starting at position $$$l$$$, ending at position $$$r$$$.

The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $$$i$$$th sneetch has $$$a_i$$$ stars on his belly ($$$0 \leq a_i \leq 1$$$). Just like normal, many [$$$l...r$$$] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between $$$l$$$ and $$$r$$$ inclusive, the sneetch at that position will have a star on his belly after if and only if he didn't have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right?

But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things $$$q$$$ times:

1. Do the usual operation: make the sneetches in positions $$$[l..r]$$$ go through the machine. $$$l \leq r$$$

2. Talk to sneetches $$$[l..r]$$$ and convince them to reverse their order. After moving, the sneetches are relabeled $$$1$$$ to $$$n$$$ from left to right.

3. Sort the range of sneetches $$$[l..r]$$$ by the number of stars on their bellies, in nondecreasing order.

After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly.

Happy Halloween! Farmer John is rather weary: he has lots of harvesting still unfinished, and his Deere sweet tractor just broke down, so he must finish the harvesting with nothing more than his scythe. He is rather depressed knowing the total amount of harvesting he has left. To make things even worse, Bessie and friends don't know how to use a toilet, so they keep leaving... fertilizer... all over the grass, causing the wheat to grow even more! So much reaping of wheat needs to be done! How grim!

Initially, FJ has $$$n$$$ blades of grass numbered $$$1..n$$$ in a row. Initially blade $$$i$$$ has height $$$a_i$$$. $$$q$$$ times, one of the following will happen:

1. FJ will slice his scythe from $$$l$$$ to $$$r$$$ at height $$$h$$$, cutting all blades from $$$l$$$ to $$$r$$$ that are strictly longer than height $$$h$$$ to height $$$h$$$.

2. FJ will transplant range $$$l..r$$$ of his field to the end of the field. He will move all grass blades forwards so, in total, positions $$$1..n$$$ are still occupied after this operation.

3. Bessie and friends will take a dump on blades of grass from $$$l$$$ to $$$r$$$. Each of them will grow by $$$x$$$ units where $$$x$$$ is the stinkiness of the... fertilizer.

After each operation, Farmer John needs to know how much work he has left to do. In particular, he would like to know the sum of heights of all blades of grass.

Note: In this version of the problem, queries of type 3 will not appear.

The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $$$i$$$th sneetch has $$$a_i$$$ stars on his belly ($$$0 \leq a_i \leq 1$$$). Just like normal, many [$$$l...r$$$] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between $$$l$$$ and $$$r$$$ inclusive, the sneetch at that position will have a star on his belly after if and only if he didn't have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right?

But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things $$$q$$$ times:

1. Do the usual operation: make the sneetches in positions $$$[l..r]$$$ go through the machine. $$$l \leq r$$$

2. Talk to sneetches $$$[l..r]$$$ and convince them to reverse their order. After moving, the sneetches are relabeled $$$1$$$ to $$$n$$$ from left to right.

3. Queries of type 3 do not appear in this version.

After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly.

The only difference between this problem and the other two is that this problem ONLY HAS QUERIES OF TYPE 1!

The sneetches are back on the beaches, with the great Sylvester McMonkey McBean! The $$$i$$$th sneetch has $$$a_i$$$ stars on his belly ($$$0 \leq a_i \leq 1$$$). Just like normal, many [$$$l...r$$$] ranges of sneetches will go through Sylvesters xor-with-1-inator. Formally, after an operation, for all positions between $$$l$$$ and $$$r$$$ inclusive, the sneetch at that position will have a star on his belly after if and only if he didn't have a star on his belly immediately before walking through the machine. You need to know the largest continuous range of sneetches that all have the same type of belly at each step. Easy stuff, right?

But wait! There is a very important detail still unaddressed: we are on a beach! And the great orator Demosthenes practices his speeches on a beach. Demosthenes is giving an inspiring speech which may at times incite the following behavior, doing one of the three things $$$q$$$ times:

1. Do the usual operation: make the sneetches in positions $$$[l..r]$$$ go through the machine. $$$l \leq r$$$

2. Queries of type 2 will not appear in this problem.

3. Queries of type 3 will not appear either.

After each operation, Sylvester needs you to report the size of the largest continuous range of sneetches that have the same number of stars on their belly.

Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in their houses, and ask for candy.

Alice and Bob just solved a problem that required them to eat about $$$10^9$$$ candies and are very full now, so instead, they will ask their neighbors to either show them a trick, or give them a brand new treap ("trick or treap")! $$$q$$$ times, one of the following will happen:

- 1. This neighbor will given them a new treap node $$$i$$$, with value $$$y$$$. Here, $$$i$$$ is the query number.

- 2. This neighbor will perform a trick: if the nodes $$$y$$$ and $$$z$$$ are not in the same group, he will merge them into the same group, with $$$y$$$'s group to the left of $$$z$$$'s group. Otherwise, he will teach them how to juggle.

- 3. This neighbor will perform a different trick: If the group containing node $$$y$$$ contains more than $$$z$$$ nodes, he will split the first $$$z$$$ nodes from the rest of them. Otherwise, he will teach them Kotlin.

- 4. Alice's and Bob's overprotective mother will call and ask them about the sum of values in the group that $$$y$$$ is in.

Can you write a bot to pretend to answer the queries for Alice so that she can continue to bother her neighbors in the middle of the night without interruption?