Asdrubal likes writing sequences of integers and eating apple pie. Sometimes he does both things simultaneously. These days he is interested in sequences of a particular type. Given an integer $$$N \ge 2$$$, he wants to find a sequence such that each set of two different integers between $$$1$$$ and $$$N$$$ appears exactly once in adjacent positions of the sequence. Besides, no other integers can appear in the sequence.

For instance, for $$$N=2$$$, there is a single set of two different integers between $$$1$$$ and $$$N$$$, which is the set $$$\{1,2\}$$$. Thus, Asdrubal would be satisfied with the sequence $$$[1,2]$$$. The only other possibility is the sequence $$$[2,1]$$$.

For $$$N=3$$$, there are three sets of two different integers between $$$1$$$ and $$$N$$$: $$$\{1,2\}$$$, $$$\{1,3\}$$$ and $$$\{2,3\}$$$. In this case a valid sequence is $$$[2,1,3,2]$$$, since the set $$$\{1,2\}$$$ only appears in the first two positions, the set $$$\{1,3\}$$$ only appears in the middle, and the set $$$\{2,3\}$$$ only appears in the last two positions, with no other integers appearing in the sequence. On the other hand, the sequences $$$[2,1,3]$$$, $$$[2,1,3,2,1]$$$ and $$$[2,1,3,2,2]$$$ are invalid.

Asdrubal thinks he has just written one of his sequences for a certain $$$N$$$. He was about to check whether the sequence was actually valid, when some apple pie fell on the paper. The apple pie covered zero or more elements of the sequence, splitting the rest into two (possibly empty) parts, one on the left of the apple pie, and one on the right. Given the left and right portions of the sequence not covered by apple pie, you must determine whether the original full sequence could have been valid.

A group of students is starting a competitive programming club, and they expect that $$$N$$$ people will join, one by one. When each person joins, they must bring between $$$1$$$ and $$$K$$$ balloons.

The founders want to make sure things stay fair and decided to impose the following fairness rule: after each person joins, it must be possible to evenly redistribute all balloons collected so far among the current members. In other words, after each step, the total number of balloons so far must be divisible by the current number of people.

Being competitive programmers, they realized that this makes for a nice counting problem, and decided to challenge you. How many sequences of $$$N$$$ balloon contributions (each contribution between $$$1$$$ and $$$K$$$) satisfy the fairness rule at every step?

Two sequences are considered different if they differ at any position.

One more year of Virada Cultural in São Paulo. The city is full of people, and the streets are full of life. People from all over the city go to the streets to enjoy a night of cultural events and a lot of music.

Oswaldo, an employee at the city hall, was assigned the task of hiring cleaners to clean the $$$S$$$ streets of São Paulo, in no more than $$$K$$$ hours after this big event. He was given by his boss a list of $$$N$$$ cleaners he could hire, numbered from $$$1$$$ to $$$N$$$, along with information related to how fast they work and the payment they accept. According to the list, cleaner $$$i$$$ can clean any street in $$$H_i$$$ hours, and accepts as payment anything between $$$L_i$$$ and $$$U_i$$$ for cleaning each street.

Oswaldo must hire a subset $$$\mathcal{C}$$$ of the cleaners that are in the list. For each hired cleaner $$$i \in \mathcal{C}$$$ he must assign $$$s_i$$$ streets for them to clean and a payment $$$p_i$$$ per street, taking into account the following guidelines:

• Each number of streets $$$s_i$$$ must be a positive integer and the sum $$$\sum_{i \in \mathcal{C}} s_i$$$ must be exactly $$$S$$$, because every street must be cleaned and no street can be cleaned by more than one cleaner.
• Note that each hired cleaner $$$i$$$ will take $$$s_i \cdot H_i$$$ hours to clean their assigned streets. Since the cleaners can work in parallel, the cleaning job will take, in total, $$$\max_{i \in \mathcal{C}} (s_i \cdot H_i)$$$ hours to be completed. This total time must be at most $$$K$$$ hours.
• The payment per street $$$p_i$$$ must be a rational number between $$$L_i$$$ and $$$U_i$$$ (that is, $$$L_i \le p_i \le U_i$$$).
• To ensure a fair hiring process, the payment per hour of work $$$\frac{p_i}{H_i}$$$ must be the same for all hired cleaners.

Hired cleaner $$$i$$$ will receive $$$s_i \cdot p_i$$$ as payment, being the total payment $$$\sum_{i \in \mathcal{C}} s_i \cdot p_i$$$. Help Oswaldo determine the minimum total payment for cleaning the streets honoring the given guidelines, or tell him that those requirements cannot be satisfied.

After the BRICS group introduced the International Common Payment Currency (ICPC), all currencies (like real, peso, dollar, etc.) are now defined by their values in ICPCs.

To help people navigate this new world order, you decided to create a website to compute the conversion rates between currencies. The website handles $$$N$$$ currencies, numbered from $$$1$$$ to $$$N$$$. Each currency $$$i$$$ has an associated integer value $$$A_i$$$, indicating that one unit of currency $$$i$$$ is worth $$$A_i$$$ ICPCs.

The website works as follows: the user selects a source currency $$$i$$$, then they select a target currency $$$j$$$ (it might be that $$$j=i$$$), and the website displays the conversion rate between them, that is, the exact decimal representation of $$$\frac{A_i}{A_j}$$$.

To deal with repeating decimals, you decided to display only the first period (represented by a line above it, when it exists). Thus, the quotient $$$\frac{4}{4} = 1$$$ requires $$$1$$$ digit to be displayed, $$$\frac{4}{3} = 1.\overline{3}$$$ needs $$$2$$$ digits, $$$\frac{41}{4} = 10.25$$$ uses $$$4$$$ digits, and $$$\frac{3}{14} = 0.2\overline{142857}$$$ takes $$$8$$$ digits.

Your website has been running successfully for quite some time. As part of your performance analytics, you want to compute the expected display size of conversion rate pages.

Given the values $$$A_1, A_2, \ldots, A_N$$$, you must compute the expected number of digits needed to display the quotient $$$\frac{A_i}{A_j}$$$, when $$$i$$$ and $$$j$$$ are chosen uniformly at random between $$$1$$$ and $$$N$$$.

A village stores emergency ration boxes. Each box contains a certain number of rations, and the village leader keeps track of how many rations are in each box. Initially, there are no boxes in the supply. Sometimes a new box is added to the supply, or an existing box is removed.

In an emergency, the villagers must choose exactly one of the following actions each day that the emergency lasts:

1. pick one non-empty box and use up all rations in that box, or
2. use one ration from every non-empty box.

The leader is worried about the possibility of rapid consumption. Therefore, after each change to the supply, the leader wants to know how many days it would take before all boxes become empty, assuming that an emergency occurs and the villagers choose actions that empty all boxes in the fewest possible days.

Note that the rations are not actually used; the leader only wants to know the minimum number of days needed to empty all boxes. As running these simulations is not something the leader can do alone, you have been asked to help.

Finding the prime factorization of big numbers is a challenging task. It is so difficult that the security of almost our entire digital world, from online banking to private messages, is built upon how hard it is. In this problem, you are asked to perform such a factorization, but some relative error is allowed in your answer.

More formally, you are given an integer $$$X$$$, and you have to provide the prime factorization of any number $$$Y = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$$$ such that

• the relative error of the factorization does not exceed $$$10^{-9}$$$ (that is, $$$\frac{|X-Y|}{X} \leq 10^{-9}$$$), and
• each prime factor $$$p_i$$$ of $$$Y$$$ does not exceed $$$10^{18}$$$ (that is, $$$p_i \leq 10^{18}$$$ for $$$i = 1, 2, \ldots, k$$$).

Gridoland is a city consisting of a grid of $$$N \times M$$$ blocks, designed for robust energy distribution. The city's power supply is a dam that can effectively generate an arbitrarily large current, and it is connected to the top-left block, at coordinates $$$(1, 1)$$$. The mayor is planning to host a big, energy-hungry celebration at the city hall, which is located at coordinates $$$(N, M)$$$, and she has hired you to help the planning committee.

Each block in Gridoland has its own energy transformer. Each transformer has an initial capacity to pass current, but this capacity changes linearly over time at a possibly different rate for each transformer. To help your job, technicians have determined each transformer's initial capacity $$$C_{ij}$$$ and its rate of change $$$R_{ij}$$$ (which can be positive, negative, or zero). Therefore, you know that the capacity of the transformer on block $$$(i, j)$$$ at minute $$$t$$$ will be $$$C_{ij} + t \cdot R_{ij}$$$.

Current flows within the city thanks to a number of power cables. All power cables in Gridoland are made of a superconductor material that can pass arbitrarily high current in either direction. The mayor herself handed you the city's connectivity map, containing all pairs of (vertically or horizontally) adjacent blocks that are connected by a power cable.

During the celebration there will be no energy consumption in any block except for the city hall, so all the current entering the energy grid will be used for the celebration. The celebration must happen at most $$$K$$$ minutes in the future, because the mayor's term will end at that time. You must answer the following question to the planning committee: what will be the grid's peak capacity to supply the celebration at an integer number of minutes $$$t$$$ in the range $$$[0, K]$$$?

At each moment, the grid's capacity from the city hall's point of view is equal to the maximum amount of current that can flow from the power supply to the city hall. The current entering each transformer is limited by that transformer's capacity, and by the constraint that all of the current that enters a block has to leave (except for the city hall, which during the celebration will consume all energy it receives).

Lola keeps a long to-do list of tasks she needs to finish. Each task has a difficulty number (the bigger the number, the harder the task), and the tasks must be completed in the order they appear.

The list keeps growing because items are rarely removed. Tired of that, Lola decided to take action: she wants to split her list into several consecutive groups of tasks, where each group represents the work she will do in one day.

To stay motivated, Lola wants to feel that each day is a step forward. So, starting from the second day, the hardest task of that day must be strictly harder than the hardest task from the previous day.

Lola also does not want to do too much in one day, so she wants to spread the work over as many days as possible.

What is the maximum number of days she can split the tasks into under these rules?

Tomás is a secret agent attempting to infiltrate the super-secure headquarters of the International Competitive Programming Consortium (ICPC). The building has $$$2N$$$ floors, numbered from $$$1$$$ to $$$2N$$$. Starting at floor $$$1$$$, he must reach floor $$$2N$$$ to steal classified algorithms, and then make a dramatic parachute escape from the roof.

He has obtained $$$M$$$ stolen elevator access codes. Each access code connects two specific floors $$$S$$$ and $$$T$$$ ($$$S \lt T$$$) and can be used to force the elevator to move upward from floor $$$S$$$ to floor $$$T$$$.

The building has an advanced security system composed of $$$N$$$ sensors. Sensor $$$i$$$ monitors floors $$$i$$$ and $$$i+N$$$ (for $$$1 \le i \le N$$$). When Tomás uses an elevator code to leave a floor, the monitoring sensor detects the intrusion and permanently seals both floors it monitors. Sealed floors cannot be entered, and codes cannot be used from sealed floors. Thus, he can enter at most one floor from each monitored pair.

Tomás needs your help to guarantee the success of the mission. Your task is to determine an infiltration route, which is a sequence of floors $$$f_1, f_2, \ldots, f_k$$$, such that

• $$$f_1 = 1$$$,
• $$$f_k = 2N$$$,
• there is an access code that allows moving from floor $$$f_{i}$$$ to floor $$$f_{i+1}$$$ for $$$1 \le i \le k-1$$$, and
• no two floors $$$f_i$$$ and $$$f_j$$$ in the sequence (with $$$i \ne j$$$) are monitored by the same sensor.

If such an infiltration route exists, output it. Otherwise, indicate that the mission is impossible.

After a glorious night of stand-up comedy, a comedian wants to measure their success. Not with surveys, not with likes, but with real crowd noises! Luckily, the mic captured all the reactions during the routine. The audio has been converted into a single string $$$S$$$ full of mashed-up sounds, such as applause, laughs, boos, etc.

The comedian uses a powerful tool for evaluating their show: the Instant Comedian Performance Calculator (ICPC). The ICPC is able to analyze $$$S$$$ and calculate the emotional score of the performance, which reflects how well the comedian did on stage.

The score is based on the occurrence of three specific substrings within the string $$$S$$$:

• each occurrence of "ha" increases the score by $$$1$$$,
• each occurrence of "boooo" decreases the score by $$$1$$$, and
• each occurrence of "bravo" increases the score by $$$3$$$.

There are $$$N$$$ chess kings placed in an infinite grid. Each of them occupies a different cell. The conquered area of the grid is defined as the number of cells in the smallest rectangular subgrid that contains all the cells occupied by the kings. The picture below shows two scenarios; on the left, the conquered area is $$$12$$$; on the right, it is $$$16$$$.

You are allowed to perform a sequence of $$$K$$$ moves. In each move, you select any king and move it to any of its eight adjacent cells, as a regular king moves in chess. No two kings may occupy the same cell at the same time.

What is the largest conquered area that can be achieved after performing $$$K$$$ moves?

There are $$$N$$$ creatures, numbered from $$$1$$$ to $$$N$$$, that live in an infinite city represented by the 2D plane. Creature $$$i$$$ lives on the straight line $$$y = M_i \cdot x + C_i$$$; it may move anywhere along that line. No two creatures share the same line, but a meeting occurs if their lines intersect. In that case, the intersection point is called a meeting point of the two creatures.

The city has just built a new playground. The playground's boundary is the (axis-aligned) parabola $$$y = A \cdot x^2 + B$$$, where $$$A \gt 0$$$. The playground is the open region $$$y \gt A \cdot x^2 + B$$$, so points exactly on the boundary are not inside the playground.

Now the city officials want to know whether the new playground is reducing loneliness, and that's where your help is needed. Your task is to count how many distinct pairs of creatures have a meeting point that lies strictly inside the playground. Each pair is counted once; the order of the creatures in a pair does not matter.