Problem Statement

You are given a 3-character string S, where the first character is a digit, the second character is the character x, and the third character is a digit.

Find the product of the two numbers in S.

Constraints

• S is a 3-character string where the first character is an integer between 1 and 9, inclusive, the second character is the character x, and the third character is an integer between 1 and 9, inclusive.

Sample Input 1

3x8

Sample Output 1

24

From 3 \times 8 = 24, print 24.

Sample Input 2

9x9

Sample Output 2

81

From 9 \times 9 = 81, print 81.

Problem Statement

Assuming that the horizon seen from a place x meters above the ground is \sqrt{x(12800000+x)} meters away, find how many meters away the horizon seen from a place H meters above the ground is.

Constraints

• 1 \leq H \leq 10^5
• H is an integer.

Sample Input 1

333

Sample Output 1

65287.907678222

We have \sqrt{333(12800000+333)} = 65287.9076782\ldots. Outputs such as 65287.91 would also be accepted.

Sample Input 2

634

Sample Output 2

90086.635834623

We have \sqrt{634(12800000+634)} = 90086.6358346\ldots.

Problem Statement

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

• The decimal part must not have trailing 0s.
• There must not be an unnecessary trailing decimal point.

Constraints

• 0 \le X < 100
• X is given to the third decimal place.

Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.

Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.

Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.

Sample Input 4

0.000

Sample Output 4

0

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

• How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

• 1 \le M \le N \le 2 \times 10^5
• 1 \le A_1 < A_2 < \dots < A_M = N
• All input values are integers.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

• From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
• From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
• From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

Problem Statement

Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude H at time 0 (the unit is seconds), and will fly for 10^9 seconds from now.

Takahashi can change his flying altitude by up to 1 per second. However, he cannot make his altitude 0 or less.

• In other words, if F(t) denotes Takahashi's altitude at time t, then F(t) satisfies all of the following conditions:
  • F(0) = H
  • -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1 for 0 \leq t \lt u \leq 10^9.
  • F(t) \gt 0 for 0 \leq t \leq 10^9.

There are N goals regarding altitude. The i-th goal is to make the altitude at time t_i at least l_i and at most u_i.
Is it possible for Takahashi to fly in a way that achieves all goals?

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq H \leq 10^9
• 1 \leq t_1 \lt t_2 \lt \dots \lt t_N \leq 10^9
• 1 \leq l_i \leq u_i \leq 10^9
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
2 5
3 1 4
8 9 11
2 6
1 1 4
3 5 8
10 36
27 37 38
30 34 54
38 20 77
45 1 36
49 38 51
52 31 58
65 43 60
71 14 42
73 36 38
85 14 29

Sample Output 1

Yes
No
Yes

For the first test case, Takahashi can achieve all goals by flying as follows:

• At time 0, he is at altitude 5.
• From time 0 to time 2, he descends at a rate of 0.5 per second.
• At time 2, he is at altitude 5 - 0.5 \times 2 = 4.
• From time 2 to time 3, he stays at the same altitude.
• At time 3, he is at altitude 4. He satisfies the first goal.
• From time 3 to time 8, he ascends at a rate of 1 per second.
• At time 8, he is at altitude 4 + 1 \times 5 = 9. He satisfies the second goal.

For the second test case, he cannot achieve all goals no matter how he flies.

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has N towns, numbered 1,2,\dots,N. Town i is at (x_i, y_i), and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers (a,b), and casting a spell (a, b) at coordinates (x, y) teleports you to (x+a, y+b).

Snuke is a great magician who can learn the spell (a, b) for any pair of integers (a, b) of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns (i, j).

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town i to Town j.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• 2 \leq N \leq 500
• 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town i to Town j by using one of the spells once for every pair (i,j) (i \neq j), achieving his objective.

• (2, 4)
• (-2, -4)
• (4, -2)
• (-4, 2)
• (-6, -2)
• (6, 2)

Another option is to learn the six spells below. In this case, he can get from Town i to Town j by using one of the spells twice for every pair (i,j) (i \neq j), achieving his objective.

• (1, 2)
• (-1, -2)
• (2, -1)
• (-2, 1)
• (-3, -1)
• (3, 1)

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print 6.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

• (1, 0)
• (-1, 0)

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

• Stay at the same square and increase his money by P_{i,j}.
• Pay R_{i,j} from his money and move to square (i,j+1).
• Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

• 2 \leq N \leq 80
• 1 \leq P_{i,j} \leq 10^9
• 1 \leq R_{i,j},D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

It is possible to reach square (3,3) in eight actions as follows:

• Stay at square (1,1) and increase money by 1. His money is now 1.
• Pay 1 money and move to square (2,1). His money is now 0.
• Stay at square (2,1) and increase money by 3. His money is now 3.
• Stay at square (2,1) and increase money by 3. His money is now 6.
• Stay at square (2,1) and increase money by 3. His money is now 9.
• Pay 4 money and move to square (2,2). His money is now 5.
• Pay 3 money and move to square (3,2). His money is now 2.
• Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004