Problem Statement

In AtCoder Kingdom, there are N horse races being held.
Horses aged A_i or younger can participate in the i-th race.
Among the N races, how many races can a K-year-old horse participate in?

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 100
• 1 \le K \le 100

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

2

• Horses aged 3 or younger can participate in the 1st race.
• Horses aged 1 or younger can participate in the 2nd race.
• Horses aged 4 or younger can participate in the 3rd race.
• Horses aged 1 or younger can participate in the 4th race.
• Horses aged 5 or younger can participate in the 5th race.

Among the 5 races, a 4-year-old horse can participate in the 3rd and 5th races, which is 2 races.

Sample Input 2

1
1
100

Sample Output 2

0

There may be no races that a K-year-old horse can participate in.

Sample Input 3

15
18 89 31 2 15 93 64 78 58 19 79 59 24 50 30
38

Sample Output 3

8

Problem Statement

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M \leq P \leq 2\times 10^5
• All input values are integers.

Sample Input 1

13 3 5

Sample Output 1

3

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

0

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

628

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

Constraints

• S consists of lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

Problem Statement

In the xy-plane, there are three points A(x_A, y_A), B(x_B, y_B), and C(x_C, y_C) that are not collinear. Determine whether the triangle ABC is a right triangle.

Constraints

• -1000 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 1000
• The three points A, B, and C are not collinear.
• All input values are integers.

Sample Input 1

0 0
4 0
0 3

Sample Output 1

Yes

The triangle ABC is a right triangle.

Sample Input 2

-4 3
2 1
3 4

Sample Output 2

Yes

The triangle ABC is a right triangle.

Sample Input 3

2 4
-3 2
1 -2

Sample Output 3

No

The triangle ABC is not a right triangle.

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

• The i-th element is between 1 and R_i, inclusive.
• The sum of all elements is a multiple of K.

Constraints

• All input values are integers.
• 1 \le N \le 8
• 2 \le K \le 10
• 1 \le R_i \le 5

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

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

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

Problem Statement

You have an integer 1 and a die that shows integers between 1 and 6 (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than N:

• Cast a die. If it shows x, multiply your integer by x.

Find the probability, modulo 998244353, that your integer ends up being N.

Constraints

• 2 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

6

Sample Output 1

239578645

One of the possible procedures is as follows.

• Initially, your integer is 1.
• You cast a die, and it shows 2. Your integer becomes 1 \times 2 = 2.
• You cast a die, and it shows 4. Your integer becomes 2 \times 4 = 8.
• Now your integer is not less than 6, so you terminate the procedure.

Your integer ends up being 8, which is not equal to N = 6.

The probability that your integer ends up being 6 is \frac{7}{25}. Since 239578645 \times 25 \equiv 7 \pmod{998244353}, print 239578645.

Sample Input 2

7

Sample Output 2

0

No matter what the die shows, your integer never ends up being 7.

Sample Input 3

300

Sample Output 3

183676961

Sample Input 4

979552051200000000

Sample Output 4

812376310

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:

• Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
• Repeat the following operation until all integers on the blackboard are erased:
  • Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
• Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.

Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

Constraints

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

Sample Input 1

4
1 3 1 4

Sample Output 1

16

For example, in the case of (L,R)=(1,4):

• The blackboard has 1,3,1,4.
• Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
• Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
• It cannot be done in fewer than two operations, so f(1,4) = 2.

Similarly, you can find f(2,4)=2, f(1,1)=1, etc.

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.

Sample Input 2

5
3 1 4 2 4

Sample Output 2

23

Sample Input 3

10
5 1 10 9 2 5 6 9 1 6

Sample Output 3

129