Castles Valley was lit by the noonday sun. One could descry two figures on a balcony of one of Castles — a big and a small ones. Dragon and Princess were drinking tea. Dragon was fond of preparing tea compositions, and he was very glad that Princess was drinking tea with great pleasure and listened with interest to his narrations on how one or another tea was composed.
Dragon always puts into a teapot m teaspoons of ingredients, which he calls portions. If it is written "put two portions of Black Ceylon Tea, add one portion of currant leaves, one portion of cornflowers, and after put another portion of Black Ceylon Tea and a portion of calendula petals" in a recipe, Dragon puts the portions to the teapot exactly in the described order: he is absolutely sure that the taste of a tea depends on the order in which ingredients are put.
Dragon told Princess that once upon a time his friend Knight imparted to him a recipe of a delicious tea, and since then he, Dragon, got into making tea compositions. He experimented with replacing some ingredients with some another ones in this recipe, and when he liked the taste of a brand new tea, he wrote down the resulting recipe. And he has done it so many times, choosing one of the written recipes as a basic one for a new recipe each time.
Dragon has an original system of composing teas and writing their recipes. He denotes all of used ingredients by lowercase Latin letters (each letter corresponds to some ingredient, the same ingredients denoted by the same letters, and different ingredients denoted by different letters). So, a tea description is a string of m letters in the same order of ingredients as in the recipe.
When Dragon was inventing the notation, he supposed that more similar (in his viewpoint) ingredients should be denoted by more closely spaced (in alphabetical order) symbols. Indeed, it is much less radical solution to replace currant leaves with blackberry leaves, than to replace calendula petals with a cinnamon. For this reason, Dragon defined the distance between recipes as a maximum absolute value of a distances between ingredients at the corresponding positions in the recipes.
Dragon writes down each recipe on a separate sheet of paper and keeps all these sheets in a special box. Since that, we cannot know the maximum amongst all of the distances between the recipes. However, Dragon assures that maximum distance is the minimum possible.
You are given n descriptions of teas composed by Dragon. Your task is to calculate the minimum value of maximal distance between the recipes.
The first line contains integers n and m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 30) — the number of recipes and the number of ingredients in each recipe.
Each of next n lines contains one recipe — the string of m lowercase latin letters. It is guaranteed that all recipes are different.
Print the single integer — minimum value of maximal distance between the recipes.
5 2
fb
ga
ef
dc
fd
2
Let us explain the sample above.
Suppose the first recipe (fb) is the recipe of the delicious tea. Easy to see that the distance between the first recipe and the second recipe (ga) is 1. Obviously, this distance is the minimum distance between any pair of recipes, and we can assume that the second recipe was prepared from the first.
The distance between the fourth recipe (dc) and the first recipe is 2; the distance between the fourth and the fifth recipes is the same. We can assume that Dragon prepared the fourth tea from the first tea, and then prepared the fifth tea from the fourth tea.
At last, the third recipe (ef) can be prepared from the fifth (fd); distance between these recipes is 2, too.
So, Dragon can compose all the recipes of tea, and when he prepares some recipe from another recipe, the distance does not exceed 2.
During tea-drinking, Princess, amongst other things, asked why has such a good-natured and cute Dragon imprisoned Prince in the Castle? Dragon smiled enigmatically and answered that it is a big secret. After a pause, Dragon added:
— We have a contract. A rental agreement. He always works all day long. He likes silence. Besides that, there are many more advantages of living here in the Castle. Say, it is easy to justify a missed call: a phone ring can't reach the other side of the Castle from where the phone has been left. So, the imprisonment is just a tale. Actually, he thinks about everything. He is smart. For instance, he started replacing incandescent lamps with energy-saving lamps in the whole Castle...
Prince chose a model of energy-saving lamps and started the replacement as described below. He numbered all rooms in the Castle and counted how many lamps in each room he needs to replace.
At the beginning of each month, Prince buys m energy-saving lamps and replaces lamps in rooms according to his list. He chooses the first room in his list, in which lamps are not replaced yet. If Prince has enough lamps to replace all lamps in the room, he replaces all ones and takes the room out from the list. If there are still some energy-saving lamps unused, he considers replacement in the next room, which is the first in his list. This repeats while he still has some energy-saving lamps and number of lamps to replace in the next room is not greater than number of energy-saving lamps which Prince has in stock. Otherwise he postpones the replacement and saves the rest of energy-saving lamps for the next month.
As soon as all the work is done, he ceases buying new lamps. They are very high quality and have a very long life cycle.
Your task is for a given number of month and descriptions of rooms to compute in how many rooms the old lamps will be replaced with energy-saving ones and how many energy-saving lamps will remain by the end of each month.
The first line contains integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 100) — the number of rooms in the Castle and the number of energy-saving lamps, which Prince buys monthly.
The second line contains n integers k1, k2, ..., kn (1 ≤ kj ≤ 1000, j = 1, 2, ..., n) — the number of lamps in the rooms of the Castle. The number in position #j is the number of lamps in #jth room. Room numbers are given in accordance with Prince's list.
The third line contains one integer q (1 ≤ q ≤ 105) — the number of queries.
The fourth line contains q integers d1, d2, ..., dq (1 ≤ dp ≤ 105, p = 1, 2, ..., q) — numbers of months, in which queries are formed.
Months are numbered starting with 1; at the beginning of the first month Prince buys the first m energy-saving lamps.
Print q lines.
Line #p contains two integers — the number of rooms, in which all old lamps are replaced already, and the number of remaining energy-saving lamps by the end of dpth month.
5 4
3 10 5 2 7
10
5 1 4 8 7 2 3 6 4 7
4 0
1 1
2 3
5 1
5 1
1 5
1 9
4 4
2 3
5 1
Dragon poured Princess another cup of tea. Princess sighed faintly and asked:
— Do princesses and princes in neighbouring castles have rental agreements too?
— Yes, of course! — Dragon answered, — To tell the truth, princesses are troublesome. So, every progressive dragon would rather lease his castles to a prince. However, the demand for rent of castles is so small now, many dragons have side job as taxi. As aerotaxi, I mean.
As Dragon told, the inhabitants of castles fly on dragons on business quite often. While flying they do not like to cross each other and require no one of their neighbours could see them. And a dispatcher, who schedules flights, has a hard work because of that.
Let us describe a simplified model of flights. Suppose air space is divided into n "air corridors". These air corridors are indexed, each corridor locates in certain height; the smaller the number of a corridor, the higher the corridor is.
Dragon begins his flight taking up any vacant corridor. During the flight, a dragon may descend and he does it step by step. The dispatcher demands dragons to descend only in integer moments of time and by only one corridor down. So, if a dragon flies along the jth air corridor, he can descend down to (j + 1)th air corridor (if (j + 1)th corridor exists). If a dragon occupies some air corridor, he must fly along it for at least one time unit.
Dragon moves at a constant horizontal speed during the whole flight. Time for moving between air corridors is negligible and should be considered zero. Dragon can't stop during the flight.
Dispatcher has a schedule wherein the periods of corridors' occupation are specified. Each period consists of some intervals of form (s, f) (s < f); it is believed that a dragon can occupy air corridor at interval's boundaries s and f, but not in any time strictly between s and f.
Dispatcher gets a request for a flight t time units long from another dragon, and he is to allocate some air corridors for the flight. Dragon's passenger wants to arrive at a destination as soon as possible.
Your task is to compute the time of flight's beginning and the times in which the dragon should descend (if it is necessary).
The first line contains integers n and t (1 ≤ n ≤ 100, 1 ≤ t ≤ 10000) — the number of air corridors and flight time.
Each of next n lines contain an air corridor's occupation periods. The line starts with integer cj (0 ≤ cj ≤ 100) — the number of time intervals. After it all the intervals are listed. An interval consists of two space-separated integers s(j)k и f(j)k (k = 1, 2, ..., cj). It is guaranteed that 0 ≤ s(j)1 < f(j)1 < s(j)2 < ... < f(j)cj ≤ 109.
Dragon (who requests a flight) is ready to begin his flight at any time starting from 0.
In the first line print an integer a — the earliest time a flight can start.
In the second line print two integers h and d — the number of air corridor where the flight starts and the number of descends.
In the third line print d space-separated integers — the times (in chronological order) in which the dragon should descend.
If there are more than one answer, choose any of them.
2 8
2 0 4 10 20
2 5 10 12 15
4
1 1
10
5 8
2 0 2 5 10
2 0 4 7 10
1 4 6
2 0 3 5 10
2 0 5 8 10
0
3 2
3 5
4 9
1 5 9
2 0 4 5 8
2 0 4 5 8
2 0 4 9 12
8
2 0
Let us explain the samples.
In the first sample dragon may start the flight at time 4 and occupy air corridor #1. At time 10 he descends to the 2nd air corridor. Flight ends at time 12.
In the second sample dragon may begin flight at time 0 and occupy the 3rd air corridor. At time 3 he descends to the air corridor number 4, at time 5 he descends again — to air corridor number 5.
In the third sample the earliest time of flight start is 8. Indeed, dragon can descend from the first air corridor to the second air corridor at time 4, then he stays in the second air corridor until time 5. At time 5 he descends to the 3rd air corridor, but he cannot stay in this corridor after time 5. At time 8 dragon may begin his flight in the 2nd or in the 3rd air corridor and move in the corridor until the end of the flight.
— And what about knights who rescue princesses? Is it also just a game? — Princess seemed to be disappointed.
— Well... If a princess and a knight have taken to each other, why hinder them? — Dragon felt a sympathy for Princess, and regretted for making her upset.
As a matter of fact, Dragon agreed with the literary classic who wrote "happy families are all alike". Long ago he counted all knights and princes in surrounding castles, and there were exactly n of them, as many as princesses. In Dragon's opinion, they needed to be acquainted with each other.
He shared these considerations with Princess and told her that he wants to offer to all knights, all princes and all princesses to make lists of preferences. In the first place of every list there should be written the name of the person, marriage with whom, he or she believes, makes her or him most happy. In the second place there should be written the name of the person, marriage with whom, he or she believes, makes her or him most happy, if marriage with the person in the first place is impossible, and so on. Every list must consist of n candidates.
After all the lists are made, all the people are divided into pairs. We call a set of such pairs a matching. Each person r1 wishes that every person r2 who is more preferable than who r1 is married, married someone, who is in r2's opinion better than r1. We call a set of such pairs a stable matching.
Let's describe it formally. Consider two pairs (m1, f1) and (m2, f2). Assume, that m2 prefers f1 over f2 (i.e. an index of f1 is less than index of f2 in the list of m2). But f1 believes that m1 is better choice than m2 (i.e. an index of m1 is less than index of m2 in the list of f1)
Otherwise the matching would not be stable, because f1 and m2 could form a pair with each other.
Then Princess doubted everyone will be happy in this case: for example there can be a pair of people where each single person put other one in end of his list.
Of course, Dragon has already thought about this and proposed to introduce a characteristics called dissatisfaction. A dissatisfaction of a person r is defined as his or her partner's number in r's list. A dissatisfaction of a matching is a maximum dissatisfaction amongst people in the matching.
You are given lists of preferences for all people, and you are to find a stable matching with minimum possible dissatisfaction.
The first line contains the integer n (1 ≤ n ≤ 200).
Each line of the following n ones contains a list of preferences of some prince or knight — a permutation of numbers from 1 to n.
Each line of the next n ones contains a list of preferences of some princess — a permutation of numbers from 1 to n.
Consider that princes and knights, as well as princesses, numbered in the order they appear in the input.
In the first line print the only integer — minimum possible dissatisfaction of a matching described above.
In the second line print n integers pj — the matching itself, where pj is the number of princess who marries prince or knight #j.
If multiple answers exist, choose any of them.
4
3 4 1 2
3 2 4 1
4 2 1 3
2 1 3 4
3 1 2 4
2 3 4 1
2 3 1 4
4 2 3 1
3
1 3 4 2
Let us explain the sample. Let us show that result matching is stable.
Consider pair (1, 1). The first partner's list of preferences contains 1 at position #3. The first partner would be happy to be in pair with 3 (first position in his list) or 4 (if 3 does not want to be in pair with him). The second partner's list of preferences contains 1 at position 2, so the second partner would be happy to be in pair with 3.
Thus the pair (2, 3) is optimal.
The first partner in pair (3, 4) is confident in his choice (4 is the first number in his list of preferences). But the second partner would rather change her current partner and be paired with 4 or (if 4 does not want) 2.
The situation in pair (4, 2) is similar to the situation in previous pair. The first partner does not want to change anything, but the second partner would rather leave his current partner in favor of 2 (or 3, if 2 does not want).
Let us analyse the preferences listed above.
The first partner in (1, 1) wants to be with 3, but 3 is paired with 2 already and wants to change nothing. Since that he tries to make pair with 4, though, unsuccessfully, since 4 is paired with 3 already and will not leave the pair in favor of 1. The second partner in (1, 1) tries to make pair with 3, unsuccessfully too because 3 in pair (3, 4) is happy of his pair.
The second partner in (3, 4) would like to change his current partner, but his desired 4 and 2 have already made their better choices.
The second partner in (4, 2) will be refused by desired 2 and 3 (from (2, 3) and (3, 4) pairs respectively).
In this matching maximum dissatisfied people are the first partner in pair (1, 1) and the second partners in pairs (3, 4) and (4, 2). Their dissatisfaction is 3.
There is no possible matching with dissatisfaction less than 3. Verify it by brute forcing all possible stable matchings.
— And do dragons do the same when they want to get married? — Princess asked.
— Dragons live alone. They come in existence in people's minds. And they evanesce when people forget about them, — Dragon answered.
Dragon told Princess that when someone imagines a new dragon, a new castle appears in the Castles Valley in which the dragon lives. If nobody thinks about the dragon for a long time, he falls asleep.
Sometimes it unusual rains in the Castles Valley. There is no clouds in the sky, the sun shines brightly, but great raindrops knock frequently on the roof of the castle where dragon sleeps. And after the rain is over, a lawn with wildflowers appears in the place where the castle was before. Moreover, rainwater brooks flow along the lanes leading from this castle. If a brook reaches a castle of a waking dragon, it stops there. However, if it reaches a castle of sleeping dragon, this castle becomes a lawn, too, and a brook flows farther.
Although dragons are only dreams, they feel for sleeping ones. They learned to foresee such rains, but they don't know which castle this rain will spill on. At the same time dragons want the number of appeared lawns to be as minimum as possible. They have a time to wake up exactly one of sleeping dragons before the rain. Now they want to know, in which castle they should wake up a dragon. Your task is to find it.
For the sake of simplicity, the input contains castles with sleeping dragons only. Also it is guaranteed that a path (consisting of one or more lanes) between every two castles exists.
The first line contains integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 2·105) — the number of castles with sleeping dragons and the number of lanes between castles.
Each of the next m lines contains two integer — numbers of castles connected by the lane.
It is guaranteed that no more than one lane between any two castles exist. Also no one lane connects a castle with itself.
Print the only integer — number of a castle in which dragon should be woken up.
If there is more then one answer, output any of them.
6 7
1 2
1 3
2 4
3 4
4 5
4 6
5 6
4
4 4
1 2
2 3
3 4
4 1
1
— But how can all of them be acquainted, if no one wants to see anyone else? — Princess still did not find Dragon's plan feasible.
— Not quite, — Dragon circumstantiated, — No one wants an unplanned contact. But, for example, they all come to intellectual competitions eagerly. There are games where teams consist of two people...
Dragon told Princess that qualification competition for Word Game begins in Castles Valley soon. Teams scored enough points participate in the next round of the competition. If several teams score an equal number of points, the team spent less time is placed higher.
Let us describe the rules of qualification game.
Game master has m cards in a pack. Only one word is written on each card. Players take turns. Before the game they agree which of them makes the first move and inform game master about it. Let us call the player who moves first The First Player, and call The Second Player another.
At the beginning, game master gives The First Player a card. The First Player tries to explain the word on the card without naming the word to The Second Player. When the explanation finished, The Second Player says his guess. If The Second Player's answer is the same as the word on the card, the team scores a point. Then, the game master gives The Second Player a card, and The Second Player tries to explain the word on the card to The First Player. Then a card is given to The First Player again... The game continues until cards run out.
But there is an important additional rule in this season. Player must use a terminology of only one subject area when he explains his word. Moreover, a terminology of each subject area should be used only once in qualification game. The n (n ≥ m) subject areas are specified in the rules.
A pair of players — X and Y — has prepared for a qualification game carefully. They believe that each of them can guess any word regardless of a terminology used for explanations. It is simply a matter of time.
After a series of trainings, they studied the time needed to guess the word that was explained with each terminology to each of them.
Now they want to know, what minimum possible time is required for them to score m points. Your tasks is to compute the time.
The first line contains integers m and n (1 ≤ m ≤ n ≤ 400) — the number of cards in a pack and the number of subject areas, which terminologies can be used for explanations.
The second line contains n integers p1, p2, ..., pn, where pj (1 ≤ pj ≤ 106) — the time player X needs to guess a word, if he listens to explanation of this word with jth subject area terminology.
The third line contains n integers q1, q2, ..., qn, where qk (1 ≤ qk ≤ 106) — the time player Y needs to guess a word, if he listens explanation of this word with kth subject area terminology.
Print integer — the minimum possible time, which players need for explanation of m words (in accordance to game rules) in the first line. Players can choose, who of them makes the first step.
3 5
5 4 7 6 2
8 3 5 4 2
9
4 4
2 4 6 8
1 4 6 7
18
In the first sample players should play the following way. The first step: player X explains a word to Y using the terms of the 2nd subject area, and Y guesses this word after 3 time units. The second step: player Y uses terms of 5th subject area for explanation of a word, and X guesses this word after 2 time units. The third step: player X explains yet another word using terms of the 4th subject area, and Y guesses this word after 4 time units.
— It' s a good game, — Princess said pensively. It was clear that she was thinking about something else.
— They like to play various games here in Castles Valley. And they invent ones themselves. Say, my friend Knight played with a princess a game some time ago, — Dragon thought it was a good idea o tell Princess about another game, if, perhaps, previous game was seemed no interesting for her.
Princess A. offered Knight to play a game of numbers. She puts down the number zero on a sheet of paper. Let us call this number a current result.
Further steps of princess A. and Knight are described below. She calls any positive integer and Knight says what she must do with this number: to add it to the current result or subtract it from the current result.
Princess A. performs the action and calculates a new value. This value becomes the new current result.
Princess A. wants that current result to be not less than zero and not greater than k at any time. The game finishes when an action makes the result out of the range or when a sequence of n numbers, which princess A. conceived, exhausts.
Knight managed to learn the sequence of n numbers that princess A. guessed, and now he wants the game to last as long as possible.
Your task is to compute maximum possible number of actions which Knight is able to perform during the game.
The first line contains integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000) — the size of sequence which princess A. conceived and an upper bound for a current result which must not be exceeded.
The second line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ k) — the sequence which princess A. conceived.
In the first line print integer d — maximum possible number of actions, which Knight is able to perform during the game.
Print d symbols "+" and "-" in the second line. Symbol at jth position specifies an action which is applied to jth number in the princess' sequence. If multiple answers exist, choose any of them.
2 5
3 2
2
++
5 5
1 2 3 4 5
4
++-+
— And Prince — what games does he play? — Princess looked at Dragon thoughtfully.
— Prince... He has so many different affairs all the time, he has no time for games, — Dragon thought for a moment and added, — Perhaps, that he is busy all the time is a reason why he doesn't want to play games...
Prince does his best to work as effectively as possible. So, some time ago Prince observed, that if he performs the same job during more than one unit of time, his work efficiency decreases conspicuously. For this reason he tries to do different jobs at any two consecutive units of time now.
Prince reports about all the work he does. After doing some kind of job during one unit of time, he paints over a cell on a strip of paper with a marker. One day Dragon took an interest what do all those colored squares mean. Prince clarified that every job corresponds to a color. Unfortunately, the number of markers is limited, so Prince can use the same color for different jobs. Of course, in this case the next job starts after the end of the previous job.
Prince boasted of his methods, and mentioned that he uses, among the other things, a forgetting parameter. The forgetting parameter is an integer k, a maximum allowable distance between two cells of the same color, if these cells are associated with the same job. It is clear, that it is not guaranteed that cells are associated with the same job if distance between cells is not greater than k and they have the same color. But it is guaranteed that every two cells are associated with different jobs if distance between them is greater than k and they have the same color.
Dragon interests what minimum number of different jobs Prince could have done for the last time. Your task is to compute it by a given colored strip and a value of k. For the sake of simplicity we use numbers instead of colors.
The first line contains integer n (1 ≤ n ≤ 105) — the number of colored cells.
The second line contains sequence of numbers c1, c2, ..., cn (1 ≤ cj ≤ 105) — the description of colored cells. The same numbers correspond to the same colors and vice versa.
The third line contains integer q (1 ≤ q ≤ 105) — the number of queries.
The fourth line contains integers k1, k2, ..., kq (1 ≤ k ≤ n) — the values of forgetting parameter, for every of which you should compute minimum possible number of jobs that Prince could have done during n units of time.
Print q integers dj (j = 1, 2, ..., q) in the first line. Number dj is the minimum possible number of jobs that Prince could have done for jth value of forgetting parameter.
6
1 1 1 1 1 1
5
1 2 3 4 5
3 2 2 2 1
15
3 2 1 3 4 8 2 1 1 3 3 1 4 6 2
6
7 3 10 5 4 6
10 12 7 10 11 10
As a matter of fact, Dragon knows what Prince is interested in now. Prince uses to spend his rare off days learning different courses and trainings. But Dragon doubts whether he should tell Princess about it.
Prince decided that he needs some extra knowledge and skills. He chose n fields in which he wanted to gain knowledge and skills most of all. After this, he learned that m1, m2, ..., mn courses and trainings of each of fields exist.
Prince took a close look at descriptions of courses and trainings and drew a table, in which sij is a value by which ith skill is increased after studying jth course (j = 1, 2, ..., mi).
Prince believes that his basic knowledge and skills in all these fields are negligible, so they can be considered zero. He wants to evolve his knowledge and skills harmonically. In his opinion, he will reach the greatest harmony if he chooses one course for each field in such a way that difference between the highest and the lowest their increases would be as minimum as possible.
Your task is to find the courses which Prince should choose.
The first line contains integer n (1 ≤ n ≤ 200) — the number of fields which Prince is interested in.
The second line contains n integers m1, m2, ..., mn (1 ≤ mj ≤ 1000, j = 1, 2, ..., n) — the number of courses for each of fields.
The next n lines contain values sij (1 ≤ sij ≤ 109) — knowledges and skills, which Prince would gain at the courses. The first of these n lines contains values s11, s12, ..., s1m1, the second — values s21, s22, ..., s2m2, etc.
The values sij are listed in the numerical order of courses for each of the fields.
In the first line print one integer — minimum difference between the highest and the lowest numbers of increase.
In the second line print n integers — numbers of courses which Prince should choose. List the numbers in the same order in which the fields are listed.
If there is more than one answer — choose any of them.
2
2 3
4 3
3 1 2
0
2 1
4
3 5 4 5
8 7 15
3 10 4 8 5
4 4 4 5
1 2 12 8 9
3
2 5 4 4
Dragon supposed that not all courses and trainings are so good. But he supposed that sport is good for sure. Of course, with no "cyber" prefix. He has witnessed how one gets addicted to computer games. Although he agreed that a computer game is an interesting pastime, it wastes too much time, in his opinion.
Then Dragon caught himself thinking, that communication with Prince was not in vain — it would seem, why should Dragon bother about how much time one spends playing computer games? Dragon, who exists outside of time...
Once upon a time Dragon watched a knight who was a computer game fan. That knight even organized a club of game fans. Initially, there were n gamers in the club.
When the knight wants to play, he selects a type of a game and sends invitation messages to his friends from the club. Then, these friends send messages to their friends, etc. So information about forthcoming game is spread among clubmates.
Amongst other things, a type of a game specifies its duration. It is worth noting that each of clubmates has their own opinion about how long can a game last at most. Therefore when a clubmate received an invitation for a too long game, he considers it inapropriate and removes himself from a mailing list forever and does not send any invitations to anybody. Otherwise, an invitation is considered apt and the clubmate plays a game.
Dragon is interested in how many man-minutes were spent on each game offered by the knight. Your task is to compute the values.
The first line contains integers n, m, p (2 ≤ n ≤ 105, 1 ≤ m ≤ 2·105, 1 ≤ p ≤ 2·105) — initial number of clubmates, number of pairs of clubmates who are friends, and number of games which were offered by the knight.
The second line contains n - 1 integers t2, t3, ..., tn (1 ≤ tj ≤ 109) — maximum allowed duration of a game for jth clubmate. The numbering of clubmates starts with 1, and the knight has number 1 and is going to play a game of any duration.
The third line contains p integers g1, g2, ..., gp (1 ≤ gk ≤ 109) — durations of games in the same order as the games themselves.
Each of the next m lines contains two integers — numbers of clubmates who are able to send messages to each other.
In the single line print p integers s1, s2, ..., sp, where sk — the total amount of time, which all gamers spent on kth game.
4 4 4
2 3 3
1 3 4 1
1 2
1 3
3 4
2 4
4 9 4 1
4 3 1
1 10 3
3
1 2
2 3
1 4
6
Let us explain the samples.
In the first sample, the following occurs. All clubmates take part in the first game, so the total amount of time is 4.
When the clubmate number 2 receives an invitation to the 2nd game, he leaves the club, and only 3 gamers participate in the second game. The total amount of time is 9.
Before the 3rd game, clubmates number 3 and 4 leave the club, and only the knight participates in the 3rd game. Therefore he plays the game number 4 alone. The total amount of time is 1 for the 4th game.
In the second sample clubmate number 2 refuses to participate in the first game; so he does not send message about the game to the clubmate number 3. Since clubmate number 3 can learn about forthcoming game only from clubmate number 2, then clubmate with 3 cannot participate in this game, too. So two clubmates were participating in the game, and the total amount of time is 6.
— It is not about games, — Dragon decided that he should not tell Princess about trainings. — It is necessary to make him want to leave the Castles Valley forever.
Princess sank into reverie again. Every day Prince goes into the world outside the Valley and comes back. What if he just does not see that many things in the big world which could change his life?
— It is better say that nothing will change for him if he leaves the Valley, — Dragon broke off Princess' thoughts.
Princess thought out long before, that she would tell Prince. But Dragon, after he listened to her narration, was sure it could not make Prince want to leave the Valley. He knew Prince quite well and realized that not all of Princess' arguments be treat by Prince as "pro"s.
Let's consider that Princess' narrative is a sequence of arguments. For each argument Dragon knew, if it is "pro", "contra" or neutral.
Dragon offered Princess to modify a sequence of arguments so that the last position of "contra" precedes the first position of "pro".
Dragon was quite considerate and understood that it is difficult to Princess to significantly modify a sequence of arguments at once. For this reason he proposed her to modify a sequence step by step. In each step Princess can swap any two consecutive arguments. Of course, there was still plenty of time until evening (when Prince comes back from his work), but Dragon wants to modify a sequence with minimum number of steps.
Your task is to compute the minimum number of the steps.
The first line contains integer n (2 ≤ n ≤ 100) — number of Princess' arguments.
The second line contains string of n symbols F, A and N, where F corresponds to argument "pro", A corresponds to argument "contra", and N corresponds to the neutral argument.
It is guaranteed that the sequence contains at least one argument "pro" and at least one argument "contra".
In the first line print the only integer — minimum number of steps, which are needed to put an original sequence in the suitable form.
6
FNAFNN
2
— How could I have forgotten? Knight is going to visit me today, — no matter how Dragon tried to be cunning, he was not very good at it, — I think, it will be interesting for you to make the acquaintance with him.
— Perhaps, we are somewhat acquainted already, — Princess smiled, — But it rarely happens to see each other: different people, different interests...
Dragon believed that common interests are not the most important things. The most important is to have the similar similar opinions on matters of principle. Dragon had a list of questions he had asked Knight and Prince already. He was going to ask Princess these questions.
Let's consider that an answer to a question is a positive integer. If the absolute value of difference between Knight's and Princess' answers is less than one of Prince's and Princess', Dragon believes that Knight's and Princess' opinions are more similar. And vice versa, if the absolute value of difference between Prince's and Princess' answers is less than one of Knight's and Princess', Dragon believes that Knight's and Princess' opinions are more similar. Dragon ignores the questions the values of which are equal.
Your task is figure out how many questions, in which Princess' and Prince's opinions are more similar, exist and how many questions, in which Princess' and Knight's opinions are more similar, exist.
The first line contains integer n (1 ≤ n ≤ 1000) — the number of Dragon's questions.
The second line contains n integers p1, p2, ..., pn — Prince's answers on Dragon questions.
The third line contains n integers k1, k2, ..., kn — Knight's answers on Dragon's questions.
The fourth line contains n integers r1, r2, ..., rn — Princess' answers on Dragon questions.
All answers are positive integer not greater than 100.
In the first line print two space-separated integers — the number of questions in which Princess' and Prince's opinions are more similar and the number of questions in which Princess' and Knight's opinions are more similar.
7
1 5 24 11 82 100 7
6 3 85 78 14 32 33
2 4 64 35 55 61 5
4 2
Dragon was drinking tea on a balcony and admiring a very beautiful sunset. Two outgoing silhouettes were still descrying in the rays of a setting sun. Of course, Princess promised to visit Dragon sometime, but what could be a reason for her to come back in the Castles Valley?..
Dragon decided to cook biscuits according to a recipe that was told him by Princess. So he needs to check if he has sufficient quantity of ingredients for it. Of course, he has a few of ginger, cinnamon, cloves and cardamon... But, comparing to making tea, he needs some more ingredients to bake biscuits.
Dragon revised all his ingredients, and knew how many units of each ingredient he had.
It was written in the recipe how many units of each ingredient are required to bake a biscuit. Certainly, Dragon wanted to bake an integer number of biscuits.
Dragon realized that he will expend some ingredients completely, while some other ingredients will remain. He believed he must purchase some extra ingredients, so that all ingredients will be completely expended after baking some number of biscuits.
Dragon knew the cost for a unit of each ingredient. Your task is to figure out minimum amount of money which is needed to spend to fulfil the condition above.
The first line contains integer n (1 ≤ n ≤ 10) — the number of ingredients.
The second line contains n integers q1, q2, ..., qn (1 ≤ qj ≤ 100, j = 1, 2, ..., n), qj — the number of units of jth ingredient, which Dragon has.
The third line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ 10, j = 1, 2, ..., n), cj — the number of units of jth ingredient which it needs for cooking a biscuit.
The fourth line contains n integers p1, p2, ..., pn (1 ≤ pj ≤ 100, j = 1, 2, ..., n), pj — cost of a unit of jth ingredient.
Print the only integer — minimum amount of money to spend.
3
15 8 10
2 3 5
12 1 4
148