You are given a $$$^\dagger $$$ bracket sequence $$$S$$$.

You can do the following operation any number of times(possibly zero):

• Choose an index $$$i$$$ $$$( 1 \leq i \leq |S| )$$$ such that $$$S_i$$$ = ')', then delete $$$S_i$$$ and insert it at any index $$$j$$$ $$$( 1 \le j \le i )$$$.

$$$^\dagger $$$ A bracket sequence is any non-empty sequence of opening and closing parentheses.

$$$^\ddagger $$$ A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, the sequences '(())()', '()' and '(()(()))' are correct, while the bracket sequences ')(', '(()' and '(()))(' are not correct.

The SCPC (Syrian Competitive Programming Contest) is getting closer. The Richard Fans decided to meet there, but they are in different houses far from each other, so choosing a house to meet in is not simple. You are given an array $$$P$$$ of length $$$N$$$ where $$$P_i$$$ denotes the position of the $$$i_{th}$$$ person's house.

They want to choose the best place such that they all walk as few as possible. Formally, they want a house that minimizes the total distance for all of them. They gave you their house positions to help them choose the best meeting point among these houses.

We denote the distance between two houses $$$i,j$$$ as $$$|P_i-P_j|$$$.

Here, $$$|X|$$$ denotes the absolute value of $$$X$$$, for example $$$|-10| = 10$$$, $$$|5| = 5$$$

You need to find and print the best house $$$P_i$$$ that minimizes the total distance for all fans.

Two players are playing a game with a pile of $$$N$$$ stones. The rules of the game are as follows:

• The players take turns alternately.
• In each move, the current player must remove a positive number of stones from the pile.
• The number of stones that can be removed must be strictly less than the most significant bit $$$^\dagger$$$(MSB) of the remaining pile size.

The player who cannot make a move loses the game. Determine the winner if both players play optimally.

$$$^\dagger$$$The most significant bit (MSB) is the value of the highest position that has a $$$1$$$ in the binary representation. For example, for $$$13_{10}=1101_{2}$$$, the most significant bit is $$$8_{10}=1000_2$$$

Finally, it's Tuesday, the day of the big contest (Div. 1). Bassam's rating is near 2100, so as a preparation, Bassam is going to buy his favorite drink, "3 in 1". He got everything set up and sat at his desk waiting for the contest to start. He solved the first problem, the second, the third—Bassam was on a roll! But suddenly, he spilled his drink all over the keyboard. Thankfully, the keyboard kept working, and Bassam continued his contest. After he finished, he went to chat with his friend Jamal, but to his surprise, the question mark key didn't work in English; when pressed, it printed the sentince "Ba3d Khamsa". So Bassam was stuck typing every question ending in "Ba3d Khamsa".

After all that, Jamal found a magical way to repair the keyboard. Now, Bassam always has a string $$$S$$$. Jamal considers a string $$$S$$$ magical if none of its substrings of length at least $$$2$$$ is a palindrome.

A palindrome is a string that reads the same backward as forward, for example strings 'z', 'aaa', 'aba', 'abccba' are palindromes, but strings 'codeforces', 'reality', 'ab' are not.

Bassam can perform this operation any number of times (possibly zero):

• Choose an index $$$i$$$ and change the character $$$S_i$$$ to any other English letter.

Now, you are given a string $$$S$$$ of size $$$N$$$ and $$$Q$$$ queries. For each query, you are given $$$L, R$$$ ($$$1 \le L \le R \le N$$$), and you should print the minimum number of operations required to make the substring $$$S[L:R]$$$ a magical string.

Note: The operations are hypothetical and do not change the original string $$$S$$$. You only need to compute the number of operations for each query.

One day, Sasha received a mysterious box containing two bracelets.

• The first bracelet was filled with letters, but unfortunately, they were arranged in a completely random order. This disorder greatly annoyed Sasha.
• The second bracelet was empty and special it was fixed on the left side.

Sasha loves playing with letters, and she decided to use her wisdom to rearrange them. Her goal was to form the $$$^\dagger$$$lexicographically minimal $$$^\ddagger$$$palindrome possible on the second bracelet.

To achieve this, she must transfer all the letters from the first bracelet to the second one. Since the second bracelet is fixed on the left, she can only add letters to its right end.

The process works as follows:

1. Take a letter from either the beginning or the end of the first bracelet.
2. Insert this letter at the end of the second bracelet.

Your task is to help Sasha determine: If it is possible to form a palindrome on the second bracelet, print the lexicographically minimal palindrome string. Otherwise, print -1.

$$$^\dagger$$$ String $$$x$$$ is lexicographically less than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x \neq y$$$), or there exists such $$$i$$$ ($$$1 \le i \le \min(|x|, |y|)$$$), that $$$x_i \lt y_i$$$, and for any $$$j$$$ $$$(1 \le j \lt i)$$$ $$$x_j = y_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$.

$$$^\ddagger$$$ A palindrome is a string that reads the same backward as forward, for example strings 'z', 'aaa', 'aba', 'abccba' are palindromes, but strings 'codeforces', 'reality', 'ab' are not.

As we are in this contest, Top Syrian teams who qualified last year to ICPC World Finals 2025 are competing live at this moment in the ICPCs.

In the name of all the judges and every Syrian contestant, we wish them Good Luck and we hope they all get medals and region champion award, maybe every other possible award as well.

Good Luck Homs University team! Good Luck Damascus University team! Good Luck Syrian Virtual University team!

Would you like to wish them Good Luck as well ?

You are given a city in the form of a cells grid of size $$$N \times M$$$. You are allowed to place $$$K$$$ fire stations at any cell on the grid $$$\bf{(at\ integer\ coordinates)}$$$.

Fire station fire fighter can move in $$$8$$$ directions (up, down, left, right, diagonals).

The distance from a station at cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$ is defined as:

• $$$distance = \max(|x_1 - x_2|, |y_1 - y_2|)$$$

You want to place the fire stations optimally so that every cell in the grid is within $$$distance \le d$$$ from at least one station. Your task is to find the smallest possible value of $$$d$$$ that guarantees full coverage.

Abdulghafour is a player who loves football. His friend Abo Al-Jood does too.

Every time they play, each one is on a different team. And of course, the team that Abo Al-Jood plays on always loses. But this time, Abdulghafour gave Abo Al-Jood a condition. He told him he must solve a task if he wants to be on the same team and win.

Help Abo Al-Jood solve the task so he can play on the winning team.

You are given an array $$$A$$$ of $$$N$$$ integers. Also, you are given $$$Q$$$ queries, there are two types of queries:

1. Update Query: '$$$1$$$ $$$i$$$ $$$val$$$' Update the element at position $$$i$$$ to $$$val$$$; $$$A_i \gets$$$ $$$val$$$.
2. Find Query: '$$$2$$$ $$$i$$$' Find any position $$$j$$$ in the array such that $$$|(i - j)^3| \ge A_j$$$

For a find query, If such a position $$$j$$$ exists, print any valid $$$j$$$. If no such position exists, print -1.

There are $$$10$$$ judges: Bassam, Abdulghafour, Maysan, Aboljood, Nawar, Jamal, Hassan, Amjad, Aysha, and Rama.

They have already agreed on $$$11$$$ problems for a contest and $$$10$$$ extra problems : $$$9$$$ of them are extra easy, and one of them is the hardest, which you are reading now.

However, even the contest problem list is already full, they decided to add one extra problem to these $$$11$$$ problems.

There are $$$10$$$ problems to choose from, the problems were numbered from 1 to 10 to decide which problem to add, Abo-Alcode gives each judge a paper on which they write the number of the problem he/she wants to be added $$$[1,2,...,10]$$$.

Each judge selects a problem, and writes a number (from $$$1$$$ to $$$10$$$) on her/his paper.

The last problem will be selected as follows:

• The problem number that appears most frequently among the problems numbers that have been written will be added to the contest.
• If there is a tie between multiple problems with the same maximum frequency, the one with the largest number (maybe the hardest) among them will be chosen.

Which problem number was added to the contest?

Finally, the electricity is back on and will last for $$$H$$$ hours before it goes out again. You have clothes to wash. You have $$$N$$$ different colors of clothes. For each color $$$i$$$, an integer $$$A_i$$$ represents the number of items of that color.

You have a washing machine. In each washing cycle (which takes one hour), you can wash:

• At most $$$P$$$ different colors of clothes.
• For each color, at most $$$K$$$ items.

Can you determine the minimum number $$$P$$$ that will allow you to wash all the clothes before the power goes out? If it is impossible, output $$$-1$$$.

Hassan and his friend Naya are nerds at math and are always fighting about who is better, as they are in the same class. One day their coach Bassam decided to give them an array $$$A$$$ of size $$$N$$$ and they will play the following game alternately for $$$N-1$$$ rounds.

Naya plays first, at each round a player takes any two elements $$$X$$$, $$$Y$$$ from the array, erases them, then adds $$$\gcd(X,Y)$$$ to the end of $$$A$$$. It can be shown that after $$$N-1$$$ rounds $$$A$$$ will have only one element.

For example, let $$$A=[3,8,5,12,1]$$$, if a player chooses $$$8$$$ and $$$12$$$, then $$$A$$$ becomes $$$[3,5,1,4]$$$.

Naya wins if at the end of the game $$$A=[1]$$$, otherwise Hassan wins. Your task is to find the winner of the game, knowing that both players play optimally.

Here, $$$\gcd(X,Y)$$$ denotes the greatest common divisor for $$$X$$$ and $$$Y$$$, for example $$$\gcd(12,8)=4$$$ and $$$\gcd(15,14)=1$$$.

You have an equilateral triangle with a height of $$$H$$$. You'll perform $$$K$$$ operations on it, in each operation the following is performed:

1. Divide the triangle into four equilateral triangles, as shown in the figure below.
2. Then, take the triangle in the middle and discard the rest.

dividing to 4 equal triangles

Now, you're interested in finding the area of the triangle after $$$K$$$ steps. Can you do that?