It is finally time to submit your essays on economics for assessment!

Each essay is characterised by its word count $$$w$$$ and its quality $$$q$$$. The required word count is $$$W$$$, so the closer $$$w$$$ to $$$W$$$ is in your essay, the better mark you may expect. And, surely, the higher the quality, the better. However, one essay can have a better quality and a bigger deviation from $$$W$$$ than another, so it is not clear which one is better.

As an economics student, you may know that this kind of situation is captured by Pareto dominance. Formally, essay $$$A$$$ is said to dominate essay $$$B$$$ in the Pareto sense if $$$|w_A - W| \le |w_B - W|$$$, $$$q_A \ge q_B$$$, and at least one of these inequalities is strict.

The professor is known to use this relation to mark the essays. First, she finds all the best essays: those that are not dominated by any other essay. These essays receive the same mark, which is the highest among this year's students (but still can fall below their expectations!). Then she removes the marked essays and repeats the procedure, but the mark will be lower this time, and so on. More precisely, she uses the following algorithm:

• All the essays are numbered from 1 to $$$N$$$.
• Each essay can be either in work, postponed, or marked. Initially, all essays are in work.
• A variable $$$r$$$ captures the rank of an essay, the lower, the better. Initially, $$$r \gets 1$$$.
• While there are any essays that are in work:
  • Iterate over all essay numbers from 1 to $$$N$$$. If the $$$i$$$-th essay is in work:
    • Iterate over all essay numbers from $$$i+1$$$ to $$$N$$$. If the $$$j$$$-th essay is in work, compare essays $$$i$$$ and $$$j$$$ for dominance:
      1. If $$$i$$$ dominates $$$j$$$, turn $$$j$$$ into postponed.
      2. If $$$j$$$ dominates $$$i$$$, turn $$$i$$$ into postponed and break the loop.
    • If the $$$i$$$-th essay is still in work, it receives rank $$$r$$$ and turns into marked.
  • All postponed essays become in work again.
  • The rank is increased: $$$r \gets r + 1$$$.

You are afraid that you, and everyone else, will get low marks, but someone told you that if it took the professor too long to perform the entire assessment, the department would take it over, and the final marks would be based on a simple multiple-choice quiz. By rigorous computations you found out that the number of essay comparisons should be at least $$$N^3 / 20$$$ for this to happen. Find the way to disrupt the assessment procedure.

The Bulgarian city of Nodnol runs a boat service to ferry its residents between the trendy areas in which they live and the large metallic structures in which they work on the next recession.

TFN (Transport For Nodnol) has issued $$$m$$$ travel cards (known affectionally as "Retsyo"), which are numbered from $$$1$$$ to $$$m$$$. Each pier has a card terminal at which passengers are required to tap "in" when starting the trip and to tap "out" when finishing it.

As there is only one card terminal on each pier, passengers use the same device to tap in and to tap out.

Trip cost depends on the distance travelled and is determined as follows:

• if the trip started at the pier $$$i$$$ and finished at the pier $$$j$$$ ($$$i \ne j$$$), then its cost is $$$|i-j|$$$ pounds;
• if the trip started somewhere and was not finished with a tap out, then it costs £100;
• if the trip started and finished in the same place, then it also costs £100, as it is interpreted as an attempt to game the system.

You are given a sequence of tapping events — for each you have the pier $$$p_i$$$ and card number $$$c_i$$$ recorded. You are to determine how much the transport authority should charge each of the cards

You are putting up an event space in Nottingham's Sherwood Forest by erecting a fence in a circular-shaped clearing you found that is exactly one kilometre in radius. You will put some fence posts in the trees around the edge of the clearing and then connect them together with fencing later.

You would like to put the fence around as much of the event space as possible. However, the ground is only suitable in a few places around the border, and you only have so many fence posts to put in the ground, so you'll have to choose carefully if you want to maximise area.

An illustration of using 4 posts to capture the maximum area in sample input 1.

Knowing the safe places to put fence posts, and the number of posts you have, what is the maximum area of clearing you can enclose?

Gry finally becomes the Executive Courier Officer in "Universe Express". He has $$$n$$$ subordinate couriers with some delivery strength $$$f_i$$$. The delivery strength of a team of three people is the median of their strength, i.e., the middle element after the sorting. Please help Gry to split the couriers into $$$k$$$ teams of three people in order to maximize the total delivery strength of "Universe Express". The total strength is the sum of the strength of these $$$k$$$ teams.

Elisabeth the Efficient, a famous magician, was called by Emmanuel the Empowered, the mighty lord of the East Embarkmentlands, to enhance the magical protection of his enchanted fortress.

After arriving at the site and studying the structure of the fortress and the existing spells that protect its integrity, Elisabeth found out the following properties of the spell to design:

• it should consist of symbols taken from the string $$$s$$$;
• all symbols should be unique;
• the strength of the spell depends only on which symbols are chosen, but not on their order;
• if symbols $$$s_i$$$ and $$$s_j$$$, $$$i \le j$$$, both exist in the spell, then its strength increases by $$$d_{i,j}$$$.

For instance, if $$$s=\texttt{ABC}$$$ and

$$$$$$ \begin{equation*} d = \left(\begin{array}{ccc} 1 & -1 & 2 \\ - & 2 & -3 \\ - & - & 1 \end{array}\right) \end{equation*} $$$$$$

then a spell A has strength 1, ABC has strength 2, and AC has strength 4.

However, the problem appeared to be too difficult to Elisabeth, because she has only little experience of working with computers. Can you help her to find the strongest spell?

Gry has started to use the new Expify song streaming platform. Since, Gry does not want to spend money Expify forces him to listen to advertisements. An advertisement can be played only after some song (it cannot be played in the middle) and only if the time from the end of the previous advertisement is at least $$$c$$$ seconds.

Gry has a circular playlist with $$$n$$$ songs where the duration of the $$$i$$$-th song is $$$d_i$$$ seconds. He wants to minimize the number of advertisements, so, he wants to find out how many advertisements will be if he starts listening to his whole playlist from $$$i$$$-th song, i.e., the circular playlist stops playing after $$$n$$$ songs.

We suppose that there is an advertisement right before Gry starts listening. Neither this advertisement nor the one, after the playlist stops, count.

Glaciers are vast rivers of slowly-flowing ice, fraught with crevasses which hide under thin layers of snow and wait for unsuspecting walkers to step into and fall in. To reduce the danger, hikers usually go in teams tied together with a thick rope to reduce the consequences of a fall–if one person falls in, the other person may yet hold them from a safe distance.

Today, you are roped up to cross a glacier with your partner. Your plan is to follow the exact same route, at the same speed, the first starting earlier and the second beginning to trace steps once you are exactly $$$x$$$ metres apart. Were you to follow a completely straight path, you would thus then remain exactly $$$x$$$ metres apart at all time.

An illustration of the path taken in the 2nd sample case, taken from above. This could also be a particularly festive diagram of someone falling into a crevasse.

However, the twisting nature of the course as you avoid obstacles means that you may not always remain exactly $$$x$$$ metres apart. What is the closest that you shall actually come while both of you are walking on the path?

Algorithms and data structures find their place in various arts, crafts, and sciences. In this problem, we are discussing one potential application in history.

Historians are studying the urban development of a city over a period of $$$n$$$ years. The urban development is quantified using an aggregate measure they call an urban development index (UDI), which could take integer values, including negative. There is an initial estimation $$$e_i$$$ of this index for each of the years. However, during the research process, due to the new documents and evidence discovered, these estimates are revised and updated. More formally, throughout the historians' work process, they could want to update the UDI estimates for all years between $$$s_j$$$ and $$$f_j$$$ (inclusive) by adding $$$d_j$$$ to each of them.

The main question historians are interested in is if the UDI has been increasing over a certain period of time. However, due to the noisy nature of estimates, we will not be using the standard definition. Instead, the following procedure is used:

• we collapse all consequent equal numbers into one. For instance, 1 1 2 2 2 3 3 3 becomes 1 2 3;
• the UDI is considered increasing from year $$$i$$$ to year $$$j$$$ if the sequence of local minima in the UDI sequence after the above transformation is strictly increasing. An element $$$p_i$$$ is considered to be a local minimum if it is less than both of its neighbors (one neighbor for the first or last element).

You are to implement the system able to store the UDI estimates and process the requests to update them and to check if the UDI has been increasing over a certain period.

When you arrive into a new country, one of the first questions is "can I charge my phone here?". Nowadays, the question of voltage is often secondary, as modern IT equipment is mostly voltage insensitive. The shapes of outlets and plugs, however, are still a problem.

In this problem we give you descriptions of electrical plugs and sockets, and you must determine whether one can insert such a plug into such a socket. In our simplified world, each plug pin is a cylinder, and each socket hole is cylindrical too. Since sockets have springs to ensure a tight contact, the diameter of a pin may be smaller than the diameter of the matching hole. We also neglect pin lengths and hole depths, so both plug and socket are described by three circles.

In both, the plug and the socket, one of these three circles corresponds to the earth wire, so they have to match. The other circles represent different power phases, and since most countries use alternating current (AC), the corresponding plug pins are allowed to match the socket holes in either way.

Given the descriptions of a plug and a socket, is it possible to insert this plug into this socket?

An illustration for the second sample test comes below.

The socket	The plug	How to insert the plug

You are making an international trip with several stops to blow off steam and celebrate your progression onto the NWERC. Since your flights are often booked with low-cost airlines, you always run the risk of your flights being cancelled last minute leaving you stuck in the airport. Normally this is no problem—take the next flight—but you have to arrive at the NWERC on time.

If any one of your flights is cancelled at the same moment you are about to depart, and all others operate as planned, you will book a new itinerary from there to your final destination. Assuming you always plot the fastest route, by how much will you be delayed in the worst case?

You are developing the scheduling module for the new operating system. This module takes $$$n$$$ tasks to be executed and the dependencies between them and then puts them in a certain order for execution.

More formally, there are $$$n$$$ tasks numbered from $$$1$$$ to $$$n$$$. You are also given $$$m$$$ dependencies numbered from $$$1$$$ to $$$m$$$; $$$i$$$-th of them is described by two numbers — $$$a_i$$$ and $$$b_i$$$, meaning that the task $$$a_i$$$ should be executed before the task $$$b_i$$$.

In some cases, there are cyclical dependencies — situations when according to the dependencies given some task $$$t_1$$$ should be executed before $$$t_2$$$, $$$t_2$$$ before $$$t_3$$$, ..., and $$$t_{k-1}$$$ before $$$t_k$$$ and $$$t_k$$$ before $$$t_1$$$. Cyclical dependencies create a problem for scheduling, so you decided to remove some of the given dependencies in such a way that the resulting set does not contain any cyclical ones.

However, you still need to keep at least $$$m/2$$$ original dependencies to preserve some of the original information. You are to write the program performing this task.

In a computer game units are described by their health $$$h$$$, damage $$$d$$$, and time to reload $$$t$$$.

When such a unit fires a missile at an opposing one — the opponent's health is decreased by $$$d$$$ $$$0.5$$$ seconds after the missile is fired. The time between consecutive missile launches for the same unit should be at least $$$t$$$ seconds.

For simplicity, we assume the missile supply to be infinite for all units in the game.

Two players — one controlling a unit with health $$$h_1$$$, damage $$$d_1$$$ and time to reload $$$t_1$$$, and the second with a unit described by $$$h_2$$$, $$$d_2$$$ and $$$t_2$$$ — have engaged in a fight in this computer game. Both units are fully reloaded at the beginning of the fight and can fire missiles immediately.

The unit is destroyed when its health becomes zero or negative. A player wins if there is a moment in time such that the opponent's unit is destroyed, while theirs is not.

Since it takes 0.5 seconds for a missile to reach its target, it is possible for both units to fire missiles at the same time and ultimately destroy each other.

You are to determine who wins in case both players act optimally.

A guy named Gry found a new game called "Mini-Tetris 3023". This small version of Tetris is played on a very long grid only $$$2$$$ cells high and has just three types of tile:

• A square made out of $$$4$$$ tiles in a $$$2 \times 2$$$ grid.
• An S-tile made out of $$$4$$$ tiles, $$$2$$$ on one row and $$$2$$$ slightly offset on the other
• A corner made out of $$$3$$$ tiles, $$$1$$$ on one row and $$$2$$$ on the other

Tiles may be rotated $$$0$$$, $$$90$$$, $$$180$$$, or $$$270$$$ degrees to fit amongst each other, however, they cannot overlap or go outside the vertical boundary of the grid.

This game provides $$$a$$$ squares, $$$b$$$ S-tiles, and $$$c$$$ corners. Gry would like to beat the high score by creating the largest-possible contiguous $$$2 \times n$$$ rectangle out of some or all of the provided tiles, without any tiles overlapping or sticking out of the rectangle.

Wine is a sophisticated business. Bottling alone encompasses the art of label design, the physics of vacuum sealing, the craft of glassforming, and the calculus of volumetric shapes.

Today we will deal with literature: every size of wine bottle has a name. You may know that a "Standard" bottle holds 0.75L. Did you also know that a 15L bottle is a "Nebuchadnezzar", and a 12L is a mighty "Balthazar"?

Usually wine bottle sizes come in multiples of 1.5L. You have some other bottles in non-standard sizes and you will need to create impressive names for them as well. Note that any two bottles of the same size must have consistent names.