Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

• X-, if 0 \leq Y \leq 2;
• X, if 3 \leq Y \leq 6;
• X+, if 7 \leq Y \leq 9.

Constraints

• 1 \leq X \leq 15
• 0 \leq Y \leq 9
• X and Y are integers.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

12

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

• Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
• S_1 \neq S_2
• T_1 \neq T_2

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

• A and B are integers.
• 1 \le A,B \le 10^{18}

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

Problem Statement

N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.

Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i, B_i\leq 10^9
• A_i+B_i \geq 1
• All input values are integers.

Sample Input 1

3
1 3
3 1
2 2

Sample Output 1

2 3 1

Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.

Sort them in descending order of their success rates to obtain the order in Sample Output.

Sample Input 2

2
1 3
2 6

Sample Output 2

1 2

Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.

Sample Input 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

Sample Output 3

3 1 4 2

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

• X is greater than or equal to N.
• There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

• N is an integer.
• 0 \le N \le 10^{18}

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.

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

Given are M digits C_i.

Find the sum, modulo 998244353, of all integers between 1 and N (inclusive) that contain all of C_1, \ldots, C_M when written in base 10 without unnecessary leading zeros.

Constraints

• 1 \leq N < 10^{10^4}
• 1 \leq M \leq 10
• 0 \leq C_1 < \ldots < C_M \leq 9
• All values in input are integers.

Sample Input 1

104
2
0 1

Sample Output 1

520

Between 1 and 104, there are six integers that contain both 0 and 1 when written in base 10: 10,100,101,102,103,104.
The sum of them is 520.

Sample Input 2

999
4
1 2 3 4

Sample Output 2

0

Between 1 and 999, no integer contains all of 1, 2, 3, 4.

Sample Input 3

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

Sample Output 3

397365274

Be sure to find the sum modulo 998244353.