In his free time, Thomas greatly enjoys working on the extensive Lego project that he has built in his attic, adding house after house to his miniature city. However, he has become a bit bored with the completely rectangular layout that is enforced by the little studs of the huge base plate that his city is built on.

After an exchange with some other Lego creators he came across a technique that will allow him to place his buildings at different angles. Each building rests on a rectangular ground plate, to the underside of which he attaches four round $$$1\times 1$$$-plates in the corners. These $$$1\times 1$$$-plates are then placed on four studs of the base plate, like in Figure 1 above.

If the ground plate of the building is $$$a\times b$$$ studs, what is the number of orientations it can be placed in using this technique, so that all the corner plates exactly fit on studs of the base plate?

This year is a good year for North America. 2022 is one of the few years where no brood of the periodical cicada is hatching and thus, no swarms will destroy the crops on the fields.

Those periodical cicadas have a somewhat strange property: They have highly synchronized life cycles, which means that almost all individuals in a local population emerge in the same year, resulting in periodical cicada plagues. Even odder is the fact that the periodicities of those life cycles appear to be prime, for example 13 or 17 years. The best theory for this so far is that a prime periodicity lets them avoid predators with shorter population cycles since a brood emergence of cicadas will rarely coincide with a predator's population boost.

But nobody likes cicada plagues, so this prime periodicity is now your problem. Your hope is that cicadas with non-prime periodicity will not be able to avoid predators anymore and that there will be fewer cicada plagues as a result. So, to prevent the next plague, you forge a plan to breed different cicada types to get a new type with non-prime periodicity. If you mate a cicada of a type with periodicity $$$a$$$ with another cicada of a type with periodicity $$$b$$$, you assume to get a cicada of a type with periodicity $$$a+b$$$. You have already captured $$$n$$$ cicadas to breed but you don't know which will mate. Therefore, you decided to set some cicadas free such that the remaining ones can mate this year in any way they want without producing a cicada of a type with prime periodicity. How many of your cicadas can you keep at most?

The city Gircle has only one street, and that street is cyclic. This was very convenient in times when people didn't carry a device with compass, GPS and detailed maps around in their pockets, because you only have to walk in one direction and will certainly arrive at your destination. Since Gircle's founding a lot of time has passed. Civil engineers now know a lot more about road network design and most people have immediate access to reliable and accurate navigation systems. However, the passage of time also affected the old street surface and more and more cracks and potholes appeared.

The local government has finally decided to improve the situation, but preserving the city's historic appeal and building new streets are unfortunately mutually exclusive. Because tourism is vital for Gircle's economy, the government's only viable option for improving the situation is to renovate segments of the street when necessary. Gircle's street is very narrow, so a construction site at a street segment makes it impossible for citizens to pass that segment or even leave or enter it.

As a member of the Gircle Construction and Planning Commission (GCPC), you always know when one of the $$$n$$$ street segments is closed or reopened. Naturally, the citizens expect you to tell them whether the trips they want to do are currently possible.

Figure 1. Depiction of the query "? 9 7" in the sample input.

Each year, the fastest platypuses of the world come together for the Great Crawling Platypus Cup (GCPC) to crawl a single lap in the platypus arena. Of course, Perry the platypus wants to take part in this great event. Perry's arch enemy Dr. Doofenshmirtz got wind of it and plans to capture Perry right when he crosses the finish line at the GCPC. To carry out his evil plan successfully, he needs to find out how long Perry needs to finish the lap. He knows that Perry takes the preparation for the GCPC very seriously and trains by crawling lap after lap in the arena at a constant speed of $$$1\,\frac{\text{m}}{\text{s}}$$$. Perry's training starts this Saturday and Dr. Doofenshmirtz knows that he will run at least $$$10^{18}$$$ seconds. To determine the exact length of one lap, Dr. Doofenshmirtz invented the Measurinator which can measure the exact distance Perry has already crawled in his current lap. Unfortunately, the Measurinator will break after too many measurements, so Dr. Doofenshmirtz has to carefully plan when to use it in order to determine the length of one lap.

Your submission can print "? t" where $$$t$$$ ($$$0\leq t \lt 10^{18}$$$) is the point in time when you want to use the Measurinator. The time $$$t=0$$$ marks the point in time where Perry starts practicing i.e. where he starts his first lap at the start and finish line. The Measurinator responds with a single integer $$$x$$$ which is the current position of Perry in his current lap. Note that the Measurinator will not respond with the number of meters Perry has already crawled in total! Thus, whenever Perry reaches the start and finish line, the Measurinator will respond with $$$0$$$. Further note that you recently lost your Timetravellinator and therefore, the values of $$$t$$$ must be strictly increasing.

If you determined the length $$$x$$$ of one lap, print "! x". After this, your program should immediately terminate.

All interactions must be ended by a newline. Further note that you additionally need to flush the standard output to ensure that the query is sent. For example, you can use:

• std::cout <{}< std::flush in C++
• fflush(stdout) in C
• System.out.flush() in Java
• sys.stdout.flush() in Python

Your submission is considered correct if you followed these rules, found the correct length of one lap, and used no more than $$$42$$$ queries. Note that giving the answer is also counted as a query.

It is guaranteed that one lap has integer length, is at least one meter long, and at most $$$10^{12}$$$ meters long.

A testing tool is provided to help you develop your solution. It can be downloaded from the DOMjudge problems overview page.

For many days now, the canteen in Hilbert's Hotel has been offering its famous Fibonacci Soup. Today is the $$$n$$$th day that they offer the soup, and the recipe changes every day:

• On the first day, it is a $$$\pi$$$-tato soup, made from a blend of local potato varieties, and served with onion strips and celery.
• On the second day, it is a $$$\tau$$$-mato soup, consisting of pur'eed tomatoes, together with carrots, onions, garlic, and basil leaves on top.

• On every day after that, the soup is made from two ingredients, the soup of the previous day and the soup of the day before that, mixed together in equal parts.

Find the composition of today's Fibonacci Soup.

Flatland is happy to announce that this year – for the first time ever – the Formula One comes to Flatland to arrange the Grand Prix of Flatland. As with many other cities, Flatland is not able to build a dedicated circuit for the race. Therefore, Flatland decided to close off some of its normal streets and crossings to form a circuit. After your excellent work as an organizer of last year's Flatland Olympics, you were hired to find a suitable circuit. Since closed off streets are annoying to the people who live there, you would like to minimize the number of crossings that need to be closed off for the race.

Visualization of the second sample. One possible optimal circuit would be: $$$(4,5,7,6)$$$.

Your job only consists of selecting some road segments which form a circle but are connected by as few crossings as possible. Note that even though all roads in Flatland are bidirectional, they can only be used in one direction during the race for safety reasons.

Every year, the top gardeners of the cities Greenville and Tomatown compete against each other in the Grand Gardening Competition. The competition consists of some number of examinations which take place over the course of one week from Monday to Sunday. In each examination, one gardener from Greenville and one gardener from Tomatown present their products to a neutral jury. A few days in advance, both gardeners officially announce how many products of each type of vegetable, fruit or berry they plan to present. During the examination, the jury then evaluates the size, weight, diversity, beauty and taste of the presented products. After careful consideration, the jury finally declares one of the two competing gardeners to be the winner of the examination.

Alan and his friends are all enthusiastic gardeners, but since they do not live in Greenville or Tomatown, they can not submit their own vegetables to the competition. However, they have started their own private contest, where they try to predict the results of the single examinations. In this contest, each participant is allowed to pick one examination from each of the seven competition days and predict its winner. If this prediction turns out to be correct, the participant is awarded one point. To keep their guessing game interesting, Alan and his friends agreed that a prediction for an examination can not be handed in after the competing gardeners have announced which products they are going to present.

By using his connections to the gardening scenes of Greenville and Tomatown, Alan has consistently managed to score more points than all of his friends in the previous years. However, when he woke up this year on Monday, the first day of the competition, Alan realized that he had completely forgotten to submit his predictions! Of course, he immediately sprinted towards his computer and tried to submit his bets. Unfortunately, all gardeners which were scheduled to present their products between Monday and Friday had already announced their selections, so Alan could only submit his predictions for two examinations on Saturday and Sunday. He then hastily grabbed the competition schedule and started to compare the announced examinations to the predictions made by him and his friends.

Help Alan to determine whether there still remains a tiny chance that he can once more win the Gardening Competition Prediction Contest.

You have probably heard about the game called hangman (and played it as a child). You try to guess a word with as few guesses as possible. In each guess, you suggest a letter, for example an a, and you get all the positions in the word, where an a appears.

That can take quite a few guesses, in particular, if a difficult word was chosen. So, let's change the game a bit. Instead of guessing just a single letter, any set of letters can be guessed in one turn. As a result you get all positions which contain one of the guessed letters.

If the word is 'hangman' and you guess the letters h, z and a in the first turn, you get the positions 1, 2 and 6. Of course, you still don't know whether there is an h, z or a at these positions, but it has to be one of those three letters.

Your task is to find the hidden word (it is not always a proper English word, but can be any string consisting of lowercase English letters) using at most 7 guesses.

This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

Your submission repeatedly sends one of two query types:

• "? s", where $$$s$$$ is a string of pairwise distinct lowercase letters. The interactor replies with an integer $$$n$$$ followed by $$$n$$$ integers $$$i_1, i_2, \dots, i_n$$$, the indices of the positions (1-indexed) in the hidden string, which contain a character in $$$s$$$.
• "! x", where $$$x$$$ ($$$1 \leq |x| \leq 10^4$$$) is a string of lower case letters. The interactor replies with "correct" in case $$$x$$$ is the hidden string, else it replies with "incorrect". After the answer "correct", your program should terminate.

All interactions must be ended by a newline. Further note that you additionally need to flush the standard output to ensure that the query is sent. For example, you can use:

• std::cout <{}< std::flush in C++
• fflush(stdout) in C
• System.out.flush() in Java
• sys.stdout.flush() in Python

The hidden word has length at most $$$10^4$$$. You may use at most $$$7$$$ queries.

A testing tool is provided to help you develop your solution. It can be downloaded from the DOMjudge problems overview page.

Your best friend is part of the business team at the Global Center for Parallel Computing (GCPC). She is responsible for buying and selling the hardware that is powering the system that will be in use for the next $$$n$$$ months. Currently, she is planning the CPU replacement cycle for a single CPU. To ensure that the system is always up-to-date, the CPU must be replaced at least every $$$m$$$ months. Fortunately, she can sell the replaced CPU to lower the overall costs to operate the new system. However, storage capacity is pricey, and she has to accept the resale value the CPU has in the month it is replaced. That means, when a CPU that was used for $$$j$$$ months is replaced in month $$$i$$$, you need to sell the current CPU for the value it has after $$$j$$$ months of usage and buy a new CPU for the price of the $$$i$$$th month. She already compiled a list of CPU prices for the next $$$n$$$ months including their resale value after $$$1$$$ to $$$m$$$ months. Note that you definitely need to buy a CPU in month $$$1$$$ and you need to sell the last CPU in month $$$n + 1$$$. How much money does the system cost at least over the $$$n$$$ months?

In Sample 1, Alice has to move at least two cards to sort her hand.

As huge card game nerds, Alice and her friends are very hyped about meeting up and trying out the card game everybody seems to talk about these days. Due to a traffic jam, Alice is a bit late to the party and her friends are impatiently waiting for her. They have already distributed all cards and everybody is ready to go, except for Alice. She has just picked up her cards and insists on sorting them by suit first. For that, she repeatedly picks one card from her hand and inserts it somewhere else until her cards are grouped by suit. Her friends are getting increasingly annoyed with Alice and she wants to sort her cards as quickly as possible. How many cards does Alice need to move before they can start playing?

On his birthday party, Glen wants to play the most exciting game. It is called Splash Game. For this, his parents built a bridge, which goes over the full length of the family pool and can be seen as a $$$2 \times n$$$ grid: it consists of $$$n$$$ steps and at each step, there are two plates. The players go over the bridge one after the other in a fixed order. At each of the $$$n$$$ steps, one of the two plates is fake and the player will fall into the pool with a big Splaaaaash when she steps onto it.

Of course, a participant can be lucky and guess the real plate and will not fall (she might still fall later). Also the first player really has a tough time. To make it to the other side, she would need to guess the real plate at every step. The later players have the advantage that they can see what the others are doing and hence know for the already entered steps, which plate is the real one (if a player guesses the real plate, everybody sees it; if she guesses the fake one and falls, everybody knows that the other plate is the real one).

The players proceed by a simple strategy. The first player starts by choosing the left plate on the first step. If she is correct, she switches to the right side and she will keep switching the side at every step (it is common knowledge that switching is a good idea). Every other player, once it is her turn, follows the correct choices as far as they are known and, afterwards, applies the switching strategy as well, i. e., if she stepped on the left plate on the previous step, she now steps on the right one and vice versa.

Of course, the game is only fun if at least a few kids make it to the other side of the bridge. But it shouldn't be too many either, since everybody has a great laugh when somebody is falling into the water. Given the number of kids and the planned layout of fake and real plates, output how many kids make it to the other side of the bridge.

The bridge layout for Sample Input 4 (cracked squares indicate the fake plates). The first player will guess the first step correctly, but fall on the second step. The second player thus knows the correct choices for the first two steps and guesses the third and fourth one correctly by switching. In the end, three of the seven kids make it to the other side.

Farmer Robert has been running a very successful cereal farm for many years. Now he wants to diversify his business and get into growing potatoes. To this end, he has bought a new plot of land on which he plans to plant the potatoes. This field is a rectangle and is exactly $$$\ell$$$ metres long and $$$w$$$ metres wide.

Since Robert is new to the potato business, he has initially purchased $$$n$$$ different potato varieties to try out in the first year. He plans to divide his plot of land into $$$n$$$ parts of equal area and plant one of the varieties on each. To make it easier for him to work the fields with his tractor, each new piece of land should itself be a rectangle and have integer side lengths. Help Robert to find a suitable division of his field.

Yesterday, a new attraction was opened at the local funfair: a hall of mirrors. This is a labyrinth in which all the walls are covered with mirrors so that visitors lose their sense of direction in a sea of reflections. The layout of the labyrinth can be described by a polygon with all sides parallel to either the x-axis or y-axis.

On the opening day, many visitors got so lost that the ride operators had to intervene and help them find their way out. To better understand where visitors get lost the most, the operators decided to install a monitoring system. This system involves an invisible laser beam running through the hall of mirrors at foot level, so that the movement of the visitors can be tracked by observing when and where the laser beam gets interrupted.

The laser beam starts at some boundary point of the polygon at an angle of $$$45$$$ degrees to the wall. Whenever it hits a mirror, it bounces off in a $$$90$$$ degree angle. To get their monitoring system to work, the operators are planning to install sensors at each of the first $$$m$$$ bouncing points of the laser beam. Find the locations where the sensors need to be installed.

Illustration of the second sample case.