Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

• 1 \leq n \leq N - 2.
• The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.

Sample Input 1

8
ABABCABC

Sample Output 1

3

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

13

Problem Statement

You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.

The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.

Determine whether it is possible that the original string S contained U as a contiguous substring.

Constraints

• T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and ?.
• T contains exactly four occurrences of ?.
• U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.

Sample Input 1

tak??a?h?
nashi

Sample Output 1

Yes

For example, if S is takanashi, it contains nashi as a contiguous substring.

Sample Input 2

??e??e
snuke

Sample Output 2

No

No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.

Sample Input 3

????
aoki

Sample Output 3

Yes

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Here, each element of A is either -1 or an integer between 1 and N, inclusive.

Determine whether there exists an integer sequence P=(P_1,P_2,\ldots,P_N) of length N that satisfies all of the following conditions, and if it exists, find one.

• P is a permutation of (1,2,\ldots,N).
• For i=1,2,\ldots,N, if A_i \neq -1, then P_i=A_i holds.

Constraints

• 1\le N\le 10
• A_i=-1 or 1\le A_i \le N
• All input values are integers.

Sample Input 1

4
-1 -1 2 -1

Sample Output 1

Yes
3 1 2 4

P=(3,1,2,4) satisfies all conditions.

Besides this, P=(1,3,2,4) or P=(4,3,2,1) also satisfies all conditions.

Sample Input 2

5
-1 -1 1 -1 1

Sample Output 2

No

There is no P that satisfies all conditions.

Sample Input 3

7
3 -1 4 -1 5 -1 2

Sample Output 3

Yes
3 7 4 1 5 6 2

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.