Aliens are visiting Earth and, as usual, they plan to abduct humans for their experiments. In the past, alien abductions have caused a lot of press coverage and wild speculation on Earth. Luckily for them, most people do not believe these stories and think that aliens are not real.

In order to keep a low profile in the future, the Galactic Committee for Person Captures (GCPC) has established rules for abductions. Besides a lot of boring paperwork, the aliens have to prepare the abduction carefully. While they can make multiple trips (in fact, alien travel is so fast in practice that this is not a limitation at all), they must be smart about it so that their secret is not revealed to humans. If aliens want to abduct a person, they are required to abduct all of their friends at the same time, so that no one notices that their friend is missing when they want to hang out. Of course, friendships on planet Earth are bidirectional, that is if Alice is a friend of Bob, then Bob is also a friend of Alice.

In preparation for the trip, the aliens have observed their targets and started taking note of all their friendships. In total, they must abduct $$$n$$$ people, including their friends. Now, they want to book a starship at their local dealership and wonder how much space they need to abduct all $$$n$$$ people. A starship's storage space is measured in terms of the number of people that can be transported simultaneously. What is the minimum storage space required to abduct all $$$n$$$ people?

Brianna is a bookworm. At home, she has a big bookshelf with all her favourite books. She has a large collection ranging from detective novels and science-fiction novels to biographies.

Recently, Brianna has expanded her collection with $$$n$$$ graphic novels. However, the new books currently lie around everywhere and form huge stacks on the floor. In the meantime, one of the shelf boards has collected dust and random household utensils that do not belong there. The new books just lying around have become too much to bear, and Brianna finally decided to put them on this shelf board. To do so, she first has to make room on it.

Visualization of Sample Input 3.

Brianna wants to arrange the books in a single horizontal line without stacking multiple books on top of each other. While the shelf is wide enough to hold all books without problems, it takes time to make room on the shelf. Therefore, Brianna wants to minimize the width of the part of the shelf that she needs to clear.

Each book can be described as a cuboid with three side lengths $$$l$$$, $$$w$$$, and $$$h$$$. Since the room above the shelf board is limited by the next shelf board above it, she can only fit a book vertically if its vertical side length is at most the distance $$$H$$$ between the two shelf boards. Brianna may rotate each book in three-dimensional space as she wants. It is guaranteed that the shelf is deep enough so that the books will not fall off, no matter the orientation. However, all books must stand properly on the shelf board, meaning that every book touches the shelf board along an entire face and not just by an edge.

What is the minimum width of shelf Brianna's books need?

Your university recently established the Graduate Code Plagiarism Control (GCPC) initiative to get hold of the ever-increasing load on the graders for the computer science assignments. Currently, the graders need to check the code of assignments manually for plagiarism. The GCPC aims to simplify this part of the graders' jobs by performing the plagiarism checks automatically.

Code consists of tokens separated by spaces. Tokens are strings of alphabetical letters, numerals, and brackets. If a token consists of only a single alphabetical letter (upper or lowercase), it is a variable in the code.

The GCPC wants the plagiarism checker to compare query pieces of code to a reference code. Specifically, it should check whether each query could have been obtained by selecting a contiguous string of tokens from the reference and consistently renaming variables. Variables are consistently renamed if no two occurrences of the same variable are renamed to different variables, and if no two different variables are renamed to the same variable.

The GCPC has asked you to develop the plagiarism checker.

One cold and foggy night, you walk down a shady alley. There should be a lamp every few metres but none of them seem to work, and in this night, not even the moon enlightens your path. Alone and in the dark, you wonder: "Even if there was a working lamp somewhere, how much would it lighten my way?". Now, back at home, you want to calculate this.

The alley can be modelled as a line with a length of $$$n$$$ metres. The fog has a uniform density and reduces the light of a lamp by a factor of $$$1-p$$$ every metre. The brightness at one point is the sum of the light that reaches this point from every lamp. You want to calculate this brightness at some points after placing some lamps.

As every Saturday, Eve is paying her local game club a visit. Today, Bob has brought a new game he has designed on his own. After thorough investigation, you claim that there exists a dominant strategy, so one player can always win. Bob is hesitant to accept that his game is boring to play, so he challenges you to play a round! Since you claim that there exists a dominant strategy, you may determine who begins the game.

The cards in the two sample interactions.

The rules are as follows. There are $$$n$$$ cards on the table, each containing a maths operation (+ or *) and an integer, as shown in Figure above. Eve and Bob alternate picking cards to manipulate a common number using one of the cards. For instance, if the current value of the number is $$$5$$$, and the card says $$$+3$$$, then the value gets updated to $$$8$$$. Each card can only be used once, and the game ends when all the cards have been used. The player who makes the first move wins if the final number is odd, and the other player wins if the final number is even. Given the list of cards and the starting value, help Eve win the game.

The interactor begins by outputting the starting state of the game in the following format:

• One line with an integer $$$n$$$ ($$$1 \le n \le 300$$$), the number of cards.
• $$$n$$$ lines, each with a character $$$o$$$ and an integer $$$x$$$ ($$$o \in \{$$$'+'$$$, $$$'*'$$$\}$$$, $$$1 \le x \le 10^6$$$) indicating one of the cards.
• One line with an integer $$$x$$$ ($$$1 \le x \le 10^6$$$), the starting value.

Then, your submission must output one of "me" or "you", depending on if you want to go first or you want the interactor to go first.

Then your submission and the interactor alternate outputting cards in the same format as above. No card can be played more than once. Your submission must exit when all cards have been played, regardless of which player made the last move.

Your submission will be accepted if it follows all the rules above and the final value has the parity indicated on the first line of your output.

Make sure you flush the buffer after each write.

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

Frida's birthday is just coming up, and as her best friend, you obviously baked a cake for her. Since you know that Frida loves rotational symmetry, you thought to bake a cake that looks the same from above when rotated by $$$180^\circ$$$. Of course, you could have simply baked a boring round cake, but without a perfectly round cake tin, this sounds easier than done. Therefore, you decided to bake a cake whose shape can be described by straight line segments.

Visualization of Sample Input 2. The swirly cake looking like an S can be cut into the red and blue part with a single cut.

However, after you are done with your cake, you notice that you also want to cut the cake into two equal pieces, one for Frida and one for yourself. More precisely, you wonder if it is possible to cut the cake along an infinite line such that it splits into exactly two parts of equal weight. You can assume that the cake has uniform density and height.

Pentominous is a grid logic puzzle based on the twelve pentominoes. A pentomino is a polygon formed by connecting five equal-sized squares edge to edge.

The twelve pentominoes (up to mirroring and rotations) and their names.

The goal of this puzzle is to divide a grid into regions of size $$$5$$$ (that is, pentominoes), so that no two regions that share a side have the same shape. You are allowed to rotate and mirror the pentominoes, but such rotations and reflections count as the same shape. The twelve possible shapes can be seen in Figure above.

In a normal Pentominous puzzle, the player is given some pre-filled cells, for which the shape of their region is already predetermined. In this problem, you are working with a completely blank grid of dimensions $$$h\times w$$$, and your task is to create any valid arrangement of pentominoes.

The German ICPC scene is widely considered one of the most competitive. At least, that's what we tell our students. Countless rivalries form a complex web of envy, despair, glory, and triumph woven around and manifested in the unrelenting echoes of two scoreboards – Winter Contest and GCPC. While generations of participants tend to forget the grudges of their predecessors, we coaches, acting as timeless beacons of continuity, preserve these petty conflicts between long forgotten teams. Striving for perfect balance, we express our dedication to our coaching duties in a furious outcry on social media against every unfair news article. That is, a coach gets mad if a news article is published that contains a rival university name more often than their own.

To smoothen the waves of conflict in this ocean of rage, a newly appointed authority is tasked with proofreading media coverage of GCPC and Winter Contest to prevent uneven coverage.

Physics can be so much fun! Yesterday, your teacher explained how interference works: If you have two waves, their heights add up over the whole waves' length! So if both waves have a peak, the resulting peak will be even higher. Likewise, if both waves have a wave trough below the water surface, the resulting wave has a trough that will be even further below. Technically, a wave's height is called amplitude and the distance between two wave peaks is called wavelength.

Today, your physics teacher describes the setup of an experiment she is about to perform. She will create stationary waves in a one-dimensional container of water. Due to her superior control over physical elements, all waves will have a precisely controlled amplitude and will only be created in an interval of given length. The wavelength of each wave is always $$$4$$$ and the first positive peak will always be at the first index of the interval. We only measure the wave's amplitude at integer points. For example, a wave with amplitude $$$2$$$ and length $$$9$$$ can be described as 2 0 -2 0 2 0 -2 0 2. If there is no wave at a point, the amplitude is $$$0$$$. Your task is to predict how high the resulting wave will be at given points in the container taking into account all the waves that were created up to that point.

Julia is preparing a present for James. She will give him some of her $$$n$$$ jigsaw puzzles, where puzzle $$$i$$$ ($$$1 \leq i \leq n$$$) consists of $$$x_i$$$ pieces and has a difficulty $$$y_i$$$ (can be negative if the puzzle is very easy).

James is already very excited and would like to know in advance what he will get. Therefore, he used some of his criminal energy to gather information about the gift. In particular, he has managed to obtain an encrypted message containing the total difficulty and total number of pieces of all the puzzles that he will receive.

Now he wonders whether it is worth spending some more time to decrypt the message. After all, it might be that this information is not enough to uniquely determine his gift. Since he was never good at these computer thingies, James asked for your assistance. Help him find out whether it is worth decrypting the message or not. If the answer is negative, you have to find two distinct gifts that result in the same encrypted message.

Karen has a beautiful precious glass object on the shelf in her living room. Unfortunately, her cat Klaus does not like it when there is stuff on his favourite shelf. Everything that is not bolted or glued in place, he will gradually push over the edge while looking Karen straight in the eyes.

Now, Klaus' paw slowly executes his diabolical deed. His cute fluffy face radiates inadvertent innocence. Knowing that any intervention would only delay the inevitable, Karen wonders what will happen to the string her sister Kim wrote on the precious glass object. After all, it took Kim a whole week to gather all the bdpq letters that make up the string.

Can you describe to Karen what the string will look like from her point of view while it tumbles towards destruction?

While falling off the shelf, Karen's precious glass object is subject to the following transformations, described as seen when looking at the object from the front.

• h: horizontal flip, e.g. bbq becomes pdd
• v: vertical flip, e.g. bbq becomes ppd
• r: 180-degree rotation, e.g. bbq becomes bqq

No flips along or rotations about any other axes are possible.

Every Sunday is laundry day, and there is always a huge pile of clothes waiting to be washed, which is certainly going to take you forever. You are particularly annoyed by how careful you have to be when washing certain items, and how important it is that you choose an appropriate washing programme for each item.

Fortunately, your washing machine is quite old and only supports three different washing programmes: A, B, and C. You can put at most $$$k$$$ items in one load, and each load can be washed using one of the programmes.

Some items are easy to care for, and you can put them in any load you like. More delicate items must not be washed using a specific programme, but the other two are fine. Of course, the worst clothes are the ones for which only one programme is appropriate.

You have already sorted the items into seven piles by putting items together for which the same combination of programmes is fine, so you know how many items are in each pile.

What is the minimum number of loads you need to wash?

Illustration of Sample Input 2 with an optimal solution. The figure on the left shows seven piles, one for each combination. The figure on the right shows a (possible) optimal solution, where each pile is washed in one load. The numbers on the pile represent how many items of each combination are washed with this load. In particular, the leftmost pile is washed using programme A, the two piles in the middle with programme B, and the two piles on the right with programme C. Thus, we need five loads to wash all items, which is optimal since we have $$$15$$$ items in total.

Shortly before the concert starts, you notice that your piano is completely out of tune! Having the ability of relative pitch, you are able to discern the difference between the pitch of any piano key to the first piano key. While this does not help you find the absolute pitch, you decide to at least tune the keys relative to each other. To do this, you need to make sure that the pitch of each key is exactly one higher than the key before it and one lower than the key after it. As the concert will start shortly, you need to minimize the total tuning effort, which is the sum of the absolute changes in pitch you apply to each key. For example, the picture below illustrates a solution for Sample Input 3, resulting in a total tuning effort of 23.

Visualization of Sample Input 3.