The São Paulo Zoo does an excellent job feeding its three tigers. One day, however, the amount of food was scarce, there was only an amount $$$W$$$ of food. They didn't know if the remaining quantity was enough to feed them, and now they want to know, given the amount of food that each tiger eats, if the remaining food is sufficient to satisfy their hunger.
The input has one line that contain four numbers, $$$W$$$, $$$A$$$, $$$B$$$, $$$C$$$ $$$(1 \le W, A, B, C \le 1000)$$$ representing, respectively, the remaining food and the amount in grams that each tiger will eat that day.
Print a line with the character 'S' if it is possible to feed the tigers, or 'N' otherwise.
300 100 100 100
S
10 3 4 5
N
Carlos loves to ride his bicycle in Ibirapuera Park, just like many people from São Paulo, but he doesn't like when the park is too crowded, making it difficult for him to enjoy his ride. On a map of the park that Carlos found, the park is described as having $$$N$$$ different locations connected by $$$M$$$ paths of varying distances, and Carlos verified that it is possible to go from any point in the park to any other using these paths.
Carlos's life changed when he started working in the park, and as a benefit of working there, he can ride his bicycle before the park opens, allowing him to enjoy the entire park while it is empty.
Carlos is on his day off and wants to take a bike ride from location $$$1$$$ to $$$N$$$, but he does not want to pass through any location that already has people there. When the park opens, numerous people start entering through $$$K$$$ different entrances. Once the people enter, they begin to use all possible paths to go to all locations. If the distance of a path is $$$D$$$, it takes people $$$2D$$$ minutes to walk the entire path. Carlos, on the other hand, has double the speed of the people, meaning he takes $$$D$$$ minutes to complete a path of distance $$$D$$$ on his bicycle.
With this in mind, Carlos is interested in knowing the minimum time he needs to leave from location $$$1$$$ before the park opens so that there is a way to reach point $$$N$$$ without passing through any location that already has people. During the journey, Carlos can arrive at some of the park's locations at the same moment as the people, but if the people arrive before Carlos, he can no longer pass through that location on his way.
The first line contains 3 integers, $$$N$$$, $$$M$$$, and $$$K$$$ $$$(2 \le N \le 10^5, N - 1 \le M \le 10^5, 1 \le K \le N)$$$. The next $$$M$$$ lines each contain 3 integers $$$A$$$, $$$B$$$, and $$$C$$$, indicating that there is a path between locations $$$A$$$ and $$$B$$$ with distance $$$C$$$ $$$(A \ne B$$$ and $$$1 \le A,B \le N$$$ and $$$1 \le C \le 20000)$$$. The paths can be used to go from $$$A$$$ to $$$B$$$ as well as from $$$B$$$ to $$$A$$$, and there is only one path between each pair of locations.
The last line contains $$$K$$$ distinct integers indicating which $$$K$$$ locations have an entrance that people enter as soon as the park opens.
Output a single integer indicating the smallest non-negative integer time in advance that Carlos needs to start his journey from location $$$1$$$ and reach location $$$N$$$ in such a way that there is a possible path without passing through any location with people.
2 1 1 1 2 10 2
10
4 3 1 1 2 40 2 3 10 2 4 30 3
20
5 4 3 1 2 10 5 2 10 3 2 6 4 5 15 1 4 3
0
Explanation of example 1:
Carlos needs to start at location $$$1$$$ with $$$10$$$ minutes in advance before the park opens. This way, he can arrive at location $$$2$$$ exactly when the park opens and the people enter. If he leaves with $$$9$$$ minutes in advance, the people will arrive at location $$$2$$$ before Carlos, and thus he will not be able to complete his journey.
Explanation of example 2:
Carlos needs to start at location $$$1$$$ with $$$20$$$ minutes in advance before the park opens. This way, he can reach the halfway point between location $$$1$$$ and $$$2$$$ when the park opens. When the park opens, people enter through location $$$3$$$ and arrive at location $$$2$$$ after twenty minutes, and Carlos also arrives at the same time. After that, since Carlos is faster than the people, he can reach location $$$4$$$ before the people arrive. If Carlos leaves with less than $$$20$$$ minutes in advance, the people will arrive at location $$$2$$$ before him, and Carlos will have no path to reach location $$$4$$$.
Explanation of example 3:
Carlos can start riding his bicycle as soon as the park opens, leaving location $$$1$$$ at time $$$0$$$, arriving at location $$$2$$$ at time $$$10$$$ minutes, and reaching the final location $$$5$$$ at time $$$20$$$ minutes, while the people will arrive at location $$$1$$$ at time $$$0$$$, at location $$$2$$$ at time $$$12$$$ minutes, and at location $$$5$$$ at time $$$30$$$ minutes.
This year is the first year of the Paulista Programming Marathon, and its organizers are creating several programs to help organize the event. Wilson is suspecting that universities from cities outside the state of São Paulo will also want to officially participate in the event, as everyone is excited about this new programming marathon. However, only cities from the state of São Paulo can officially participate.
Wilson is so suspicious that he obtained approximate integer coordinates of the registered cities as if they were points on a Cartesian plane. In this approximate model, the state of São Paulo is geometrically drawn as the following polygon, as shown in the image: $$$(0, 100)$$$, $$$(100, 0)$$$, $$$(200, 0)$$$, $$$(100, -100)$$$, $$$(0, -100)$$$, $$$(-100, 0)$$$, $$$(-200, 0)$$$, $$$(-100, 100)$$$.
Now Wilson wants to make a program that checks which cities are inside or on the edge of this polygon to determine which cities are really in the state of São Paulo, but he is not good at geometry and asked for your help.
The first line contains an integer $$$N$$$ representing the number of cities $$$(1 \le N \le 100)$$$. In the following $$$N$$$ lines, two integers $$$x$$$ and $$$y$$$ are given, representing the coordinates of each city $$$(-1000 \le x, y \le 1000)$$$.
The output should contain $$$N$$$ lines with only one character to respond in order about each of the cities given in the input, 'S' if the point representing the city is inside or on the edge of the polygon representing the state of São Paulo, or 'N' otherwise.
3 0 0 100 50 100 -50
S N S
5 0 100 1 100 0 99 -1 100 0 101
S N S S N
The city of São Paulo is known for having great hot dog snacks. Ernesto is one of the owners of a very famous hot dog trailer in the area. To make a quality hot dog, he follows some rules:
Ernesto has $$$N$$$ ingredients in his trailer and he numbers them from $$$1$$$ to $$$N$$$. The first ingredients from $$$1$$$ to $$$P$$$ are all types of bread. The ingredients numbered from $$$P+1$$$ to $$$P+S$$$ are all types of sausage. The possible remaining ingredients numbered from $$$P+S+1$$$ to $$$N$$$ are various other ingredients. Ernesto will inform you of a list of $$$M$$$ pairs of ingredients that he thinks do not go well together and has asked for your help in determining how many different ways he can make hot dogs while respecting his rules.
The first line of input contains $$$4$$$ integers, $$$N$$$, $$$M$$$, $$$P$$$, and $$$S$$$ $$$(2 \le N \le 20, 0 \le M \le \frac{N(N-1)}{2}, P \ge 1, S \ge 1, P+S \le N)$$$ which are the integers indicated in the statement.
The next $$$M$$$ lines contain two integers $$$A$$$ and $$$B$$$ $$$(A \ne B, 1 \le A,B \le N)$$$ indicating that ingredients $$$A$$$ and $$$B$$$ do not go well together (all pairs are different).
Print only one line with an integer indicating the number of possible hot dogs.
4 1 1 1 3 4
3
6 2 2 1 4 1 5 6
9
The 25 de março street is one of the most well-known shopping spots in São Paulo. Alceu and Bernardo are two delivery man who work collecting products from stores to make deliveries. They have a list of $$$N$$$ products that can be collected. For each product, they know its value and also the position in meters where the product is located on the 25 de março street, with the distance measured from the beginning of the street.
On a workday, each delivery man can collect any number of products, but they cannot pick two products that are more than $$$D$$$ meters apart, to ensure that their work journey is not too tiring.
Alceu and Bernardo want your help to calculate the maximum sum of the product values that can be collected by both in a workday. Each product can only be collected by one of the delivery man.
The first line contains two integers, $$$N$$$ and $$$D$$$, representing the number of listed products and the maximum distance $$$D$$$ between products collected by the same delivery man $$$(1 \le N \le 10^5, 0 \le D \le 10^9)$$$.
In the next $$$N$$$ lines, we have two integers $$$X_i$$$ and $$$V_i$$$ indicating the position in meters and the value of each product $$$(0 \le X_i \le 10^9, 1 \le V_i \le 10^4)$$$.
The output should contain only one integer with the maximum sum of the values that the two delivery man can collect together.
4 2 0 10 2 15 5 20 8 40
65
4 2 0 10 2 15 5 30 8 40
70
Newto went on a trip with his friends and brought several clothes to keep him warm, as he was warned that the place they were going to is very cold. Upon arriving there, he discovered that, in fact, the place is very hot. To make it worse, his friends turned on the air conditioning in some rooms of the house in heat mode at high temperatures, causing the place to become very warm.
He wants to solve this by moving through the rooms, turning on the air conditioning to lower the temperature and cool down the house. The house has $$$N$$$ rooms and $$$N-1$$$ corridors between them, such that there is a way to walk from any room to any other room. Newto starts in room $$$1$$$, representing the room he is currently in, and he wants to traverse the corridors the fewest number of times to ensure that the temperature of all rooms is less than or equal to a value $$$K$$$, which he believes is the ideal temperature at the moment. Upon arriving in a room, he can choose any temperature he desires in the range from $$$1$$$ to $$$99$$$ to be the new temperature of that room. As the path may be long, possibly involving passing through the same room more than once, Newto asks for your help to determine the minimum number of times he needs to traverse the corridors.
The first line contains two integers $$$N$$$ and $$$K$$$ $$$(1 \le N \le 10^5, 1 \le K \le 99)$$$, indicating the number of rooms in the house and the ideal temperature for Newto. The second line will have $$$N$$$ values $$$v_i$$$, the current temperature of the $$$i$$$-th room $$$(1 \le v_i \le 99)$$$. The next $$$N-1$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ indicating that there is a corridor between rooms $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le N$$$ and $$$a_i \ne b_i)$$$.
Your program must print a single value, the minimum number of times Newto must traverse corridors to achieve his goal.
5 4 3 7 5 2 6 1 2 1 3 3 4 3 5
4
4 35 30 31 32 33 1 2 2 3 3 4
0
Explanation of example 1:
Newton needs to cool down the rooms 2, 3 and 5. Possible path: 1 → 2 → 1 → 3 → 5.
André was responsible for checking the registrations for the Paulista Programming Marathon, and his job was to ensure that the Brazilian state of the registration was indeed São Paulo. The registration system uses the standard ISO 3166-2 codes to represent the main subdivisions of Brazil, as shown in the table below:
Unfortunately, a bug occurred in the system, and all the registration codes had one character replaced by '?', and now you need to help André determine if a certain code with one character replaced by '?' was originally equal to the code for São Paulo (BR-SP) or not.
The input consists of a single line containing one of the $$$27$$$ codes from the table in the statement, but with one character replaced by '?'.
The output consists of a single line with the character 'S' if the original code was definitely the code of São Paulo, or 'N' if it definitely was not the code of São Paulo, or 'T' if it could be the code of São Paulo but it is not possible to be sure about it.
B?-SP
S
BR-M?
N
BR-S?
T
Carolina, a skilled programmer from Monitoramento e Proteção Paulista (MPP), specialized in information security, faces her biggest challenge: a hacker has invaded the database of the social security system in São Paulo!
The hacker completely scrambled the database, but fortunately, Carolina has a plan to recover this data. We can represent the scrambled database as a very long sequence of data. Carolina divides this sequence into consecutive blocks of size $$$K$$$, meaning the first block contains positions from $$$0$$$ to $$$K-1$$$, the next from $$$K$$$ to $$$2K-1$$$, and so on. To recover the original sequence, Carolina wants to apply a sequence of operations to the database, which consist of block rotations, position swaps, and queries on data segments to check consistency.
Formally, we have a sequence $$$A$$$ of integers that represents the initial positions of the data (scrambled), i.e., initially $$$A[i] = i$$$ for all $$$i \ge 0$$$. It can be considered that the sequence is infinite. Carolina's plan consists of operations of the following types:
1 p: rotates each of the blocks to the left $$$p$$$ times. This operation is applied to each block independently. Each time the block is rotated to the left, the last value of $$$A[i]$$$ becomes the first, and all other values of $$$A[i]$$$ become equal to $$$A[i+1]$$$.
2 s t: swaps the values of $$$A[i\cdot K + s]$$$ and $$$A[i\cdot K + t]$$$ for all $$$i \ge 0$$$.
3 l r: prints the sum of $$$A[i]$$$ for all $$$i$$$ such that $$$l \le i \le r$$$.
After implementing the recovery system, Carolina needs to validate whether the operations were applied correctly. Write a program that, given the operations of Carolina's plan in the order they were applied, prints the output of all operations of type 3.
The first line contains two integers $$$Q$$$ and $$$K$$$ $$$(1 \le Q \le 10^5, 2 \le K \le 10^6)$$$, the number of operations and the size of the blocks, respectively.
The following $$$Q$$$ lines contain the description of each operation, as in the statement, in the order they are applied. It is guaranteed that $$$1 \le p \le K$$$ in each operation of type 1, that $$$0 \le s, t \lt K, s \neq t$$$, in each operation of type 2, and that $$$0 \le l \le r \le 10^9$$$ in each operation of type 3.
The output consists of one line for each operation of type 3, containing an integer equal to the result of each operation of type 3, in the order they appear in the input.
5 5 3 1 8 2 0 3 3 1 8 1 3 3 2 7
36 33 28
6 500 1 100 2 25 75 3 1050 9000 1 50 2 30 60 3 1000000 500000000
39948825 124999500250500150
Explanation of example 1:
In this first example, the first two blocks of 5 positions look like this:
Betinho was born in the state of São Paulo and while he was looking at his ID, he noticed that the issuing authority of the document was SSP-SP (Public Security department of São Paulo). He found the name quite curious because if you concatenate the abbreviation of the state of São Paulo "SP" with itself and add an "S" in front (to its left), the result is "SSPSP", which is the same as the name of the issuing authority. In the same way, it is possible to invent a sequence of increasingly larger names by following the same process, where the next term is equal to the previous one concatenated with itself plus an "S" in front. Thus, the first terms of the sequence are as follows:
| $$$s_1$$$ = SP |
| $$$s_2$$$ = SSPSP |
| $$$s_3$$$ = SSSPSPSSPSP |
| $$$s_4$$$ = SSSSPSPSSPSPSSSPSPSSPSP |
| $$$s_5$$$ = SSSSSPSPSSPSPSSSPSPSSPSPSSSSPSPSSPSPSSSPSPSSPSP |
| $$$...$$$ |
Betinho is very curious about this sequence and came up with a challenge. Betinho will write a string $$$A$$$ made up only of the letters 'S' and 'P' and will also create string $$$B$$$ formed by the concatenation of $$$N$$$ terms of this sequence. You must calculate how many intervals of string $$$B$$$ are also substrings of string $$$A$$$. More formally, you need to calculate the number of distinct pairs $$$(i,j)$$$ such that the string formed by the characters of $$$B$$$ from position $$$i$$$ to $$$j$$$ is a substring of string $$$A$$$.
For example, if $$$A$$$ = "PSP" and $$$B = S_2 + S_1 =$$$ "SSPSPSP", in this case, the answer is $$$14$$$ because $$$A$$$ has $$$5$$$ distinct substrings ("P", "S", "PS", "SP", "PSP") and these substrings can be found in $$$14$$$ different intervals of string $$$B$$$:
| $$$(1,1) →$$$ |S|SPSPSP | $$$(3,5) →$$$ SS|PSP|SP | $$$(5,7) →$$$ SSPS|PSP| |
| $$$(2,2) →$$$ S|S|PSPSP | $$$(4,4) →$$$ SSP|S|PSP | $$$(6,6) →$$$ SSPSP|S|P |
| $$$(2,3) →$$$ S|SP|SPSP | $$$(4,5) →$$$ SSP|SP|SP | $$$(6,7) →$$$ SSPSP|SP| |
| $$$(3,3) →$$$ SS|P|SPSP | $$$(5,5) →$$$ SSPS|P|SP | $$$(7,7) →$$$ SSPSPS|P| |
| $$$(3,4) →$$$ SS|PS|PSP | $$$(5,6) →$$$ SSPS|PS|P |
Betinho needs your help now to solve this challenge. Since the answer can be very large, print the answer modulo $$$998244353$$$.
The input consists of $$$3$$$ lines. The first line contains the string $$$A$$$ of up to $$$1000$$$ letters made up only of characters 'S' and 'P'. The second line contains the integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ equal to the number of terms of the sequence that will be concatenated to form string $$$B$$$. The third line contains $$$N$$$ integers $$$T_i$$$ $$$(1 \le T_i \le 1000)$$$ indicating the terms of the sequence that should be concatenated to form string $$$B$$$.
The output should contain only one line with the number of intervals of string $$$B$$$ that are substrings of string $$$A$$$ modulo $$$998244353$$$.
PSP 2 2 1
14
SSS 1 3
11
S 5 1 2 3 4 5
57
Pedrinho did not like studying mathematics in school. He already didn't enjoy calculations that only involved numbers, but he had to start studying polynomials, which have several terms in terms of '$$$x$$$' that he never understood. When he began studying composite functions, he really gave up on mathematics for good.
As a homework, he needs to calculate the composite function of two polynomials, that is, given two polynomials $$$p(x)$$$ and $$$q(x)$$$, calculate the coefficients of the polynomial $$$p(q(x))$$$. For example, if $$$p(x) = x^2 + x + 2$$$ and $$$q(x) = x + 1$$$, then $$$p(q(x)) = (x+1)^2 + (x+1) + 2 = x^2 + 3x + 4$$$. Since Pedrinho already gave up on mathematics, he asked for your help to calculate all the coefficients of the resulting polynomial. Since the coefficients can be very large, the teacher asked to calculate the remainders of the coefficients modulo $$$998244353$$$.
The input consists of $$$4$$$ lines.
The first line contains an integer $$$N_1$$$ $$$(1 \le N_1 \le 300)$$$ equal to the degree of polynomial $$$P$$$. The second line contains $$$N_1 + 1$$$ integers $$$P_i$$$ $$$(0 \le P_i \le 10^6)$$$ indicating the coefficients of polynomial $$$P$$$ from the lowest degree $$$0$$$ to the highest degree $$$N_1$$$, that is, polynomial $$$P$$$ is equal to the sum of $$$P_i \cdot x^i$$$ for $$$i$$$ from $$$0$$$ to $$$N_1$$$.
The third line contains an integer $$$N_2$$$ $$$(1 \le N_2 \le 300)$$$ equal to the degree of polynomial $$$Q$$$. The fourth line contains $$$N_2 + 1$$$ integers $$$Q_i$$$ $$$(0 \le Q_i \le 10^6)$$$ indicating the coefficients of polynomial $$$Q$$$ in the same manner as the coefficients of polynomial $$$P$$$, from the lowest degree to the highest. The leading coefficient of both polynomials is different from $$$0$$$.
Print a line with $$$N_1 \cdot N_2 + 1$$$ integers equal to the coefficients of $$$p(q(x))$$$ modulo $$$998244353$$$, in order from the lowest degree to the highest degree.
2 2 1 1 1 1 1
4 3 1
2 1 1 1 2 1 1 1
3 3 4 2 1
Explanation of example 1:
Example from the statement, $$$p(x) = x^2 + x + 2$$$, $$$q(x) = x + 1 \implies p(q(x)) = x^2 + 3x + 4$$$.
Matheus practices kickboxing and spends a lot of time working on his kicks. In his kick training, he performs several consecutive kicks and then rests a bit, thus dividing his training into several series of kicks. However, as Matheus gets tired during the training, he never performs a series of consecutive kicks with more kicks than the previous series.
Matheus wants to train to achieve a total of $$$N$$$ kicks and is curious to know how many different ways he can divide his series of kicks without ever increasing the number of consecutive kicks. Additionally, he never performs a series of $$$K$$$ kicks because he finds it boring. For example, if $$$N = 4$$$ and $$$K = 3$$$, there are $$$4$$$ ways to divide his series:
Note that in none of the possibilities does Matheus perform a series with $$$3$$$ consecutive kicks, because we have $$$K = 3$$$. Furthermore, in none of the possible trainings does he perform a series of $$$2$$$ kicks after a series of a single kick, as he cannot perform a series with more kicks than the previous one.
Matheus now wants your help to find out how many ways he can divide his training. Since the number of ways can be very large, print the answer modulo $$$998244353$$$.
The input consists of a single line containing two integers, $$$N$$$ and $$$K$$$ $$$(1 \le N \le 4000, 1 \le K \le N)$$$.
The output should contain only a single integer, the answer modulo $$$998244353$$$.
2 1
1
4 3
4
100 7
108559115
Sofia is organizing her collection of books. She has $$$N$$$ stacks of books, each one should contain only books of the same genre. For this reason, Sofia has encoded the genres of her books with numbers from $$$1$$$ to $$$N$$$, such that books of genre $$$i$$$ should be in stack $$$i$$$.
To make her task more fun, Sofia will try to organize her collection by making only the following type of move: taking the book from the top of one stack and placing it on the top of another stack.
Tell her if it is possible to organize her collection using only this type of move. She can make as many moves as necessary.
The first line contains the integer $$$N$$$ $$$(1 \le N \le 100)$$$, the number of stacks (and genres of books). The following $$$N$$$ lines contain the description of the $$$N$$$ stacks. Each line starts with a non-negative integer $$$K_i$$$ equal to the number of books in that stack, followed by $$$K_i$$$ integers $$$L_j$$$ $$$(1 \le L_j \le N)$$$ equal to the genre of each of those books. The books are described in the list such that the last one is on top.
It is guaranteed that $$$\sum_{i=1}^{N} K_i \le 300$$$. Note that there may be no books of some of the $$$N$$$ genres.
Print only one line with a character, 'S' if it is possible to organize the books according to the statement or 'N' if it is not possible.
3 3 3 2 1 0 0
S
2 2 1 2 2 1 2
N
Explanation of example 1:
She can move the book of type $$$1$$$ to stack $$$2$$$, then move the book of type $$$2$$$ to stack $$$2$$$, and then it is possible to move the book of type $$$3$$$ to stack $$$3$$$, thus the book of type $$$3$$$ will already be in the right place. After that, she can move the book of type $$$2$$$ to stack $$$3$$$, then the book of type $$$1$$$ to stack $$$1$$$. Finally, move the book of type $$$2$$$ to stack $$$2$$$ and thus all the books will be in the correct stack.
The Shell Beach, located in Guarujá, is known for having many shells. A group of local scientists has developed a robot capable of collecting shells from the seabed. The robot first identifies a sequence of $$$N$$$ shells in a line on the seabed, assigns positions from $$$1$$$ to $$$N$$$ to them, and detects the type of each shell, represented by some integer from $$$1$$$ to $$$N$$$.
After this, the robot chooses the first shell to collect. As soon as the robot reaches the seabed and collects the first shell, all shells in positions with a difference less than or equal to $$$K$$$ compared to the position of the first shell end up being covered by sand due to the impact of the robot's landing. For example, if $$$K = 2$$$ and the position of the first shell is $$$5$$$, the shells in positions $$$3$$$, $$$4$$$, $$$6$$$, and $$$7$$$ gets covered by sand.
After collecting the first shell, the robot can only collect the uncovered shells that are in a position less than the position of the first shell, freely deciding which of these possible shells to take or not.
Now this group of scientists is curious about how many different sets can be collected by this robot. Two shells of the same type can be considered indistinguishable, meaning that two sets of shells are different if and only if there is some type of shell with a different quantity between the two sets. Since the answer can be very large, print the answer modulo $$$998244353$$$.
The first line contains two integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(0 \leq K \lt N)$$$ which are respectively the number of shells in line detected by the robot and the integer $$$K$$$ that indicates the position difference at which the shells are covered when the robot collects the first shell. The second line contains $$$N$$$ integers $$$T_i$$$ $$$(1 \leq T_i \leq N)$$$ indicating the types of shells found by the robot in order of their positions from $$$1$$$ to $$$N$$$.
The output should contain only one integer equal to the number of different sets of shells that can be collected by the robot in a single trip to the sea modulo $$$998244353$$$.
3 2 1 2 3
3
7 3 1 2 3 1 2 3 3
11
Explanation of example 1:
Possible sets: $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$. Only the first shell can be taken; the others get covered.
Explanation of example 2: Possible sets: $$$\{1\}$$$, $$$\{1, 2\}$$$, $$$\{1, 2, 3\}$$$, $$$\{1, 2, 3, 3\}$$$, $$$\{1, 3\}$$$, $$$\{1, 3, 3\}$$$, $$$\{2\}$$$, $$$\{2, 3\}$$$, $$$\{2, 3, 3\}$$$, $$$\{3\}$$$, $$$\{3, 3\}$$$.
Diogo is a child who loves to play by jumping on the steps of the park's staircase in his city. Each step of the staircase has a light, and Diogo enjoys jumping on the steps that are illuminated. He always jumps every $$$K$$$ steps where $$$K$$$ is greater than $$$1$$$, as he does not like to climb the stairs like everyone else normally does by stepping on every step. In other words, if we number the steps starting from $$$1$$$, Diogo will land on steps $$$K$$$, $$$2K$$$, $$$3K$$$, and so on.
Diogo always tries to find out the number $$$K$$$ that will allow him to jump on the largest number of illuminated steps. Therefore, he asked for your help to develop a program that calculates the maximum number of illuminated steps he can jump on.
Initially, all the step lights are off, and you will receive a list of numbers indicating which steps will toggle the state of its light in order. For each operation of toggling the light of a step, your program must respond with the maximum number of lights Diogo can step on by choosing the best possible $$$K$$$ to jump every $$$K$$$ steps $$$(K \gt 1)$$$.
The first line contains an integer $$$N$$$ indicating the number of light operations $$$(1 \leq N \leq 10^5)$$$. The second line contains $$$N$$$ integers $$$D_i$$$ indicating in order the number of the step that will toggle the state of its light, either turning it off or on $$$(2 \leq D_i \leq 10^6)$$$.
For each light operation, you should print a line with the maximum number of illuminated steps that Diogo can step on if he jumps every $$$K$$$ steps for some $$$K$$$ greater than $$$1$$$.
6 2 4 6 2 15 9
1 2 3 2 2 3
4 3 5 25 50
1 1 2 3