Problem Statement

We have the following 3 \times 3 board with integers from 1 through 9 written on it.

You are given two integers A and B between 1 and 9, where A < B.

Determine if the two squares with A and B written on them are adjacent horizontally.

Constraints

• 1 \le A < B \le 9
• A and B are integers.

Sample Input 1

7 8

Sample Output 1

Yes

The two squares with 7 and 8 written on them are adjacent horizontally, so print Yes.

Sample Input 2

1 9

Sample Output 2

No

Sample Input 3

3 4

Sample Output 3

No

Problem Statement

You are given a positive integer N.

Output N lines. The i-th line (1\le i\le N) should contain Fizz if i is a multiple of 3, and i if i is not a multiple of 3.

Constraints

• N is an integer between 1 and 100, inclusive.

Sample Input 1

4

Sample Output 1

1
2
Fizz
4

The first line should contain 1 since 1 is not a multiple of 3.

The second line should contain 2 since 2 is not a multiple of 3.

The third line should contain Fizz since 3 is a multiple of 3.

The fourth line should contain 4 since 4 is not a multiple of 3.

Sample Input 2

10

Sample Output 2

1
2
Fizz
4
5
Fizz
7
8
Fizz
10

Problem Statement

There is an exam structured as follows.

• The exam consists of N rounds called round 1 to N.
• In each round, you are given an integer score between 0 and 100, inclusive.
• Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
  • Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.

Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.

Constraints

• All input values are integers.
• 3 \le N \le 100
• 0 \le X \le 100 \times (N-2)
• 0 \le A_i \le 100

Sample Input 1

5 180
40 60 80 50

Sample Output 1

70

Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.

Sample Input 2

3 100
100 100

Sample Output 2

0

Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.

Sample Input 3

5 200
0 0 99 99

Sample Output 3

-1

Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.

Sample Input 4

10 480
59 98 88 54 70 24 8 94 46

Sample Output 4

45

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X \leq N
• 1 \leq A_i \leq N
• A_i \neq i
• All values in input are integers.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

3

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

• One day, Takahashi let Friend 2 learn the secret.
• Friend 2 shares it with Friend 1.
• Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

7

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

You can perform the following operation zero or more times in any order:

• Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)

Here, |A| represents the length of the integer sequence A.

Find the minimum possible value of the final |A| after repeating the operation.

Constraints

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

Sample Input 1

10
1 1 1 4 4 4 4 1 2 3

Sample Output 1

2

You can make |A|=2 with two operations as follows:

• Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
• Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.

It is impossible to make |A| less than 2, so output 2.

Sample Input 2

3
2 1 3

Sample Output 2

3

You cannot perform any operation from the beginning.

Sample Input 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

Sample Output 3

5

Problem Statement

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

Among the non-empty substrings s of S, count those that do not contain T as a (not necessarily contiguous) subsequence.

Here, two substrings of S are distinguished if they are taken from different positions, even if they are equal as strings.

Constraints

• S is a string consisting of lowercase English letters.
• 1\le |S|\le2\times10 ^ 5, where |S| is the length of S.
• T is a string consisting of lowercase English letters.
• 1\le |T|\le50, where |T| is the length of T.

Sample Input 1

abrakadabra
aba

Sample Output 1

51

For example, the substring abr consisting of the first through third characters of S does not contain T as a subsequence. Including this, there are 51 substrings satisfying the condition, such as k (only the fifth character of S) and akada (the fourth through eighth characters of S).

Note that the string abr can be obtained both as the substring from the first to third characters of S and as the substring from the eighth to tenth characters of S, but they are taken from different positions, so they are counted separately.

Sample Input 2

aaaaa
a

Sample Output 2

0

All non-empty substrings of S contain T as a subsequence.

Thus, there are no substrings satisfying the condition, so output 0.

Sample Input 3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

Sample Output 3

263

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

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

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

Problem Statement

You are given three integer sequences of length N, namely A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N), and C=(C_1,C_2,\ldots,C_N), and an integer K.

For each of the N^3 choices of integers i,j,k (1\leq i,j,k\leq N), compute the value A_iB_j + B_jC_k + C_kA_i. Among all these values, find the K-th largest value.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq \min(N^3,5\times 10^5)
• 1\leq A_i,B_i,C_i \leq 10^9
• All input values are integers.

Sample Input 1

2 5
1 2
3 4
5 6

Sample Output 1

31

The N^3=8 values are computed as follows:

• For (i,j,k)=(1,1,1): A_1B_1+B_1C_1+C_1A_1=1\times 3+3\times 5+5\times 1=23
• For (i,j,k)=(1,1,2): A_1B_1+B_1C_2+C_2A_1=1\times 3+3\times 6+6\times 1=27
• For (i,j,k)=(1,2,1): A_1B_2+B_2C_1+C_1A_1=1\times 4+4\times 5+5\times 1=29
• For (i,j,k)=(1,2,2): A_1B_2+B_2C_2+C_2A_1=1\times 4+4\times 6+6\times 1=34
• For (i,j,k)=(2,1,1): A_2B_1+B_1C_1+C_1A_2=2\times 3+3\times 5+5\times 2=31
• For (i,j,k)=(2,1,2): A_2B_1+B_1C_2+C_2A_2=2\times 3+3\times 6+6\times 2=36
• For (i,j,k)=(2,2,1): A_2B_2+B_2C_1+C_1A_2=2\times 4+4\times 5+5\times 2=38
• For (i,j,k)=(2,2,2): A_2B_2+B_2C_2+C_2A_2=2\times 4+4\times 6+6\times 2=44

Sorting these values in descending order, we have (44,38,36,34,31,29,27,23), so the 5th largest value is 31.

Sample Input 2

3 10
100 100 100
100 100 100
100 100 100

Sample Output 2

30000

Sample Input 3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

Sample Output 3

689589940713840351