Nicoleta is a happy kid, he goes every day to school and is always complaining about waking up early and having to complete his homework assignments. His favorite professor, Afonsox, is very funny and created a new challenge for him.
Even though Nicoleta is just a kid, Afonsox introduced him to the world of graph theory. Nicoleta is amazed, he is very obsessed with this graph that Afonsox decided to call K-round graph. A K-round graph with N vertices is a graph where every vertex u, numbered from 0 to N - 1, has an edge to vertices (u + 1)%N, ..., (u + K)%N. Here a%b is the operator that gives the remainder of the integer division of a by b. Also, an edge between vertices u and (u + i)%N has value i.
Nicoleta likes this graph because if you draw it, it looks like a circle of kids, where each kid has K arms with different lengths with which they can reach the K next kids, like the picture below, which he drew in his notebook. Imagining this makes Nicoleta smile.
The challenge Afonsox has proposed to Nicoleta is for him to find the sum of all the values of the edges in the maximum spanning tree of a given K-round graph. A maximum spanning tree of a graph is composed of all of its vertices and a subset of edges such that there is one and only one path from one vertex to another and the sum of the values of the edges is maximal. Can you help Nicoleta finding the answer to Afonsox challenge?
The input consists of a single line containing two integers N and K (1 ≤ K < N ≤ 109), indicating the number of vertices in the graph and the number of outgoing edges from every vertex.
Output a single integer - the sum of the values of the edges in the maximum spanning tree of the K-round graph.
3 2
4
6 2
9
A k-cyclic shift of an integer x is a function that removes the last k digits of x and inserts them in its beginning. For example, the k-cyclic shifts of 123 are 312 for k = 1 and 231 for k = 2.
Teo, a kid from Canada, learned from his Canadian friends this definition of ugly numbers: a number is ugly if, and only if every one of its k-cyclic shifts returns a number greater than or equal to it.
Given an n-digit decimal number x, can you answer if it is ugly or not?
The first line of the input contains a single integer n (1 ≤ n ≤ 5 × 105), indicating the number of digits of the number.
The next line contains an n-digit decimal number, indicating the value of x.
Output "Yes" if x is an ugly number and "No" otherwise.
3
123
Yes
4
2214
No
After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integer a, a being the product of n integers v1, v2, ..., vn. The other cat likes all integers with exactly b divisors. You were asked to count the number of integers that satisfy both cats. If you count correctly, you may go to the heaven of AC problems, full of balloons, otherwise you're sent to hell NO.
As the answer can be quite large, print the remainder of this number modulo 109 + 7.
The first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103).
The following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a.
Output a single integer - the number of integers that satisfy both cats modulo 109 + 7.
2 3
19 5 2
3
3 2
366 169
1
Byung is playing a game on her infinite checkerboard. The goal of the game is to move from a starting position (rs, cs) to a target position (rt, ct) using exactly x moves, where x is determined by a roll of a N-sided dice.
A move consists in going from a square on the checkerboard to one of its four neighbors - up, down, left or right.
Her dice is unbiased, meaning that every number from 1 to N has the same probability of being rolled.
She's interested in knowing what's the number of different rolls that allow her to move to the target position in the last move. She can move to the same square more than once if she needs to. Can you help her?
The input is composed by a single line containing 5 integers N (1 ≤ N ≤ 109), rs, cs, rt and ct ( - 109 ≤ rs, cs, rt, ct ≤ 109) indicating respectively the number of sides of the dice, the coordinates of the starting position and the coordinates of the target position.
An integer number indicating the number of outcomes that she'll get a good roll.
5 1 1 2 3
2
500 -100 -100 100 100
51
Loppinha loves to go to the gym with his friends. He takes his training sessions very seriously, and he always follows his schedule very strictly. He just created a new plan where he has set exactly what he is going to do at every single one of the N minutes of the session.
Loppinha loves having a sopinha (small soup) before training. The soup contains K grams of protein. As you can imagine, he needs that protein to be able to endure his very tough exercises. He is burning protein at every minute he is working out, and the amount of protein he burns in a minute depends on how many minutes he has been working out without a minute of rest. If he has trained for p minutes without resting, in the (p + 1)-th minute of workout he is going to burn p + 1 grams of protein.
Of course, if he doesn't have enough protein at any moment he dies. For example, if he has 3 grams of protein at a moment and at that minute his workout requires 4, if he does the workout he dies. Given his schedule and the amount of protein K he has before starting the training session, Loppinha, who is willing to change some minutes of his workout, wants to know what is the minimum amount of minutes he has to change from working out to resting so he does not die.
The first line of the input contains two integers N (1 ≤ N ≤ 450) and K (1 ≤ K ≤ 107), indicating the number of minutes in Loppinha's training session and the amount of proteins in his soup. The next line contains a string with N characters, either 0 or 1, where 0 indicates a minute of rest and a 1 indicates a minute of workout.
Output a single integer - the minimum number of minutes Loppinha has to switch from workout to rest so that he can finish his exercises without dying.
4 2
1101
1
10 5
1101100111
3
3 1
111
2
In the first test case, if he changes the second minute to rest, he will consume exactly 2 grams of protein. Notice that if he changes the last minute to rest instead, he would need 3 grams of protein to complete his workout session without dying.
Laërdos is organizing a party and invited all his N mathematician friends. He decided to decorate his party with positive integers, ranging from 1 to 1018. He's now struggling to choose the integers that he's going to use because his friends are very picky about numbers.
He talked to all his friends beforehand, and they all told him their preferences. Each one of them described their preference by either:
He wants to know how many integers he can use that will please all his friends.
The first line of the input contains a single integer N (1 ≤ N ≤ 105) indicating the number of friends that were invited to the party.
Each of the following N lines describes the preferences of each friend. The i-th line contains the preferences of the i-th friend and has the following format:
t s l1 ... ls
t is 1 if the friend listed the integers that he or she likes and 2 otherwise. s (1 ≤ s ≤ 105) indicates the number of integers that were listed. It is followed by s integers l1... ls (1 ≤ lj ≤ 1018), indicating the integers that the friend listed.
The total number of integers listed by all friends is not greater than 2 × 105.
Output a single integer, the number of integers that all Laërdos' friends like.
3
1 3 1 2 3
2 1 1
1 3 1 2 4
1
5
1 3 1 2 3
1 3 1 2 4
1 3 1 2 5
1 3 1 2 7
2 1 8
2
2
1 2 10 11
2 2 10 11
0
Sancho was making a road trip with his family and got really bored, so he recorded the position and initial speed of every car on the highway. For Sancho, the highway is an infinite straight line, the starting time is 0, the cars are moving points, and no car will pass another car (Sancho is very idealistic).
The cars maintain their initial speed unless they are slowed down by other cars. Car A is slowed down by car B if B started in front of A, but after a while, A reached B. When this happens, both cars move together and A's speed becomes the same as B's.
Sancho knows that there will be only a finite amount of times that a car will be slowed down by another car, and wants to know when the last slowing down will take place. If no car will be slowed down, the answer is 0.
The first line of the input contains a single integer N (1 ≤ N ≤ 105), indicating the number of cars.
N lines follow. The i-th line contains two integers Si and Vi (0 ≤ S, V ≤ 109), indicating the starting position of the i-th car and its speed. No two cars start in the same position.
Output a single decimal number - the time of the last slow down. Your answer will be considered correct if the absolute or relative error is no greater than 10 - 4.
Namely: let's assume that your answer is a, and the official answer is b. The checker program will consider your answer correct, if
.
4
0 10
10 3
20 3
30 2
20.000000
Tata and Tynati are still too young to understand exactly what their father works with, but they love playing with his briefcase. The briefcase has a combination lock composed of N wheels, and each wheel has all the digits (0 up to 9) engraved in it. The wheels can be rotated to display any combination of the N digits. Tata and Tynati tried to open the briefcase but they soon realized that it would take too much time to find out the right combination. So, instead of trying to open the briefcase, they decided to play a game with the combination lock.
The rules of the game are the following:
Tata plays first because she invented the game. Tata and Tynati already played this game hundreds of times, so both play optimally. Given the initial configuration of the game, can you tell who is going to win?
The first line of the input contains a single integer N (1 ≤ N ≤ 100) indicating the number of wheels in the combination lock. The following line contains N integers indicating the digits of the initial configuration of the game from left to right.
Output either TATA or TYNATI indicating the winner of the game knowing that both play optimally.
3
223
TATA
4
1110
TATA
4
1111
TYNATI
GEMA is hosting Q rounds of 10-hour-long contests in honor of the great Danfto. Everybody wants to honor Danfto, but 10 hours is a really long time, so people are wondering whether to go or not.
A person's decision is affected by their best friend's decision. Each person has at most one best friend and there are no cycles (this is not a Disney movie and there are no reciprocated friendships), meaning that if Nicoleta's best friend is Sancho and Sancho's best friend is Teoo, Teoo's best friend is not Sancho nor Nicoleta. In this case, Nicoleta will participate only if Sancho does, Sancho will participate only if Teoo does, and Teoo doesn't have a best friend so he doesn't depend on anyone.
People can also depend on some other factors like the weather, their mood or their mothers' permission. So there's no guarantee that they will participate even if their best friend does.
Now the rounds have passed and you are very curious about who were the brave souls that went to each round. You asked Tomaso if Teoo participated in a round, but Tomaso was drunk, so instead of replying yes or no, he told you that Nicoleta participated. You can deduce that Teoo went to the contest too because Nicoleta would only participate if Sancho did, which in turn would only go if Teoo did.
You asked Tomaso Q questions, one for each round, of whether y participated, and he told you that x did. Is it possible to know for sure if y participated in the round given that x did?
The first line of the input contains two integers, N (2 ≤ N ≤ 1 × 105) and Q (1 ≤ Q ≤ 2 × 105), indicating the number of people invited to the Danfto honor rounds and the number of questions you asked Tomaso.
The next line contains N integers. The i-th integer ai (ai = - 1 or 0 ≤ ai ≤ N - 1) indicates that the i-th person will only participate in a round if the ai-th person does. If a person doesn't depend on anyone, ai is -1.
Q lines follow. The j-th line contains two integers xj and yj (0 ≤ xj, yj ≤ N - 1) indicating that you want to know if the yj-th person participated in the j-th round, and Tomaso told you that the xj-th person did.
For each query, output "Yes" if you can determine that the y-th person participated and output "No" otherwise.
3 2
1 2 -1
0 2
2 0
Yes
No
Friendo is a super hero that protects the city of Fancouver from bad games. He knows that a new game from the Velda franchise - one that tricks people into thinking it's good and makes them go crazy - will be released in the next few days and is going to be sold at N game stores.
In Fancouver, the game stores have a mafia and are connected in such a way that there is always one path and only one path from one to another, so that when you want to go to from one game store to another, you may have to visit stores you didn't want to visit and end up buying games you didn't want to buy.
With his power, Friendo can destroy any number of stores, as long as the distance between any two of them is at most K. What is the largest number of stores that Friendo can destroy?
The input starts with a single line containing two integers N and K (1 ≤ K < N ≤ 105). Each of the following N - 1 lines contains two integers u, v (1 ≤ u < v ≤ N) indicating that game store u is connected to game store v.
Output a single integer that indicates the largest number of game stores Friendo can destroy.
6 2
2 3
3 5
6 4
6 3
1 6
4
Little Teo is playing with colored magnets and made N colorful snakes numbered from 1 to N by sticking colored magnets one after another in a row. The number of magnets in each snake is a power of two because that makes them special.
Today, little Teo's playtime lasts Q minutes. Just looking at the snakes is boring and little Teo is hyperactive, so at each minute he may do one of four things:
When little Teo sticks two snakes, the new snake gets numbered with the smallest positive number he didn't use yet; and when he splits a snake, the left part of the snake gets the smallest unused positive number and the right part gets the second smallest (see notes for clarity).
As his nanny, it is your duty to answer all of little Teo's questions so that he doesn't throw a tantrum, decreasing your already slim paycheck.
The first line of the input contains two integers N and Q (1 ≤ N, Q ≤ 105), indicating the number of snakes little Teo initially has and the number of minutes of little Teo's playtime.
Each of the following N lines starts with an integer si (1 ≤ si ≤ 216) indicating the size of the i-th snake, followed by si integers. The j-th integer cij ( - 109 ≤ cij ≤ 109) represents the color of the j-th magnet of the i-th snake.
Each of the following Q lines describe what little Teo will do during his play time and has the following format:
It is guaranteed that the size of each snake is a power of two and that the sum of the sizes of the snakes doesn't exceed 105.
For each query of type 4, output in a separate line the size of the longest sequence of magnets with the same color in snake z.
2 12
4 1 2 1 2
4 2 1 2 1
4 1
4 2
2 2 1
4 3
1 2 6 3
4 3
1 4 8 3
4 3
3 3
4 4
3 5
4 6
1
1
2
4
4
4
2
If little Teo starts with 3 snakes, they will be numbered 1, 2 and 3.
If he sticks snake 1 to snake 2, the new snake will be numbered 4.
If he afterwards splits snake 4, the left part will be numbered 5 and the right one will be numbered 6.
Otvio is a calm guy with a guilty pleasure: kicking PCs. Now he is participating in a programming competition where the computers are arranged as a tree, that is, the N PCs are connected by N - 1 cables and there is only one cable path from one PC to another.
Otvio wants to kick as many PCs as possible. To do so, he will walk along a cable path, kicking all the PCs in the path. He will start at PC a, the one he will use in the contest. However, to prevent getting caught, he will not pass by PCs he already kicked nor kick any PC twice.
Laerco, knowing Otvio's guilty pleasure, wants to know the maximum number of PCs Otvio can kick satisfying the conditions above. Remember that Otvio will kick his own PC for sure.
The first line of the input consist of two integers integer N and a (1 ≤ N, a ≤ 105), the number of PCs in the contest and the number of Otvio's PC, in this order. Each of the next N - 1 lines contains two integers u and v (1 ≤ u, v ≤ N), indicating that there is a cable connecting PCs u and v.
Output a single integer - the maximum number of PCs Otvio can kick.
5 2
1 2
1 3
2 5
3 4
4