Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

• A contains exactly K distinct integers greater than A_i.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

• Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
• Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
• Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
• Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
• Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
• Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

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.