Problem Statement

Takahashi has N teeth arranged in a single row from left to right. The current condition of his teeth is represented by a string S.

If the i-th character of S is O, it means that the i-th tooth from the left is healthy. If it is X, it means that the i-th tooth has a cavity. Healthy teeth do not have cavities.

When he has K consecutive healthy teeth, he can eat one strawberry using those K teeth. After eating a strawberry, those K teeth develop cavities and become unhealthy.

Find the maximum number of strawberries he can eat.

Constraints

• 1 \leq K \leq N \leq 100
• N and K are integers.
• S is a string of length N consisting of O and X.

Sample Input 1

7 3
OOXOOOO

Sample Output 1

1

He can eat one strawberry by using the three consecutive healthy teeth from the 4th to 6th tooth from the left. After this, he cannot eat any more strawberries. Besides, there is no way for him to eat more than one strawberry. Therefore, print 1.

Sample Input 2

12 2
OXXOOOXOOOOX

Sample Output 2

3

Sample Input 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

Sample Output 3

2

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

• choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

• Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
• S and T have the same length.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

Problem Statement

You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.

Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.

• For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.

Constraints

• N is an even number between 2 and 3000, inclusive.
• Each A_{i, j} is # or ..

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem F.)

• \lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
• For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
• Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Constraints

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

Sample Input 1

8
2 3 1 1 2 2 1 1

Sample Output 1

4

For example, taking the subarray from the 3-rd to 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer (contiguous) subarray that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

3
1 2 2

Sample Output 2

2

Sample Input 3

1
1

Sample Output 3

0

Note that a sequence of length 0 also satisfies the conditions for a 1122 sequence.