"Guys!!! Omda is coming in 5 minutes" said the battle's organizer. Till then let us tell you some things about this contest:

• First, This contest has only one setter who came up with all the problems.
• Second, This contest's theme is Nesr El Scene.
• Third, If you don't enjoy this contest we hope you at least enjoy the jokes.
• The fourth was scored by Origi.
• fifth fifth fifth fifth fifth.
• The answer to this problem is "Yes" if there exists a string consisting of lowercase English letters of size $$$N$$$ (input) with no palindromic subsequences of size $$$2$$$ or more otherwise, the answer is "No".

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

"I'll call him Hanya" said Omda.

Omda in one of his amazing punchlines tried to call his opponent Hanya. However, It backfired because his aunt's name is Hanya and as we all know Omda's aunt is dead.

Hanya was a working aunt. She delivered packages to people everywhere. However, she didn't like to turn around a lot ... it hurts her back.

Let's represent the world as a number line. Initially, Hanya's on point $$$0$$$ with no direction set for her.

In one move, she can either set a direction or move in that direction (of course, the direction needs to be set first).

Given $$$N$$$ packages where the $$$i^{th}$$$ package needs to be delivered to point $$$A_{i}$$$, What's the minimum number of times Hanya needs to set a direction to deliver all packages in any order if Hanya can carry all packages at once?

"I found Donald Duck, Micky Mouse, and Minnie Mouse. What are you doing? We're not in Disney Land" said Omda.

There was an invasion of Sasa's studio by Disney characters. Help us, God!!.

Moda wanted to find out the order in which the characters entered the studio so that, he could hunt them down.

Disney characters are represented by a permutation of $$$N$$$ integers.

A permutation is an array consisting of $$$N$$$ distinct integers from $$$1$$$ to $$$N$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$N=3$$$ but there is $$$4$$$ in the array)

Additionally, you are given $$$M$$$ restrictions. You want to recover the lexicographically smallest permutation under those restrictions or report that there isn't any valid permutation.

The $$$i^{th}$$$ restriction says that $$$P_{X_i} \neq Y_i$$$.

Please help Moda recover the permutation of Disney characters.

"I was going with a "Do", but I think you guys are going for a "Tak"" said Teemo.

Teemo and Omda are playing Do and Tak Game.

The rules of Do and Tak are simple. Just stand in a circle and $$$\dots$$$ Oh wait wrong game.

Initially, We have $$$N \times K$$$ chips. A player can make one of two moves :

• Use a Do, i.e remove $$$K$$$ chips. You can only use a Do if the current number of chips is $$$\ge K$$$
• Use a Tak, i.e remove $$$1$$$ chip.

The one who removes all chips first wins. If Omda starts playing, can you figure out who will win this game?

"I'm not done yet. I'm not done yet. I'm not done yet." said Omda.

We want Omda to be done with Battle rap.

Let's define the map as a 2D plane with $$$N$$$ integer points on it. These points are the positions of rappers.

For Omda to be done with Battle Rap he needs to choose one point and then defeat some number of rappers and remove their points from the map.

Omda becomes done with Battle rap when his point becomes a part of the plane's Convex Hull's perimeter.

You want Omda to be done. So you decided to calculate for each point the minimum number of rappers he needs to defeat, such that this point becomes a part of the plane's Convex Hull's perimeter.

A convex hull is a shape of the minimum area that contains all points on the plane.

"I graduated from Engineering Ain Shams University" - said Omda.

As we all know engineers are the third known gender in Egypt. As an engineer, Omda was trying to add a little engineering to his sick rhymes by getting the greatest common divisor of two rap tracks $$$A$$$ and $$$B$$$.

A rap track is a string consisting of lowercase English letters.

A divisor of a track $$$S$$$ is another $$$T$$$ such that $$$T$$$ can be concatenated some number of times to make $$$S$$$.

More formally $$$T$$$ is a divisor of $$$S$$$ if $$$T_1+T_2+T_3+\dots+T_{\frac{|S|}{|T|}} = S$$$ where $$$T_i = T_{i-1}$$$

The greater of the two divisors is the one with a bigger length.

Help Omda find the greatest common divisor of tracks $$$A$$$ and $$$B$$$.

It's guaranteed that there's always a solution.

"From your blood I drink, Milk" said Omda.

We all know that good rappers drink milk every day.

Omda was trying to walk on the beat same as he does every day.

Initially, Omda is standing on point $$$0$$$ on the beat. Each moment he'd do one of three operations:

• Build the beat by using his rap skills and move from point $$$i$$$ to point $$$i+1$$$.
• He gets some beats from the beat and moves from point $$$i$$$ to point $$$i-1$$$.
• He stands at point $$$i$$$ drinking his milk.

Badran was taking pics of Omda while he was doing this greatness. So he took $$$N$$$ pics the $$$i-th$$$ pic Omda was standing at point $$$A_i$$$.

Badran will ask you $$$Q$$$ questions, each question is in the form of $$$U_i$$$ and $$$V_i$$$ and goes like this, Are you sure that Omda went to point $$$U_i$$$ and then went to point $$$V_i$$$?

More formally, according to the above rules are there some two points in time $$$A \leq B$$$ were at $$$A$$$ Omda was standing at $$$U_i$$$ and at $$$B$$$ Omda was standing at $$$V_i$$$?

"Tell him we're going to Alexandria Library today and tomorrow we go to Marwan" said Omda.

Omda is using his car to go to his fellow rappers in Cairo to make feats that will eventually become hits and show us his talent.

Cairo is a connected acyclic graph of $$$N$$$ nodes and $$$N - 1$$$ bidirectional unweighted edges, i.e a tree.

Omda wants to play a game with you.

Let's define $$$dist(X, Y)$$$ as the shortest distance between $$$X$$$ and $$$Y$$$

He's going to give him $$$Q$$$ queries each query consists of 2 nodes $$$U$$$ and $$$V$$$ and he wants you to find out the number of nodes $$$K$$$ where $$$dist(U, K) = dist(V, K)$$$.

The point of this query is to find out at the $$$i^{th}$$$ moment for those two nodes what common cities will people come from to kill listen to Omda's singing.

"Wigz is here" said Badran.

Omda wants to make a feature with Wigz. However, Wigz has a condition for them to make a feat.

Omda needs to pick some Wigz for Wigz to wear.

Given a carton of Wigz represented by a grid of $$$N$$$ rows and $$$M$$$ columns where the Wig at row $$$i$$$ and column $$$j$$$ has a value $$$G_{i,j}$$$.

Omda has an integer $$$K$$$ he needs to choose a set of rows $$$R$$$ and a set of columns $$$C$$$ such that $$$|R| + |C| \leq K$$$ and $$$ \sum_{i \in R \space or \space j \in C} G_{i,j} $$$ is maximum.

Can you get help Omda to get the maximum sum for the above problem?

"There's no difference" said Hanz.

As we all know, Hobz is a hundred-faced person. Damn, With all these hundered-faced people I miss two-faced people.

However, thank god today we will only be dealing with $$$N$$$ two-faced copies of Hobz. The $$$i-th$$$ Hobz has value $$$A_i$$$ on the first face and value $$$B_i$$$ on the second face.

Now let's calculate their Salkan. Salkan is the Xor of values on their faces.

Now Hobz has a plan to deceive us. Because we all know he has $$$0$$$ Salkan. He will choose which face each of his copies will show so that their Salkan is maximum.

However, Hanz knows about Hobz's plan. So he decided to place a parameter $$$K$$$.

If Hobz's copies output Salkan $$$ \gt K$$$ Hanz will be sure that Hobz is playing them. Then Hobz's Salkan Becomes $$$0$$$.

Do you know what value Hobz will print if he wants his Salkan to be maximum?

"I swear to god if what I am thinking is true. I will $$$010101010100011$$$ And $$$01010100001111$$$" said Modda.

Modda can rap in binary. As we all know to rap in binary the string must be non-empty and have the number of ones in even positions equal to the number of ones in odd positions.

Now Modda asks you if you can remove some number of characters from the given binary string $$$S$$$ so that you can use it in rap.

If I were you, I'd answer his question quickly. You don't want to know what happened to Hobz.