A string is called a k-string if it can be represented as k concatenated copies of some string. For example, the string "aabaabaabaab" is at the same time a 1-string, a 2-string and a 4-string, but it is not a 3-string, a 5-string, or a 6-string and so on. Obviously any string is a 1-string.
You are given a string s, consisting of lowercase English letters and a positive integer k. Your task is to reorder the letters in the string s in such a way that the resulting string is a k-string.
The first input line contains integer k (1 ≤ k ≤ 1000). The second line contains s, all characters in s are lowercase English letters. The string length s satisfies the inequality 1 ≤ |s| ≤ 1000, where |s| is the length of string s.
Rearrange the letters in string s in such a way that the result is a k-string. Print the result on a single output line. If there are multiple solutions, print any of them.
If the solution doesn't exist, print "-1" (without quotes).
2
aazz
azaz
3
abcabcabz
-1
Polycarpus is an amateur businessman. Recently he was surprised to find out that the market for paper scissors is completely free! Without further ado, Polycarpus decided to start producing and selling such scissors.
Polycaprus calculated that the optimal celling price for such scissors would be p bourles. However, he read somewhere that customers are attracted by prices that say something like "Special Offer! Super price 999 bourles!". So Polycarpus decided to lower the price a little if it leads to the desired effect.
Polycarpus agrees to lower the price by no more than d bourles so that the number of nines at the end of the resulting price is maximum. If there are several ways to do it, he chooses the maximum possible price.
Note, Polycarpus counts only the trailing nines in a price.
The first line contains two integers p and d (1 ≤ p ≤ 1018; 0 ≤ d < p) — the initial price of scissors and the maximum possible price reduction.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.
Print the required price — the maximum price that ends with the largest number of nines and that is less than p by no more than d.
The required number shouldn't have leading zeroes.
1029 102
999
27191 17
27189
A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.
The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.
6 3
ABBACC
2
ABCACA
3 2
BBB
1
BAB
The country Treeland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are n - 1 roads in the country. We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.
The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city a is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.
Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.
The first input line contains integer n (2 ≤ n ≤ 2·105) — the number of cities in Treeland. Next n - 1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers si, ti (1 ≤ si, ti ≤ n; si ≠ ti) — the numbers of cities, connected by that road. The i-th road is oriented from city si to city ti. You can consider cities in Treeland indexed from 1 to n.
In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.
3
2 1
2 3
0
2
4
1 4
2 4
3 4
2
1 2 3
A parking lot in the City consists of n parking spaces, standing in a line. The parking spaces are numbered from 1 to n from left to right.
When a car arrives at the lot, the operator determines an empty parking space for it. For the safety's sake the chosen place should be located as far from the already occupied places as possible. That is, the closest occupied parking space must be as far away as possible. If there are several such places, then the operator chooses the place with the minimum index from them. If all parking lot places are empty, then the car gets place number 1.
We consider the distance between the i-th and the j-th parking spaces equal to 4·|i - j| meters.
You are given the parking lot records of arriving and departing cars in the chronological order. For each record of an arriving car print the number of the parking lot that was given to this car.
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 2·105) — the number of parking places and the number of records correspondingly.
Next m lines contain the descriptions of the records, one per line. The i-th line contains numbers ti, idi (1 ≤ ti ≤ 2; 1 ≤ idi ≤ 106). If ti equals 1, then the corresponding record says that the car number idi arrived at the parking lot. If ti equals 2, then the corresponding record says that the car number idi departed from the parking lot.
Records about arriving to the parking lot and departing from the parking lot are given chronologically. All events occurred consecutively, no two events occurred simultaneously.
It is guaranteed that all entries are correct:
- each car arrived at the parking lot at most once and departed from the parking lot at most once,
- there is no record of a departing car if it didn't arrive at the parking lot earlier,
- there are no more than n cars on the parking lot at any moment.
You can consider the cars arbitrarily numbered from 1 to 106, all numbers are distinct. Initially all places in the parking lot are empty.
For each entry of an arriving car print the number of its parking space. Print the numbers of the spaces in the order, in which the cars arrive to the parking lot.
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8
1
7
4
2
7
4
1
3