Description

Compute the numbers of islands on the map.
The character '~' means water. There are two types of islands, denoted as '#' and '@'.
Take the following map for example:

The number of #-typed islands is 3, and the number of @-typed islands is 2.

Note that two '#'s are considered connected only if they are horizontal or vertical neighbors. Diagonal neighbors are not considered connected. The rule is the same for '@'.

Input

The first line contains two integers m, n, representing the height and width of the map.

The next m lines contain n characters for the mth row of the map.

It is guaranteed that 1 ≤ m, n ≤ 1000

Output

Print the number of islands for '#' and the number of islands for '@'.

The two numbers are separated by a whitespace. Please include a newline character '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have to place N queens on a NxN chessboard in such a way that no queen threatens another one.

The rule is that each row and column of the board contains exactly 1 queen , and each diagonal contains no more than 1 queen.

Your mission is to compute how many possible ways to place N queens on that chessboard.

Input

An integer N which represent the size of chessboard and the number of queens

where 1<=N<=50.

Output

An integer which represent the number of possible distributions of  N queens.

There is no need to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You want to stimulate shooting route in a room. You know the boundary of room, the start point of a shooting object, and the direction of shooting. When the object hitting the boundary, it would reflect with 45 degrees. Your mission is to show the route of the shooting object.

Input

The first line has three numbers, C, F and H, which respectively means the length of the ceiling, the length of the floor, and the height between the ceilings and floors.

The second line has a number S, which means the start point of shooting object. It's noted that the location below the ceiling is 1, and the location below that is 2, and so on.

• 1 ≤ C, F ≤ 20
• 2 ≤ H ≤ 20
• 1 ≤ S ≤ H

The third line has a character 'u' or 'd'. It  corresponds to the initial direction of shooting.

• u: upper-right in 45 degree
• d: lower-right in 45 degree

There are only one case for each testcase

Output

Draw the map and the route of the shooting object.
The route of shooting object is marked as '*', which appears until the object is out of boundaries.

You need to use a (H+2)*(max{C, F, the horizontal length of the route of shooting}) array to print out the result

Remember there is '\n' in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are n children in Johnny Johnny' s family.

And number i child wants to have a_i units of sugar.

But their PaPa don't want them eat too much sugar. Therefore he will randomly choose some children and only give them the great common divisor of a_i. 

 

For example, if there're n=5 children and a_i = { 1, 4, 6, 7, 18 }.

Suppose PaPa choose the children numbered 2,3,5.

Then all children will only get  gcd(a₂, a₃, a₅) = gcd(4,6,18) = 2 unit of sugar.

 

Now Johnny wants to know what's the maximum amount of sugar they can get.(PaPa will at least choose two child) 

If you can help him, he will laugh at you for you don't have any sugar " Ha Ha Ha!!! "

 

To calculate great common divisor, you can use the method 輾轉相除法(https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)

Input

input contains two lines.

First line only contains one integer n ( 2 <= n <=  1000)

Second line contain n integers a₁ ~ a_n ( 1<= a_i <= 1000 )

Output

output contains only one integer the maximum amount of sugar they can get.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss