This is the easy version of the problem. Note that the only difference in the problems are the constraints over $$$N$$$, $$$K$$$ and $$$T$$$.

Mari and Klaus are a beautiful couple who love mathematics. They also share a very particular passion: they are Permátomo tasters. The Permátomo is an abstract object that represents the combinatorial essence of couples, and Mari and Klaus enjoy experimenting with it in creative ways. Today, they are looking to obtain the k-th best couple of the Permátomo.

Formally, given an array of size N, Mari and Klaus want to compute the sum of all possible pairs $$$(i, j)$$$ where $$$1 \leq i, j \leq N$$$. For each pair $$$(i, j)$$$ they calculate: $$$s_k = a_i + a_j$$$ where $$$k$$$ corresponds to the number of the couple created. In total, there are exactly $$$N^2$$$ possible couples.

Then, Mari and Klaus ask themselves: What is the k-th best couple of the Permátomo? For Permátomo tasters, this means finding the k-th smallest sum among all possible sums $$$s_k$$$.

We have a maze with $$$T (1\le T\le 3)$$$ spheric balls inside. We want to achieve a certain state of the maze by only slanting it to any of the four cardinal directions. So, for example, if we slant the maze to the north, then the spheric balls would move up the maze until they hit a wall, hit another ball, or hit the border of the maze.

Given the initial and final states of the maze, say if we can achieve the final state only by slanting the maze to the four cardinal directions.

You are responsible for a company that produces and distributes Aboreo, an alcoholic beverage valued for the variety in its oplo degree, a component that provides sweetness. Using specialized rays, it is possible to precisely modify the oplo degree of stored bottles. You must develop a system to simulate the state of a warehouse where Aboreo bottles are stored and modified. Initially, the warehouse is empty. A total of $$$q$$$ operations will be performed on the warehouse, each in one of the following forms:

1. '1 x' (Add bottle): A new bottle with an oplo degree of $$$x$$$ ($$$1 \leq x \leq 10^8$$$) is added to the warehouse.

2. '2 x' (Increase oplo): The oplo degree of each bottle in the warehouse increases by $$$x$$$ ($$$-10^8 \leq x \leq 10^8$$$). If the oplo degree of the $$$j$$$-th bottle was $$$v_j$$$ before the operation, it becomes $$$v_j + x$$$ afterward.

3. '3 p q' (Multiply oplo): The oplo degree of each bottle is multiplied by $$$\frac{p}{q}$$$ ($$$-10^8 \leq p, q \leq 10^8$$$, $$$q \neq 0$$$, $$$p \neq 0$$$). If the oplo degree of the $$$j$$$-th bottle was $$$v_j$$$ before the operation, it becomes $$$v_j \cdot \frac{p}{q}$$$ afterward.

4. '4 j' (Query degree): Print the oplo degree of the bottle added in operation $$$j$$$ ($$$1 \leq j \leq i$$$), considering all operations performed up to that point.

Notes:

- The oplo degree may become extremely large, small, negative, or non-integer after operations. - For queries (type 4), it is guaranteed that the oplo degree of the queried bottle is an integer $$$0 \leq v \leq 10^8$$$, avoiding precision issues

Implement an algorithm that performs this simulation efficiently.

A mapping company is testing a new signal simulation system. They have placed $$$N$$$ signal towers at different positions on a flat map. Each tower is located at coordinates $$$(x_i, y_i)$$$, where $$$1 \le x_i, y_i \le 2 \cdot 10^5$$$, all $$$y_i$$$ values are distinct and all $$$x_i$$$ values are distinct as well, additionally, there are no three colinear points.

To analyze signal interference, the company draws a virtual line between every pair of towers. These lines are extended downward, and the engineers are interested in how these lines affect positions on a distant horizontal scan line at $$$y = -10^{18}$$$.

They define a function $$$f(x)$$$ for real numbers $$$x$$$, which represents interference at horizontal position $$$x$$$ on the scan line. Initially, $$$f(x) = 0$$$ for all $$$x$$$.

Then, for every pair of towers $$$i \lt j$$$, the following process is applied:

• Consider the directed line from point $$$i$$$ to point $$$j$$$.
• For a fixed real number $$$x$$$, consider the point $$$(x, -10^{18})$$$.
  • If this point is on or to the left of the line (remember that the line is directed from point $$$i$$$ to point $$$j$$$), then update $$$f(x) := f(x) \oplus a$$$.
  • If it is to the right of the line, then update $$$f(x) := f(x) \oplus b$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

After processing all pairs, the function $$$f(x)$$$ becomes piecewise constant: the real line is divided into a number of intervals where $$$f(x)$$$ has the same value. We define a Trujo as any such interval where $$$f(x) = 0$$$.

Your task is to count how many Trujos appear on the real number line.

For many years, the kingdoms of Karsmir, ruled by King Telo, and Elyria, ruled by Queen Sofia, lived in perfect harmony. Their alliance was not only political; it was also the reflection of a deep love that had united their hearts since youth.

They shared victories, developed magical defense technology, and dreamed of building a peaceful world. However, this union ended suddenly when Sofia discovered that Telo had been secretly communicating with an old love from the northern lands. Telo claimed it was just a diplomatic exchange, but Sofia, feeling betrayed, decided to break the relationship—and the alliance. Now, both kingdoms are at war, and the situation is bleak.

In the kingdom of Karsmir, there are $$$n$$$ underground bunkers placed in a row, numbered from $$$1$$$ to $$$n$$$, from left to right. Each bunker has a depth $$$d_i$$$ and an energy cost $$$e_i$$$.

Because of the air attacks ordered by Sofia, it is necessary to select the largest possible subset of bunkers that can be connected using magical communication without interference. To make this work, the following condition must be satisfied:

• Close Energy Optimization

  A bunker $$$i$$$ can only be selected if the first bunker to its right with a lower depth ($$$d_j$$$ < $$$d_i$$$) also has a lower energy cost ($$$e_j$$$ < $$$e_i$$$).

  Formally, let $$$j$$$ be the smallest index such that $$$j \gt i$$$ and $$$d_j \lt d_i$$$ . Then, bunker $$$i$$$ can be selected only if $$$e_i \gt e_j$$$.

  If there is no bunker to the right of $$$i$$$ with lower depth, then $$$i$$$ can be selected freely.

  (Bunkers closer to the surface interfere with the signal if they consume more energy than the deeper bunker trying to communicate)

Your task is to print the longest possible subsequence of bunkers that can be created following this condition.

The eccentric mathematician and dimensional builder Mr. Padalustro has spent his life studying geometric shapes in higher dimensions. His latest obsession is a structure he calls an Obo.

An Obo is an n-dimensional rectangular box. Formally, it has $$$n \geq 1$$$ sides with positive integer lengths ($$$ l_1, l_2, l_3, \ldots, l_n $$$), and its area is calculated by multiplying all the lengths:

$$$$$$AreaObo= l_1 \cdot l_2 \cdot l_3 \cdot \ldots \cdot l_n$$$$$$

Mr. Padalustro wants to build an Obo with area exactly equal to a given positive integer $$$A$$$. However, building an Obo is not easy: each side must be a positive integer greater than 1, and no side can be longer than $$$X$$$, because his tools cannot create sides longer than that.

He is also obsessed with dimensions: he wants to build an Obo with the maximum number of dimensions possible (i.e., the largest possible value of $$$n$$$ such that the product of the side lengths is exactly $$$A$$$ , and every side is less than or equal to $$$X$$$).

Your task is to help him determine the maximum number of dimensions such an Obo can have. If it is not possible to build any Obo with area exactly equal to $$$A$$$ and side lengths not greater than $$$X$$$, you must print a special message.

A group of friends is trapped inside an abandoned building that has been converted into a giant escape room. The building's layout is modeled as a simple, connected, undirected graph where each node represents a room and each edge represents a corridor connecting two rooms.

One of the friends —Mr. Tacafroto— managed to reach the control room. In this room, Tacafroto has full access to the building's lighting system and blueprints. Each corridor is equipped with its own light that can shine in a fixed color. However, the building is initially in complete darkness: all corridor lights are turned off. Tacafroto can activate the lights, but with one important constraint: at any given moment, he may turn on the lights of only one chosen color.

Before issuing any instructions, Tacafroto is allowed to set up the building's corridors as follows:

Assignment of Colors: Each corridor (i.e., every existing undirected edge) is assigned a color from the set $$$\{ 1,2,3 \}$$$. That is, every corridor has its dedicated light of a specific color.

Optional Passage: He may also build at most one new one-way passage (a directed edge) connecting two rooms that are not already connected. This new passage is assigned a color (from 1 to 3) just like the other corridors.

The remaining friends are stuck in different rooms. Tacafroto does not know exactly how many friends there are, nor in which rooms they are located. To gather them, Tacafroto can issue a sequence of instructions. In each instruction he selects a color $$$c \in \{ 1,2,3 \}$$$ and performs the following steps:

All corridor lights are turned off first.

Then, the lights for all corridors whose assigned color is $$$c$$$ (including the light of the extra one-way passage, if one was built and have color $$$c$$$) are turned on.

Immediately after, every friend (regardless of their room) makes a move:

If there is at least one corridor from their current room whose light is on (i.e., whose assigned color is c), the friend must choose one such corridor and move to the adjacent room.

If there are multiple illuminated options, the friend may pick any of them arbitrarily. Tacafroto does not control these choices and has no knowledge of the friends movements.

If no corridor from their room is lit, the friend remains in place.

The goal is to design the initial color assignments (and optionally, add the directed passage) along with a sequence of at most 205 instructions —each instruction simply a color— to guarantee that, regardless of how many friends there are or where they start, all friends eventually meet in the same room.

This is the hard version of the problem. Note that the only difference in the problems are the constraints over $$$N$$$, $$$K$$$ and $$$T$$$.

Mari and Klaus are a beautiful couple who love mathematics. They also share a very particular passion: they are Permátomo tasters. The Permátomo is an abstract object that represents the combinatorial essence of couples, and Mari and Klaus enjoy experimenting with it in creative ways. Today, they are looking to obtain the k-th best couple of the Permátomo.

Formally, given an array of size N, Mari and Klaus want to compute the sum of all possible pairs $$$(i, j)$$$ where $$$1 \leq i, j \leq N$$$. For each such pair $$$(i, j)$$$ they calculate: $$$s_k = a_i + a_j$$$ where $$$k$$$ corresponds to the number of the couple created. In total, there are exactly $$$N^2$$$ possible couples.

Then, Mari and Klaus ask themselves: What is the k-th best couple of the Permátomo? For Permátomo tasters, this means finding the k-th smallest sum among all possible sums $$$s_k$$$.

In the bustling city of Chorizolandia, Sergeant Camelas, a sharp and experienced traffic officer, has just pulled over a driver for a violation. The sergeant is well aware that in this city, some drivers attempt to "negotiate" their fines through subtle, often indirect means. To effectively identify these illicit attempts, the sergeant has meticulously memorized five secret keywords. He understands that if these five words are spoken consecutively by a driver, forming any one of their 5 possible ordered arrangements, it constitutes a clear signal of attempted bribery, leading to a significantly escalated fine.

The driver, desperate to avoid the standard traffic fine and completely unaware of the sergeant's unique detection method, decides to launch into a long, rambling statement. Their hope is to "smooth over" the situation by trying out various combinations of words, including, unknowingly, permutations of the sergeant's secret keywords.

Your task is to analyze the driver's complete sentence. Specifically, you must determine if any of the 5! permutations of the five secret keywords appears as a contiguous substring within the phrase the driver says to the sergeant. If such a specific keyword sequence is detected, indicating a negotiation attempt, the fine will be increased. Otherwise, the original fine remains in effect.

There are $$$n$$$ candies in a row, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th of them has a repose $$$v_{i}$$$ and a color $$$c_{i}$$$.

Timulo wants to choose a subsequence of candies, such that adjacent candies in the chosen subsequence have different colors

Formally, if the indices of the candies that Timulo chose were $$$i_{1} \lt i_{2} \lt \dots \lt i_{k}$$$, then $$$c_{i_{j}} \neq c_{i_{j + 1}}$$$ for all $$$1 \leq j \leq k -1$$$.

Timulo wants to maximize the sum of the repose from the subsequence. Can you help him find the maximum possible sum?

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Doctor Padalustro, a renowned interdimensional scientist, is conducting a dangerous experiment with uxions, microscopic creatures capable of duplicating themselves at insane speeds.

Padalustro started the experiment by placing exactly one uxion in a petri dish. However, uxions have a very peculiar behavior:

• On odd-numbered minutes, the number of uxions grows by the same amount as in the previous minute.
• On even-numbered minutes, the number of uxions grows by twice the amount that was added in the previous minute.

The experiment is considered to begin at minute 0, at which point there is exactly 1 uxion.

You have received a calendar cube for your birthday! Fascinated by the fact that each day of the month could be constructed by using the two cubes in a specific orientation, you got an idea. You ordered $$$n$$$ cubes online. Each cube has some digit written on each of its six faces. Digits may repeat within a cube.

Two number cubes forming the number $$$25$$$.

Your curious mind begins to wonder: what are the $$$k$$$ smallest numbers that cannot be obtained by using some of the $$$n$$$ cubes in a specific orientation? Numbers must not contain leading zeros. Note that you can choose to not use some cube if you don't want to.