Problem Statement

You are given a length-N sequence A=(A_1,A_2,\ldots,A_N) of positive integers.

Determine whether A is a geometric progression.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 6 12 24 48

Sample Output 1

Yes

A=(3,6,12,24,48).
A is a geometric progression with first term 3, common ratio 2, and five terms.
Therefore, print Yes.

Sample Input 2

3
1 2 3

Sample Output 2

No

A=(1,2,3).
Since A_1 : A_2 = 1 : 2 \neq 2 : 3 = A_2 : A_3, A is not a geometric progression.
Therefore, print No.

Sample Input 3

2
10 8

Sample Output 3

Yes

A is a geometric progression with first term 10, common ratio 0.8, and two terms.
Therefore, print Yes.

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

• C[a][b] is #.
• C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
• At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

• 3 \leq H, W \leq 100
• C[i][j] is # or ..
• No two different squares that comprise two different crosses share a corner.
• H and W are integers.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

• X is greater than or equal to N.
• There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

• N is an integer.
• 0 \le N \le 10^{18}

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.