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

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

• 2\leq N\leq 100
• 0\leq A_i<B_i\leq 100
• 0\leq C_i<D_i\leq 100
• All input values are integers.

Sample Input 1

3
0 5 1 3
1 4 0 5
2 5 2 4

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.

Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.

Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

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

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

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

Sample Input 1

4
1 5 4
7 8
6

Sample Output 1

13

If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.

It can be shown that this is the maximum achievable value.

Sample Input 2

3
1 2
3

Sample Output 2

3

N can be odd.

Sample Input 3

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

Sample Output 3

75

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\ldots,A_N). Find the number of triples of positive integers (i,j,k) that satisfy all of the following conditions:

• 1\leq i < j < k\leq N,
• A_i = A_k,
• A_i \neq A_j.

Constraints

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

Sample Input 1

5
1 2 1 3 2

Sample Output 1

3

The following three triples of positive integers (i,j,k) satisfy the conditions:

• (i,j,k)=(1,2,3)
• (i,j,k)=(2,3,5)
• (i,j,k)=(2,4,5)

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

0

There may be no triples of positive integers (i,j,k) that satisfy the conditions.

Sample Input 3

13
9 7 11 7 3 8 1 13 11 11 11 6 13

Sample Output 3

20

Problem Statement

There is an octopus-shaped robot and N treasures on a number line. The i-th treasure (1\leq i\leq N) is located at coordinate X_i.
The robot has one head and N legs, and the i-th leg (1\leq i\leq N) has a length of L_i.

Find the number of integers k such that the robot can grab all N treasures as follows.

• Place the head at coordinate k.
• Repeat the following for i=1,2,\ldots,N in this order: if there is a treasure that has not been grabbed yet within a distance of L_i from the head, that is, at a coordinate x satisfying k-L_i\leq x\leq k+L_i, choose one such treasure and grab it.

Constraints

• 1 \leq N\leq 200
• -10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
• 1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
• All input values are integers.

Sample Input 1

3
-6 0 7
3 5 10

Sample Output 1

6

k=-3,-2,-1,2,3,4 satisfy the condition. For example, when k=-3, the robot can grab all three treasures as follows.

• The first leg can grab treasures at coordinates x satisfying -6\leq x\leq 0. Among them, grab the first treasure at coordinate -6.
• The second leg can grab treasures at coordinates x satisfying -8\leq x\leq 2. Among them, grab the second treasure at coordinate 0.
• The third leg can grab treasures at coordinates x satisfying -13\leq x\leq 7. Among them, grab the third treasure at coordinate 7.

Sample Input 2

1
0
1000000000000000000

Sample Output 2

2000000000000000001

All integers k from -10^{18} to 10^{18} satisfy the condition.

Sample Input 3

2
-100 100
1 1

Sample Output 3

0

No k satisfies the conditions.

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertex 1, vertex 2, \ldots, vertex N, and edge 1, edge 2, \ldots, edge M, respectively, and edge i (1\leq i\leq M) connects vertices U_i and V_i.

You are also given distinct vertices A,B,C on G. Determine if there is a simple path connecting vertices A and C via vertex B.

Constraints

• 3 \leq N \leq 2\times 10^5
• N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right)
• 1\leq A,B,C\leq N
• A, B, and C are all distinct.
• 1\leq U_i<V_i\leq N
• The pairs (U_i,V_i) are all distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

One simple path connecting vertices 1 and 2 via vertex 3 is 1 \to 5 \to 4 \to 3 \to 2.

Thus, print Yes.

Sample Input 2

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

Sample Output 2

No

No simple path satisfies the condition. Thus, print No.

Sample Input 3

3 2
1 3 2
1 2
2 3

Sample Output 3

No

Problem Statement

Snuke has come up with the following problem.

You are given permutations P=(P_1,P_2,\ldots,P_N) and Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N). Let us build a graph with N vertices and N edges as follows.

• For i=1,2,\ldots,N in this order, draw an edge of weight Q_i connecting vertices i and P_i bidirectionally.

When removing some number of edges to eliminate cycles from the graph, find the minimum possible total weight of the removed edges.

Alice and Bob came up with the following solutions.

Alice: Initialize the answer to 0. For i=1,2,\ldots,N in this order, if the edge connecting vertices i and P_i is contained in a cycle, remove that edge and add its weight to the answer.

Bob: Initialize the answer to 0. For i=N,N-1,\ldots,1 in this order, if the edge connecting vertices i and P_i is contained in a cycle, remove that edge and add its weight to the answer.

Snuke has realized that their solutions are both incorrect, and he wants to know the number of inputs for which neither of their solutions gives the correct answer.

Among the (N!)^2 possible inputs, find the number, modulo 998244353, of inputs for which neither Alice's nor Bob's solution gives the correct answer.

Constraints

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

Sample Input 1

3

Sample Output 1

4

The following four inputs satisfy the condition.

• P=(2,3,1),Q=(2,1,3)
• P=(2,3,1),Q=(3,1,2)
• P=(3,1,2),Q=(2,1,3)
• P=(3,1,2),Q=(3,1,2)

For example, for the input P=(2,3,1),Q=(2,1,3), the correct answer is 1, but Alice's solution gives 2 and Bob's gives 3.

Sample Input 2

2

Sample Output 2

0

There may be no inputs that satisfy the condition.

Sample Input 3

6

Sample Output 3

314708

Sample Input 4

318

Sample Output 4

321484323