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

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

• the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

• 1 \leq A,B,C,D,E\leq 13
• Not all of A, B, C, D, and E are the same.
• All values in input are integers.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

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

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

• Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

• S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

3

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

• Swapping the 1-st and 2-nd characters of S results in S being bac.
• Swapping the 1-st and 3-rd characters of S results in S being cba.
• Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

1

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

There is a directed graph with N vertices and M edges. The vertices are numbered from 1 to N, and the i-th edge is a directed edge from vertex U_i to vertex V_i. Here, the out-degree of each vertex is at least 1.

Also, each vertex has a character written on it, and the character written on vertex i is S_i. Here, S_i refers to the i-th character of S.

Alice and Bob play the following game on this graph using one piece:

• Initially, the piece is placed on vertex 1, and they alternately perform the following operation K times each, with Alice going first and Bob going second.

  • Let u be the vertex where the piece is currently placed. Choose a vertex v such that there is an edge from vertex u to vertex v, and move the piece to vertex v.

• Let v be the vertex where the piece is finally placed. If S_v = A, Alice wins; if S_v = B, Bob wins.

Find the winner of the game when both players play optimally.

In each input, you are given T test cases. Solve each of them.

Constraints

• 1 \leq T
• 2 \leq N, M \leq 2 \times 10^5
• 1 \leq K \leq 10
• S is a string of length N consisting of A and B.
• 1 \leq U_i, V_i \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j .
• The out-degree of each vertex is at least 1.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.
• The sum of M over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
4 6 2
AABB
1 2
2 3
3 1
3 3
3 4
4 2
4 6 2
ABAB
1 2
2 3
3 1
3 3
3 4
4 2
5 8 3
ABABB
1 2
2 2
2 3
3 1
3 4
4 4
4 5
5 3

Sample Output 1

Alice
Bob
Bob

We will explain an example of how the game proceeds in the first test case. Here, both players do not necessarily play optimally.

• Initially, the piece is placed on vertex 1.
• Alice moves the piece to vertex 2.
• Bob moves the piece to vertex 3.
• Alice moves the piece to vertex 3.
• Bob moves the piece to vertex 1.

At this point, S_1 = A, so Alice wins.

Problem Statement

There are N points on a two-dimensional plane, with the i-th point at coordinates (X_i, Y_i). It is guaranteed that no two points are at the same position, and no three points are collinear.

Among the combinations of four points from these points, how many combinations can form a trapezoid as a polygon with those four points as vertices?

Constraints

• 4 \leq N \leq 2\,000
• 0 \leq X_i, Y_i \leq 10^7 (1 \leq i \leq N)
• No two points are at the same location.
• No three points are collinear.
• All input values are integers.

Sample Input 1

5
0 2
0 5
1 0
2 1
2 4

Sample Output 1

3

The given points are arranged as shown in the figure below.

Among the combinations of four points, the following three combinations can form a trapezoid as a polygon with those points as vertices:

• The 1st, 5th, 4th, 3rd points.
• The 1st, 3rd, 4th, 2nd points.
• The 1st, 2nd, 5th, 4th points.

Note that parallelograms and rectangles are also treated as trapezoids.

Sample Input 2

8
0 1
1 3
2 3
3 1
0 2
1 0
2 0
3 2

Sample Output 2

22

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1,2,\ldots ,N, and the i-th edge is an undirected edge connecting Vertices u_i and v_i.

For each integer i\,(1 \leq i \leq N), find \sum_{j=1}^{N}dis(i,j).

Here, dis(i,j) denotes the minimum number of edges that must be traversed to go from Vertex i to Vertex j.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
2
3

We have:

dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3,

dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2,

dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3.

Sample Input 2

2
1 2

Sample Output 2

1
1

Sample Input 3

6
1 6
1 5
1 3
1 4
1 2

Sample Output 3

5
9
9
9
9
9