Your friend, Greedy George, visits a candy store for his snacks for the school excursion, grabbing 300 yen in his hand. In the candy store, one item of each different kind of snack is placed in a line on the shelf. After entering the store, Greedy George picks up a shopping basket and starts checking the snacks on the shelf from left to right. If the sum of the prices of snacks in the basket will not exceed 300 yen, he immediately puts the checked snack into the basket. If the sum should exceed 300 yen, he tearfully skips that snack. After examining all the snacks in this manner to the right end, George heads to the checkout.

Given a list of the prices of the snacks in the store, compute how much money Greedy George will spend.

Figure A-1: The first dataset of Sample Input

Two athletes run a long-distance race, but the race is different from usual athletics events. They run for a predetermined duration, and the one who runs longer will be the winner. At every minute after the start, the distances both runners ran in the previous one minute are recorded. You are expected to write a program that, given the record of a race, counts the number of overtakings by either runner during the race. You should assume that both runners keep constant paces for every one minute before their distances are recorded.

Here, the term overtaking stands for the event where the runner previously behind takes the lead. Note that, before overtaking, the two runners may run side by side for a while, during which neither takes the lead. Figure B-1 shows the times and the positions of two runners for the third dataset of Sample Input. The number of overtakings in this case is two.

Figure B-1: The first dataset of Sample Input

A plane is tiled completely with regular hexagons. Each hexagon is called a cell. You can move in one step from a cell to one of its adjacent cells that share an edge. You want to know the minimum number of steps to move from the central cell to the specified cell.

Each cell is specified by a pair of integers. The central cell is $$$(0, 0)$$$. One of the directions perpendicular to the edges of the regular hexagons is defined to be the rightward direction. For each cell $$$(x, y)$$$, its right adjacent cell is $$$(x + 1, y)$$$ and its upper-right adjacent cell is $$$(x, y + 1)$$$. See the figure below.

Write a program that computes the minimum number of steps required to move from the cell $$$(0, 0)$$$ to the cell $$$(x, y)$$$ for given integers $$$x$$$ and $$$y$$$.

Figure C-1: How to specify the cells

A bug that looks like a pill bug is walking on a plane. A Cartesian coordinate system is defined on the plane, in which its $$$x$$$-axis is directed from west to east, while its $$$y$$$-axis is directed from south to north.

The bug is initially at a lattice point (a point where both the $$$x$$$- and $$$y$$$-)coordinates are integers), facing the positive direction of $$$x$$$. Obstacles are placed at some of the lattice points on the plane. The bug continues to move according to the following rules, avoiding obstacles.

• The bug attempts to move from its current position to the adjacent lattice point in the direction it is currently facing.
• If that adjacent lattice point has no obstacles, the bug moves there without changing its direction.
• If that adjacent lattice point has an obstacle, the bug turns 90 degrees to the left, without changing its position.

The initial position of the bug, the locations of the obstacles, and a moving distance are given. You are requested to find the position of the bug after it has moved exactly the given distance.

Some of the datasets in Sample Input are illustrated below. The points marked with an "X" indicate the presence of obstacles. The left figure corresponds to the first two datasets of Sample Input. In these datasets, the initial position of the bug is $$$(0, 1)$$$, and it moves to $$$(1, 1)$$$ and then to $$$(2, 1)$$$. Next, it attempts to move to $$$(3, 1)$$$, but since there is an obstacle there, it turns to the positive direction of y and moves to $$$(2, 2)$$$. The points the bug traverses are shown with orange circles. The right figure shows the next two datasets.

Figure D-1: The first two datasets of Sample Input (top) and the next two datasets (bottom)

A square-shaped plot of land is divided into $$$n$$$ rows and $$$n$$$ columns of square sections by streets extending in the east-west and north-south directions.

You will build one house each on some of these sections. At least one house must be built in every row and also at least one in every column. You then paint each house in one color; there are $$$n$$$ colors available, from color $$$1$$$ to color $$$n$$$.

You are interested in the views from four directions, north, south, east, and west. When seen from one direction, $$$n$$$ frontmost houses can be seen, lined up from left to right. Your goal is to build and paint the houses so that the $$$n$$$ frontmost houses seen from all the four directions are in the same specified color order.

Figures E-1 and E-2 both show examples with $$$n = 4$$$, where the specified color order is $$$1$$$, $$$2$$$, $$$3$$$, and $$$1$$$, from left to right, which correspond to the first dataset of Sample Input. When viewing the plot in Figure E-1 from the south, the color order is $$$1$$$, $$$2$$$, $$$3$$$, and $$$1$$$, which coincides with the specified order. When viewing from the east, however, the order is $$$1$$$, $$$3$$$, $$$2$$$, and $$$1$$$, which is different. Therefore, this example does not achieve the goal. The example in Figure E-2 achieves the goal.

Figure E-1: Inappropriate arrangement	Figure E-2: Appropriate arrangement

For the specified color order, determine whether there exists an arrangement of the positions of houses and their colors that achieves your goal, and if so, provide an example.

You are challenging a game with prizes, which is similar to billiards. This game uses a kind of billiard table, several balls of the same size, and a prize coin. The top of the table has a flat rectangular cloth-covered area bounded by elastic bumpers, called cushions. The balls can move on this area. The cushions limit the moves so that the centers of the balls are restricted to stay within a rectangular area of width $$$a$$$ and length $$$b$$$, called the movable area.

Let the coordinates of the four corners of the movable area be $$$(0, 0)$$$, $$$(a, 0)$$$, $$$(a, b)$$$, and $$$(0, b)$$$. At the start of a game, all the balls and the coin are placed on the table so that their centers are at distinct inner lattice points on the movable area, that is, not on its boundaries. As the balls and the coin are small enough, they do not touch each other unless a ball goes toward the center of another ball or the coin.

The challenger chooses one of the balls, and strikes it with a cue to the direction with an angle of 45 degrees to the edges of the boundary of the movable area. The direction is such that both $$$x$$$- and $$$y$$$-coordinates increase. The struck ball will move straight until it reaches a boundary of the movable area, hits another ball, or drops into one of the holes placed at four corners. When the ball reaches a boundary, it bounces on the cushion at the reflection angle equal to its incident angle and continues its straight move. When it hits another ball or drops into a corner hole, the game is over. If it hits the coin before hitting another ball or dropping into a hole, the challenger will win the coin.

Which ball should you strike to win the coin? You want to know all the balls bringing you the coin.

Figure F-1 depicts the first and the second datasets of Sample Input.

Figure F-1: The first and the second datasets of Sample Input

For the first dataset, when the ball No. 2 is struck, it goes directly toward the coin. The ball No. 4 hits the coin after bouncing on the right-side cushion. As the ball No. 1 hits the ball No. 2, and the ball No. 3 drops in the upper right hole, striking them will not be awarded a coin.

For the second dataset, when the only ball No. 1 is struck, after bouncing on the cushions 5 times, it will pass through its original position, and then after bouncing twice more, it reaches the coin.

As an entertainment after the programming contest, you hold a game event for the participants.

Two sets of cards, red ones and blue ones, are used in the game. Both of the two sets have the same number of cards as the number of the participants, and each card has one integer written on it. It is known that the contents of these two sets are the same; the integers on the red cards are the same as those on the blue cards as multisets. Even though, you don't know what integers are actually written on the cards. The same integer may be written on two or more cards of the same color, and the integers may be negative.

You distributed one red card and one blue card to each of the participants. As the game result depends on the sum of the integers on the two cards distributed to each participant, you asked all the participants to declare their sums.

Your task is to find a possible card distribution consistent with the participants' declarations, that is, a combination of integers on the cards distributed to each participant. Note that such a combination might not exist, as the participants may commit miscalculations. In such a case, report that there is no consistent combination.

Alice is playing a puzzle game where she slides a tile piece to move it to its destination on a rectangular grid board consisting of unit squares. Only parallel moves of the piece on the game board are allowed; no rotations nor lifting up. Some squares on the board are marked no-entry where any parts of the tile piece should not enter.

The tile piece is composed of a number of unit squares joined tightly along their edges. The tile piece is initially placed to touch both the left and the top ends of the board. The goal of Alice is to slide the tile piece to make it touch both the right and the bottom ends of the board.

Bob, on the other hand, wants to make Alice's goal unachievable by changing some squares to no-entry. Each square, except for those initially covered by the tile piece, can be made no-entry by paying the specified number of coins. Compute the minimum number of coins Bob has to pay in total to make Alice's goal unachievable.

You are playing a first-person shooter with your friends. In this game, $$$n$$$ players are divided into two teams fighting against each other. Each player is crowned with a balloon on top of the head, and players try to pop the balloons of the players of the opposing team.

Players are numbered from 1 through $$$n,$$$ which are called the action orders. Also, each player is given a real number called the hit probability. The game consists of $$$n$$$ phases. In the $$$i$$$-th $$$(i = 1, \ldots, n)$$$ phase, the player of the action order $$$i$$$ (the attacker) takes the following action.

• If the balloon of the attacker has already been popped, the attacker is dead and this phase is skipped without any actions.
• If all of the opposing team members are dead, the phase is skipped as well.
• Otherwise, one of the opposing players alive is chosen as the target to attack. The choice may be based on the results of previous actions. The attack succeeds with the hit probability of the attacker, regardless of the target. When the attack succeeds, the balloon of the target is popped, and the target is killed.

The game ends when all of the phases are completed.

You don't want any of the players of your team to be killed. Calculate the probability of keeping all the players of your team alive until the end of the game by optimally choosing the targets. Assume that the opposing players choose their targets at random.