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 an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

• 0 \leq N \leq 9999
• N is an integer.

Sample Input 1

321

Sample Output 1

0321

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

7777

Sample Output 2

7777

Sample Input 3

1

Sample Output 3

0001

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\ldots,A_N) of positive integers.

Determine whether A is a geometric progression.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 6 12 24 48

Sample Output 1

Yes

A=(3,6,12,24,48).
A is a geometric progression with first term 3, common ratio 2, and five terms.
Therefore, print Yes.

Sample Input 2

3
1 2 3

Sample Output 2

No

A=(1,2,3).
Since A_1 : A_2 = 1 : 2 \neq 2 : 3 = A_2 : A_3, A is not a geometric progression.
Therefore, print No.

Sample Input 3

2
10 8

Sample Output 3

Yes

A is a geometric progression with first term 10, common ratio 0.8, and two terms.
Therefore, print Yes.

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

• C[a][b] is #.
• C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
• At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

• 3 \leq H, W \leq 100
• C[i][j] is # or ..
• No two different squares that comprise two different crosses share a corner.
• H and W are integers.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

• X is greater than or equal to N.
• There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

• N is an integer.
• 0 \le N \le 10^{18}

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.

Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.

1. Aoki specifies a positive integer K_i.
2. After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.

3. Repeat the following K_i times.

   • Replace the integer x written on the blackboard with A_x.

If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.

Find the number of rounds Takahashi wins if both players play optimally to win.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A_i\leq N
• All values in the input are integers.

Sample Input 1

3
2 2 3

Sample Output 1

2

In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.

For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.

On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.

Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.

Sample Input 2

2
2 1

Sample Output 2

2

In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.

Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.

Problem Statement

There is a graph with N + Q vertices, numbered 1, 2, \ldots, N + Q. Initially, the graph has no edges.

For this graph, perform the following operation for i = 1, 2, \ldots, Q in order:

• For each integer j satisfying L_i \leq j \leq R_i, add an undirected edge with cost C_i between vertices N + i and j.

Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.

A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

4 3
1 2 2
1 3 4
2 4 5

Sample Output 1

22

The following edges form a minimum spanning tree:

• An edge with cost 2 connecting vertices 1 and 5
• An edge with cost 2 connecting vertices 2 and 5
• An edge with cost 4 connecting vertices 1 and 6
• An edge with cost 4 connecting vertices 3 and 6
• An edge with cost 5 connecting vertices 3 and 7
• An edge with cost 5 connecting vertices 4 and 7

Since 2 + 2 + 4 + 4 + 5 + 5 = 22, print 22.

Sample Input 2

6 2
1 2 10
4 6 10

Sample Output 2

-1

The graph is disconnected.

Sample Input 3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output 3

199651870599998