Julia wants to celebrate her birthday in a very special way this year – she wants to invite her friends to an amusement arcade and play all the awesome video arcade games from her childhood with them!

For this purpose she rented a venue with $$$n$$$ arcades where all machines are arranged in one straight line. Some of her friends are very vivid players who tend to scream whenever they manage to beat the game. As this is very distracting for the others, Julia rented a venue that is so large that in case the very first and very last machine is occupied, everyone else can be seated such that there is always exactly one empty seat between any two neighbouring players.

Her friends, however, arrive at the amusement arcade one by one and do not know how many people will come in total. To sit as comfortable as possible, they always choose an arcade that is maximally far away from any other player. In case there are multiple machines that are equally secluded, they choose one of them uniformly at random. After having taken a seat, they will stay there until the end of the party.

As the host, Julia is the first person to arrive at the venue. Now she is wondering where she should take a seat such that all of her friends find an arcade to play and there is exactly one empty seat between neighbouring players once everyone is seated.

This is not a problem about Brexit. Or at least not about the social or economic implications of Brexit. Instead, we – the Grammatical Correctness Policing Committee (GCPC) – want to focus exclusively on the linguistic challenges posed by this combination of the words "Britain" and the noun "exit". We are very concerned about the ambiguity of this construction. When using the term Brexit, it is not clear at all whether it is supposed to refer to to Great Britain or Brazil. Or perhaps Bremen leaving the Bundesliga.

And it's not just Brexit, you might also have heard of "Megxit" (having to do something with the British royal family) and similar constructions.

Looking ahead, we want to avoid a similar disaster in the future. For that purpose we, as a European agency with German roots, would like to implement some standardisation. We have focused on the act of entering. If a subject (a person, an organization, a plant, etc. ) enters (or possibly reenters) something, our leading linguistic scientists suggest we look for the last vowel in the subjects name (a, e, i, o and u are considered vowels). We cut off any letters after this last vowel and add the ending ntry instead. Here are some examples:

• If Britain were to reenter the European Union, we would call it "Britaintry"$$$^{\text{∗}}$$$.
• If Canada were to enter, say, the NWERC region, that would be a "Canadantry".
• And whenever a person named "Paul" enters someplace, we clearly have a "Pauntry".

Given a subject's name, determine how the act of entering should be called for this subject.

Recently, I got into playing the trading card game Wizardry – The Meeting. And since I really wanted to build an awesome deck, I decided to search online for only the best cards. It turns out most of those cards are quite expensive and can only be acquired by insane luck, when purchasing a random set of cards, or by bidding in online auctions. As auctions are a huge time sink and I really rather wanted to play instead of bidding the whole day, I came up with a different idea: A trading card marketplace.

Each card type is produced in bulk, so a buyer does not really care from which seller they buy a specific card. Therefore, the idea is to create one web page for each card type and users can set buy and sell offers. Take the card "Green Mana" for instance. If you wanted to buy one, you could create a buy offer, e.g. for $$$10.00$$$€. This offer means that you are willing to buy the card for $$$10.00$$$€ or less (if there is a seller for less). On the other hand, if you wanted to sell one "Green Mana" card, you could create a sell offer, e.g. for $$$12.01$$$€. This offer means you are willing to sell your card for $$$12.01$$$€ or more (if there is a buyer for more).

Now, every couple of seconds, the website automatically calculates a card price based on both types of offers. It then considers only those offers that are compatible with this price (as described above) and satisfies as many of those as possible.

As an aspiring entrepreneur, I decided that I deserve a cut of every sale happening on the website. But I have a little trouble to come up with an algorithm that determines the price such that the turnover, i.e. the price times the number of successful sales, is as high as possible (which would mean my cut being as high as possible).

— Original message from Zodiac

For one of his first letters he used the following two step encryption scheme.$$$^{\text{∗}}$$$ First, he applied a Caesar cipher which means that he replaced each letter with the one that comes $$$k$$$ steps later in the alphabet, where $$$k$$$ is a fixed number between 0 and 25 inclusive. Note that for this step it is assumed that after z the alphabet starts again with a. In the second step, he cut the message into two parts at an arbitrary position and swapped the parts. It is allowed for one of the two parts to be empty, in which case the message did not change during this second step.

Normally, a simple brute force search could be used to decrypt the message. However, to do this, one needs to automatically check if a message makes sense. Since Zodiac might have made some mistakes during the first step of the encryption, this is not easy to decide.

For this reason, you decided to try another approach. You want to try meaningful candidate sentences and encrypt them and then count how many mistakes would be required to make them match with Zodiac's encrypted message.

It is a lovely summer day, and Alice wants to do a day trip. She lives in Tampere, and wants to travel to Porvoo to enjoy the Old Town and the surrounding nature. Alice does not only love travelling, but also planning.

She has created a map of the most beautiful paths to Porvoo. On her trip she needs to visit $$$n$$$ cities in order, where Tampere is the first city and Porvoo is the last city. The cities are connected by roads, with each road connecting two consecutive cities, and there is always at least one road between each pair of consecutive cities.

When driving from one city to the next, Alice needs to choose which road to take. Some of these roads have a tarmac surface, while others are just gravel roads and some roads have bridges which will not support vehicles that are too heavy. For each road it is known how long it takes to traverse it and what is the maximal weight of vehicles that can safely drive on it.

Illustration of the second sample input. The red path from Tampere to Porvoo is the optimal choice for a car of weight $$$31$$$.

Alice collects many different cars of different weights, but she is not sure yet which car she will use for the day trip. As she wants to enjoy as much time in Porvoo as possible, she wants you to help her find the minimal travel time for each car.

Help the bird Faby to navigate through a sequence of $$$n$$$ pairs of pipes, by finding the shortest line he can fly on to reach his destination. For simplicity, we represent Faby as a single point in the plane and assume every pipe has width zero. This way, the gap between every pair of pipes can be represented as an interval on the $$$y$$$ axis. The bird starts out at $$$s = (x_s, y_s)$$$ and his goal is to reach $$$t = (x_t, y_t)$$$. Find the shortest line from $$$s$$$ to $$$t$$$, passing through all intervals in between in increasing order of their $$$x$$$ coordinates.

Visualisation of the second sample input. The red lines represent the intervals and the black line the shortest possible path. Faby and the black dots are the points in the output. Note that $$$(2, 1)$$$ can optionally be included in the output too.

Your friend Ellie owns a local parcel delivery business called Grid City Parcel Courier (GCPC) which operates in Grid City, a town where all houses are aligned on a rectangular grid of streets. Each house is placed at the intersection of two streets, one running in north-south direction (vertically) and one running in east-west direction (horizontally). There are $$$w$$$ vertical streets and $$$h$$$ horizontal streets, resulting in a $$$h\times w$$$ grid of houses.

To grow her business, Ellie wants to start offering parcel pickup too. However, the mayor of Grid City recently decided that all streets will be one-way streets during the day to combat traffic jams. During this time, the streets of Grid City can only be passed from north to south or west to east, respectively.

Visualization of the grid of one-way streets given in the first sample input.

Ellie already rented a large garage located at the city's northwesternmost intersection, from which her drivers will start their journeys to collect parcels. She asked you to help her figure out how many drivers she needs to hire to collect all parcels during the day and bring them to her logistics center located at the city's southeasternmost intersection.

An upcycled shipping container makes a good site to open a pop-up store in a trendy part of town. Such a business comes with its own risks – for example, this morning a local freight company mistook your premises for one of their crates and sent it to the shipyard for loading.

Your crate is now sitting in the shipyard in one of two stacks ready for loading onto the ship. Each crate except yours has its own tracking number.

Illustration of Sample Input 2. Your business is in the unmarked crate.

The system for loading crates is automated and proceeds in a preset order. First, the crate with the next tracking number is uncovered by picking up all of the crates on top, one-by-one, and moving every single one across to the other stack individually. Then the crate is taken to the ship. Since your crate is not part of this order, it is generally ignored and will not be loaded.

After loading a crate, some time is spent securing the whole cargo on board. This is your chance to recover your container – if it is on top of one of the stacks, you will have just enough time to slide it off and get it back.

How many such opportunities will you have in total?

The epidemiologist W. Andy wants to find the index case of an ongoing crisis. To do this, he modelled the city of the outbreak and its $$$n$$$ residents with a cellular automaton. The city is represented by $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$ and each cell has two neighbouring cells, one to its left and one to its right. The left neighbour of cell $$$i$$$ is cell $$$i-1$$$ and the right neighbour is cell $$$i+1$$$. Additionally, the left neighbour of cell $$$1$$$ is cell $$$n$$$ and the right neighbour of cell $$$n$$$ is cell $$$1$$$. Thus, the city and the corresponding automaton form a simple cycle.

Each cell contains an integer between $$$1$$$ and $$$m$$$ which represents how likely it is that this person is infected. Since the virus can only be transmitted by personal contact, the value in the $$$i$$$th cell on day $$$d$$$ only depends on the values of its neighbours and itself on the previous day. If we denote this value by $$$s_{d}[i]$$$, then the outbreak can be simulated by a function $$$f$$$ using the formula: $$$s_{d}[i]=f\big(s_{d-1}[i-1],s_{d-1}[i],s_{d-1}[i+1]\big).$$$ Note that as the city is cyclic both $$$i+1$$$ and $$$i-1$$$ are calculated modulo $$$n$$$.

Andy wants to find the index case, so he first has to find $$$s_0$$$, the state of the city on day zero. This poses a problem, however, as it is not known on which day the crisis started. Right now, Andy believes that he accomplished the task and found the state $$$s_0$$$, but you are not convinced. Therefore, you want to check if there may be a state previous to the initial state proposed by Andy, i.e. whether there exists any state $$$s_{-1}$$$ that gets transformed into $$$s_0$$$ by applying $$$f$$$.

Lucy is very lazy. Her boss asked her to go to a conference and of course she wants her to go to as many meetings as possible. But Lucy is lazy and so she decides to choose her meetings such that all other meetings overlap with at least one of the meetings she is attending. This way, her boss cannot complain as there is no way for her to attend additional meetings.

While reading the schedule of the conference, Lucy finds out that even with this approach of choosing the meetings there are quite many meetings she has to attend. Luckily, her good friend Max is one of the organisers of the conference and in particular responsible for the timetable. Max is unfortunately not able to cancel meetings or to reschedule them, but he can help Lucy in another way.

Since the meetings are normally boring, nobody will pay too much attention if the topic changes. Therefore, whenever there are two meetings that overlap, he can combine them into a single meeting instead. Two meetings $$$a$$$ and $$$b$$$ overlap if $$$\text{start}(a) \le \text{start}(b) \le \text{end}(a)$$$ or vice versa, and when they are combined the new meeting will start at time $$$\min(\text{start}(a),\text{start}(b))$$$ and end at time $$$\max(\text{end}(a),\text{end}(b))$$$. Max can then repeat this merging process and it is even possible to further combine these combined meetings with other meetings. Non-overlapping meetings cannot be combined as then people would notice that someone is tampering with the schedule.

Lucy now wonders if she can reduce the number of meetings she has to attend with this method. If it is possible, how many such merges are necessary to reduce this number by at least one?

The General Counsel for Peaceful Congregations (GCPC) has a very, very stressful job. Almost every day they are approached by someone who has to organise a meeting whose attendees do not really get along. More specifically, in any group of attendees there may be several pairs of people who are known to dislike each other. Nevertheless people sometimes need to meet, so the general strategy of the GCPC is to split up the meeting attendees into two groups. These groups will then meet in different rooms and GCPC employees will deliver messages back and forth between the two rooms. Let's call these two rooms the East and the West room – for no particular reason. To ensure peaceful and productive meetings, the GCPC assigns people to the East and West room such that no two people in each room dislike each other.

Over time, the process of assigning people to the East and West rooms has become a bit tedious, so you decided to undertake a little experiment. Some of the GCPC's clients schedule the same meeting with the exact same people every year. To keep things interesting, you want to use a new assignment of people to the East and West rooms for each meeting. If the editions of the meeting are numbered starting from $$$1$$$, what is the number of the first meeting where you are forced to reuse an assignment of people that you have already used before? Note that simply swapping the rooms, i.e. assigning the people from the East room to the West room and vice versa, is not considered a different assignment – after all, the same people will meet. Since your investigation will almost certainly only be of an academic nature, you are not interested in the exact value. It will suffice to find the remainder when dividing the result by a given odd prime number $$$p$$$.

You may know the game Where is Waldo?. In this game you need to find a person named Waldo in a crowd of people. This problem is kind of similar. You need to find an axis-aligned rectangle of minimal area which contains the letters W, A, L, D and O and those letters are hidden in a crowd of other letters.

Illustration of the second sample case.

This could be you if you choose poorly. Photo by Armin Kübelbeck, cc-by-sa

However, it turns out that you are the first explorer to find him in over a hundred years, so he has grown incredibly bored. Instead of a fight, he offers to play a game for his artefacts. The hall has $$$d$$$ closed doors, but only one of them leads to the artefacts (Monty knows which one it is, of course). The procedure is as follows:

1. You choose $$$s$$$ closed doors.
2. Monty opens $$$e$$$ doors that were not selected by you and lead to empty rooms.
3. Among the remaining closed doors, you may change your selection of $$$s$$$ doors however you want (you can even stay with your current selection if you wish to).
4. Monty reveals which door leads to the room with his artefacts.

This majestic footpath has the colours red, white, purple and green. SOURCE: Botanical Garden München-Nymphenburg.

You have been given a perfect model of the botanic garden, consisting of $$$n$$$ intersections (numbered from $$$1$$$ to $$$n$$$) and $$$m$$$ footpaths going between those. To keep order, each footpath can only be used in the given direction. Currently, the plants are exhibiting $$$k$$$ different colours (numbered from $$$1$$$ to $$$k$$$) and for each footpath, you are given a list of all the colours that are visible along it when viewed from the intersection where it starts. A user is currently at intersection $$$1$$$ and wants to navigate to intersection $$$n$$$. You can assume that the user will follow the app's directions perfectly, but whenever faced with multiple options (because the given colour is visible along multiple footpaths), you have to assume they will make the worst possible choice. How long will it take to reach the target when your app gives the best possible instructions?