Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

• S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.

Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.

Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.

Problem Statement

You are given a 3-digit positive integer N. Determine whether all digits are the same when N is represented in decimal.

Constraints

• 100 \leq N \leq 999
• The input value is an integer.

Sample Input 1

444

Sample Output 1

Yes

The digits of 444 are 4,4,4, which are the same, so output Yes.

Sample Input 2

160

Sample Output 2

No

The digits of 160 are 1,6,0, which are not the same, so output No.

Sample Input 3

999

Sample Output 3

Yes

Problem Statement

You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).

The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.

Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:

• S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).

Constraints

• 1 \leq M \leq N \leq 50
• N and M are integers.
• Each of S_{i,j} and T_{i,j} is . or #.
• There is exactly one pair (a,b) satisfying the condition.

Sample Input 1

3 2
#.#
..#
##.
.#
#.

Sample Output 1

2 2

The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.

Sample Input 2

2 1
#.
##
.

Sample Output 2

1 2

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq x_j \leq 10^9
• All values in input are integers.

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

5 5
1 2 3 4 5
6
5
4
3
2

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• -10^9 \leq B_i, W_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

19

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

15

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

0

It is possible to choose no balls.

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

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

The following operation will be performed K times:

• For i=1,2,\ldots,N, simultaneously update P_i to P_{P_i}.

Print P after all operations.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq K\leq10^{18}
• 1\leq P_i\leq N\ (1\leq i\leq N)
• P_i\neq P_j\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

6 3
5 6 3 1 2 4

Sample Output 1

6 1 3 2 4 5

With each operation, P changes as follows:

• After the first operation, P is (2,4,3,5,6,1).
• After the second operation, P is (4,5,3,6,1,2).
• After the third operation, P is (6,1,3,2,4,5).

Thus, print 6 1 3 2 4 5.

Sample Input 2

5 1000000000000000000
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Since P_i=i, P does not change no matter how many operations are performed.

Sample Input 3

29 51912426
7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16

Sample Output 3

18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20

Problem Statement

Find the maximum side length of a regular triangle that can be drawn within a rectangle whose side lengths are A and B.

Constraints

• 1 \leq A,B \leq 1000
• A and B are integers.

Sample Input 1

1 1

Sample Output 1

1.03527618041008295791

The following figure shows an optimal drawing, with the side length of \sqrt{6} - \sqrt{2}.

Note that the sample output does not strictly match \sqrt{6}- \sqrt{2}, but the error is within 10^{-9}, so it is considered correct.