Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps:
it means when adding two numbers we will get something like this:
Unfortunately as Gaby is too young she doesn't know what the third step means so she just omitted this step using her own standard algorithm (Gaby's addition algorithm). When adding two numbers without carrying when necessary she gets something like the following:
Gaby loves playing with numbers so she wants to practice the algorithm she has just learned (in the way she learned it) with a list of numbers adding every possible pair looking for the pair which generates the largest value and the smallest one.
She needs to check if she is doing it correctly so she asks for your help to find the largest and the smallest value generated from the list of numbers using Gaby's addition algorithm.
The input starts with an integer n (2 ≤ n ≤ 106) indicating the number of integers Gaby will be playing with. The next line contains n numbers ni (0 ≤ ni ≤ 1018) separated by a single space.
Output the smallest and the largest number you can get from adding two numbers from the list using Gaby's addition algorithm.
6
17 5 11 0 42 99
0 99
7
506823119072235413 991096248449924896 204242310783332529 778958050378192979 384042493592684633 942496553147499866 410043616343857825
52990443860776502 972190360051424498
In the first sample input this is how you get the minimum and the maximum value
Ivan is a new professor of the University of Nice Algebra Lovers (UNAL), he is going to give a data structures course, that's why he is preparing his slides and wants to draw a beautiful rooted tree. As he loves math, he has a very special array of numbers A and he wants to use each element of the array as the number of children for some level in the tree. For example, if A = [2, 1, 3] two of the possible trees he could draw are the following:
Ivan wants to draw a rooted tree that has the maximum number of nodes. As he is busy with LaTeX he wants you to write a program that computes such number.
The first line consists of an integer n (1 ≤ n ≤ 32), the next line contains n numbers separated by a single space, the elements of A (1 ≤ Ai ≤ 10).
Print one number, the maximum number of nodes Ivan can draw. It is guaranteed that the answer fits on a 63-bits integer.
3
2 1 3
16
The number of levels of the tree (except for the root) is the same as the number of elements in the array
Lately the communication between planets has been an important issue, which is why the Earth has made many efforts to be connected to every other planet in the universe.
The Universal Network Army of Lasers (UNAL) is trying to connect the Earth with other planets in the universe. In order to make this, the UNAL uses a laser machine which each time it is used, it sends a communication signal in the form of a ray of light in the direction of the planet.
This laser machine is so powerful, that a ray of light generated by it is capable to cross all the planets it touches until the end of the universe. Moreover, when it fires a ray of light in one direction it also fires a ray of light in the opposite direction.
Given the coordinates of all the planets in the universe, help the UNAL to design the way to communicate the Earth with all other planets in the universe using the machine the minimum number of times.
The first line of input contains one integer n (1 ≤ n ≤ 5000), the number of planets.
The next n lines contains the list of coordinates of the planets. In particular, the i - th line contains three integers xi, yi, zi ( - 109 ≤ xi, yi, zi ≤ 109), the coordinates of the i - th planet, respectively. The Earth is the first planet on the list. It is guaranteed that all the planets have different coordinates.
Output a single integer, the minimun number of times the machine should be used to communicate the Earth with all other planets in the universe
3
0 0 0
1 1 0
-1 -1 0
1
4
0 0 0
1 0 0
0 1 0
0 0 1
3
Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can't figure out how to do it. Your task is to find a way to use the machines to get exactly n coins.
The input consists of a single line containing n (1 ≤ n ≤ 109).
For each one output a string of A's and B's giving the order in which the machines are used.
7
AAA
10
ABB
One of the most useful tools nowadays are text editors, their use is so important that the Unique Natural Advanced Language (UNAL) organization has studied many of the benefits working with them.
They are interested specifically in the feature "find", that option looks when a pattern occurs in a text, furthermore, it counts the number of times the pattern occurs in a text. The tool is so well designed that while writing each character of the pattern it updates the number of times that the corresponding prefix of the total pattern appears on the text.
Now the UNAL is working with the editor, finding patterns in some texts, however, they realize that many of the patterns appear just very few times in the corresponding texts, as they really want to see more number of appearances of the patterns in the texts, they put a lower bound on the minimum number of times the pattern should be found in the text and use only prefixes of the original pattern. On the other hand, the UNAL is very picky about language, so they will just use the largest non-empty prefix of the original pattern that fit into the bound.
The first line contains the text A (1 ≤ |A| ≤ 105) The second line contains the original pattern B (1 ≤ |B| ≤ |A|) The third line contains an integer n (1 ≤ n ≤ |A|) - the minimum number of times a pattern should be found on the text.
A single line, with the prefix of the original pattern used by the UNAL, if there is no such prefix then print "IMPOSSIBLE" (without the quotes)
aaaaa
aaa
4
aa
programming
unal
1
IMPOSSIBLE
abracadabra
abra
1
abra
Hello World!
H W
5
IMPOSSIBLE
Bob is creating an algorithm that can generate words. It works as follows:
Given an integer seed s:
For example, if s = 3705
From B we can generate "mico" as follows: [13, 9, 3, 15] = [m, i, c, o]
From B we can also generate "kecci" as follows: [11, 5, 3, 3, 9] = [k, e, c, c, i]
Please note that when doing the words-number trailing zeroes are not allowed. For example, 02 does not correspond to b.
Alice thinks that Bob's model is very poor and that in fact, it can't generate words that belongs to any language. Bob is very confident about his model, that's why he wants to write a program that given s computes how many words can be generated. As Bob knows you are training to participate on the ACM - ICPC World Finals, he wants you to write a program that counts the possible words.
There will be multiple cases. Each line contains a positive integer s less than 106.
For each case output the number of valid words mod 109 + 7 on a single line.
3705
1001
505
1331
4224
552
86
8
13
23580
There are n (1 ≤ n ≤ 105) students numbered from 0 to n - 1, the favorite number of student i is fi (1 ≤ fi ≤ 109). Student i is friend of student j if and only if |i - j| ≤ k (1 ≤ k ≤ 20). The students will be divided in two math classes.
Class A is for palindromes lovers, so naturally, only students with a palindrome as a favorite number can take it. A number is palindrome if read from right to left is the same. So 1, 55, 121 and 1331 are palindromes and 10, 233 and 990 are not.
Class B is for superstitious people, so naturally, only students with a lucky number as a favorite number can take it. A number is lucky if it's formed by only digits 4 and 7. So 4, 7, 44, and 474477 are lucky numbers and 5, 40, 71 and 4474347 are not lucky numbers.
Your task is to find out if it's possible to split the students into classes A and B, so that every student is in exactly one class and every student has at least one friend on the same class.
The first line has two integers n and k. The second line contains n space separated integers f0, f1, ..., fn - 1 the favorite number of each student. All numbers are given with no leading zeroes.
Print "Yes" or "No", without quotes, whether or not is possible to split the students as stated above.
4 1
474 101 7 4
Yes
4 1
447 101 7 4
No
Note that one of the classes might be empty.
Jeronimo the bear loves numbers and he is planning to write n numbers in his notebook.
After writing the first m numbers, Jeronimo felt that he was spending a lot of time thinking new numbers, so he wrote the next n - m missing numbers as the sum modulo 3 × 107 of the numbers in the i - m and i - m + 1 positions for m < i ≤ n
While Jeronimo was writing, his sister Lupe arrived and asked him q questions. The i - th question consist of a number bi, Jeronimo has to say what would be the number in the position bi if all the numbers were sorted in ascending order. Jeronimo wants to answer each question as soon as possible but he spends a lot of time counting so he ask your help.
The first line of the input has three integers n (3 ≤ n ≤ 3 × 107), m (3 ≤ m ≤ min(100, n)) and q (1 ≤ q ≤ 10000).
The second line contains m numbers a1, a2, ..., am, (0 ≤ ai < 3 × 107), The first m numbers that Jeronimo wrote.
The third line contains q questions b1, b2, ..., bq (1 ≤ bi ≤ n)
Print q lines. The i - th line must be the answer of the i - th question made by Lupe.
6 3 6
1 2 3
1 2 3 4 5 6
1
2
3
3
5
6
10 4 3
1 2 9 10
1 5 10
1
10
30
Tamref love random numbers, but he hates recurrent relations, Tamref thinks that mainstream random generators like the linear congruent generator suck. That's why he decided to invent his own random generator.
As any reasonable competitive programmer, he loves trees. His generator starts with a tree with numbers on each node. To compute a new random number, he picks a rooted subtree and multiply the values of each node on the subtree. He also needs to compute the number of divisors of the generated number (because of cryptographical applications).
In order to modify the tree (and hence create different numbers on the future), Tamref decided to perform another query: pick a node, and multiply its value by a given number.
Given a initial tree T, where Tu corresponds to the value on the node u, the operations can be summarized as follows:
and count its divisors, where T(u) is the set of nodes that belong to the subtree rooted at u. Tamref is quite busy trying to prove that his method indeed gives integers uniformly distributed, in the meantime, he wants to test his method with a set of queries, and check which numbers are generated. He wants you to write a program that given the tree, and some queries, prints the generated numbers and count its divisors.
Tamref has told you that the largest prime factor of both Tu and x is at most the Tamref's favourite prime: 13. He also told you that the root of T is always node 0.
The figure shows the sample test case. The numbers inside the squares are the values on each node of the tree. The subtree rooted at node 1 is colored. The RAND query for the subtree rooted at node 1 would generate 14400, which has 63 divisors.
The first line is an integer n (1 ≤ n ≤ 105), the number of nodes in the tree T. Then there are n - 1 lines, each line contains two integers u and v (0 ≤ u, v < n) separated by a single space, it represents that u is a parent of v in T. The next line contains n integers, where the i - th integer corresponds to Ti (1 ≤ Ti ≤ 109). The next line contains a number Q (1 ≤ Q ≤ 105), the number of queries. The final Q lines contain a query per line, in the form "RAND u" or "SEED u x" (0 ≤ u < n, 1 ≤ x ≤ 109).
For each RAND query, print one line with the generated number and its number of divisors separated by a space. As this number can be very long, the generated number and its divisors must be printed modulo 109 + 7.
8
0 1
0 2
1 3
2 4
2 5
3 6
3 7
7 3 10 8 12 14 40 15
3
RAND 1
SEED 1 13
RAND 1
14400 63
187200 126