Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

Constraints

• S consists of lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

• How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

• 1 \le M \le N \le 2 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_M = N
• All input values are integers.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

• From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
• From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
• From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

Problem Statement

You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:

• For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
• For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.

For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)

How many ways are there to write numbers to satisfy the conditions?

Constraints

• 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
• All values in input are integers.

Sample Input 1

3 4 6 3 3 7

Sample Output 1

1

The following is the only way to satisfy the conditions. Thus, 1 should be printed.

Sample Input 2

3 4 5 6 7 8

Sample Output 2

0

There may not be a way to satisfy the conditions.

Sample Input 3

5 13 10 6 13 9

Sample Output 3

120

Sample Input 4

20 25 30 22 29 24

Sample Output 4

30613

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

• 2\leq N\leq 16
• 1\leq D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

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

Sample Output 3

75