Problem Statement

You are given two positive integers A and B.

Output the square of A + B.

Constraints

• 1 \leq A,B \leq 2025
• All input values are integers.

Sample Input 1

20 25

Sample Output 1

2025

(20+25)^2=2025.

Sample Input 2

30 25

Sample Output 2

3025

Sample Input 3

45 11

Sample Output 3

3136

Sample Input 4

2025 1111

Sample Output 4

9834496

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

• 1 \le N \le 100
• 1 \le D \le 10^9
• 1 \le T_i \le 10^9(1 \le i \le N)
• T_i < T_{i+1}(1 \le i \le N-1)
• All values in the input are integers.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

1300

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

600

If multiple double clicks were fired, be sure to print only the first such event.

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

• choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

• Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
• S and T have the same length.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

Currently, AtCoder High School has K classes and N students, and the i-th (1\le i\le N) student belongs to the A _ i-th class.

Takahashi is transferring to AtCoder High School in September. At that time, he can choose any one class among the K classes and belong to that class.

He will be sad if there is a class with more students belonging to it than the class he belongs to. Otherwise, he will be happy.

Find how many classes make him happy if he belongs to them.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le K\le N
• 1\le A _ i\le K\ (1\le i\le N)
• All input values are integers.

Sample Input 1

8 5
3 3 5 5 4 4 3 2

Sample Output 1

3

For example, if Takahashi chooses the fifth class and belongs to it, the number of students belonging to the fifth class becomes 3. Then, he will be happy since there is no class with more than three students belonging to it.

On the other hand, for example, if he chooses the first class and belongs to it, the number of students belonging to the first class becomes 1. Then, he will be sad since three students belong to the third class.

He will be happy if and only if he chooses the third, fourth, or fifth class, so output 3.

Sample Input 2

6 1
1 1 1 1 1 1

Sample Output 2

1

It is possible that AtCoder High School has only one class.

Sample Input 3

14 8
6 1 5 3 8 4 3 4 3 5 1 2 5 1

Sample Output 3

4

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

Snuke is observing a snake and is curious about which parts are the head, body, and tail. He divided the snake into N blocks and evaluated the head-likeness, body-likeness, and tail-likeness of each block. Then, he decided to find the division that maximizes the sum of the likeness values.

You are given length-N integer sequences 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).

Find the maximum possible value of \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i for a pair of integers (x, y) satisfying 1 \leq x < y < N.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i, B_i, C_i \leq 10^6
• All input values are integers.

Sample Input 1

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

Sample Output 1

16

With (x, y) = (2, 3), we have \displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i = 1 + 4 + 4 + 4 + 3 = 16.

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Sample Output 2

3

Sample Input 3

6
2 10 7 7 7 11
5 7 9 10 9 12
6 6 7 10 12 7

Sample Output 3

50

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\ldots,A_N). Find the number of triples of positive integers (i,j,k) that satisfy all of the following conditions:

• 1\leq i < j < k\leq N,
• A_i = A_k,
• A_i \neq A_j.

Constraints

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

Sample Input 1

5
1 2 1 3 2

Sample Output 1

3

The following three triples of positive integers (i,j,k) satisfy the conditions:

• (i,j,k)=(1,2,3)
• (i,j,k)=(2,3,5)
• (i,j,k)=(2,4,5)

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

0

There may be no triples of positive integers (i,j,k) that satisfy the conditions.

Sample Input 3

13
9 7 11 7 3 8 1 13 11 11 11 6 13

Sample Output 3

20

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.