As a student of the Biology And Probability Course at your university, you have just performed an experiment as part of the practical assignments. However, your results do not look very nice: you had hoped that the average of your samples would be different from what it is now.

To improve your results, you decide to let some of your samples "magically disappear" (i.e., dump them in the waste bin). In order to not raise suspicion with your teacher, you can remove only a few of your samples. How close can you possibly get to your desired average?

As any photographer knows, any good sunset photo has the sun setting over the sea. In fact, the more sea that is visible in the photo, the prettier it is!

You are currently visiting the island Bellevue, and you would like to take a photo of either the sunrise to the east or the sunset to the west to submit it to Bellevue's Astonishing Photography Competition. By carefully studying the topographic maps, you managed to find the east-west profile of the island. Now you would like to know the maximal amount of sea that you could capture in a photo, measured as the viewing angle covered by water.

The profile of the island is given as a piecewise linear function consisting of $$$n-1$$$ segments between $$$n$$$ points. The island starts and ends at sea level. As an example, Figure below shows the profile of the first sample case.

Note that the viewing angle of your lens is not large enough to capture the ocean to the east and west of the island in one shot. Also, the viewing angle of sea at sea level is $$$0$$$ degrees.

You are writing code for a hackathon where you need to decode Binary ALGOL Punch Cards. You have already come up with the optimal solution and only need to type it out. The solution consists of $$$c$$$ characters, and your typing speed is $$$1$$$ character per time unit. However, your computer is prone to sudden crashes: after every character you type there is a probability of $$$p$$$ that your computer crashes and you need to start over again. Recovering after a crash costs $$$r$$$ time units, and you can then continue typing from the last point where you saved your code.

You can click "Save" at any time (which costs $$$t$$$ time units) to save your code and to be able to restart from this point after crashes. Clicking "Save" will not cause your computer to crash.

Determine how many (expected) time units you need to complete the code. Note that the code should be saved after typing the last character.

At the Bacteria And Protein Centre, you own a large collection of DNA. In fact, new strands of DNA come in all the time. To organise the vast amount of data, you identify each piece by its unique substrings: substrings that do not already occur in the database.

Your database can quickly determine whether a given piece of DNA occurs as a substring in the database or not. Naturally, if a certain DNA string is found in the database, it also contains all its substrings.

You now want to determine the uniqueness of a given piece of DNA: the maximal number of disjoint substrings it contains that are absent from the database.

You are given the length $$$n$$$ of the query string $$$q_1\dots q_n$$$, and you can repeatedly ask the database whether it contains the substring $$$q_i\dots q_{j-1}$$$.

As an example, consider the first sample interaction. In this case, the database contains strings "TGC" and "CT", and the query string is "CTGCAA". It has uniqueness $$$3$$$, because it can be split into the new substrings "CTGC", "A", and "A". The new substring "CTGC" cannot be split up further: for example, the subdivision "CT" and "GC" is not allowed, because both substrings occur (possibly as substrings) in the database. Note that the actual characters in the string are not used in the interaction.

You may use at most $$$2n$$$ queries to the database.

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

The interactor first sends one line with an integer $$$n$$$ ($$$1\leq n\leq 10\,000$$$), the length of the DNA piece for which you need to compute the uniqueness.

Then, your program should make at most $$$2n$$$ queries. Each query is made by printing one line of the form "? $$$i$$$ $$$j$$$" ($$$0\leq i \lt j \leq n$$$), indicating that you want to query whether the substring starting at position $$$i$$$ and ending at position $$$j-1$$$ occurs in the database. The interactor will respond with either "present" or "absent", indicating whether the substring was found in the database.

When you have determined the uniqueness $$$x$$$ of the piece of DNA, print one line of the form "! $$$x$$$", after which the interaction will stop. Printing the answer does not count as a query.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Using more than $$$2n$$$ queries will result in a wrong answer.

As a radio engineer at the Balanced Audio Podcast © your job is to deliver an equal listening experience at all times. You did a poll among the listeners and they are especially concerned about fluctuations in loudness. To resolve this you bought a transformer to equalise the audio, but alas, its software got corrupted during transport.

Your job is to rewrite the equalising software. As input the transformer gets $$$n$$$ amplitudes $$$a_1, \ldots, a_n$$$, with an average perceived loudness of $$$\frac{1}{n}\sum_{i=1}^n a_i^2$$$. The output should contain the same amplitudes, but renormalised by some constant positive factor, such that the average perceived loudness is $$$x$$$. There is one exception: total silence should always be preserved.

Ahoy! You are sailing towards the next "Boats Are Pretty Cool" convention to sell your latest gadget: a new type of compass.

On a normal compass, it is difficult to read off the precise wind direction. However, your new type of compass lets you read off wind directions to a much higher precision! The display can display strings of at most $$$1000$$$ characters.

Unfortunately, you have encountered some bad weather. After a few hours of heavy winds and big waves, you can finally look at your compass again. You read off the wind direction $$$X$$$ you are going and know in which wind direction $$$Y$$$ you need to go. However, to make the ship turn you have to enter the degrees of the angle the ship has to make in the control system. What is the smallest turn, in degrees, you have to make to get back on the right course?

A wind direction can also consist of $$$k\geq 3$$$ letters $$$l_1l_2\ldots l_k$$$. In that case, the last two letters indicate one of the four two-letter wind directions, i.e., $$$l_{k-1}l_k \in \{\text{NE}, \text{SE}, \text{SW}, \text{NW}\}$$$ and the other letters are equal to one of these, i.e., $$$l_i \in \{l_{k-1}, l_k\}$$$ for all $$$i \leq k-2$$$. This wind direction points precisely in the middle of the following two wind directions:

• wind direction $$$l_2\ldots l_k$$$,
• the first wind direction of at most $$$k-1$$$ letters you encounter when starting in $$$l_2\ldots l_k$$$ and move along the circle towards $$$l_1$$$.

During the renovation of your garden, you decide that you want a gravel path running from the street to your front door. Being a member of the Boulders And Pebbles Community, you want this path to look perfect. You already have a regular grid to put the gravel in, as well as a large container of gravel containing exactly as much as the total capacity of the grid.

There is one problem: the gravel does not yet fit perfectly into the grid. Each grid cell has the same (fixed) capacity and every piece of gravel has a certain weight. You have a grindstone that can be used to split the stones into multiple pieces, but doing so takes time, so you want to do a minimal number of splits such that the gravel can be exactly distributed over the grid.

As an example, consider the first sample case. There are three grid cells of size $$$8$$$, which can be filled as follows. Put the stones of weight $$$2$$$ and $$$6$$$ in the first cell. Now grind the stone of weight $$$7$$$ into two pieces of weight $$$3$$$ and $$$4$$$. Then the other two grid cells get filled by weights $$$3, 5$$$ and $$$4, 4$$$ respectively.

You are addicted to the latest world-simulation game: Building A Perfect City. In your current play-through, you have created a city that has an equal number of streets and intersections. All that is left is to number the houses in every street.

The city is represented by a connected graph with intersections and streets. Every street is a connection between two intersections $$$u$$$ and $$$v$$$, and has $$$h$$$ houses which are all on one side of the street. There is at most one street between two intersections. There are two ways to number the houses in this street: either you start with house number $$$1$$$ adjacent to intersection $$$u$$$ and end with house number $$$h$$$ at intersection $$$v$$$, or house number $$$1$$$ is adjacent to $$$v$$$ and house number $$$h$$$ is adjacent to $$$u$$$. To avoid confusion, you want to ensure that no intersection has two adjacent houses with the same number.

Find a way to number the houses in every street that satisfies this property (or report that it is impossible).

You are writing a paper for the Beta Astronomy Physics Conference about your recent discovery on grey holes. One of your collaborators has performed a huge number of measurements, which you would like to analyse in order to draw some conclusions. The only problem is: the data is measured in a wide variety of units, and to your disgust, they appear to use a mix of the imperial and metric systems. To simplify your analysis, you need to convert all these measurements into a different unit.

The future is here! The Boxes And Parcels Centre has decided to start delivering parcels using drones. Being a BrAinPort Company, naturally the first deliveries will be to Eindhoven.

To keep the flight logic simple, the first prototype will only deliver to the roofs of the tallest buildings. After take-off, the drone will take a $$$w\times h$$$ ($$$1 \leq w\leq 10\,000$$$, $$$1\leq h\leq 10^{18}$$$) photo of the skyline, as shown in Figure 1. You have been tasked with the problem of determining the location and height of the tallest building in this photo, so that the drone knows where to go.

You have access to a classifier that can determine for each pixel whether it is "sky" or "building". You can use this multiple times for different pixels. To avoid unnecessary delays, you may run the classifier at most $$$12\,000$$$ times.

It is guaranteed that the buildings will not contain any hovering parts: whenever a pixel that is not on the bottom row of the photo is classified as building, the pixels below it will also be classified as building.

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

The interactor first sends one line with two integers $$$w$$$ and $$$h$$$ ($$$1\leq w\leq 10\,000$$$, $$$1\leq h\leq 10^{18}$$$), the width and height of the photo in pixels.

Then, your program should make at most $$$12\,000$$$ queries to find the highest building. Each query is made by printing one line of the form "? $$$x$$$ $$$y$$$" ($$$1\leq x\leq w$$$, $$$1\leq y\leq h$$$). The interactor will respond with either "sky" or "building", indicating the classification of the pixel at coordinates $$$(x, y)$$$.

When you have determined the $$$x$$$-coordinate of one of the highest buildings and its height $$$y$$$, print one line of the form "! $$$x$$$ $$$y$$$", after which the interaction will stop. Printing the answer does not count as a query.

The interactor is not adaptive: the skyline is fixed up front, and does not depend on your queries.

If there are multiple valid solutions, you may output any one of them.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Using more than $$$12\,000$$$ queries will result in a wrong answer.

You are planning to start a Beautifully Arranged Placid Camping. You already have bought a field, which you have divided into a $$$h \times w$$$-grid of plots, and numbered them with distinct numbers $$$a_{ij}$$$ from $$$1$$$ to $$$h \cdot w$$$. However, you forgot one thing: you still need to place the reception kiosk at one of the plots. You want to minimise the maximal distance that any guest will walk from the reception kiosk to their plot. Guests will however not take the shortest path to their plot, but instead they follow the following procedure, starting at the reception kiosk:

• Look at the numbers of the four neighbouring plots.
• Go to the plot with the number closest to the destination number. In case of a tie, out of the two tying plots, go to the one with the number closest to the current plot number.
• Repeat until the destination is reached.

Note that this procedure might not terminate in some cases.

Given the numbering of the plots, find the plot number of the optimal position for the reception kiosk and the maximal walking distance to any plot from this kiosk. If, for every possible position for the reception kiosk, there is at least one plot for which the procedure outlined above does not terminate, output that this is impossible.

Figure 1 shows the third sample case: one solution is to put the kiosk in plot $$$4$$$, so that every other plot is at most distance $$$3$$$ away. Placing the kiosk in plot $$$7$$$ does not work as plot $$$9$$$ cannot be reached from there.

It is the year 2222. The whole universe has been explored, and settlements have been built on every single planet. You live in one of these settlements. While life is comfortable on almost all aspects, there is one dire problem: the latency on the internet connection with other planets is way too high.

Luckily, you have thought of a solution to solve this problem: you just need to put Bonded, Astronomically Paired Cables between all planets, and internet will be super fast! However, as you start developing this idea, you discover that constructing a cable between two planets is more difficult than expected. For this reason, you would like the first prototype of your cable to be between two planets which are as close as possible to each other.

From your astronomy class, you know that the universe is best modelled as a large cube measuring $$$10^9$$$ lightyears in each dimension. There are exactly $$$10^5$$$ stationary planets, which are distributed completely randomly through the universe (more precisely: all the coordinates of the planets are independent uniformly random integers ranging from $$$0$$$ to $$$10^9$$$).

Given the random positions of the planets in the universe, your goal is to find the minimal Euclidean distance between any two planets.