In the beginning God created the heaven and the earth, the next five days God created the light, the water, the sky, the land, the trees and the living creatures, and on the sixth day he formed a man from the dust of the ground, called Adam. Afterwards, God took one of the man’s ribs and made a woman from the rib, called Eve. Adam and Eve lived in peace and harmony in the land, until God told them they should not take any apple from the only apple tree in Earth (at that moment, in year 0).
How they disobeyed God is a story from another day, now we are interested in how apple trees population increased over all those years. Apple trees are very interesting because their cycle of life is the following: first an apple fall into the ground and immediately a new apple tree blooms, from this moment we consider this as an apple tree, exactly ten years later the tree is full-grown and it starts to generate apples, from here every ten years the tree generates f(x) apples, where 
and x is the age of the tree, note that x will be always be a multiple of 10. Every apple generated from a tree will fall into the ground and generate a new tree, finally every apple tree dies exactly at the age of 45.
Now we want to know how many apple trees will be living on Earth after n years of the creation. At year 0 the apple tree created by God was not full-grown (this happened 10 years later).
The input consists of only one integer n (0 ≤ n ≤ 1015) - the number of years after the creation of the Earth including Adam, Eve and the first apple tree.
Print a single integer - the number of apple trees on Earth at the end of the n - th year after the creation of Earth, as this number can be very big print it modulo 109 + 7
9
1
10
17
44
77328
45
77327
In the first case, at 9th year there was on Earth only the apple tree that God first created.
In second case we have that in the 10th year the first apple tree was full-grown and 16 apples that belonged to that tree made new 16 trees, therefore there were 17 trees.
In fourth case, we have that at year 45 the first apple tree died, so it doesn't count anymore.
Felipe has a binary string A of length n (1 ≤ n ≤ 5000) which he wants to transform into string B (of length n as well) using a series of operations. He can use the following operations:
- Operation 1: He can move the last element of A to the front. For example, 01001 would become 10100.
- Operation 2: He can take any two consecutive elements and flip them. A flip turns a 1 into a 0 and a 0 into a 1. For example, if he applies this operation to the first two elements of 10100, it would become 01100.
Felipe actually doesn't like operation 2, so he wants to use it as few times as possible. Given A and B find the minimum number of operations type 2 needed to transform A into B, or say if it's impossible.
Input consist of two lines with binary strings A and B, respectively.
It is guaranteed that both strings have the same length.
Print one single line with the minimum number of operations type 2 needed to transform A into B. or - 1 if it's impossible to do so.
01001
01010
0
11111
00000
-1
001010
100001
1
The United Nations Against Leaks (UNAL) is trying to prove a method to encrypt e-mails to make them more secure to the world. However, this encryption method is not an easy process. First you have the original text to encode, then every character of the text is changed to any other character with a certain cost because the UNAL has to pay some money in order to change characters into other characters (this process can be repeated zero or various times). After this process is finished, we will have a new brand text which will be the message that will be send through the internet.
We already have the original text, the encrypted text, and which characters can be changed along with the corresponding cost. As the UNAL is paying for the encryption, they are hiring you to calculate the minimum cost of the e-mail encryption.
The first line of the input consists of a string s of size |s|, (1 ≤ |s| ≤ 105) - the original message.
The second line consists of a string t of size |t|, (|t| = |s|) - the encrypted message.
The third line consists of a number m (1 ≤ m ≤ 5 * 104), the number of possible changes between characters.
Finally m lines follow, each containing a, b, c, where a and b (a ≠ b) are ASCII characters and c is an integer (1 ≤ c ≤ 103), the cost of changing a into b.
It is guaranteed that s and t have the same length, don't have any whitespaces, and they are made using only printable characters ASCII (ASCII codes from 33 to 126).
Print one line with the minimum cost of encrypting s to t. If there is no way to encrypt s to t print - 1.
hello!
world!
8
a b 1
a d 3
e o 5
h w 10
l r 12
l e 5
o a 2
o d 8
32
Aa
ab
2
a b 10
a b 12
-1
Ignacio is a famous mathematician, some time ago he was married with Dolly, a famous scientific, at that time they bought a huge piece of land that they would use to construct a national university, they chose the land with the following property: if someone walks straight from any place inside the land to any other place inside the land then all that path would be inside the land, that's because they wanted that people could go from any point of the university to another as fast as possible.
Sadly, today Ignacio and Dolly are getting divorced, so they need to divide the land in two parts, to be fair with this division Dolly will give to Ignacio a list consisting of many different pairs of corners of the land, because governmental laws only permit to divide a land using corners of that land. Then, after dolly makes the list Ignacio will choose one pair of corners from that list and then they will divide the land with a straight wall from one of the corners to the other, the area of this wall is zero. Finally, Dolly will take the part with the biggest area.
For example, the image below corresponds to a land with coordinates (0, 0), (1,-1), (3, -1), (4, 0), (4, 2), (3, 3), (1, 3) and (0, 2) in that order, then Dolly made a list with 3 options, for the first one she chose corners with indexes 2 and 5, for the second she chose corners 7 and 3 and for the last she chose corners 4 and 7. In each case the shaded area corresponds to the area that would correspond to Ignacio if he chooses that option from the list.
You are hired from Ignacio to help him see which is the maximum area possible of the land he can have.
The first line of input contains 2 numbers n(3 ≤ n ≤ 105) and m(2 ≤ m ≤ 105) - the numbers of corners of the land and the number of pairs in the list of Dolly respectively
Next n lines follow, the i-th of these lines contains xi and yi ( - 108 ≤ xi, yi ≤ 108) - the i-th coordinate of a corner from the land.
Finally, m lines follow, the i-th of these lines contains pi and qi (1 ≤ pi, qi ≤ n, pi ≠ qi) - the i-th pair of the corners in the list from dolly. It is guaranteed that all pairs are different and that there are no 3 co-linear corners in the land.
Print a single number - the maximum area of the land that Ignacio could keep for himself.
You answer is considered correct, if its absolute or relative error does not exceed 10 - 4
4 2
0 0
0 100
100 100
100 0
1 3
4 2
5000.000000
8 3
0 0
1 -1
3 -1
4 0
4 2
3 3
1 3
0 2
2 5
3 7
4 7
7.000000
Yeison drew an equilateral triangle of side length n cm. Then for each side of the triangle he drew n - 1 lines parallel to it, with 1 cm of separation between them. Now the big triangle contains n2 equilateral small triangles of side length 1.
Let S be the set of all points that are vertices of any of the small triangles, now he is interested in knowing how many different pairs of points {a, b} where 
contain some other point 
and c ≠ b in the line segment ab, two pairs {a1, b1} and {a2, b2} are considered equal if a1 = a2 and b1 = b2 or if a1 = b2 and b1 = a2, two pairs are different if they are not equal.
For n = 3 the triangle drew by him would be the following:
Help Yeison to solve this problem.
The input consist of a single integer n (1 ≤ n ≤ 50) - the length of the triangle drew by Yeison.
Print one single integer - the answer of the problem.
2
3
3
12
The UN finals are here!, the coaches/ex-coaches team is creating a new exciting contest to select which teams will compete in the Colombian finals. Ivan said: the rules are clear, the only limitation to enroll teams in the Colombian finals is to pick a maximum of k teams per career. A team can be labeled with career X if there is no career Y such that more team members are enrolled in career Y than in career X. Finally, each team consists of three students (as usual).
Someone in the UN campus (UN finals are pretty popular) said, hey you guys should pick the teams careers in such a way that it maximizes the number of enrolled teams. Diego said: ah that is too easy. You will prove Diego right (or wrong). Given the description of the teams, output the maximum number of teams that can be enrolled in the Colombian finals.
The first line is n (1 ≤ n ≤ 100) - the number of teams that registered to participate in the UN finals.
Next n lines contains each the information from each team, that is, there will be three strings per team (one per team member) separated by a single space. Each string consists of distinct upper case letters which represent the careers that a team member is studying (UN students love to study multiple careers).
The last line contains an integer k (1 ≤ k ≤ n) - the maximum allowed number of teams per career.
Print a single integer - the maximum number of teams that can be enrolled.
5
A ABC B
C C C
B B B
A A A
C AC CB
2
5
In the first example first and fourth team can represent career A, second and fifth team can represent career C and third can represent team B.
Lucko is a greedy boy that is looking for ways to gain some money, one easy way he has found is to invest in bets on different lotteries, but he knows that the probability of winning a lottery is really low, for this reason he decides to play on a new lottery called UN-lotto.
To play UN-lotto one chooses a string of length m, then the lottery generates a string of length n (n ≥ m) randomly, both strings are formed only by lower-case letters from the english alphabet. You win if the string you have chosen is a subsequence of the generated text by UN-lotto.
Formally, for a string s = s1s2...sn we say that sa1sa2...sam is a subsequence of s of length m if 1 ≤ a1 < a2 < ... < am ≤ n. For example, suppose that n = 4 and m = 3 and Lucko chooses the string abc, some of the winning generated strings for him would be abcb, abbc and abzc, and some of the losing generated strings would be acba, azbz and zzzz
Good news for Lucko, information about this lottery has been leaked:
- The text is generated taking each letter randomly from a probability distribution.
- The selection of the letter for each position in the text is independent.
- The probability distribution of the letters was also leaked.
Lucko has already chosen his string to play UN-lotto, help him using the leaked information to tell him which is his probability P / Q of winning. As Lucko only likes low integer numbers calculate the probability modulo 109 + 7, i.e., calculate 
The first line of input contains 2 numbers n and m (1 ≤ m ≤ n ≤ 5000) — the length of the string generated by UN-lotto and the length of the string chosen by Lucko respectively.
The second line of input contains s — the string chosen by Lucko.
Next 26 lines contains each a pair of integers separated by spaces, i.e. the i-th line contains pi, qi, where 
corresponds to the probability of taking the i-th letter, being a the first letter, b the second letter and so on. For every i = 1, ..., 26, 0 ≤ pi ≤ 1000, 1 ≤ qi ≤ 1000 and pi / qi is an irreducible fraction.
It is guaranteed that 
.
Output one integer — the probability modulo 109 + 7 of Lucko winning UN-lotto with the string s.
5 1
a
1 1
0 1
... 24 more lines ...
1
5 3
aaa
1 2
1 2
0 1
... 23 more lines ...
500000004
The Universidad Nacional de Colombia (UN) was created on September 22 of 1867, a Sunday. In 2017 the UN had its sesquicentenary, i.e. it was its 150th birthday. The sesquicentenary of the UN was on a Friday. As it is really important to know all the details corresponding to the date of this huge celebration for every year, we want to know which day of the week corresponds to a specific birthday of the Universidad Nacional de Colombia.
Remember that a year usually has 365 days, except for some years, called leaps-years which have 366 days. To know which year is a leap-year we have the following rule: Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400. For example, the years 1700, 1800, and 1900 were not leap years, but the years 1600 and 2000 were.
The input consists of a number n (0 ≤ n ≤ 10000)
Output just one word corresponding to the day of the week at the n - th birthday of the UN.
Print the day on the following format (without quotation marks): 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday' or 'Sunday'.
0
Sunday
150
Friday
There is a new intense giant wheel in UNAL town, in UNAL town the wheels move in counterclockwise direction, also as this wheel has n cabins, everyone and everything can play. In particular, numbers come to this attraction. However, a complete number doesn't fit in one cabin, in fact, each cabin have space only for one bit. For this reason a number splits into its binary from and ride the wheel each bit per cabin. As numbers do not want to mess it up, the bits enter into the attraction in the same order the number is formed. Nonetheless, the wheel moves k times (entering and exiting from the attraction don't count as moves), then when the bits have to get out of the wheel they probably don't do it in the same order they entered, therefore making a different number.
For example, when the number 13 enter in a intense 8-bit it will look like the left side of the image below, after 5 moves the wheel will look like the right side of the image, in this case the number exiting the wheel will be 161.
You as the chief of the numbers in the UNAL town want to know how the wheel can affect the numbers that ride this attraction.
First line of input contains 2 numbers n (1 ≤ n ≤ 50) and m (1 ≤ m ≤ 1000) - the quantity of cabins in the wheel and the quantity of numbers that ride in the wheel, respectively.
Next m lines of input contains each 2 integers num (0 ≤ num < 2n) and k (1 ≤ k ≤ 1018) - the number that ride the wheel and the quantity of times the wheel move, respectively.
For each number that ride the wheel print the resulting number after leaving the wheel. Output this number in its decimal form.
8 3
1 1
13 5
17 12
2
161
17
Note that all numbers that ride into the wheel have exactly n bits, for example the number 13 in a 8-cabin wheel is not 1101 but 00001101 (see example).
Metr Pitrichev attended the 2018 ACM-ICPC World Finals in Beijing, China. Now that he finished streaming the contest he wants to travel from Beijing to Shanghai by train (he likes trains).
There are n (2 ≤ n ≤ 500) train stations in China and there are m (n - 1 ≤ m ≤ 500) train routes. Each train route consist of:
- u (1 ≤ u ≤ n): Station where the train starts.
- v (1 ≤ v ≤ n, v ≠ u): Station where train goes.
- t (1 ≤ t ≤ 1000): Number of minutes it takes the train to go from station u to station v. So, if the train departs from u at minute x, it will arrive to v at minute x + t.
- c (1 ≤ c ≤ 1000): Cost of taking the train (In RMB, the Chinese currency).
- f (1 ≤ f ≤ 10): Frecuency of the train, in minutes.
- s (0 ≤ s < f): Minute in which the first train leaves, so a trains leaves at each of these minutes: s, s + f, s + 2f, ...
In order for Metr to take a train that leaves at time x that goes from station a to station b, he must have been in station a at time x - 1.
Beijing railway station is station number 1 and Shanghai railway station is station number n. Metr arrived at Beijing railway station at time 0. Being very smart, Metr will take best route and arrive to Shanghai as early as possible and if there are multiple ways to arrive as early as possible he will spend as little money as possible. There is always at least one way to go from station 1 to station n.
The first line of input contains two integers n and m.
Each of the following m lines describes a train route with 6 space separated integers: u, v, t, c, f and s.
Print one line with two integers separated by a single space - the time Metr reaches his destination and the total cost of the trip (In RMB), respectively.
4 5
1 2 1 3 5 0
2 4 5 4 5 0
1 3 1 5 5 0
1 3 2 4 10 1
3 4 5 8 5 0
10 12
In the example:
- If Meter takes the first route and then the second route, he will arrive in 15 minutes and spend 7 RMB.
- If Meter takes the third route and then the fifth route, he will arrive in 15 minutes and spend 13 RMB.
- If Meter takes the fourth route and then the fifth route, he will arrive in 10 mitues and spend 12 RMB.
The UNAL programming coaches have lost a bet, they bet the 6 UNAL teams would occupy the first six positions in the regional finals. Now, they have to shave their heads!. Some of them have more hair than others, and consequently, it takes more time to shave a head completely. However, all of the coaches really love their hair, therefore there is a probability that some (posibly all) of them daunt at the very last moment and do not permit the hairdresser to shave their heads.
Norbert, the hairdresser who loves probability, would like to order the coaches' schedule such that the average time in the hair salon is minimized for all the coaches. First all the coaches are there at the same time, then they start going one by one to Norbert, if by the moment a coach has to go to the hairdresser, he or she daunts then he or she simply leaves the hair salon and it is the turn of the next coach, after the head of a coach is shaved then that coach leaves the hair salon. The time between turns is negligible.
For example, suppose that shaving Diego's head takes 2 minutes and shaving Ivan's takes 3 minutes, but Diego has probability of 0.5 of not daunting meanwhile Ivan for sure will shave his head. If Ivan goes first, he will stay 3 minutes in the hair salon and Diego will stay there 3 minutes if daunting or 5 minutes if not (3 of them waiting for Ivan to finish), in this case the average expected time of the coaches in the hair salon would be 3.5, note this is not the optimal arrangement.
Now, Norbert knows the time it takes to shave each head and the probability of a coach to accept to have the head shaved in the barbershop, help him to know the minimum average expected time in the hair salon of the coaches.
The first line of input is an integer n (1 ≤ n ≤ 5 * 105) - the number of coaches.
The next n lines contain each an integer x (0 ≤ x ≤ 100) and a decimal number y (0 ≤ y ≤ 1) separated by a single space - the time in minutes it takes to shave the head of the i - th coach and his probability of not daunting, respectively.
Print the minimum expected average time. The relative error of your answer should not exceed 10 - 6.
2
2 0.5
3 1.0
2.500000000
2
0 0.4
20 0.6
6.000000000
The Che square of the Universidad Nacional de Colombia is represented by an N × N matrix and is going to be remodeled. To achieve this goal, the engineers have one 1 × 1 square-tile and a lot of L-tiles (Enough to fill the entire Che square). Unfortunately, one of the workers have placed the square tile at location in row R and column C ignoring the fact that this could affect the positions of other tiles. Given the importance of the Che square, we need your help in order to know how to place the rest of the tiles so that all N2 positions of the Che square are covered by exactly tile.
The rotations of a L-tile are showed at the following figure, you can place each L-tile in the rotation you want.
The first line contains N (1 ≤ N ≤ 2048, will be a power of 2), the size of the square matrix. The second line contains integers R and C (1 ≤ R, C ≤ N), the row and the column where the worker placed the square tile.
Print a matrix of size N × N ]. The C-th character of the R-th line must be a dot ('.'), representing the 1 × 1 square tile. Every L-tiles must be represented by three uppercase letters. If two L-tiles are adjacent to each other (share more than a point), they must be represented by different letters. Since there are many possible answers, you can print any.
8
3 4
BBCCBBCC
BAACBAAC
CAB.CCAB
CCBBACBB
BBCAABCC
BACCBBAC
CAABCAAB
CCBBCCBB
Juan have N red marbles, M blue marbles, and K bottles. He will put a certain number of marbles on each of the K bottles such that no bottle remains empty and every marble is inside a bottle.
Andres is a Santa Fe fan, so he will pick one bottle at random with an uniform distribution, then he will pick a marble inside of it at random with an uniform distribution, with the hope is a red marble. As Juan is a Millonarios fan, he wants to distribute the marbles in the bottles such that the probability of Andres picking a blue marble is maximized. Juan has a busy life, therefore he needs your help to determine the best arrangement for the marbles and the probability of Andres getting a blue marble.
The input consist of three integers separated by spaces, N M and K (1 ≤ N, M, K ≤ 109) - the number of red marbles, blue marbles and bottles respectively.
Print the probability of Bob getting a blue marble such that the marble arrangement is optimal. Your answer will be considered correct, if its absolute or relative error does not exceed 10 - 6.
50 50 2
0.747474747