Rodingo "Cria", the god of Creation, has invited the demigods Renang and Wan to spend their break on Mount Olympus. The two of them love fruits, so they will visit the $$$t$$$ markets of this Greek region, known for their high-quality kakis, plantains and other delicacies.

When Renang and Wan enter a market, they visit each of the $$$n$$$ selling points inside this market and buy exactly one packet of fruits from each selling point. All sellers in the market sell their fruits in packets with different numbers of fruits which are sorted in increasing order on their tables.

After leaving the market, to satisfy a whim from Rodingo, Renang and Wan want to open their packets and distribute all their fruits between them in such a way that they are left with the same number of fruits each after the distribution.

However, none of our character is very good with calculations. Therefore, you must help them decide whether or not, for each visited market, they can or cannot accomplish Rodingo's whim.

Byakronos was organizing the first marathon contest. However, near the beginning of the competition, he realized that there weren't enough balloons!

Because of this, Byakronos sent Mori to get balloons from the MaratonUSP's carriage. Fortunately, Mori came across the shop of the God Helios, which sells 'quantum' balloons. So, Mori bought inflated balloons (to save time!) of $$$N$$$ colors, where $$$b_i$$$ balloons of color $$$i$$$ $$$(1 \leq i \leq N)$$$ were purchased.

When Mori loaded the balloons onto the truck, he realized that the carriage could hold a maximum of $$$S$$$ inflated balloons. Thus, Mori needs to deflate balloons so that there are at most $$$S$$$ inflated balloons left.

As the balloons are quantum, they only deflate if Mori looks at them. Furthermore, the inflated balloons follow the rules of radioactive decay, with a half-life of $$$1$$$ second. In other words, every $$$1$$$ second Mori looks at $$$x$$$ inflated balloons, $$$\left \lfloor \frac{x}{2} \right\rfloor$$$ will still be inflated at the end of that second.

Therefore, to deflate the balloons, Mori will choose a color $$$i$$$ every second and look at balloons of that color for exactly $$$1$$$ second (if Mori were to look at more than one color, he'd lose track!).

Clearly, looking at quantum balloons for too long is not healthy. So, Mori wonders, what is the minimum number of seconds needed for at most $$$S$$$ inflated balloons to remain?

The members of MaratonUSP were invited by the god Zeos to visit Mount Olympus. May, knowing about the legendary banquets that take place there, quickly agreed.

After a long stroll through the fields of Caieffes, the MaratonUSP members were invited to a banquet. However, to the surprise of almost everyone, the banquet consisted only of cheese balls and coxinhas! Secretly, Thilio, the finicky one, told the gods that this was the only food that MaratonUSP members liked, so he wouldn't have to deal with any ancient Greek food.

May was revolted because she hates coxinhas. The gods served the snacks on a table, organized in $$$n$$$ rows and $$$m$$$ columns. Since May still wants to visit more places before returning to IME, she doesn't have time to feast with her colleagues. She decided to go to the snack table and take all the snacks from a rectangular subsection of the table at once. To make it easier, she will select a rectangular subsection of the table (that is, a contiguous subset of rows and columns) and take all the snacks from this subsection. The following image shows some valid choices for the third test case.

Help May discover the maximum number of cheese balls she can take in this way without taking any coxinhas.

Henrique and Juliana are a sertanejo duo from Panteão Olímpico Lírico dos Imortais (POLI), which goal was to create divine music to honor the gods. The score of a divine music is a sequence of notes represented by only the numbers 0, 1 and 2. Also, it is such that the sum of every three consecutive numbers is equal to 3.

Nowadays, an old score of the famous duo was found, but some of its notes were blurred. Hence, Pedro, the musician, was commissioned to recover the original score. Pedro is afraid that this work may not be possible: it could exist more than one divine music score such that, if some of their notes were blurred, would be equal to the found score.

Tormented by that possibility, Pedro asks you to count the number of distinct divine music scores that could be the one originally written by the sertanejo duo. Notice that the answer to this question could be 0.

Otávio, the archaeologist, was about to enter the archaeological site where he is currently conducting his research when he was stopped by the sphinx known as Matheusphinx.

In order to pass and continue his research, Otávio would need to answer the sphinx's riddle. This time, Matheusphinx asked a simple question: 'What percentage of statistics are false?'

The question caught Otávio off guard, and he immediately answered '75%', which was completely incorrect. Fortunately, sphinxes work retroactively, meaning that if for some reason this answer becomes correct, the sphinx will grant passage to Otávio.

Otávio has spent his entire life studying archaeology, so he knows the exact number of true statistics $$$v$$$ and the number of false statistics $$$f$$$.

Another thing Otávio learned in his research is that proclaiming the phrase 'More than 75% of the statistics are false' counts as a statistic and changes the number of true or false statistics according to $$$v$$$ or $$$f$$$. If $$$\frac{f}{v + f} \gt 75\%$$$ and this phrase is proclaimed, it is true, and therefore the value of $$$v$$$ increases by $$$1$$$. Otherwise, the value of $$$f$$$ would increase by $$$1$$$.

Otávio needs to get back to work and has asked for your help to write a program that, given the number of true statistics $$$v$$$ and the number of false statistics $$$f$$$, shows him how many times the phrase 'More than 75% of the statistics are false' needs to be used so that exactly 75% of the statistics will then be false.

In the quest for adoration and ego enhancement, the gods of Olympus organize an election on Earth every 100 years to determine the most adored god by humans. In this edition, $$$m$$$ deities, including Byakronos, Marceloki, and Zeos, the favorites, are competing for the title. Only a few randomly selected individuals are invited to vote.

The prophet Kobus, a fervent follower of Zeos, is determined to secure his victory. She possesses privileged knowledge about the voters and knows exactly how many votes each god has received up to the moment. For the $$$i$$$-th god, she has information that they have received the partial quantity of votes $$$a_i$$$.

However, Kobus needs your help to determine the minimum quantity $$$t$$$ of votes she must purchase to ensure Zeos' victory. In other words, Zeos must have more votes than any other deity in the competition. It is important to note that Zeos is the first god on the list provided by Kobus and that when she buys a vote, it is taken from another god and transferred to Zeos.

The ancient and bustling city of Cnossos was renowned for its mysterious labyrinth, composed of a set of $$$N \times M$$$ square rooms arranged in an $$$N$$$ by $$$M$$$ grid. The rooms were named by an ordered pair $$$(A,B)$$$, where $$$A$$$ represented the row and $$$B$$$ represented the column in which the room was located. The entrance to the labyrinth was at position $$$(1,1)$$$.

In this city, there was a fearless adventurer named Gusteseu. He was known for his courage and skill in unraveling the most complex riddles.

One day, Gusteseu received an extraordinary mission: to explore the labyrinth and find a legendary treasure rumored to be hidden in its depths. However, there was a daunting challenge in Gusteseu's path. The labyrinth was inhabited by a creature feared by all: the mighty Maynotauro.

The Maynotauro, a creature with the body of a woman and the head of a bull, guarded the labyrinth's entrance and protected the path to the treasure. Its dwelling was known as the Maynotauro's room, located at position $$$(X,Y)$$$ in the labyrinth.

Determined to complete his mission, Gusteseu knew he had to avoid the Maynotauro's room. He understood that passing through that room would result in his capture and failure in the quest for the treasure.

Due to the unpleasant conditions within the labyrinth, Gusteseu aimed to reach the treasure room as efficiently as possible, passing through the fewest number of rooms. He disregarded any other ways of achieving this path.

With his sharp mind and expertise in competitive programming, Gusteseu decided to employ his skills to calculate the number of efficient ways to reach the treasure room, located at position $$$(N,M)$$$, without passing through the Maynotauro's room.

According to historical evidence, it is believed that in ancient Nlogonia, all citizens lived in peace and harmony, confident that they were protected from any enemy thanks to a powerful hero: Morethor. The god Hadesoko, known for his terrifying monsters, constantly sought to torment humanity, but our hero prevented his evil deeds. However, recent discoveries point to a period of darkness: after Morethor's encounter with the god Promethilio, our hero went missing for a long time, allowing Hadesoko to invade the lands of our ancestors. We know that Morethor reappeared at some point in the past and immediately began hunting the monsters sent by Hadesoko and facing them in the order they were encountered. However, despite the collected data, researchers have not yet been able to conclude whether Morethor defeated all the forces of evil or if he failed in his mission. Thus, they have asked for your help to evaluate the data and resolve this great doubt!

Given Morethor's ability $$$H$$$ right after his return, determine if he is capable of facing all $$$N$$$ monsters from Hadesoko. The $$$i$$$-th encountered monster has a strength $$$F_i$$$. Morethor faces only one monster at a time and is able to defeat it if his current ability is greater than or equal to the monster's strength. If our hero wins the battle, he acquires the strength of his opponent (meaning he adds the monster's strength to his ability). Otherwise, he is defeated.

Before we start telling this magnificent tale, we need a few definitions:

• We say that a vector $$$\mathcal{P}$$$ is a permutation if each of the 26 letters of the alphabet appears in exactly one position of $$$\mathcal{P}$$$. For example, the vector $$$\mathcal{A} = (D, F, C, O, I, L, S, W, V, X, H, K, A, T, Q, M, R, Y, Z, J, B, E, U, N, G, P)$$$ is a permutation, while the vector $$$\mathcal{B} = (A, F, C, O, I, L, S, W, V, X, H, K, A, T, Q, M, R, Y, Z, J, B, E, U, N, G, A)$$$ is not, as the letter 'A' appears multiple times.
• Let $$$L$$$ be the $$$\ell$$$-th letter of the alphabet and $$$\mathcal{P}$$$ a permutation. Then, we define $$$\mathcal{P}(L)$$$ as the $$$\ell$$$-th letter of $$$\mathcal{P}$$$. Using the example from the previous item, $$$\mathcal{A}$$$(D) $$$=$$$ O, because D is the fourth letter of the alphabet and O is the fourth letter in $$$\mathcal{A}$$$. Similarly, given a text $$$T$$$ and a permutation $$$\mathcal{P}$$$, we define $$$\mathcal{P}(T)$$$ as the resulting text obtained by applying $$$\mathcal{P}$$$ to each letter in $$$T$$$. For example, $$$\mathcal{A}$$$(EU AMO AC) $$$=$$$ IB DAQ DC.
• Given a set of words $$$U$$$, we say that a text $$$T \in U*$$$ if $$$T$$$ contains only words from $$$U$$$. For instance, if $$$U = \{AC, SIM, CORRETO\}$$$, then the text SIM SIM AC belongs to $$$U*$$$, while the text AC WA AC does not.

Now we shall tell the story of the origin of competitive programming among humans. Legend has it that thousands of years ago, in ancient Nlogonia, the god Rárada constantly invented new problems and algorithms to solve them, sharing these ideas among the gods. It is known that the gods used very few words when communicating with each other, more specifically, the deities only used words from the set $$$U =$$$ {AC, AMOR, BRASILEIRO, CAVALO, MARATONUSP, OSSO, OVO, PATA, RARADA, TLE, VOO}; do not question why they chose these words, and, yes, the gods from Nlogonia spoke portuguese. Among these gods was Promethilio, who, amazed by these new ideas, believed that this knowledge should be passed on to humans. However, fearing that humans would become too powerful, he didn't convey exactly the same message as Rárada. Every time Promethilio heard a phrase $$$T \in U*$$$ from Rárada, he would choose a permutation $$$\mathcal{P}$$$ and send the text $$$\mathcal{P}(T)$$$ to the hero Morethor (perhaps you've heard of him in another question). Morethor would then transcribe the phrase $$$\mathcal{P}(T)$$$ onto stone tablets with the aim of disseminating these ideas and preserving competitive programming knowledge forever.

Otávio, the archaeologist, has found a stone tablet with a text $$$S$$$ and is extremely excited about the possibility of having discovered one of the ancient tablets written by Morethor containing Rárada's foundational ideas. He now needs your help to decide whether he has truly found a historical relic or just an ordinary text.

On special occasions, the gods meet at the university restaurant for a joyful feast. Anthena always invites Nathena to such feasts, but Nathena often refuses to join arrogantly.

As his presence at the university restaurant is so extremely rare, legends tell that, since Nathena emerged from Zeos' head, he has only recharged his university restaurant credit balance once. It is known that one can buy at most 200 drachmas (yes, the gods still use this currency) worth of credit at once. It's also known that each meal at the university restaurant costs exactly two drachmas.

Knowing how many drachmas worth of credit Nathena bought on his recharge and his current credit balance, discover how many times he has feasted at the university restaurant.