Problem Statement

You are given two strings S and T consisting of lowercase English letters.

Determine if there exists a pair of integers c and w such that 1 \leq c \leq w < |S| and the following condition is satisfied. Here, |S| denotes the length of the string S. Note that w must be less than |S|.

• If S is split at every w characters from the beginning, the concatenation of the c-th characters of the substrings of length at least c in order equals T.

Constraints

• S and T are strings consisting of lowercase English letters.
• 1 \leq |T| \leq |S| \leq 100

Sample Input 1

atcoder toe

Sample Output 1

Yes

If S is split at every two characters, it looks like this:

at
co
de
r

Then, the concatenation of the 2nd characters of the substrings of length at least 2 is toe, which equals T. Thus, print Yes.

Sample Input 2

beginner r

Sample Output 2

No

w=|S| is not allowed, and no pair of integers 1 \leq c \leq w < |S| satisfies the condition. Thus, print No.

Sample Input 3

verticalreading agh

Sample Output 3

No

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
   • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
   • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_{i+1}
• All values in the input are integers.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

• Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
• Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• N and M are integers.
• 1 \leq N, M \leq 10
• Each S_i is a string of length M consisting of o and x.
• For every i (1 \leq i \leq N), there is at least one o in S_i.
• For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

• 1 \leq N \leq 5 \times 10^5
• |A_i| \leq 10^9 (i=1,2,\dots,N)
• |B_j| \leq 10^9 (j=1,2,\dots,N)
• All input values are integers.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

• 1\leq N\leq 13
• S is a string of length N consisting of digits.
• N is an integer.

Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

840