CodeforcesRound#244(Div.2)

The prison of your city has n prisoners. As the prison can‘t accommodate all of them, the city mayor has decided to transfer c of the prisoners to a prison located in another city.

For this reason, he made the n prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.

Then, the mayor told you to choose the c prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,

• The chosen c prisoners has to form a contiguous segment of prisoners.
• Any of the chosen prisoner‘s crime level should not be greater then t. Because, that will make the prisoner a severe criminal and the mayor doesn‘t want to take the risk of his running away during the transfer.

Find the number of ways you can choose the c prisoners.

The first line of input will contain three space separated integers n (1?≤?n?≤?2·105), t (0?≤?t?≤?109) and c (1?≤?c?≤?n). The next line will contain nspace separated integers, the ith integer is the severity ith prisoner‘s crime. The value of crime severities will be non-negative and will not exceed109.

Print a single integer — the number of ways you can choose the c prisoners.

Your city has n junctions. There are m one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction i can protect junction j if either i?=?j or the police patrol car can go to j from i and then come back to i.

Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.

You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.

In the first line, you will be given an integer n, number of junctions (1?≤?n?≤?105). In the next line, n space-separated integers will be given. The ithinteger is the cost of building checkpost at the ith junction (costs will be non-negative and will not exceed 109).

The next line will contain an integer m (0?≤?m?≤?3·105). And each of the next m lines contains two integers ui and vi (1?≤?ui,?vi?≤?n; u?≠?v). A pair ui,?vi means, that there is a one-way road which goes from ui to vi. There will not be more than one road between two nodes in the same direction.

Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (109?+?7).

Police headquarter is monitoring signal on different frequency levels. They have got two suspiciously encoded strings s1 and s2 from two different frequencies as signals. They are suspecting that these two strings are from two different criminals and they are planning to do some evil task.

Now they are trying to find a common substring of minimum length between these two strings. The substring must occur only once in the first string, and also it must occur only once in the second string.

Given two strings s1 and s2 consist of lowercase Latin letters, find the smallest (by length) common substring p of both s1 and s2, where p is a unique substring in s1 and also in s2. See notes for formal definition of substring and uniqueness.

The first line of input contains s1 and the second line contains s2 (1?≤?|s1|,?|s2|?≤?5000). Both strings consist of lowercase Latin letters.

Print the length of the smallest common unique substring of s1 and s2. If there are no common unique substrings of s1 and s2 print -1.

Imagine that your city is an infinite 2D plane with Cartesian coordinate system. The only crime-affected road of your city is the x-axis. Currently, there are n criminals along the road. No police station has been built on this road yet, so the mayor wants to build one.

As you are going to be in charge of this new police station, the mayor has asked you to choose a suitable position (some integer point) for building it. You should choose the best position for the police station, so that you could minimize the total time of your criminal catching mission. Your mission of catching the criminals will operate only from this station.

The new station will have only one patrol car. You will go to the criminals by this car, carry them on the car, bring them back to the police station and put them in prison. The patrol car can carry at most m criminals at a time. Note that, the criminals don‘t know about your mission. So, they will stay where they are instead of running away.

Your task is to find the position for the police station, so that total distance you need to cover to catch all the criminals will be minimum possible. Note that, you also can built the police station on the positions where one or more criminals already exist. In such a case all these criminals are arrested instantly.

The first line of the input will have two integers n (1?≤?n?≤?106) and m (1?≤?m?≤?106) separated by spaces. The next line will contain n integers separated by spaces. The ith integer is the position of the ith criminal on the x-axis. Absolute value of positions will not exceed 109. If a criminal has position x, he/she is located in the point (x,?0) of the plane.

The positions of the criminals will be given in non-decreasing order. Note, that there can be more than one criminal standing at some point of the plane.

Note: since the size of the input/output could be very large, don‘t use slow input/output techniques in your language. For example, do not use input/output streams (cin, cout) in C++.

Print a single integer, that means the minimum possible distance you need to cover to catch all the criminals.