Problem Statement

Given positive integers N and M, find the remainder when \lfloor \frac{10^N}{M} \rfloor is divided by M.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq M \leq 10000

Sample Input 1

1 2

Sample Output 1

1

We have \lfloor \frac{10^1}{2} \rfloor = 5, so we should print the remainder when 5 is divided by 2, that is, 1.

Sample Input 2

2 7

Sample Output 2

0

Sample Input 3

1000000000000000000 9997

Sample Output 3

9015

Problem Statement

We have N cards numbered 1 to N. Each side of each card has a color represented by a positive integer.

One side of Card i has a color a_i, and the other side has a color b_i.

For each card, you can choose which side shows up. Find the maximum possible number of different colors showing up.

Constraints

• 1 \leq N \leq 200000
• 1 \leq a_i,b_i \leq 400000
• All numbers in input are integers.

Sample Input 1

4
1 2
1 3
4 2
2 3

Sample Output 1

4

We can choose the sides with 1, 3, 4, 2 to have four colors.

Sample Input 2

2
111 111
111 111

Sample Output 2

1

They are painted with just one color.

Sample Input 3

12
5 2
5 6
1 2
9 7
2 7
5 5
4 2
6 7
2 2
7 8
9 7
1 8

Sample Output 3

8

Problem Statement

There are N people numbered 1 to N and N pieces of baggage numbered numbered 1 to N. Person i has a weight of a_i, and Baggage j has a weight of b_j. Initially, Person i has Baggage p_i. We want to do the operation below zero or more times so that each Person i will have Baggage i.

• Choose i,j (i \neq j), and swap the baggages of Person i and Person j.

However, when a person has a piece of baggage with a weight greater than or equal to his/her own weight, the person gets tired and becomes unable to take part in a future operation (that is, we cannot choose him/her as Person i or j). Particularly, if a_i \leq b_{p_i}, Person i cannot take part in any operation.

Determine whether there is a sequence of operations that achieves the objective, and if so, construct one such sequence with the minimum possible number of operations.

Constraints

• 1 \leq N \leq 200000
• 1 \leq a_i,b_i \leq 10^9
• p is a permutation of 1, \ldots, N.
• All numbers in input are integers.

Sample Input 1

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

Sample Output 1

3
3 4
1 3
4 2

Initially, People 1, 2, 3, 4 has pieces of baggage with weights 1, 3, 3, 5, respectively, so no one is tired.

First, we do the operation choosing Person 3 and 4. Now, people 1, 2, 3, 4 has pieces of baggage with weights 1, 3, 5, 3, so no one is tired yet.

Second, we do the operation choosing Person 1 and 3. Now, people 1, 2, 3, 4 has pieces of baggage with weights 5, 3, 1, 3, so Person 1 gets tired.

Lastly, we do the operation choosing Person 4 and 2. Now, people 1, 2, 3, 4 has pieces of baggage with weights 5, 3, 1, 3, so no one gets tired.

This sequence of operations has made everyone have the right piece of baggage, with the minimum possible number of operations, so it is valid.

Sample Input 2

4
1 2 3 4
4 3 2 1
4 3 2 1

Sample Output 2

-1

No sequence of operations achieves the objective.

Sample Input 3

1
58
998244353
1

Sample Output 3

0

The objective is already achieved in the initial state.

Problem Statement

Given is a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \cdots, N, and the i-th edge connects Vertices a_i and b_i. Also given is a sequence of positive integers: c_1, c_2, \cdots, c_N.

Convert this graph into a directed graph that satisfies the condition below, that is, for each i, delete the undirected edge (a_i, b_i) and add one of the two direted edges a_i \to b_i and b_i \to a_i.

• For every i = 1, 2, \cdots, N, there are exactly c_i vertices reachable from Vertex i (by traversing some number of directed edges), including Vertex i itself.

In this problem, it is guaranteed that the given input always has a solution.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq a_i, b_i \leq N
• The given graph has no self-loops and no multi-edges.
• 1 \leq c_i \leq N
• There always exists a valid solution.

Sample Input 1

3 3
1 2
2 3
3 1
3 3 3

Sample Output 1

->
->
->

In a cycle of length 3, you can reach every vertex from any vertex.

Sample Input 2

3 2
1 2
2 3
1 2 3

Sample Output 2

<-
<-

Sample Input 3

6 3
1 2
4 3
5 6
1 2 1 2 2 1

Sample Output 3

<-
->
->

The graph may be disconnected.

Problem Statement

In this problem, you will be given T test cases for each input.

Given integers A, B, C, and D, find the number of positive integers i satisfying the following condition:

• None of the integers between A + B \times i and A + C \times i (inclusive) is a multiple of D.

We can prove from the constraints that the count is finite.

Constraints

• 1 \leq T \leq 10{,}000
• 1 \leq A < D
• 0 \leq B < C < D
• 2 \leq D \leq 10^8

Sample Input 1

2
3 1 2 5
99 101 103 105

Sample Output 1

1
25

The pairs (A + B \times i, A + C \times i) for the first case are listed below. We can see that only i = 3 satisfies the condition.

• i = 1: (4, 5)
• i = 2: (5, 7)
• i = 3: (6, 9)
• i = 4: (7, 11)
• i = 5: (8, 13)
• :

Problem Statement

Yosupo loves query problems. He made the following problem:

A Query Problem

We have an integer sequence of length N: a_1,\ldots,a_N. Initially, a_i = 0 (1 \leq i \leq N). We also have a variable ans, which is initially 0. Here, you will be given Q queries of the following forms:

• Type 1:

  • t_i (=1) l_i r_i v_i

  • For each j = l_i,\ldots,r_i, a_j := \min(a_j,v_i).

• Type 2:

  • t_i (=2) l_i r_i v_i

  • For each j = l_i,\ldots,r_i, a_j := \max(a_j,v_i).

• Type 3:

  • t_i (=3) l_i r_i

  • Compute a_{l_i} + \ldots + a_{r_i} and add the result to ans.

Print the final value of ans.

Here, for each query, 1 \leq l_i \leq r_i \leq N holds. Additionally, for Type 1 and 2, 0 \leq v_i \leq M-1 holds.

Maroon saw this problem, thought it was too easy, and came up with the following problem:

Query Problems

Given are positive integers N,M,Q. There are ( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q valid inputs for "A Query Problem". Find the sum of outputs over all those inputs, modulo 998{,}244{,}353.

Find it.

Constraints

• 1 \leq N,M,Q \leq 200000
• All numbers in input are integers.

Sample Input 1

1 2 2

Sample Output 1

1

There are 25 valid inputs, and just one of them - shown below - results in a positive value of ans.

t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1

ans will be 1 in this case, so the answer is 1.

Sample Input 2

3 1 4

Sample Output 2

0

Sample Input 3

111 112 113

Sample Output 3

451848306