The city of Rio de Janeiro is under attack! By a swarm of bees? That act in a very specific manner? That's correct, and unfortunately, MatheusAB has been caught in the middle of this mess. Luckily for him though, he was able to find a bunker in time to hide in and for some reason he has a special device that is able to track the location and direction of the bees. As previously mentioned, they behave in a very specific way: there are $$$n$$$ queen bees that command a swarm of millions of bees and they will attack anything that is present in the smallest convex polygon that contains all the queen bees.

With MatheusAB's special device, he's able to track the location of the queen bees, and he realizes that each of them has a specific constant velocity and direction. Since he's exhausted from this situation, given the initial positions of the queen bees, he asks you to help him find out what's the minimum amount of time he'll have to wait in order for the city to be safe to roam in again. Initially, all queen bees are within city limits. Rio de Janeiro is considered safe once there aren't any areas within it that are susceptible to a bee attack. The city is conveniently a convex polygon defined by $$$m$$$ vertices.

I don't feel like wasting your time today with long statements, so let's cut straight to the point.

Let $$$p(x)$$$ be the product of all square numbers that divide $$$x$$$, or more formally, $$$p(x) = \displaystyle\prod_{\substack{i = 1 \\ i^2 | x}}^{\infty} i^2$$$.

Given $$$a$$$ and $$$b$$$, your task is to calculate the number of times $$$a!^b$$$ divides $$$p\big(a!^b\big)$$$. More formally, calculate the maximum value of $$$c$$$ such that $$$(a!^b)^c \mid p\big(a!^b\big)$$$.

Since $$$c$$$ can be quite large, print the sum of its digits in base $$$10$$$.

A lovely couple, Sergio and Ana, go out on a romantic evening to paint. They go to this place that has some very special paint colors, which are able to glow in the dark and some of which have some very funky effects! The event starts with the couple receiving $$$q$$$ blank canvases, and a whole variety of $$$k$$$ colors to choose from. The colors are numbered from $$$1$$$ to $$$k$$$. These can be divided into two: those who are weird and those who are permanent. The colors that are deemed weird have this special effect: if a person tries to color the canvas an even amount of times with the same weird color, every speck of it magically disappears! Permanent colors don't suffer from this (un)fortunate condition.

This painting gallery has some very strict rules on how to use the colors: the couple has $$$n$$$ color palettes to choose from, and once the palettes are chosen, they need to use every color contained in each one. As per guidelines, permanent colors can't be present in the same palette as weird ones. These palettes each contain each color at most once, and contains enough paint of each color to paint the entire canvas (the couple doesn't need to use the same palette twice). Every canvas is an independent query, so they have the complete set of palettes available.

For each $$$q_i$$$ canvas, Ana decides that she wants Sergio to paint it using a specific array of colors. As Sergio wants to paint each one without tiring himself too much, he wants to know for each canvas, what's the least amount of different palettes that he has to choose from in order to satisfy Ana.

Davi Holanda, usually known by his nickname, Deaga, has been fiddling around with arithmetic progressions, as it's something very important to know for the entrance exam of the Institute of Meaningful Equations, otherwise known as IME. He discovered the existence of third-order arithmetic progressions, which are arithmetic progressions that, given the first four elements, follow the construction rule: $$$a_{i + 3} - 3a_{i + 2} + 3a_{i + 1} - a_i = k$$$, where $$$k$$$ is some non-zero constant. The constant varies depending on the sequence.

In order to furthermore learn about this type of arithmetic sequence, he began playing around with making operations with it. He got an array $$$v$$$, of length $$$n$$$, and given the first four elements and two indices $$$i$$$ and $$$j$$$, $$$(i \lt j)$$$, he'd add the elements of the sequence onto the array. Of course he'd add them in order, with the first element being added to index $$$i$$$, and the $$$(j - i)^{th}$$$ element being added to index $$$j$$$. However, he'd perform these operations given some restrictions:

• The constant $$$k$$$ of the given sequence is divisible by $$$6$$$.
• The following is true: $$$(a_2 - a_0 - \frac{4k}{3}) \equiv 0 \mod 2$$$.

Deaga does this many times and ends up getting bored doing all the calculations, and asks for your help to speed things up! Based on the initially empty array, he performs $$$q$$$ queries, in which one will add a certain sequence to a certain range of the array, and another one which will ask the sum of elements of a certain range.

Such graphic depicts what a third-order arithmetic progression looks like

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$|s|$$$ .

Navarro is (or was? I'm really not sure) a prominent student at the Institute of Making Ethanol, commonly known around the block as IME. He loves playing around with strings (of characters, not related to ropes) and so he also enjoys applying random algorithms to them. On one fine afternoon, he devised a simple algorithm to create a graph from a string with the following construction: two indices $$$i$$$ and $$$j$$$ are connected only if the substring $$$[i, j]$$$ is a palindrome. Seems simple right?

From the graph that's created, Navarro wants to find out the amount of connected components.

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$|s|$$$ .

Navarro is (or was? I'm really not sure) a prominent student at the Institute of Making Ethanol, commonly known around the block as IME. He loves playing around with strings (of characters, not related to ropes) and so he also enjoys applying random algorithms to them. On one fine afternoon, he devised a simple algorithm to create a graph from a string with the following construction: two indices $$$i$$$ and $$$j$$$ are connected only if the substring $$$[i, j]$$$ is a palindrome. Seems simple right?

From the graph that's created, Navarro wants to find out the amount of connected components.

You live in a tree-shaped country with $$$n$$$ cities, and you conveniently live in city $$$1$$$. It's almost Christmas, so you want to send a gift to your friends. Luckily, you can use the famous post service called IMEmail. It's so quick that it only takes one day to move packages between two neighboring cities (wow! What a relief!). As always, there are some caveats when it comes to this: once a package travels through a city, it can't take a route that passes through that city again. In other words, there can't be a cycle in the path a package takes.

This year, you decided to gift all your friends headphones! You just finished buying the headphones, but now realized that they didn't come with a charging cable. Your friends will only be happy if they receive both the headphones and the charging cable exactly on Christmas day. Now, you decide to call many manufacturers to see how soon they can start distributing the cables across the country.

On the $$$i^{th}$$$ query, you'll send the headphones $$$x$$$ days before Christmas. You also find out that there's a manufacturer located in city $$$u$$$ that will send out the chargers $$$y$$$ days before Christmas. Given these various parameters, for each query, you want to know how many friends will be happy on Christmas Day.

Somewhere along a famous beach in Rio de Janeiro, $$$n$$$ friends share a house (because how can you afford rent alone?). They all follow one sacred rule: always leave your shoes by the door when entering.

Each friend has $$$k$$$ pairs of shoes, and since they are too poor to afford a decent shoe rack, they decided to just draw lines on the ground to create $$$nk$$$ slots to place their pairs of shoes. The slot $$$i$$$ is at a distance of $$$i$$$ from the door, and initially contains a shoe from the person $$$a_i$$$.

Every day, each person selects a random pair of shoes they own and leaves the house in the morning. They all arrive in the afternoon in a random order, and place their shoes on the first slot available (closest to the door).

You need to answer $$$q$$$ queries. On each query, given two integers $$$x$$$ and $$$d$$$, calculate the expected average distance of all the pairs of shoes of person $$$x$$$ to the door after $$$d$$$ days. It can be shown that this answer can always be expressed as a fraction $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1}\mod (10^9+7)$$$.

In a fictitious universe, there are two species of aliens that have agreed to peacefully coexist until the heat death of the universe. Once every 500 trillion years, the two parties hold a conference in some galaxy to discuss issues (and have some nice drinks). You are given the task to decide in which galaxy to hold this amazing conference (party).

There is one catch: intergalactic travel is expensive, so an alien from one species will be happy with the chosen place if and only if there exists an alien from the other species that has to travel the exact same distance to arrive at the conference. Luckily, the $$$n$$$ galaxies are located in a straight line, with a separation of $$$1$$$ megaparsec between adjacent ones.

Given the distribution of the aliens of both species in these galaxies, what is the maximum number of aliens you can make happy by choosing the position of the conference?

Pedro Vieira is a student at the Institute of Many Equations, commonly referred to as IME. He's attending a class hosted by none other than the infamous Mr. Potato and since his class is soooooo boring (really, it is), Pedro begins making up random algorithms and running them in his mind (as one commonly does).

On one beautiful morning, he overheard Mr. Potato talking some nonsense about XOR operations, and so, tried to come up with an algorithm that does the following: given an array of integers, find the greatest value that can be obtained from XOR-ing a subset of this array. Since this is too easy, he reformulated the problem. Given an array $$$a$$$ of $$$n$$$ elements, for every $$$i$$$ from $$$1 ... n$$$, find the maximum XOR value of a subset of the array $$$(a_1, a_2, ..., a_i)$$$.

At the 2023 Brazilian Summer Camp, prominent Polish coder kostka told his students how hashing is the best thing in the world. It makes problems related to strings that much easier! As such, an easy question related to strings must be made in order to show how efficient it is. The task is quite simple: you are given a string $$$s$$$ and an integer $$$k$$$. You only need to print out how many substrings $$$t$$$ exist, such that $$$(|t| * freq(t) = k)$$$, where $$$freq(t)$$$ is the amount of times the substring appears in the string. If at least one substring fits the criteria, you should print out the lexicographically smallest and the lexicographically largest (note that they may be the same). Quite an easy task, right?

Lexicographical order is defined as follows: when ordering two strings $$$a$$$ and $$$b$$$, $$$a$$$ is lexicographically smaller than $$$b$$$ if and only if one of the following holds:

• $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
• in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter of $$$b$$$.

The students of some programming summer camp love going to a meeting place known by all as the little gas station. For some reason, the city they currently live in can be thought of as having $$$n$$$ road intersections, with a total of $$$n - 1$$$ roads. From every intersection, you can reach every other one. They loved going to the same little gas station as always, which was originally located at the intersection whose label is $$$1$$$. However, the students sometimes complained that they had to walk too much in order to get to the original little gas station, as they could sometimes be on the other side of town.

Thus, a businessman from out of town appeared in order to help these poor students. Depending on the day, this businessman would build a replica of the original little gas station at some intersection $$$x$$$ (he would never build in an intersection that already contains a gas station). The owner of the original little gas station, furious with this new businessman, would, depending on the day, destroy one of the businessman's gas station replicas. However, the students simply didn't care enough about this fight between them, so given a day in which they wanted to hang out at a little gas station, they'd go to the nearest to the intersection they're currently at.

This fight lasted for $$$q$$$ days, and on each day, one of three events could occur: the businessman could build a replica at intersection $$$x$$$, the original owner could destroy a replica at intersection $$$y$$$, or the students, currently at intersection $$$z$$$, want to find out the minimum amount of roads they need to cover to reach any little gas station.

Schubert has recently been studying properties of arrays, and something that caught his attention is called inversions. From what he recalls from class, the number of inversions of an array $$$a$$$ of size $$$n$$$ is defined by the number of pairs $$$(i, j)$$$ such that $$$(1 \leq i \lt j \leq n)$$$, in which $$$(a_i \gt a_j)$$$. Schubert realized that given an array, there are plenty of subarrays whose number of inversions is the same as the original array. As such, he gave this simple task: given an array, find the size of the smallest subarray in which the number of inversions is the same as in the original array.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.