Registration has closed with $$$N$$$ former contestants signed up as individuals, and the contest is played in teams of two. The organizers have to put them into pairs.

Every participant has a rating. The registration system stores it as the difference from a fixed baseline, so the rating $$$a_i$$$ of participant $$$i$$$ is an integer that can also be negative, for somebody who has not written code in a contest for many years.

Every pair must hold exactly two different participants, and each participant may belong to at most one pair. The participants who are left over help as volunteers instead. A pair is competitive if the sum of the ratings of its two members is at least $$$X$$$.

A participant who cannot be placed in a competitive pair simply stays unpaired. Find the maximum possible number of competitive pairs.

Almost everything at a contest site is done by volunteers: printing, balloons, the help desk, the door of the contest hall. Before the contest starts, the organizers have to build the volunteer schedule.

There are $$$M$$$ shifts and $$$N$$$ volunteers. A shift with too few people cannot cover the hall, and a shift with too many people only creates noise, so shift $$$j$$$ needs at least $$$L_j$$$ and at most $$$U_j$$$ assigned volunteers. The volunteers have their own talks and meetings too: volunteer $$$i$$$ is available for some of the shifts and may be assigned to at most $$$c_i$$$ shifts. Writing the same person twice in the same shift helps nobody, so a volunteer can be assigned to the same shift at most once.

Find any assignment that satisfies every requirement, or determine that no such assignment exists.

Elisa is late for the practice session, and the university building hosting the contest does not make it easy. The floor is a rectangle of rooms drawn as a grid of cells. Some cells are blocked by walls, some cells hold an access badge that a volunteer left on a table, and some cells hold a locked door. Every badge and every door has one of $$$K$$$ colours.

Elisa can carry at most one badge, because the readers accept a single card only. When she enters a cell that holds a badge, she may leave it there, or take it. If she takes it, the badge she was carrying before goes into the lost-and-found box and is gone for her. Badges never run out, because the volunteers keep a full box on every table: a cell that holds a badge still holds one after Elisa takes it, so she may come back to that cell later and take another badge of the same colour.

A locked door of colour $$$c$$$ can only be entered while carrying a badge of the same colour $$$c$$$. When Elisa enters it, that badge is swallowed by the reader and the door is propped open: from that moment, every door of colour $$$c$$$ on the floor is permanently unlocked and behaves like an ordinary empty cell.

Elisa never throws a badge away for nothing. She can only lose a badge by taking another one, or by using it on a locked door.

Elisa starts carrying no badge. In one step, she moves to one of the four cells that share a side with her current cell. She cannot leave the floor or enter a wall.

Entering a badge cell costs one step; choosing whether to take the badge costs no additional steps. Entering a locked door also costs one step. The required badge is spent during that step, and Elisa finishes the step inside the now unlocked door cell.

Find the minimum number of steps she needs to reach the team room.

The sponsor banner was left outside during the night, and the wind tore it into $$$n$$$ fragments. The banner was cut along its height, so every fragment still has the full height of the original banner, from the bottom edge to the top edge.

Each fragment is a filled convex polygon. Every fragment is contained between the horizontal lines $$$y=0$$$ and $$$y=H$$$, the bottom and the top edge of the banner, and touches both lines.

The volunteers want to hang all the fragments again on the wall behind the scoreboard, and that wall is short. They may hang the fragments in any order and move each fragment to the left or to the right by any real distance. They may not move a fragment up or down, rotate it, or turn it over: every fragment hangs from the same rail, with its bottom edge on the line $$$y=0$$$.

An arrangement is valid if the interiors of every two fragments are disjoint. Their boundaries are allowed to touch, and a fragment hung exactly against its neighbour is what the volunteers want.

The length of an arrangement is the difference between the largest and smallest $$$x$$$-coordinates occupied by any fragment, that is, the piece of wall it needs. Find the minimum possible length of a valid arrangement.

The contest hall already has $$$P$$$ help desks, and $$$K$$$ teams are sitting at their tables. When a team needs paper, a printout or a new keyboard, one of its members walks to the nearest help desk. The hall is one open floor without walls, so the walk is measured with the ordinary straight-line (Euclidean) distance.

The organizers have enough volunteers to open exactly one more help desk. Its location may be any point of the hall with real-valued coordinates: it does not have to be one of the given integer points, and it is allowed to coincide with an existing help desk or with a team table.

After the new help desk is opened, every team walks to whichever help desk — an existing one or the new one — is closer to its table. The organizers are judged by the team that walks the most, so they want to choose the location of the new help desk so that the longest walk made by any team is as short as possible.

Help them find this minimum possible value.

The jury has collected $$$N$$$ candidate problems, and has only a few weeks to turn them into a contest. Problem $$$i$$$ would add $$$g_i$$$ points of quality to the set, a non-negative integer.

Preparing a problem is not only writing the statement. It also needs tests, a validator, a checker and at least two independent solutions, so one problem takes a full working day of the whole jury.

Every candidate problem also has an author who is available only for a limited time. Problem $$$i$$$ must be finished on day $$$d_i$$$ at the latest, where $$$d_i$$$ is a positive integer.

The jury works on days $$$1,2,3,\ldots$$$ and can prepare at most one problem per day, and no problem can be prepared twice. If problem $$$i$$$ is prepared on day $$$t$$$, then $$$t \le d_i$$$ must hold.

The jury may also drop any candidate problem. Find the maximum total quality of the final problem set.

Every minute of the contest, some team decides that a statement is ambiguous and sends a clarification request. Elisa is the judge on duty at the clarification desk, and her shift lasts exactly $$$2n$$$ minutes. In that time she must take exactly $$$n$$$ requests and answer every one of them.

The jury rates a shift with an operations score. Taking a request the moment it arrives raises that score, because the team stops waiting. Answering lowers it, because a written reply has to be read by the whole jury before it goes out.

During minute $$$i$$$ Elisa must do exactly one of the following:

• Take the request that arrived this minute. The score rises by $$$a_i$$$, and the request joins her queue, where it waits to be answered on a later minute.
• Answer one request that she took earlier and has not answered yet. The score falls by $$$b_i$$$.

A request can only be answered after it has been taken. When the $$$2n$$$ minutes are over, Elisa must have taken exactly $$$n$$$ requests and answered all of them. Determine the highest operations score she can finish her shift with.

The contest ends with a long photo session. The $$$n$$$ participants sit in a single row, and each of them wears the jersey of the university they competed for years ago. Participant $$$i$$$ wears the jersey $$$a_i$$$, so the row is described by $$$a_1,a_2,\ldots,a_n$$$.

The archivist writes a caption for every group of consecutive participants that the photographer shoots. Two people from the same university look the same on the photo and cannot be separated in the caption, but a participant who is the only one wearing their jersey inside the group can always be named. Such a participant is a unique witness of that group.

Formally, take any non-empty contiguous stretch of seats $$$a_l,a_{l+1},\ldots,a_r$$$, and count jerseys using only the positions from $$$l$$$ through $$$r$$$. The stretch has a unique witness if there is at least one position $$$i$$$, $$$l \le i \le r$$$, such that the jersey $$$a_i$$$ occurs exactly once inside that stretch.

Only one such position is needed. The jersey does not have to be unique in the whole row: if it also appears in other parts of the row, it is still a witness where it appears alone inside the stretch.

Determine whether every non-empty contiguous stretch has a unique witness.

One ICPC tradition never dies: every solved problem earns the team a balloon. Elisa is the one who delivers them.

The floor of the contest hall is covered with square tiles, and the organizers describe it as an infinite grid of cells. Elisa hands out the balloons. She starts at the cell $$$(0,0)$$$, where the balloon table stands, and the volunteer coordinator has already written her whole route for this round as one non-empty string of orders. Elisa follows the orders from left to right, and each order takes her to one of the four cells next to the current one:

• U: walk one cell up;
• D: walk one cell down;
• L: walk one cell left;
• R: walk one cell right.

The hall is large enough that she never reaches a wall, and her route may cross itself as many times as the coordinator wants.

After the round, the cleaning crew wants to know how much of the floor was used. Find the number of distinct cells Elisa steps on, including the cell $$$(0,0)$$$ where she starts.