A sequence $$$a$$$ of length $$$n$$$ is called palindromic if $$$a_i=a_{n-i+1}$$$ for all $$$1 \leq i \leq n$$$.

You are given the sequence $$$b$$$ of $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$. Determine whether it is possible to increase exactly one element of $$$b$$$ by $$$1$$$ in such a way that the resulting sequence will not be palindromic.

Gleb has just had a good time in a bar on Nekrasova street, and is now heading to the place of his accommodation that happened to be hotel Indigo. His path goes along Liteyny Avenue that we consider to be a perfect straight line.

For the purpose of this problem Gleb only moves along the avenue and across it. He now stays at point $$$0$$$ along the avenue and the hotel he goes to is located at point $$$L$$$. Moreover, the hotel is located on the other side of the avenue. There are $$$n$$$ pedestrian crossings between Gleb and Indigo, the $$$i$$$-th of them is located at integer point $$$x_i$$$. In order to get to the hotel Gleb needs to walk all the avenue from point $$$0$$$ to point $$$L$$$ and cross the street at some moment of this walk.

All crossings are equipped with a traffic light. All these traffic lights have cycles of the same duration. They go green for $$$g$$$ seconds and red for $$$r$$$ seconds. However, they are not synchronized, i.e. each traffic light has some random equiprobable cycle shift. All shifts are integers, so there are only $$$r + g$$$ possible shifts in total. Gleb knows integers $$$r$$$ and $$$g$$$ but at beginning he knows nothing about the shifts.

Each crossing traffic light has a timer that shows the current state of this traffic light's cycle. If the light is green, the timer shows how many seconds are left to cross the street, if the light is red, the timer shows how many seconds to wait before the light goes green. Gleb is able to notice the light's color and the timer state only when he is at the exact point this crossing and traffic light are located. The good part is that Gleb is capable of remembering everything he has seen during this walk, so he keeps in mind the current state of all the traffic lights he has already seen.

All coordinates are integer and are given in meters. Gleb moves with a speed of one meter per second. Moreover, it is known that pedestrian crossings are not too frequent. Formally, there are no three crossings located within $$$g + r$$$ meters.

Gleb can move in any direction along the avenue and cross it arbitrary number of times. It takes $$$b$$$ seconds to cross the avenue, and the traffic light must be green during all this period.

Gleb has socks of $$$n$$$ distinct colors. In particular, he owns $$$a_i$$$ pairs of socks of color $$$i$$$. He wears these pairs one after the other till there are no more clean pairs of socks left, then it is time for The Great Wash.

Gleb puts all of his socks into a washing machine with a drying option and waits for an two-three hours. Now, the worst part begins. Gleb needs to assemble socks in pairs again. To simplify the process we assume that all socks of the same color are indistinguishable. In other words, any two socks of the same color can form a pair. Obviously, Gleb never forms a pair of socks from two of distinct color.

Gleb performs the following process. We denote the set of all socks inside the washing machine as $$$A$$$ and the set of all socks that haven't been matched yet and lie near Gleb as $$$B$$$.

1. Gleb puts his hand into a washing machine and checks whether there are any socks left in $$$A$$$. If there are none, the process finishes. Otherwise, he puts out one random sock (with equal probabilities for all socks in $$$A$$$), we denote this sock as $$$x$$$. This is a single action that takes exactly one second.
2. He then tries to find a pair for this sock among all socks with no pair already extracted out of the washing machine and lie near him, i.e. all socks in set $$$B$$$.
3. Gleb considers all socks of $$$B$$$ in random order. All orders are equiprobable. It takes exactly one second to consider one sock from $$$B$$$. If the sock $$$x$$$ matches the sock just extracted from $$$A$$$ by color, they form a pair and this step finishes.
4. If all socks from $$$B$$$ were considered and no match for $$$x$$$ was found, Gleb puts $$$x$$$ in the heap of unpaired socks. In other words sock $$$x$$$ goes to set $$$B$$$.
5. Gleb goes back to step one.

While waiting for wash-and-dry cycle to finish Gleb wonders, what is the expected time the process described above will take? The last time he took part in a programming competition was several years ago, so he needs your help to find out the answer.

There are $$$n$$$ children numbered $$$1, 2, \dots, n$$$. They stand in a circle. Each child has a bag with non-empty set of distinct positive integers.

As a part of Christmas celebration, children want to play a game of the following rules:

1. Each child has to take exactly one integer from her bag.
2. Each child passes her integer to the next one, so child $$$1$$$ passes her number to child $$$2$$$, child $$$2$$$ passes her number to child $$$3$$$, and so one, child $$$n$$$ passes her number to child $$$1$$$.
3. Each child puts her newly acquired number back in her bag.
4. The procedure described above should be performed exactly once. Children win if after they are done with passing integers, each bag contains only distinct integers, i.e. no bag contains the same integer twice.

Help children win the game or find out that this is impossible.

For any positive integer $$$y$$$ we define $$$A(y)$$$ as the set of all positive integers that are anagrams of $$$y$$$. Formally, we consider the sequence of all digits of $$$y$$$ in decimal representation without leading zeroes, then we apply all possible permutations to this sequence. For any permutation we throw away leading zeroes and assemble digits back to an integer. All integers that can be obtained that way belong to $$$A(y)$$$. For example, for $$$2021$$$ set $$$A(2021)$$$ consists of integers $$$122$$$, $$$212$$$, $$$221$$$, $$$1220$$$, $$$2120$$$, $$$2210$$$, $$$1202$$$, $$$2102$$$, $$$2201$$$, $$$1022$$$, $$$2012$$$ and $$$2021$$$. Note, that set $$$A(y)$$$ always contains $$$y$$$, thus it is never empty.

For any positive integer $$$x$$$ we define $$$S(x)$$$ as the set of all positive integers $$$z$$$ such that greatest common divisor of all integers in $$$A(z)$$$ equals $$$x$$$.

You are given the integer $$$n$$$, find the minimum integer $$$z$$$ in $$$S(x)$$$, or determine that $$$S(x)$$$ is empty.

In graph theory, a cactus is a connected undirected graph in which any two simple cycles have at most one vertex in common.

Given an integer $$$n$$$, build a connected graph with $$$n$$$ vertices that is not a cactus. Note that your graph can't have self-loops or multiple edges. The number of edges in your graph should be minimum possible.

One of the greatest e-sport events, The Invitational TOAD-3 Championship, will feature $$$16$$$ best teams in the world. In order to prolong the fascinating event and acquire more money from advertising a double-elimination tournament scheme will be used.

First, all teams are ordered by their rating and the $$$i$$$-th team in the sorted list plays versus the team at position $$$(17-i)$$$. The winner of each of these matches goes to the winners' bracket, the loser goes to the losers' bracket.

Participants of the winners' bracket continue to play a single-elimination tournament, except that the losers of each round "drop down" into the losers' bracket.

Each round of the loser's bracket is conducted in two stages; a minor stage followed by a major stage. Both contain the same number of matches which is the same again as the number of matches in the corresponding round of the winners' bracket. If the minor stage of a looser's bracket round contains $$$2^k$$$ matches, there will be $$$2^k$$$ winners. Meanwhile, the $$$2^k$$$ matches in the corresponding round of the winners' bracket will produce $$$2^k$$$ losers. These $$$2^{k+1}$$$ teams will then form pairs for $$$2^k$$$ matches of the corresponding major stage of the looser's bracket. At this stage of the round, looser of the winners' bracket round can play only against winners of the minor stage of the looser's bracket.

In both brackets, before each round opponents are chosen at random to form pairs. Same apply to the process of forming pairs of type "loser from winners' bracket versus winner of the minor stage from the losers' bracket" at the major stages of the losers' bracket rounds.

All players who are eliminated from the same stage are considered to share the same position in the resulting ranking.

Below is the scheme of how the double-elimination tournament for 16 teams is held.

• The first round is played; winners of the first round form the winners' bracket, losers of the first round form the losers' bracket.
• The eight losers of the first round form pairs of the first minor stage of the losers' bracket, we denote this stage as $$$L_8a$$$. The four losers are eliminated (their participation in the tournament is over, they share places from $$$13$$$ to $$$16$$$), while the four winners proceed to the major stage of this round, we denote it as $$$L_8b$$$.
• The eight winners of the first round form pairs for the first round of the winners' bracket, we denote this as $$$W_8$$$. The four winners proceed to the stage $$$W_4$$$, four losers proceed to stage $$$L_8b$$$.
• During stage $$$L_8b$$$, each losing team from $$$W_8$$$ plays against the winning team from $$$L_8a$$$, the four losers are eliminated (they end up at places $$$9-12$$$), while the winners proceed to the stage $$$L_4a$$$.
• The four winners of $$$L_8b$$$ go to stage $$$L_4a$$$. The losers are eliminated (they end up at places $$$7-8$$$), while two winners proceed to stage $$$L_4b$$$.
• The four winners of $$$W_8$$$ form pairs for the second round of the winners' bracket (named $$$W_4$$$), the two winners proceed to stage $$$W_2$$$, the two losers proceed to stage $$$L_4b$$$.
• In stage $$$L_4b$$$, each losing team from $$$W_4$$$ plays against some winner $$$L_4a$$$, the two losers are eliminated (they end up at places $$$5-6$$$), while the winners proceed to stage $$$L_2a$$$.
• In stage $$$L_2a$$$ the two winners of $$$L_4b$$$ play one match against each other, the loser finishes the tournament at the $$$4$$$-th place, the winner proceeds to stage $$$L_2b$$$ (also know as loser's bracket final).
• In stage $$$W_2$$$ one match is played. The winner proceeds directly to the grand final, the loser proceeds to stage $$$L_2b$$$.
• In stage $$$L_2b$$$ one match is played, the winner proceeds to the grand final, the loser finishes the tournament at the third place.
• The winner of the match in grand final is declared a champion, the loser finishes the tournament second.

You are given the list of teams with the results of all matches played by this team during the tournament in chronological order. Determine the final place for each team.

Given the string $$$S$$$, consisting of letters 'I', 'V', 'X', 'L', 'C', 'D' and 'M'. Your task is to split the string to the minimum number of strings that are:

• correctly written Roman numerals;
• palindromes.

The following table from Wikipedia displays how the Roman Numerals are written:

• The numerals for 4, 9, 40, 90, 400 and 900 are written using "subtractive notation" where the first symbol is subtracted from the larger one (for example, for 40 ("XL") 'X' (10) is subtracted from 'L' (50)). These are the only subtractive forms in standard use.
• A number containing several decimal digits is built by appending the Roman numeral equivalent for each, from highest to lowest.
• Any missing place (represented by a zero in the place-value equivalent) is omitted.
• The largest number that can be represented in the Roman notation is 3,999 (MMMCMXCIX).

Given $$$n$$$ points $$$p_1, p_2, \ldots p_n$$$ in the two-dimensional Euclidean plane, calculate the total pairwise Euclidean distance between them. Simple as that.

Recall that Euclidean distance between two points $$$a = (x_1, y_1)$$$ and $$$b = (x_2, y_2)$$$ is defined as follows:

$$$$$$ \operatorname{dist}(a, b) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$$$$$

The game "Dungeons and Rainbows" uses dices of various shapes and various number of faces. The game process consists of moving between dungeons and performing various actions. The game has $$$n$$$ states in total, that number already includes all possible combinations of positions, items, skills and so on. The game rules define for each state which particular dice should be used in order to determine the next state. As the dice being used can have more than $$$n$$$ faces, rules of the game define how many faces of the dice should correspond to each particular outcome (transition to some other state).

For example, consider there are $$$3$$$ states in a game and for one of them it is required to use a dice with $$$5$$$ faces. One possible distribution can be the following: $$$2$$$ faces correspond to transition to the state $$$1$$$, $$$1$$$ face corresponds to transition to state $$$2$$$ and remaining $$$2$$$ faces correspond to transition to state $$$3$$$.

Players start the game in state $$$1$$$ and the game lasts $$$k$$$ rounds. In order to get a spectacular ending of the game players must make a transition to state $$$s$$$ in the last round. Note, that it doesn't matter whether they have already visited this state in other rounds or not.

Experienced host knows probabilities of each face of every dice. In each round he chooses which faces will correspond to which outcomes. So, at the beginning of every round the host assigns the next state for face of the dice that will be used in this round (this is determined by current state only). If it happens that players transit to the same state more than once, the host can make a different assignment of outcomes to faces every time.

The host wants to maximize the probability that the game will have a spectacular ending. Calculate this probability if the host acts optimal.

The Kingdom of Berland is great and glorious, but it is currently ruled by a powerful and peevish king Vlad who got old and now sees treasons and plots all around him. He now suspects his two sons in planning a coup, so he decided to establish his control over all their communications.

The Kingdom of Berland is formed by $$$n$$$ cities connected by $$$m$$$ bidirectional roads in a way that makes it possible to get from any city to any other city using these roads only. The elder son of King Vlad lives in city $$$1$$$, while the younger son lives in city $$$n$$$.

In order to control all messengers who run between city $$$1$$$ and city $$$n$$$ Vlad wants to pick some cities and establish a secret police department in each of them. It turns out that no matter how powerful you are, you are not able to keep all the things secret. If city $$$v$$$ has a police department established in it, the mayor of this city somehow becomes aware of this. Moreover, the mayor of any city that is connected to $$$v$$$ by a direct road becomes aware of this police departments as well.

Of course, the King wants to keep his sons unaware of his new secret police. Therefore he has three limitations.

1. There should be no way to get from city $$$1$$$ to city $$$n$$$ using roads without visiting any city that has a police department in it.
2. There can be no secret police department in city $$$1$$$ and city $$$n$$$. Though, there can be a secret police department in a city that is connected to city $$$1$$$ or city $$$n$$$ by a direct road.
3. The total number of city mayors that are aware of at least one secret police department should be minimum possible.

You don't want to help King Vlad in his malicious games, but the problem itself looks nice so you want to find the optimal answer just for fun.

With the speed of light are food technologies conquering cities and towns of Berland, and, especially, its gorgeous capital City N.

FoodBerry is the largest food delivery that operates in City N. Consider the city as a two-dimensional square with sides parallel to coordinate axis. The bottom left corner of this square has coordinates $$$(-10^{4}, -10^{4})$$$ and the top right corner has coordinates $$$(10^{4}, 10^{4})$$$. All coordinates are given in meters.

FoodBerry has one Super Large Warehouse located at $$$(0, 0)$$$ and $$$n$$$ dark stores (smaller warehouses), the $$$i$$$-th of them is located at point $$$(x_i, y_i)$$$. Each dark store has two types of delivery: by foot and by car. Delivery by foot can be used for all points that are located no more than $$$a$$$ meters from this dark store, while delivery by car can be used for up to $$$b$$$ meters distances ($$$a \leq b$$$, obviously). During one day each dark store is able to execute no more than $$$c$$$ deliveries. Moreover, due to the limitation of vehicles, no more than $$$d$$$ of these deliveries can be done by car ($$$d \leq c$$$).

Super Large Warehouse is located at $$$(0, 0)$$$ and is capable of performing any number of deliveries to any locations in the city. However, using this option is expensive and FoodBerry tries to avoid it to for as long as possible.

In this problem we are going to analyze one day of FoodBerry in City N. There were $$$m$$$ orders during that day, they are given in the order they were made and processed. The $$$i$$$-th order asks for the delivery to point $$$(x'_i, y'_i)$$$. For the purpose of this problem we introduce some bold assumptions.

1. First all orders were received. Then all deliveries were executed.
2. No two orders appear in the same moment of time.
3. After each order appears, there is enough time to re-process everything. Scheduling center assumes there will be no more orders today and makes a distribution of orders between dark stores (and the warehouse). Moreover, for each delivery it is determined whether it should be done by foot or by car. This distribution is completely re-done after any new order appears, it doesn't need to depend on the previous distribution in any way.

Of course, each distribution is done with respect to limitations on distance and quantity of orders per dark store given by parameters $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$. If there is a distribution of orders that satisfies all the requirements and executes all the deliveries without using Super Large Warehouse, the scheduling program goes for it.

Assuming all distributions are made optimal, what is the minimum order index $$$i$$$ such that there will be no way to make a valid distribution without using Super Large Warehouse?

There are $$$n$$$ crossings in Bytetown, connected with $$$m$$$ bidirectional roads. The $$$i$$$-th road connects crossings $$$u_i$$$ and $$$v_i$$$, has length of $$$l_i$$$ meters and a cost factor of $$$c_i$$$.

In order to ease the road traffic, a special fine system is used in Bytetown. You can drive with any speed and change the speed whenever you want. However, if the maximum speed during your travel along the road $$$i$$$ is $$$v$$$ meters per second, you should pay $$$v \cdot c_i$$$ dollars fine.

You live near the crossing $$$1$$$ and want to get to the crossing $$$n$$$ in no more than $$$T$$$ seconds. What is the smallest possible fine you will have to pay if you choose the route and the speed for each road optimally?

You are given six positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$ and $$$f$$$. You need to find out whether there exists a triangle $$$ABC$$$ with the following properties.

• $$$AB/BC=a/b$$$;
• $$$BC/CA=c/d$$$;
• $$$CA/AB=e/f$$$;
• Area of $$$ABC$$$ is positive;
• The perimeter of the triangle is integer.

If such triangle exists, find the minimum possible value of its perimeter.

Max enjoys to play chess a lot. The only thing in this world that excites him more is to come up with ideas for programming contest's problems. This particular problem is of an ultimate delight for him as he was able to join his interests in one masterpiece.

Max has invented a tree-coordinate two-dimensional board and you are going to move a chip named treeshop along it. Formally, you are given two connected undirected acyclic graphs (also known as trees) of size $$$n_1$$$ and $$$n_2$$$ respectively. The position of a treeshop is defined by a pair of vertices $$$(u, v)$$$, where $$$u$$$ is some vertex of the first tree and $$$v$$$ is some vertex of the second tree.

The distance between two vertices of the same tree equals to the number of edges the only simple path connecting these two vertices consists of. A treeshop is able to move from position $$$(u, v)$$$ to position $$$(u', v')$$$ in one move if and only if the distance between vertices $$$u$$$ and $$$u'$$$ equals to the distance between vertices $$$v$$$ and $$$v'$$$. Obviously, if it is possible to get from $$$(u, v)$$$ to $$$(u', v')$$$ in one move, it is also possible to get from $$$(u', v')$$$ to $$$(u, v)$$$ in one move.

You are given $$$q$$$ pairs of positions. For each of them you need to compute the minimum number of moves it will take a treeshop to get from one of these positions to the other.