IT is hiding in the abandoned house. To get there children need to open the door with a tricky lock. The lock is in fact a tree with $$$n$$$ vertices, each of them is either white or black. The lock opens after every vertex is eliminated. For that purpose 2 operations are available:
- Change the color of one vertex.
- Set up a chain reaction eliminating a group of connected vertices of the same color. More formally, one vertex of color $$$c$$$ can be chosen, then the group of vertices of color $$$c$$$, which can be reached from the chosen vertex through the vertices of color $$$c$$$, will be eliminated.
Naturally, the children want to get inside sooner, so they wonder how many operations are needed to open the lock.
The first line contains $$$n$$$ — the number of vertices in the graph. ($$$1 \le n \le 200\,000$$$). The next line contains a string $$$s$$$ of the length $$$n$$$ consisting of $$$0$$$ and $$$1$$$. If the $$$i$$$-th symbol of the string $$$s$$$ is $$$0$$$, than $$$i$$$-th vertex is white, otherwise — it is black. The next $$$n - 1$$$ lines contain 2 integer numbers each $$$a_i$$$ and $$$b_i$$$ — the edges of the tree ($$$1 \le a_i, b_i \le n$$$).
It is guaranteed that the edges form a tree.
Output one number — the minimum number of operations needed to open the lock.
4 1000 1 2 1 3 1 4
2
In the first test case the lock can be open with 2 operations as follows:
- Change the color of vertex $$$1$$$ to white.
- Set up a chain reaction from vertex $$$1$$$, which will eliminate every vertex.
Joker is well known for his madness. That's why he uses base $$$a$$$ numeral system, where all numbers consist of digits from $$$0$$$ to $$$a - 1$$$. Also Joker likes to dance. He can dance for a very long time so he created a rule for himself which will limit his dancing. Naturally, the rule is also crazy: when Joker dance, each second, starting with the first he says aloud the number of seconds passed from the start of the dance (naturally he says the number in the $$$a$$$-based numerical system), with no leading zeros. for example, if $$$a = 3$$$, the first 5 numbers which Joker says will be:
- One second passed: $$$1$$$
- Two seconds passed: $$$2$$$
- Three seconds passed: $$$10$$$
- Four seconds passed: $$$11$$$
- Five seconds passed: $$$12$$$
Joker chose an array $$$b_i$$$, consisting of $$$a$$$ non-negative integers. He decided to stop his dance if after saying a number during entire his dancing he said digit $$$i$$$ exactly $$$b_i$$$ times for each $$$0 \le i \lt a$$$. Please, help him determine how many seconds his dance will last or if he will be dancing forever.
The first line has number $$$a$$$ — the base of the numerical system ($$$2 \le a \le 100\,000$$$). The second line contains $$$a$$$ integer numbers $$$b_i$$$ ($$$0 \le b_i \le 10^9$$$).
If Joker will dance forever, output $$$-1$$$. Otherwise, output the duration of dance in seconds.
10 1 2 1 1 1 1 1 1 1 1
10
2 3 5
4
5 0 0 0 0 0
-1
3 1 3 1
-1
Maleficent got upset when she could not cancel the spell cast upon Aurora because it's infinite and unbreakable. Luckily for us it's not such a big problem because in our version of the story all spells are mathematically described and can be cancelled much easier.
The spell is determined by two positive integer numbers $$$a$$$ and $$$b$$$. The process of cancelling the spell goes as follows:
- Multiply numbers from $$$a$$$ to $$$b$$$ inclusive
- Count the sum of digits of the result
- If the sum of digits isn't less then $$$10$$$, go to step $$$2$$$
To finish the cancellation rite, you need to say the resulting number. Please, help Maleficent to find it.
The first line contains number $$$a$$$, the second — number $$$b$$$ ($$$1 \le a \le b \lt 10^{100\,000}$$$). Both numbers have no leading zeros.
Output the resulting number.
1 5
3
6 8
3
After the victory over Pennywise "The Losers Club" almost succeeded in escaping from the abandoned house, the only thing that is left is to decode the lock on the door.
There are $$$n$$$ integer positive numbers on the lock $$$a_1, a_2, \ldots, a_n$$$. To open it we need to find the size of the biggest subset of these numbers such that the gcd of the elements from the subset is greater than one. The gcd of the subset is the biggest positive integer number such that it divides every element from the subset.
Please, help!
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of elements.
The second line contains $$$n$$$ positive integers $$$a_i$$$ ($$$2 \leq a_i \leq 10^{18}$$$).
Output one integer — the size of the biggest subset such that the gcd is greater than 1.
4 6 15 10 42
3
3 2 2 2
3
1 35
1
In the first test case one possible answer is $$$\{6, 15, 42\}$$$, the gcd equals $$$3$$$.
Aurora has $$$n$$$ blocks. Each block has 6 sides, each side has a digit from $$$0$$$ to $$$9$$$ on it. The same digit on one block can appear multiple times.
Fairies taught Aurora some arithmetic and gave her a task — to build numbers with blocks. Aurora can choose any subset of blocks, rotate them any side up and arrange them in any order to get the target number. Naturally, Aurora builds a number with no leading zeros.
Now, Aurora needs to learn how to count. Fairies intend to ask her to build positive integers in the ascending order. Blocks used for one number can be reused for another number. Please help the fairies to determine the minimum number which Aurora will never be able to build using a given set of blocks.
The first line contains one integer $$$n$$$ — the number of blocks ($$$1 \le n \le 100\,000$$$).
Each of the next $$$n$$$ lines has 6 digits — $$$a_{i,1}, a_{i,2}, \ldots, a_{i,6}$$$ ($$$0 \le a_{i,j} \le 9$$$).
Output the minimal number which Aurora won't be able to build.
2 012345 098765
11
3 123456 789012 345678
90
5 111111 222222 333333 444444 555555
6
You have a tree where $$$m$$$ simple paths are chosen: $$$(u_1, v_1)$$$, $$$(u_2, v_2)$$$, $$$\ldots$$$, $$$(u_m, v_m)$$$ — each path is determined by two vertices $$$u_i$$$ and $$$v_i$$$, the start and the end. All paths have non-zero length, meaning $$$u_i \neq v_i$$$.
Some jokester wants to assign weights to edges each being either $$$0$$$ or $$$1$$$. Let's consider $$$s_i$$$ a sum of all weights of the edges along the $$$i$$$-th path modulo $$$2$$$ (in other words, xor of all weights along this path). The jokester calls an arrangement of weights on the edges crazy if the following inequality is correct: $$$s_{i} \le s_{i+1}$$$ for all $$$1 \le i \lt m$$$.
Your task is to calculate the number of crazy arrangements of weighs. Because the arrangements are crazy, you have to find the answer by modulo $$$998\,244\,353$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices in the tree and the number of chosen paths ($$$2 \le n, m \le 250\,000$$$).
The second line contains $$$n - 1$$$ integers $$$p_i$$$ denoting that there is an edge in the tree connecting the vertices $$$p_i$$$ and $$$i + 1$$$ ($$$1 \le p_i \lt i + 1$$$).
The next $$$m$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$ each — the start and the end of the $$$i$$$-th path ($$$1 \leq u_i \lt v_i \leq n$$$).
Output one number — the number of crazy arrangements of weights on the edges by modulo $$$998\,244\,353$$$.
3 31 21 22 31 3
2
4 41 1 11 22 33 41 4
3
4 21 2 31 23 4
6
Sam is not the only one who builds roads. Today he met a man who does the same. They instantly hit it off and decided to play a game.
Right now they are building a rectangular part of the road $$$n$$$ by $$$m$$$ meters. Let's imagine that the road is placed on a grid and consists of $$$n \times m$$$ cells. Before the start of the game no cell is build. Players take turns. The first player can choose any rectangle on the grid with total area less or equal to $$$s$$$, but no cell of that rectangle should be build. Then the player builds all the cells of the chosen rectangle. The second player does the same. The winner takes the last turn. Sam goes first. Please, help him understand if he will be the winner considering that both players intend to win and play optimally.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$s$$$ ($$$1 \le n, m \le 1\,000$$$, $$$1 \le s \le n \cdot m$$$) — the sizes of the road and maximum area of the chosen rectangle.
If Sam can win output "YES". Otherwise output "NO".
1 4 2
YES
Aurora and Knotgrass decided to play tennis and asked Thistlelwit to be the judge. At the start the score was $$$0 : 0$$$. Then, a few times the score increased by $$$1$$$. The game ended with the score $$$a : b$$$.
Thistlelwit was bored so she counted the sum of the gcds of the players' scores after each score change. the gcd — is the greatest divisor of two numbers. For example, the game could go as follows:
- $$$0 : 0$$$
- $$$1 : 0$$$, $$$\textrm{gcd}(1, 0) = 1$$$
- $$$2 : 0$$$, $$$\textrm{gcd}(2, 0) = 2$$$
- $$$2 : 1$$$, $$$\textrm{gcd}(2, 1) = 1$$$
- $$$2 : 2$$$, $$$\textrm{gcd}(2, 2) = 2$$$
- $$$2 : 3$$$, $$$\textrm{gcd}(2, 3) = 1$$$
In that case, Thistlelwit would get $$$1 + 2 + 1 + 2 + 1 = 7$$$.
After the end of the game Thistlelwit got curious about what minimal number she could potentially get. Please, help her calculate that number.
The first line contains two integers $$$a$$$ and $$$b$$$ — the final scores of Aurora and Knotgrass ($$$0 \le a, b \le 10^9$$$).
Output one number — the minimal score which Thistlelwit could get.
2 1
3
4 6
11
0 0
0
10 10
31
Today Phillip and Aurora have a wedding and all the fairies of the Moors are invited. Aurora got bored a little bit and decided to watch the fairies talk.
At the start $$$n$$$ fairies were present at the wedding, Aurora numbered them from $$$1$$$ to $$$n$$$. Fairy $$$i$$$ is characterized by her talkativeness — a positive integer $$$a_i$$$.
On her watch, Aurora saw $$$q$$$ interesting moments. At the $$$j$$$-th moment one of 3 possible events took place:
- Fairy with talkativeness $$$v_j$$$ comes to the wedding. Aurora assigns her the first number which was not used before. For example, the first coming fairy gets the number $$$n + 1$$$, the next — $$$n + 2$$$ and so on.
- Fairy $$$p_j$$$ leaves the wedding.
- A dance starts, which is characterized by its expressiveness $$$e_j$$$ — a non-negative number. After the dance, the talkativenesses of all fairies change. If before the dance the fairy had the talkativeness $$$b$$$, then after the dance her talkativeness becomes $$$b \oplus e_j$$$, in other words it becomes xor of $$$b$$$ and $$$e_j$$$.
Aurora wonders how intensively the fairies talk. For that purpose she intends to count the total sum of all talkativenesses of each fairy present at the wedding after each event. Please, help Aurora with this difficult task.
The first line contains two integers - $$$n$$$ and $$$q$$$ — the number of fairies present at the wedding at the start and the number of interesting moments on Aurora's watch ($$$1 \le n, q \le 100\,000$$$).
The second line contains $$$n$$$ integers $$$a_i$$$ — talkativenesses of the fairies who are present at he start ($$$1 \le a_i \le 10^9$$$).
The next $$$q$$$ lines describe interesting moments. Each of them start with an integer $$$t_j$$$ — the type of event ($$$t_j \in \{1, 2, 3\}$$$).
- If $$$t_j = 1$$$, than there is an integer $$$v_j$$$ — the talkativeness of the newcomer ($$$1 \le v_j \le 10^9$$$). The newcomer gets the first unused number.
- If $$$t_j = 2$$$, than there follows integer $$$p_j$$$, signaling that fairy $$$p_j$$$ leaves the wedding. It is guaranteed that at that moment fairy $$$p_j$$$ was present at the wedding.
- If $$$t_j = 3$$$, than there is an integer $$$e_j$$$ — expressiveness of the dance ($$$1 \le e_j \le 10^9$$$).
After each event output the total sum of all talkativenesses of the fairies present at the wedding.
6 5 2 3 9 5 6 6 1 3 3 5 2 2 3 2 2 7
34 37 31 27 23
"The Loosers club" led by Bill tries to escape from the abandoned house where Pennywise attacked them.
The house could be describes as a table $$$n \times m$$$, each cell is either an empty space or a wall. At first, the children are in an empty cell. The exit is somewhere in a different empty cell. The children can move to the next empty cell which shares a side with their cell.
To frighten the children and prevent the escape Pennywise changes the air temperature. Each time when the children move between two squares from the same row he decreases the temperature by 1 degree and when they move between two squares from the same column he increases the temperature by 1 degree. Air temperature can equal any number including negative numbers.
The children would like that when they leave the house the temperature is as closer as possible to the initial temperature. Please, help them determine the minimal possible difference between the initial temperature and the final temperature. Please, note that air temperature within the house is not important. If needed the children can visit some cells more than once, including the starting cell and the exit cell.
The first line contains two integers $$$n$$$ and $$$m$$$ — the size of the table ($$$1 \le n, m \le 1000$$$).
The following $$$n$$$ lines contain $$$m$$$ characters — the description of the table. The description consists of symbols ".", "#", "s" and "f".
If $$$j$$$-th symbol in the $$$i$$$-th line equals "#", then there is a wall in the cell $$$(i, j)$$$, otherwise the cell is empty.
Symbol "s" notifies the starting cell, symbol "f" notifies the exit cell.
It is guaranteed that there is exactly one symbol "s" and exactly one symbol "f".
If the children will never leave the house output -1. Otherwise, output a non-negative integer — minimal possible difference between the initial and the final temperatures.
4 3 ..f ..# s## ...
0
In the first test case friends can first move up 2 times and then move right 2 times. Then the temperature will go up by 2 and then — down by 2. Overall, the difference will be $$$0$$$ degrees.
In order to win over the cruel clown in the final battle Mike called all his friends. The only thing left is to decide on tactics.
In total there will participate $$$n$$$ friends. For efficiency of the battle let us enumerate them from $$$1$$$ to $$$n$$$. First they formed a line, in which $$$i$$$-th place was taken by the friend number $$$a_i$$$. After long considerations Mike concluded that most effective disposition of the friends will be achieved if $$$i$$$-th place is taken by friend $$$b_i$$$.
To change the order of the friends in the line Mike can do several reorganizations. Each reorganization is performed as follows: Mike chooses some non-empty subset of friends and after that these friends go out from the line and go to its beginning in the reversed order. The order of the friends which were left in the line does not change.
For example, if friends were standing in the order $$$3, 4, 7, 6, 2, 5, 1$$$, and Mike have chosen friends with numbers $$$4, 7, 5$$$, after the reorganization friends will be standing in order $$$5, 7, 4, 3, 6, 2, 1$$$.
The fight with Pennywise starts quite soon so Mike wants to accomplish reordering in not more than $$$15$$$ reorganizations. Help him!
Please pay attention that it is not required to minimize number of reorganizations. It is guaranteed that it is possible to achieve the desired order in not more than $$$15$$$ reorganizations.
The first line contains one integer $$$n$$$ — the number of friends in the line ($$$1 \le n \le 10\,000$$$).
Second line contains $$$n$$$ different integer numbers $$$a_i$$$ from $$$1$$$ to $$$n$$$ — the initial order of the friends in the line ($$$1 \le a_i \le n$$$). Third line contains $$$n$$$ different integer numbers $$$b_i$$$ from $$$1$$$ to $$$n$$$ — the desired order of the friends in the line ($$$1 \le b_i \le n$$$).
To the first line output an integer $$$k$$$ ($$$0 \le k \le 15$$$) — the number of reorganizations in the found solution. In each of the following $$$k$$$ lines output description of the reorganizations, which should be done. For each reorganization first output number $$$c_i$$$ — the number of friends, which should go out of the line ($$$1 \le c_i \le n$$$), then $$$c_i$$$ different integer numbers from $$$1$$$ to $$$n$$$ — the numbers of the friends, who should go out of the line. The numbers of the friends can be written in any order.
5 5 4 3 2 1 3 4 5 1 2
4 5 1 2 3 4 5 1 5 1 4 1 3
7 3 4 7 6 2 5 1 2 6 3 4 5 7 1
3 3 6 5 7 3 3 4 5 3 2 6 3
In the first test, the order of the friends is changing in the following way:
$$$5, 4, 3, 2, 1 \rightarrow 1, 2, 3, 4, 5 \rightarrow 5, 1, 2, 3, 4 \rightarrow 4, 5, 1, 2, 3 \rightarrow 3, 4, 5, 1, 2$$$
In the second test, the order of the friends is chaning in the following way:
$$$3, 4, 7, 6, 2, 5, 1 \rightarrow 5, 6, 7, 3, 4, 2, 1 \rightarrow 4, 3, 5, 6, 7, 2, 1 \rightarrow 2, 6, 3, 4, 5, 7, 1$$$
Playing with unknown spells, Maleficent got a scroll with messages from the future. There was an interesting spell in the scroll.
<note>
<to></to>
<from></from>
<heading></heading>
<body></body>
</note>
Maleficent noticed several regularities. In particular: the spell is a balanced parenthesis sequence, in which an opening parenthesis is represented by "<S>", and a closing parenthesis is represented by "</S>", where string S is a non-empty string of lowercase Latin characters.
Maleficent found her old not working spell. She decided to check if it is possible to reorder some characters in it so that it conforms to the same rules as the spell from the scroll from the future. Please, help Maleficent to reorder the characters in her spell in a desired way, or say that it is impossible.
Single line contains string $$$s$$$, consisting of lowercase Latin characters and characters "<", ">" and "/" — Maleficent's spell ($$$1 \le |s| \le 100\,000$$$).
If it is impossible to reorder characters in a desired way, output "Impossible".
Otherwise, output the string, which can be obtained from the source spell by permutation of its characters and conforms to desired rules.
<test></test>
<test></test>
test<tist>/<>
Impossible
te<ste>st/<t>
<tset></tset>
<>test<>//<>test<>
<te><st></st></te>