The city's art museum is known for its long straight corridor and the artistically decorated tiles laid along it. The corridor is a rectangular area $$$2$$$ meters wide and is divided into one-meter-square cells. Each cell is either occupied by a single tile or is empty.

As a part of the renovation of the museum, all the empty cells will be covered with tatami mats, which are traditional Japanese floor mats. Each tatami mat is $$$1$$$ meter by $$$2$$$ meters in size, so each tatami mat covers exactly two adjacent cells. Tatami mats must not overlap each other, and they must not overlap any tile.

Depending on the initial placement of the tiles, it may be impossible to cover all the empty cells with tatami mats. To address this, the museum allows each tile to be moved from its original position to one of its adjacent cells that shares a side, but not farther. Tiles must not be moved out of the corridor. No more than one tile should be on a single cell after the moves.

Figure A.1: Before and after the renovation for Sample Input 1

The left figure shows the initial positions of the tiles for Sample Input 1, and the right figure shows one possible way to move one tile and arrange tatami mats to cover all the empty cells.

Determine whether it is possible to cover all the empty cells with tatami mats when you move some (possibly none) of the tiles appropriately. If it is possible, find the minimum number of tiles to be moved.

A wild boar.

www.irasutoya.com

The farmland you are cultivating consists of a certain number of plots arranged from west to east. Currently, each plot contains a certain amount of wheat; the amounts may differ across plots. All the wheat will be ready for harvest after a certain number of days.

One big problem you are facing is that a hungry wild boar comes from the west every night. If none of the plots have any wheat remaining, the boar just turns back. Otherwise, the boar goes to the westernmost plot that still has wheat and eats one unit of wheat there. The boar then continues by moving to the adjacent plot to the east and eating one unit of wheat, until it either encounters a plot with no wheat remaining or finishes eating at the easternmost plot, at which point it returns home.

To mitigate the damage, you plan to choose some plots (possibly none) and remove all the wheat from these plots today, so that the boar may return without eating too much wheat on subsequent days. After that, the boar continues to come every night, but there is nothing you can do to mitigate the damage further.

You are given one or more candidate days on which you may harvest. For each candidate harvest day, determine the maximum possible amount of wheat remaining for harvest on that day, assuming you remove all the wheat from optimally chosen plots. The optimal choice of plots may vary across candidate days.

An island on an extrasolar planet is famous as a good bird-watching spot, where you can see many seagull-lookalikes (simply called seagulls hereafter) throughout a year. The planet is quite similar to the Earth, but the number of days in a year is different.

Each seagull comes to the island exactly once a year, stays for a while, and leaves exactly once a year as well. Each seagull has its own schedule of coming and leaving the island, and quite punctually sticks to the schedule. That is, every year, it comes to the island on the same day of the year. Also, every year, it leaves on the same day of the year. Seagulls come to the island early in the morning and leave late in the afternoon. Seagulls that have come to the island may leave on the same day. On the other hand, seagulls may leave the island on one day and come again on the next day.

Members of the bird-watching club count the number of seagulls staying on the island every day around noon. Their counting is perfect, so that all seagulls present at that time are counted without any omission or duplication. However, the seagulls look so similar that identifying individuals is not possible.

Note that seagulls that leave the island on one evening and come again on the next morning are counted on all days in a year.

Given the daily counts of seagulls throughout a year, you want to know the total number of seagulls visiting the island. Since seagulls are indistinguishable, it is not possible to know the exact number. For example, if the counts are one on two consecutive days, the number of seagulls may be one or two. The minimum possible number is the only valuable information you can obtain.

Determine the minimum possible number of individual seagulls counted at least once in a year. If this minimum is small enough, also show a possible list of their stay periods that attains this minimum.

You are given an integer greater than or equal to $$$2$$$. When this number is decomposed into the sum of two positive integers, a new integer number can be formed as the concatenation of the decimal representations of the two integers. Find the maximum possible number formed in this way.

For example, $$$102$$$ can be decomposed and concatenated as follows.

You are preparing miso soup, a favorite among Japanese people, with one of the most popular ingredients, tofu. Tofu is a white cuboid-shaped food that is usually cut into smaller pieces and then put into the soup.

You plan to chop a single block of tofu to make at least a required number of cubes of the same size. You cut the tofu along planes parallel to the faces of the tofu block. Each cut goes all the way through the block, dividing all the pieces it passes through. You should not move the tofu block nor its fragments until tofu cubes are completely cut out.

Figure E.1: An example of cutting the tofu

As long as the required number of tofu cubes can be obtained, you want to make cubes as large as possible. You don't mind leaving excess tofu cubes or leftover fragments, as they can be used for other dishes.

Given the dimensions of the block of tofu (its length, width, and height) in integer multiples of unit length, and the required number of tofu cubes, your task is to find the maximum possible side length of the tofu cubes. Since it can be proven that the answer is a rational number under the given constraints, it should be represented as a reduced fraction.

You, a young astronomer, are interested in the spatial arrangement of a set of stars with distinctive features. Knowing this might contribute to the understanding of early-universe cosmology. You can perform measurements using a specialized instrument for this purpose.

The instrument uses its own three-dimensional Cartesian coordinate system, in which the origin $$$(0,0,0)$$$ is set on Earth, and the positions of the stars are modeled as lattice points (points whose coordinates are all integers). You already know the distances to all the stars of interest from Earth, but their directions are unknown.

In a single measurement, you specify two distinct stars, and the instrument reports the distance between them. Note that the instrument does not report the absolute or relative directions of the stars.

Determine the distances between all pairs of the stars within the limited number of measurements.

The first line of input contains an integer $$$n,$$$ the number of stars of interest ($$$2 \le n \le 100$$$). The stars are numbered from $$$1$$$ to $$$n.$$$ The second line contains $$$n$$$ integers. The $$$i$$$-th of them is the squared distance from the origin to star $$$i.$$$ It is guaranteed that all stars have integer coordinates, each between $$$-4000$$$ and $$$4000$$$, inclusive. No two stars are at the same position. No star is at the origin.

After reading in these two lines, you may start measurements. To measure the distance between stars $$$i$$$ and $$$j$$$, write a line of the form "measure $$$i$$$ $$$j$$$", where $$$i$$$ and $$$j$$$ are distinct integers between $$$1$$$ and $$$n$$$, inclusive. In response, an input line containing an integer denoting the squared distance between stars $$$i$$$ and $$$j$$$ becomes available. You can perform up to 300 measurements.

When you have determined the distances between all pairs of the stars, write a line containing only answer, followed by $$$n-1$$$ lines of the following format.

If your output does not conform to the specifications above, or if the number of measurements exceeds 300, your submission will be judged as a wrong answer.

The coordinates of the stars are fixed before the interaction starts; they do not change during the interaction.

You are provided with a command-line tool for local testing. For more details, refer to the attachments in the contest system.

You are joining a charity raffle in which several types of prizes can be won. The raffle is held in a somewhat unusual way: with one draw using a single draw ticket, two prizes of different types are randomly picked up. However, you don't win both of them; you should choose one out of the two.

You have a certain number of draw tickets. You will use all of them and win the same number of prizes. As you don't want too many prizes of the same type, when choosing out of the two prizes, you choose the one that you have won fewer so far. You may have won the same number of the two prize types, including cases where both are zero. The prize types are sequentially numbered, and you choose the one with the lower type number in that case.

Despite the above strategy, it is not certain that you can avoid winning too many prizes of the same type. You feel unhappy if there is a prize type for which the number of prizes you win exceeds a certain limit. You want to know how many possible combinations of prizes you may get that do not make you unhappy after using up all of your draw tickets. Two combinations of prizes are considered different when they differ in the count of at least one type of prize. You may assume that there is an unlimited supply of any type of prize.

A rectangular pond is in the backyard of your house. As the length and width of the pond are integer multiples of one meter, the pond can be considered to consist of one-meter-square sections.

You always feel the pond is too large, and you want to cover some of its sections using the panels kept in the barn. All of these panels have the same size and the same shape, consisting of one-meter-square boards arranged in a U shape. The overall size of the panels is $$$k$$$ meters by $$$k$$$ meters, and $$$3k-2$$$ boards are on the three edges of that square. The rest, the $$$(k - 2) \times (k - 1)$$$ rectangular area, is void. Figure H.1 illustrates a panel of size $$$k=5.$$$

Figure H.1: A panel of size $$$k = 5$$$ (left) and its top view (right)

You plan to cover certain one-meter-square sections of the pond with the panels and leave the rest uncovered. Panels should be placed so that each of their boards fits exactly one section. As long as this is satisfied, orientations of the panels can be arbitrarily chosen. Panels should not overlap one another nor stick out of the pond.

Determine whether your plan is feasible or not.

Alice and Bob are playing a game on a board with a certain number of cells in a single row. Some (possibly none) of the cells have a player's name written in them, either "Alice" or "Bob". Other cells are initially blank.

Starting with Alice, the two players alternately take moves. In one move, the player in turn chooses a blank cell that does not have an adjacent cell with the player's own name, and then writes the player's name in the chosen blank cell. Note that the opponent's name in an adjacent cell does not matter.

The player who cannot make a move loses the game. Given the initial state of the board, determine which of Alice and Bob will win when they play their best.

As an archaeologist, you have discovered a rectangular wooden board in the ruins of an ancient city. The board is divided into a grid, and each grid cell appears to have been engraved originally with one of the letters 'C', 'I', and 'P'. However, due to decay over time, some of the letters are now indistinguishable.

During your investigation, you made the following hypothesis: any square of $$$2 \times 2$$$ cells on the board originally had two 'C's, one 'I', and one 'P'.

You now want to check whether this hypothesis is consistent with the discovered board. If it is, show one possibility of the original arrangement of the letters that aligns with the hypothesis.

A secret society with an undisclosed name was established in the year 1899 by a single founder, whose name is also kept secret. Subsequent members have joined the society through recommendations of existing members.

One unique rule for joining the society has been strictly enforced: Recommendations can be made by one or more existing members, but the same member group can recommend only one new member. For example, if a member was allowed to join upon the recommendation by a group of existing members $$$\{A, B, C\},$$$ no other persons can be allowed by the same recommender group. It is perfectly acceptable, however, for a group $$$\{A, B\}$$$ to recommend another new member. Although the set $$$\{A, B\}$$$ is a subset of $$$\{A, B, C\},$$$ they are distinct sets. For consistency, the group of recommenders of the founder is considered to be the empty set.

Through investigation of this secret society, you have obtained several information fragments representing some part of the membership structure of the society. Each information fragment takes one of the following forms of statements, in which the symbols $$$a, b$$$ and $$$c$$$ are integers designating certain members of the society.

• recommend  $$$a$$$  $$$b$$$ – meaning that the member $$$a$$$ belongs to the group that recommended the member $$$b$$$ to join.
• not-recommend  $$$a$$$  $$$b$$$ – meaning that the member $$$a$$$ does not belong to the group that recommended the member $$$b$$$ to join.
• intersection  $$$a$$$  $$$b$$$  $$$c$$$ – meaning that the group of the recommenders of the member $$$a$$$ is the set intersection of recommender group of $$$b$$$ and that of $$$c.$$$ In other words, all of those who recommended $$$a$$$ also recommended both $$$b$$$ and $$$c,$$$ and all of those who recommended both $$$b$$$ and $$$c$$$ also recommended $$$a.$$$

The obtained information may be partial, that is, the recommendations of some members may be missing, and, moreover, there may be some members not mentioned in any of the statements.

As the information sources are not necessarily reliable, some false information might have crept in. You would like to know whether these statements are consistent, that is, whether there can be a recommendation relationship consistent with all of these statements.

It is well known that two disks on a plane have four distinct common tangent lines when they are disjoint (neither overlapping nor touching).

You are given four lines on the $$$xy$$$-plane. Your objective is to apply parallel translations to these lines so that they become four distinct common tangent lines of some pair of disjoint disks with positive radii. You want to do this with a cost as low as possible, where the cost is defined as the sum of the translation distances. The translation distance for a line is the distance between the lines before and after the translation.

Each line is specified by two parameters, $$$a$$$ and $$$d,$$$ and is defined by $$$$$$x \cos\Bigl( \frac{\pi a}{180} \Bigr) + y \sin\Bigl( \frac{\pi a}{180} \Bigr) = d.$$$$$$ For example, the line with $$$(a,d)=(60,1)$$$ represents $$$x/2 + \sqrt{3}y/2 = 1$$$, since $$$\cos(\pi/3)=1/2$$$ and $$$\sin(\pi/3)=\sqrt{3}/2$$$.

First, determine whether the objective is achievable. If it is, determine the minimum required cost, defined as follows: the minimum value $$$c$$$ such that the objective is achievable with a cost at most $$$c+\varepsilon$$$ for any positive real $$$\varepsilon.$$$ The objective does not have to be achievable with the cost exactly equal to $$$c$$$.