Åke has heard that there may be some suspicious 5G radiation in his city. To test this, he uses the antenna on his roof to measure the 5G level each day. However, he does not know how he should analyze the data.

We are given the measurements for $$$n$$$ consecutive days as a list of numbers $$$x_1, \ldots, x_n$$$ (where $$$x_i$$$ denotes the measurement for day $$$i$$$) and a constant $$$c$$$ that measures how much Åke expects the radiation to vary from day to day. We want to find, for each day $$$i$$$, the most significant difference between the measurement on day $$$i$$$ and any earlier day, after the expected variations are taken into account. More precisely, the goal is to find the maximum value of

$$$$$$|x_i-x_j| - c \cdot |i-j|$$$$$$

where $$$j \le i$$$. I.e., we want to find a large difference in 5G level that has happened recently.

Selma is visited by her two grandchildren Elsa and Asle who love chocolate. To be precise, they are especially fond of the brand Nut Cream Puffed Chocolate that comes in bars made up by $$$6 \times 6$$$ squares. The bars can be broken along the valleys between squares into smaller rectangular bars of integer dimensions. Due to the fragile nature of this type of chocolate, the bars often break into smaller rectangular bars even before you unpack them (but still only of integer dimensions).

Thus Selma finds herself with a set of rectangular bars of various dimensions in her candy stash. She knows how important it is to be fair to children, so not only does she want to give Elsa and Asle the same amount of chocolate, but also identical collections of rectangular bars (where an $$$a \times b$$$ bar is considered identical to a $$$b \times a$$$ bar). To do this, Selma can break her bars into smaller pieces. A break is the operation of taking an $$$a\times b$$$ bar and breaking it along a valley to produce two bars of dimensions $$$c\times b$$$ and $$$(a-c)\times b$$$, for some integer $$$c\in [1,a-1]$$$, or two bars of dimensions $$$a\times d$$$ and $$$a\times (b-d)$$$, for some integer $$$d\in [1,b-1]$$$. See Figure B.1 for an example.

Figure B.1: Explanation of Sample Input 1. First make a vertical break as shown on the $$$3 \times 5$$$ bar (orange), then make a horizontal break on the newly created $$$3 \times 2$$$ bar (blue). This way Elsa and Asle can each get one $$$1 \times 2$$$, one $$$2 \times 2$$$, and one $$$3 \times 3$$$ bar, in total $$$15$$$ squares each.

With lifted restrictions, the border trade between Norway and Sweden will surely be back to its former glory. But the authorities are worried that this will also mean an increase of illegal smuggling of goods. The customs authorities of Norway and Sweden must cooperate to prevent this from becoming too big of a problem.

To pass through the customs, one must visit a series of checkpoints, the Nordic Customs and Passport Control. There are $$$n$$$ checkpoints in total, numbered from $$$1$$$ to $$$n$$$, where $$$1$$$ is the entrance and $$$n$$$ is the exit. There are $$$m$$$ pairs of bidirectional roads that connect distinct checkpoints. The $$$i$$$th checkpoint takes some amount of time $$$t_i$$$ to pass through, and this is the bottleneck in crossing the border (the time it takes to walk the roads is negligible).

Each checkpoint can be watched by one customs unit, either a Norwegian one or a Swedish one. There are $$$k$$$ Norwegian customs units available, and $$$n-k$$$ Swedish units. When a road has both of its endpoints watched by customs units from the same country, any smugglers using that road will be caught. Smugglers are of course always in a hurry, and will always attempt to go from $$$1$$$ to $$$n$$$ in as short amount of time as possible.

Your task is to decide where to put the $$$n$$$ customs units, so that any smugglers who take a fastest possible route from $$$1$$$ to $$$n$$$ will be caught.

You find yourself on a remote island, searching for a legendary lost treasure. However, despite having gotten your hands on directions leading straight to the treasure, you have a problem. It turns out you have a saboteur in your expedition, and that at some point they edited the precious directions so they might no longer lead to the treasure.

The island can be viewed as a rectangular grid, and the instructions are a sequence of east/west/north/south steps to take in this grid, from a given starting position. These instructions lead straight to the treasure (but may involve walking around obstacles) in the sense that there is no shorter way of reaching the treasure. However, the saboteur has arbitrarily replaced each step of the instructions by a step in one of the other three directions. In other words, any "west" step has been replaced by "east", "north" or "south". This replacement has been done independently for each step, so one "west" may have been replaced by "north" and another by "south", and so on.

Because of this sabotage, the instructions seem pretty useless. But maybe they can still be used to narrow down the search. Write a program to find all possible locations of the treasure.

Alice wants to send $$$n$$$ messages to Bob over a communication channel. The $$$i$$$th message takes $$$t_i$$$ time steps to send. At each integer time step, Alice can start sending any number of her messages. Once started, a message must be transmitted in its entirety (it cannot be paused and resumed later). Any number of messages can be sent in parallel over the channel without affecting the transmission time of individual messages.

An attacker has the capability to disable the security protocols of the channel for an interval of $$$x$$$ continuous time steps, but only once (i.e., after doing this, they cannot wait a while and then disable it for another $$$x$$$ time steps). While the security is disabled, the attacker is able to listen in, and any message that is sent in its entirety during those $$$x$$$ time steps is considered exposed.

What is the minimum time needed for Alice to send all $$$n$$$ messages to Bob so that at most two messages are exposed, no matter when the attacker chooses to disable the security?

Figure E.1: Left: Illustration of a solution to Sample Input 1. Right: sending the message of length $$$4$$$ a time step earlier would not be a solution, because the three messages of length $$$6$$$, $$$4$$$, and $$$3$$$ would then be exposed to an eavesdropper listening in from time step $$$5$$$ to time step $$$15$$$.

Your friend Ómar's favourite video game is Striker-Count. But he has now grown tired of actually playing the game and is more interested in the lootboxes found in the game. This activity amuses Ómar, but does not interest you in the slightest. You are more interested in the numbers: you know that each lootbox Ómar opens has probability $$$p$$$ of containing an item of highest rarity, independently for each lootbox. You want to find the expected number of lootboxes Ómar will open before concluding his process.

This year, there have been unusually many UFO sightings reported. Nobody knows if they are caused by optical illusions, weather phenomena, or secret technology being tested by foreign powers (terrestrial or not). UFO enthusiasts across the world rejoice, and speculations run wild. But someone who is not impressed is the farmer Celeste. Her large grain field has repeatedly been used as a landing site by the UFOs, destroying her crops. Celeste would like to bring whoever is responsible to justice, but before she can do so she must assess the damage caused by the unidentified flying offenders.

In total $$$n$$$ circular UFOs have landed in Celeste's field. The $$$i$$$th one left a crop circle which destroyed all crops within radius $$$r_i$$$ of the point $$$x_i, y_i$$$. The field is very large, so you can assume that it extends infinitely in all directions. Your task is to estimate the total area of crops destroyed by the UFOs. Celeste only needs a rough estimate of the true answer, and your answer will be counted as correct if its relative error is less than $$$10\%$$$.

A certain large unnamed software development company has $$$n$$$ developers. The productivity of each coder working for the company has been rigorously measured in terms of two key performance indicators: the number of lines of code they write per hour, and the number of bugs they fix per hour.

When a project needs to be done, the manager in charge of the project is allocated some budget of $$$t$$$ man-hours of programmer time. The manager can then staff different coders on the project, up to a total of $$$t$$$ hours. For instance if there are three programmers, the manager can allocate any non-negative real numbers $$$t_1$$$, $$$t_2$$$, and $$$t_3$$$ hours of their respective work hours, as long as $$$t_1 + t_2 + t_3 \le t$$$. If the three programmers write $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$ lines of code per hour, a total amount of $$$t_1 \cdot l_1 + t_2 \cdot l_2 + t_3 \cdot l_3$$$ lines of code will then be written for the project. Similarly if they fix $$$b_1$$$, $$$b_2$$$, and $$$b_3$$$ bugs per hour, a total of $$$t_1 \cdot b_1 + t_2 \cdot b_2 + t_3 \cdot b_3$$$ bugs will be fixed.

Due to the uncertain economy, the company has a hiring freeze, meaning that no new coders are hired to the company. However, under certain conditions, a manager is allowed to bring in outside help by outsourcing a project to an external consultant rather than doing it in-house. But this is only allowed if it is not possible to do the project equally efficiently in-house. In particular, if the consultant writes $$$\ell$$$ lines of code and fixes $$$b$$$ bugs in $$$t$$$ hours, and there exists some allocation of our existing coders which would write at least $$$\ell$$$ lines of code and fix at least $$$b$$$ bugs in at most $$$t$$$ hours, then a manager is not allowed to hire this consultant (regardless of whether those existing coders would actually have time to work on the project or whether they are already too busy with other projects).

While no new coders are hired, employees do sometimes decide to leave the company. Given a chronological list of events – requests to use a consultant, and employees quitting – find out which of the requests will be approved.

Gustav is an astronaut on the Nordic Celestial Planetary Craft (NCPC), a large space station in orbit around Mars. Today, one of Gustav's tasks is to look over the satefy routines on board.

The space station consists of $$$n$$$ modules arranged in a circle, so that module $$$i$$$ is connected to module $$$i+1$$$ for $$$i = 1 \ldots n-1$$$, and module $$$n$$$ is connected to module $$$1$$$. Each module $$$i$$$ has a non-negative integer type $$$a_i$$$, representing the kind of equipment that can be found there. Different modules can have the same type. In case of emergency, the equipment must be rearranged so that each module $$$i$$$ instead gets type $$$b_i$$$, for some list $$$b_1, b_2, \cdots, b_n$$$. Here, the list $$$b$$$ is a rearrangement of the list $$$a$$$.

Gustav has noticed that if some module connections are severed, causing the space station to split into separate parts, it may become impossible to perform this rearrangement of the equipment. He decides to estimate how likely it is that the safety routines can be followed, by calculating in how many ways the space station can be separated into two or more parts such that it is still possible to rearrange the equipment according to the emergency procedures.

In other words, your task is to count in how many ways the circular list $$$a$$$ can be partitioned into at least two non-empty contiguous intervals, in such a way that the circular list $$$b$$$ can be obtained by rearranging elements within each interval. Since this number can be quite big, you should find its remainder modulo $$$10^9+7$$$.

For example, consider Sample Input 1 below. Here the list $$$a$$$ could be split into $$$[1 | 2 2 3 | 4]$$$, indicating that the connection between modules $$$1$$$ and $$$2$$$, and the connection between modules $$$4$$$ and $$$5$$$, are severed. Note that the connection between module $$$5$$$ and $$$1$$$ remains in this split. The second possible way in which $$$a$$$ could be split is $$$[1 2 | 2 | 3 4]$$$.

In Sample Input 2 below, the only possible way to split the list $$$a$$$ into at least two non-empty parts is to separate the two modules. But then it is impossible to rearrange the parts to create the list $$$b$$$. Hence, the answer is $$$0$$$.

Like so many good stories, this one begins with a claim that Kari is a faster runner than Ola, who of course challenges Kari to a run-down. Dubbed (rather ironically) Non-Competitive Pace Challenge, they want to see who can run the furthest in a certain amount of time $$$t$$$. Clearly they both choose to run in straight lines with constant speed.

Kari wrote an app to make sure that Ola does not cheat, but the app requires that their phones constantly communicate over Bluetooth.

After their run, Kari needs to ensure that they were never too far apart from each other at any time during the run. Write a program that computes the maximum distance between Kari and Ola at any point during the run.

Sonja the scout is taking a test to see if she knows all the knots a scout is supposed to know. The Scout's Big Book of Knots has descriptions of $$$1\,000$$$ different knots, conveniently numbered from $$$1$$$ to $$$1\,000$$$. For the test, Sonja needs to learn a specific set of $$$n$$$ of these knots. After some intense studying, she has learned all except one of them, but she has forgotten which knot she does not yet know.

Given the list of knots Sonja needs to learn, and the ones she has learned so far, find the remaining knot to learn.

There are two different species of periodical cicadas that only appear from hibernation every $$$13$$$ and $$$17$$$ years, respectively. Your old grandpa tells you that he saw them simultaneously back in '92. You start pondering how many years you have to wait until you see them again. You collect information about other pairs of periodical cicadas and when they were last observed to find out when the next simultaneous appearance is.

Given several different pairs of cicadas and their last simultaneous appearance, find the next year that one of the pairs reappears.

A marathon race is being planned in the beautiful countryside. The course will be somewhere along a long, bidirectional, road. The organizers want to determine exactly where along this road the race should be in order to maximize the experience for the runners, so that they get to enjoy as much beautiful scenery as possible and are distracted from their tired limbs. The scenery varies in beauty depending on where on the road you are, and also in which direction you are running. Because of this, the organizers are fine with having the runners make up to two U-turns, as long as no part of the road is used more than once in each direction.

We model the road of length $$$m$$$ meters as a rectangular grid of size $$$2 \times m$$$, where each cell has a non-negative "beauty" value associated with it. The columns represent each meter of the road ordered from start to to end. The top row in a column represents the beauty for this part of the road when running in the direction towards the end of the road, and the bottom row in a column represents the beauty when running towards the start of the road. A race of length $$$x$$$ is then some set of exactly $$$x$$$ of the cells in the grid. Those $$$x$$$ cells must form a path in the grid where no cell is visited more than once, we only move to the right or down from cells in the top row, and we only move to the left or up from cells in the bottom row. See Figure M.1 for an example race. The "total beauty" of a race is the sum of the beauty values of the included cells.

The road is long, so rather than providing a list of all of the $$$2m$$$ beauty values, each side of the road is divided into a small number of segments, where the cells within a segment have some constant beauty value (and cells with beauty $$$0$$$ are simply omitted).

Figure M.1 Illustration of Sample Input 1. The numbers in the cells indicate the beauty value for each meter of the road (with omitted values being $$$0$$$). The highlighted cells and arrows mark the optimal race, involving two U-turns.