A: Ghots Riddle

The students taking the C programming course recently learnt how to find the n^th number in the fibonacci sequence, but found it to be too easy. So they asked the class ghot to come up with a more difficult function to find. The relation he came up with is defined as follows:

) if x has two or more distinct divisors other than 1 and itself

(x) =

x if x has 1 divisor or less apart from 1 and itself

Where div₁ and div₂ are the two largest distinct divisors of n, other than 1 and the number itself. In this question, you will be provided with a number n and your task is to find f(n). Note: this is not the Fibonacci sequence defined above. Please read the question.

Input

The first line of input contains a single integer N (1 N 10⁵), for which you must find f(N).

Output

The output should contain a single integer that is the answer as described by the function above.

input 10

output 7

explanation f(10) = f(5)+f(2), Since 5 and 2 do not have any proper divisors, f(5) = 5 and f(2) = 2 and hence f(10) = 5 + 2 which is equal to 7.

input 8

output

6

B: Tourism

One day you decide to visit the Grand Line for some sightseeing. The grand line consists of N different islands numbered from 1 to N. The waters between the Grand Line are incredibly dangerous and its easy to get lost, so you buy a log pose to help you navigate. Depending on the island you are currently standing on, the log pose points to zero or more other islands and you can travel to any of these islands. You can start your journey from any island initially. You want to know the maximum number of distinct islands that can be reached from a starting island of your choice (the island you start from should also be counted) Note that from your current island you can only travel to an island that the log pose points to. Keep in mind that you need to find the maximum number of islands that you can possibly reach from the starting island, not a path with the largest number of islands. See sample case for clarity.

Input

The first line of input contains two space-separated integers N and M (1 N 1000, 0 M 1000) denoting the number of islands and island transitions you can make respectively. In the M lines that follow, the i^th line containing two space-separated integers, U_i and V_i representing that from island U_i, one of the islands that the log pose points to is V_i.

Output

Print a single integer X denoting the maximum number of islands that you can reach if you start from some island.

input

5 5

1 2

1 5

5 4

5 3

3 2

output 5

explanation

if we draw the corresponding possible paths between islands, we can see that from the island 1 we can reach all other islands. From 2, we cant reach any other node. from 3 we can reach 3 and 2. from 4 we can reach only itself. from 5 we can only reach

5 and 4. Clearly we can see that if we start from node 1 our answer would be 5 which is maximum possible.

C: Klutz

N people are participating in the binary blitz competition this time, each numbered from 1 to N and all of them have a particular rating on codeforces. It is known that if two people compete, the one with the higher rating wins for sure. It is guaranteed that the ratings of all the N people are unique. The problem is that no one provided their actual codeforces handle so you dont know anyones rating. All the N people play exactly once against every other person. So obviously there will be a total of games in total played by the N people. The competition is over and you have kept a record of all the matches in the following format: You have rows, and each row containing two space separated integers. The first number of these is the winner and the second one is the loser. It turns out you have lost exactly one row from this list and you have to try and fill in the missing record so that it doesnt contradict any of the other rows. If it is not possible to determine the winner and loser, print them in any order.

Input

The first line contains a single integer N which is the number of people participating (3 N 200).

The following 1 lines contain two space-separated integers each U_i and V_i, where U_i is the winner of that round and V_i is the loser.As an extra challenge, try to solve this with the constraint

3 N 2000.

Output

Output a single line containing two space-separated integers that is the missing entry. If you cannot determine the winner and loser with the give information then print them in any order

input

4

4 2

4 1

• 1
• 1

2 3

output

4 3

explanation

notice that if we put 3 4 then it would contradict line 1 and line 5

D: Geass Code

You are the leader of the resistance against Britannia and you have N Knightmares that you can use during the revolution. The i^th Knightmare initially has a power P_i. You decide that the current power of your Knightmares isnt enough so you ask your lead scientist Rakshata to help you out. She comes up with M power multipliers placed one after the other in a row. each multiplier has a different power where i^th multiplier has a power Mult_i. She uses this in the following way: Start by placing the first index of the multiplier over the first element in P. Then for all 1 i M, P_i = P_i Mult_i. Then move the starting position of the multiplier to the second position of P. Then for all 1 i M, P_i+1 = P_i+1Mult_i. Then move the starting position of the multiplier over to the third element of P and for all i 1 i M, P_i+2 = P_i+2 Mult_i. Keep moving the starting position of the multiplier and multiplying its elements in a similar manner. Do this process a total of nm+1 times. You must output the final powers of all the knightmares after all the operations are completed. Since the numbers can be very large, output them modulo (10⁹ + 7). Note: Please ensure to use long int/long long int to avoid integer overflow since upon multiplication, the numbers can exceed the size of int.

Input

The first line consists of two space-separated integers N and M, the number of Knightmares and the number of multipliers. (1 M N 10⁵). The second line contains N space-separated integers which are the initial powers of the knightmares P₁,P₂,,P_n. The third line contains M space-separated integers, representing the power of each of the M multipliers, A₁,A₂,,A_m (1 P_i,A_i 10⁹ i).

Output

Print a single line of N space-separated integers, the final powers of the knightmares after all operations modulo (10⁹ + 7).

input

5 3

5 3 1 7 2 1 2 4

output

5 6 8 56 8

explanation

Initially the array A gets multiplied on to the first three elements of P, then the second three, and so on. It is easy to see that this is the answer.

E: Who Will Win Today?

Shirogane wants to impress Kaguya and so he tells her that given a set of letters from the english alphabet, he can enumerate all possible words of length K using only those letters in 1 second or less. Obviously, this is an impossible task so he asks you, Ishigami, to bail him out so that he doesnt look stupid in front of Kaguya.

Input

The first line consists of two space-separated integers N and K, the number of letters you can use, and the length of each word respectively (it is guaranteed that N^K 10⁵ and sum of lengths of all possible words does not exceed 10⁵). The second line contains a string of N distinct lowercase English alphabets (no capital letters or special characters) representing the possible letters that you can use. Note that you cannot use any character or letter not present in the string.

Output

print N^K lines, each line containing a distinct string of length K. Two strings are considered distinct if they differ in at least one position.

input

2 3

ab

output aab bbb abb bab baa aba bba aaa

F: Koro-sensei and the Powers of Two

While the students of class 3E thought they bought some respite after last weeks problem on primes, Koro-sensei is back at it again, with another weird question. Given a number N, the students have to find the number of ways it can be represented as a sum of power of 2. Can you help them?

Input

The only line of input contains a single integer N. (0 N 10²)

Output

Print one integer, X denoting the number of ways N can be expressed as a sum of powers. Please note that reorderings of the same sum do not count as multiple ways eg. (2+2+1), (2+1+2), (1+2+2) are all treated as the same thing.

input 7

output 6

explanation

7 can be represented as: (4 + 2 + 1), (4 + 1 + 1 + 1), (2 + 2 + 2 + 1), (2 + 2 + 1 + 1 + 1), (2+1+1+1+1+1), and (1+1+1+1+1+1+1), since the powers of 2 are 2⁰,2¹,2² which are 1,2,4

input 4

output 4

explanation

(4),(2 + 2),(2 + 1 + 1),(1 + 1 + 1 + 1)

G: The COVID Vaccine

Its finally here and all this can end! However, before normalcy can completely return, enough people need to be vaccinated for everything to be safe. The owner of a vaccine manufacturing facility wants to start selling and shipping vaccines as soon as possible. However, business being business, she wants to ensure that the company spends the least amount of money for shipping the products. Vaccines are first stored in small boxes, which are then stacked inside big boxes before being loaded onto cargo ships and planes. All big boxes have a fixed weight B, but the weights of the small boxes can vary considerably. Given a list of weights of N small boxes, what is the minimum number of big boxes youd need to ship all the vaccines available? At most two boxes (s_i,s_j) can be placed in one big box, due to government regulations. s_i + s_j B. Additional thinking: How would the answer change if this government regulation was removed? To be clear this is not a part of the problem statement just something to think about.

Input

The first line of input contains N (1 N 210³). The second line of input contains a sequence of N space-separated integers (s_i B 10⁴), representing the weights of the small boxes that we have. The third line of input contains the number B, the weight of the large box.

Output

Print a single integer X denoting the minimum number of large boxes you would need.

input input

2 10

• 1 9 12 7 5 4 3 3 1 8 4
• 13

output output

1 5

explanation explanation

We can fit both these small boxes in One valid configuration: (12, 1),

one big box of size 3 (9, 4), (8, 5), (7, 4), (3,3)

H: Aggregating the Binary Tree

You are given a complete binary tree in which all the nodes are at the same depth relative to the root. The binary tree is represented as an array A, where A[0] is the root. For every i^th index, its left child is stored in A[2i + 1] and its right child in A[2i + 2]. You need to aggregate all the elements in the binary tree following a special rule: S = ^P_i A_i L_i, where A_i is the value at that node and L_i is the level. Note: the level of the root node is 1, and the level of its children would be 2, its grandchildren 3, and so on.

Input

The first line contains a single integer N (1 N 2¹⁸ 1) denoting the number of elements in the binary tree where N is of the form 2^k 1 where k is a positive integer. The next line contains N positive space separated integers.

Output

Print a single integer S, denoting the aggregate sum of the binary tree.

input 3

21 9 7

output 53

explanation

The root of the binary tree is 21 (level 1), while its left child is 9 (level 2) and its right child is 7 (level 2). Aggregated sum = (21 1) + (9 2) + (7 2) = 53

input 7

1 2 4 6 7 5 3

output 76

explanation

1 1 + (2 + 4) 2 + (6 + 7 + 5 + 3) 3 = 76

I: The Dinosaur Conundrum

The inauguration of the Jurassic Park is about to happen tomorrow, and John Hammond has a problem on his hands. While they could successfully clone N different species of dinosaurs, they soon realized that dinosaurs would start attacking each other as soon as they woke up. After a lot of observation, the handlers notice that not all dinosaurs are aggressive towards each other only dinosaurs that have been cloned from the same raw genetic material fight each other. Each dinosaur has a tag, which indicates the source of their genetic material. If the tags of two dinosaurs start with the same first character, they fight, otherwise they dont. You have C different cages to store the dinosaurs in, each of which can store any number of dinosaurs. Given the tags of all N dinosaurs, separate the dinosaurs into cages such that a minimum number of pairs of dinosaurs fight. For eg, if a cage has three dinosaurs (XAHSG-2737, XAGFS-89 and XSGFS-999) each dinosaur will fight with the other two to form 3 pairs of fights (XAHSG-2737, XAGFS89), (XAHSG-2737, XSGFS-999), (XAGFS-89 and XSGFS-999).

Input

The first line of input contains two space-separated integers, N and C. The following N lines contain strings (of length 20) denoting the tags of all the dinosaurs. It is guaranteed that the characters in the tag will be from the set [A-Z,0-9].

Output

Print one integer, P, the number of pairs of fights that will happen in the minimal case.

input6 4XGB189ABFG99XFG983BST535TIN846 XC67TPoutput0

input6 2FFT998DFFT99BWFT36BERT99BLIP87 BHIJ78output2

J. Air Tickets

You have been invited to the Annual Computing Conference which is going to be held in Tokyo this year. Sadly, the organizers have declined to reimburse your flight tickets to the conference. So, you decide to take the flight path (a flight path may have multiple hops) to Tokyo which will cost you the least. Given the all the hops possible between the major cities of the world, find the cost of the minimum flight path. Assume that each hop costs you the same, i.e. $100. Note: You must use adjacency lists to solve this problem.

Input

The first line of input contains four space-separated integers N (1 N 5000), M (0 M

N-1) and T (0 T N-1) denoting the number of cities, the number of hops,

the city you live in and city you wish to reach (Tokyo) respectively. The following M lines contain two space-separated integers U_i and V_i (0 U_i, V_i N-1) denoting an undirected hop between the cities U_i and V_i. It is guaranteed that atleast one flight path exists to Tokyo.