Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

• 1\leq N \leq 100
• 1\leq A_i\leq 100
• 1\leq P\leq Q<R\leq S \leq N
• Q-P=S-R
• All values in the input are integers.

Sample Input 1

8 1 3 5 7
1 2 3 4 5 6 7 8

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.

Constraints

• S is a string of uppercase and lowercase English letters.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

AtCoderBeginnerContest

Sample Output 1

ACBC

The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.

Sample Input 2

PaymentRequired

Sample Output 2

PR

Sample Input 3

program

Sample Output 3

Note that S may contain no uppercase letters.

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

• N is an integer between 2 and 30, inclusive.
• M is an integer between 1 and 30, inclusive.
• S_i is a string of length M consisting of o and x.

Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.

Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

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

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is ice;
• if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

• First, specify the direction of movement: up, down, left, or right.
• Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
  • if the next square in the direction of movement is ice, go to that square and keep moving;
  • if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

• 3 \le N,M \le 200
• S_i is a string of length M consisting of # and ..
• Square (i, j) is rock if i=1, i=N, j=1, or j=M.
• Square (2,2) is ice.

Sample Input 1

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

Sample Output 1

12

For instance, the player can rest on (5,5) by moving as follows:

• (2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

• (2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

215

Problem Statement

There is a connected undirected graph with N vertices and M edges, where the i-th edge connects vertex U_i and vertex V_i bidirectionally.
Each vertex has an integer written on it, with integer A_v written on vertex v.

For a simple path from vertex 1 to vertex N (a path that does not pass through the same vertex multiple times), the score is determined as follows:

• Let S be the sequence of integers written on the vertices along the path, listed in the order they are visited.
• If S is not non-decreasing, the score of that path is 0.
• Otherwise, the score is the number of distinct integers in S.

Find the path from vertex 1 to vertex N with the highest score among all simple paths and print that score.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• N-1 \le M \le 2 \times 10^5
• 1 \le A_i \le 2 \times 10^5
• The graph is connected.
• 1 \le U_i < V_i \le N
• (U_i,V_i) \neq (U_j,V_j) if i \neq j.

Sample Input 1

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

Sample Output 1

4

The path 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 has S=(10,30,40,50) for a score of 4, which is the maximum.

Sample Input 2

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

Sample Output 2

0

There is no simple path from vertex 1 to vertex N such that S is non-decreasing. In this case, the maximum score is 0.

Sample Input 3

10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7

Sample Output 3

5

Problem Statement

You are given a string S of length N consisting of A and B.
Process a total of Q queries of the following types.

1 i c

Type 1: Change the i-th character of S to c.

2 l r

Type 2:
Let string T be the string obtained by extracting the l-th through r-th characters of the current string S.
If it is possible to obtain string T by the following operation, output Yes; otherwise, output No.

• Starting from the empty string, perform the following two operations any number of times, possibly zero, in any order.
  • Choose any position in the string (possibly the beginning or the end) and insert A there.
  • Choose any position in the string (possibly the beginning or the end) and insert AB there.

Constraints

• N is an integer satisfying 1 \le N \le 5 \times 10^5.
• S is a string of length N consisting of A and B.
• Q is an integer satisfying 1 \le Q \le 2 \times 10^5.
• Each given query is of type 1 or 2.
• Queries of type 1 satisfy the following constraints:
  • i is an integer satisfying 1 \le i \le N, and
  • c is A or B.
• Queries of type 2 satisfy the following constraints:
  • l and r are integers satisfying 1 \le l \le r \le N.

Sample Input 1

10
AABBAABABB
6
2 1 10
1 5 B
2 1 10
2 6 8
1 3 A
2 1 10

Sample Output 1

Yes
No
Yes
Yes

This input contains six queries.

• Initially, S= AABBAABABB.
• For the 1-st query, T= AABBAABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the following steps, so output Yes.
  • Start from the empty string.
  • Insert AB at the beginning of the empty string, making the string AB.
  • Insert AB right after the 1-st character of AB, making the string AABB.
  • Insert AB at the end of AABB, making the string AABBAB.
  • Insert AB right after the 5-th character of AABBAB, making the string AABBAABB.
  • Insert AB right after the 7-th character of AABBAABB, making the string AABBAABABB.
• For the 2-nd query, change the 5-th character of S to B. As a result, S= AABBBABABB.
• For the 3-rd query, T= AABBBABABB, obtained by extracting the 1-st through 10-th characters of S, cannot be obtained by the operation described in the problem statement, so output No.
• For the 4-th query, T= ABA, obtained by extracting the 6-th through 8-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.
• For the 5-th query, change the 3-rd character of S to A. As a result, S= AAABBABABB.
• For the 6-th query, T= AAABBABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.