Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

• X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H and W are integers.
• C_{i, j} is . or #.

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Problem Statement

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

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

Sample Input 1

4
3 -5 7 -4

Sample Output 1

3

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.

Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.

The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.

The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.

For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Constraints

• 1 \leq N, M \leq 200000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

• After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
• After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
• After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
• After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
• After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
• After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
• After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2