Problem Statement

You are given an integer K. Print the string obtained by repeating the string ACL K times and concatenating them.

For example, if K = 3, print ACLACLACL.

Constraints

• 1 \leq K \leq 5
• All values in input are integers.

Sample Input 1

3

Sample Output 1

ACLACLACL

Problem Statement

Snuke likes integers that are greater than or equal to A, and less than or equal to B. Takahashi likes integers that are greater than or equal to C, and less than or equal to D.

Does there exist an integer liked by both people?

Constraints

• 0 \leq A \leq B \leq 10^{18}
• 0 \leq C \leq D \leq 10^{18}
• All values in input are integers.

Sample Input 1

10 30 20 40

Sample Output 1

Yes

For example, both like 25.

Sample Input 2

10 20 30 40

Sample Output 2

No

Problem Statement

There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M. Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

• Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.

After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

• 2 \leq N \leq 100,000
• 1 \leq M \leq 100,000
• 1 \leq A_i < B_i \leq N
• No two roads connect the same pair of cities.
• All values in input are integers.

Sample Input 1

3 1
1 2

Sample Output 1

1

Initially, there are three cities, and there is a road between City 1 and City 2.

Snuke can achieve the goal by building one new road, for example, between City 1 and City 3. After that,

• We can travel between 1 and 2 directly.
• We can travel between 1 and 3 directly.
• We can travel between 2 and 3 by following both roads (2 - 1 - 3).

Problem Statement

You are given a sequence A_1, A_2, ..., A_N and an integer K.

Print the maximum possible length of a sequence B that satisfies the following conditions:

• B is a (not necessarily continuous) subsequence of A.
• For each pair of adjacents elements of B, the absolute difference of the elements is at most K.

Constraints

• 1 \leq N \leq 300,000
• 0 \leq A_i \leq 300,000
• 0 \leq K \leq 300,000
• All values in input are integers.

Sample Input 1

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

Sample Output 1

7

For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.

• It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).
• All of the absolute differences between two adjacent elements (|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) are at most K = 3.

Problem Statement

You have a string S of length N. Initially, all characters in S are 1s.

You will perform queries Q times. In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit). Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

• 1 \leq N, Q \leq 200,000
• 1 \leq L_i \leq R_i \leq N
• 1 \leq D_i \leq 9
• All values in input are integers.

Sample Input 1

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.

Problem Statement

There are 2N people numbered 1 through 2N. The height of Person i is h_i.

How many ways are there to make N pairs of people such that the following conditions are satisfied? Compute the answer modulo 998,244,353.

• Each person is contained in exactly one pair.
• For each pair, the heights of the two people in the pair are different.

Two ways are considered different if for some p and q, Person p and Person q are paired in one way and not in the other.

Constraints

• 1 \leq N \leq 50,000
• 1 \leq h_i \leq 100,000
• All values in input are integers.

Sample Input 1

2
1
1
2
3

Sample Output 1

2

There are two ways:

• Form the pair (Person 1, Person 3) and the pair (Person 2, Person 4).
• Form the pair (Person 1, Person 4) and the pair (Person 2, Person 3).

Sample Input 2

5
30
10
20
40
20
10
10
30
50
60

Sample Output 2

516