Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

• -1000 \leq a,b \leq 1000
• 1 \leq d \leq 360
• All values in input are integers.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

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

You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.

Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.

Constraints

• 1 \leq N \leq 3000
• -10^9 \leq x_i, y_i \leq 10^9
• 1 \leq r_i \leq 10^9
• (s_x, s_y) lies on the circumference of at least one of the N circles.
• (t_x, t_y) lies on the circumference of at least one of the N circles.
• All values in input are integers.

Sample Input 1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

Sample Output 1

Yes

Here is one way to get from (0, -2) to (3, 3).

• From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
• From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
• From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).

Thus, Yes should be printed.

Sample Input 2

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

Sample Output 2

No

It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.

Problem Statement

There are N integers a_1,\ldots,a_N written on a whiteboard.
Here, a_i can be represented as a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} using m_i prime numbers p_{i,1} \lt \ldots \lt p_{i,m_i} and positive integers e_{i,1},\ldots,e_{i,m_i}.
You will choose one of the N integers to replace it with 1.
Find the number of values that can be the least common multiple of the N integers after the replacement.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq m_i
• \sum{m_i} \leq 2 \times 10^5
• 2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9
• p_{i,j} is prime.
• 1 \leq e_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

4
1
7 2
2
2 2
5 1
1
5 1
2
2 1
7 1

Sample Output 1

3

The integers on the whiteboard are a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14.
If you replace a_1 with 1, the integers on the whiteboard become 1,20,5,14, whose least common multiple is 140.
If you replace a_2 with 1, the integers on the whiteboard become 49,1,5,14, whose least common multiple is 490.
If you replace a_3 with 1, the integers on the whiteboard become 49,20,1,14, whose least common multiple is 980.
If you replace a_4 with 1, the integers on the whiteboard become 49,20,5,1, whose least common multiple is 980.
Therefore, the least common multiple of the N integers after the replacement can be 140, 490, or 980, so the answer is 3.

Sample Input 2

1
1
998244353 1000000000

Sample Output 2

1

There may be enormous integers on the whiteboard.

Problem Statement

You are given a tree with N vertices. For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i and has a weight w_i.

Consider choosing some of the N-1 edges (possibly none or all). Here, for each i = 1, 2, \ldots, N, one may choose at most d_i edges incident to Vertex i. Find the maximum possible total weight of the chosen edges.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq u_i, v_i \leq N
• -10^9 \leq w_i \leq 10^9
• d_i is a non-negative integer not exceeding the degree of Vertex i.
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

7
1 2 1 0 2 1 1
1 2 8
2 3 9
2 4 10
2 5 -3
5 6 8
5 7 3

Sample Output 1

28

If you choose the 1-st, 2-nd, 5-th, and 6-th edges, the total weight of those edges is 8 + 9 + 8 + 3 = 28. This is the maximum possible.

Sample Input 2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

Sample Output 2

2184

Problem Statement

There are H \times W cards on a grid of squares with H rows and W columns. For each pair of integers (i, j) such that 1 \leq i \leq H, 1 \leq j \leq W, the card at the i-th row and j-th column has an integer A_{i, j} written on it.

Takahashi and Aoki will cooperate to play a game, which consists of the following steps.

• First, Takahashi chooses some of the H rows (possibly none or all) and places a red token on each card in the chosen rows.
• Second, Aoki chooses some of the W columns (possibly none or all) and places a blue token on each card in the chosen columns.
• Now, they compute their score as follows.
  • If there is a card with a negative integer that has both red and blue tokens placed on it, the play is a "total failure"; the score is -10^{100}.
  • Otherwise, they collect all cards that have one or more tokens placed on them. The score is the sum of the integers written on the collected cards.

Find their maximum possible score.

Constraints

• 1 \leq H, W \leq 100
• -10^9 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
-9 5 1
6 -2 4

Sample Output 1

9

If Takahashi chooses just the 2-nd row and Aoki chooses just the 3-rd column, they collect four cards, for a score of 6 + (-2) + 1 + 4 = 9. This is the maximum possible.

Sample Input 2

15 20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16
14 31 43 -73 49 -7 -65 13 -40 -45 36 88 -54 -43 99 87 -94 57 -22 31
-85 67 -46 23 95 68 55 17 -56 51 -38 64 32 -19 65 -62 76 66 -53 -16
35 -78 -41 35 -51 -85 24 -22 45 -53 82 -30 39 19 -52 -3 -11 -67 -33 71
-75 45 -80 -42 -31 94 59 -58 39 -26 -94 -60 98 -1 21 25 0 -86 37 4
-41 66 -53 -55 55 98 23 33 -3 -27 7 -53 -64 68 -33 -8 -99 -15 50 40
66 53 -65 5 -49 81 45 1 33 19 0 20 -46 -82 14 -15 -13 -65 68 -65
50 -66 63 -71 84 51 -91 45 100 76 -7 -55 45 -72 18 40 -42 73 69 -36
59 -65 -30 89 -10 43 7 72 93 -70 23 86 81 16 25 -63 73 16 34 -62
22 -88 27 -69 82 -54 -92 32 -72 -95 28 -25 28 -55 97 87 91 17 21 -95
62 39 -65 -16 -84 51 62 -44 -60 -70 8 69 -7 74 79 -12 62 -86 6 -60
-72 -6 -79 -28 39 -42 -80 -17 -95 -28 -66 66 36 86 -68 91 -23 70 58 2
-19 -20 77 0 65 -94 -30 76 55 57 -8 59 -43 -6 -15 -83 8 29 16 34
79 40 86 -92 88 -70 -94 -21 50 -3 -42 -35 -79 91 96 -87 -93 -6 46 27
-94 -49 71 37 91 47 97 1 21 32 -100 -4 -78 -47 -36 -84 -61 86 -51 -9

Sample Output 2

1743

Problem Statement

We have a grid of squares with N rows arranged vertically and N columns arranged horizontally. The square at the i-th row from the top and j-th column from the left has an integer label a_{i,j}.
Consider paths obtained by starting on one of the squares and going right or down to an adjacent square zero or more times. Find the number, modulo 998244353, of such paths that start and end on squares with the same label.
Two paths are distinguished when they visit different sets of squares (including the starting and ending squares).

Constraints

• 1 \leq N \leq 400
• 1 \leq a_{i,j} \leq N^2
• All values in input are integers.

Sample Input 1

2
1 3
3 1

Sample Output 1

6

The following six paths satisfy the requirements. ((i, j) denotes the square at the i-th row from the top and j-th column from the left. Each path is represented as a sequence of squares it visits.)

• (1,1)
• (1,1) → (1,2) → (2,2)
• (1,1) → (2,1) → (2,2)
• (1,2)
• (2,1)
• (2,2)