Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

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

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

• Move item 1 from box 2 to box 1. The cost is 33.
• Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

17254

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

• In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
• In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
• In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC