Problem Statement

The AtCoder railway line has N stations, numbered 1, 2, \ldots, N.

On this line, there are inbound trains that start at station 1 and stop at the stations 2, 3, \ldots, N in order, and outbound trains that start at station N and stop at the stations N - 1, N - 2, \ldots, 1 in order.

Takahashi is about to travel from station X to station Y using only one of the inbound and outbound trains.

Determine whether the train stops at station Z during this travel.

Constraints

• 3 \leq N \leq 100
• 1 \leq X, Y, Z \leq N
• X, Y, and Z are distinct.
• All input values are integers.

Sample Input 1

7 6 1 3

Sample Output 1

Yes

To travel from station 6 to station 1, Takahashi will take an outbound train.

After departing from station 6, the train stops at stations 5, 4, 3, 2, 1 in order, which include station 3, so you should print Yes.

Sample Input 2

10 3 2 9

Sample Output 2

No

Sample Input 3

100 23 67 45

Sample Output 3

Yes

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

• S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
• T is a string obtained by the procedure described in the problem statement.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

• Type a.
• Try to type b but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Type b.
• Try to type c but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Try to type c but mistakenly type y.
• Press the backspace key, but the character is not deleted.
• Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.

Problem Statement

There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.

You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:

• First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.

• For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.

Find the maximum possible height of the head of the topmost giant P_N from the ground.

Constraints

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

Sample Input 1

3
4 10
5 8
2 9

Sample Output 1

18

If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.

The head height of the topmost giant from the ground cannot be greater than 18, so print 18.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

5

Sample Input 3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

Sample Output 3

7362669937

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N).

A length-K sequence of indices (i_1, i_2, \dots, i_K) is called a good index sequence if it satisfies both of the following conditions:

• 1 \leq i_1 < i_2 < \dots < i_K \leq N.
• The subsequence (P_{i_1}, P_{i_2}, \dots, P_{i_K}) can be obtained by rearranging some consecutive K integers.
  Formally, there exists an integer a such that \lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace.

Find the minimum value of i_K - i_1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_i \neq P_j if i \neq j.
• All input values are integers.

Sample Input 1

4 2
2 3 1 4

Sample Output 1

1

The good index sequences are (1,2),(1,3),(2,4). For example, (i_1, i_2) = (1,3) is a good index sequence because 1 \leq i_1 < i_2 \leq N and (P_{i_1}, P_{i_2}) = (2,1) is a rearrangement of two consecutive integers 1, 2.

Among these good index sequences, the smallest value of i_K - i_1 is for (1,2), which is 2-1=1.

Sample Input 2

4 1
2 3 1 4

Sample Output 2

0

i_K - i_1 = i_1 - i_1 = 0 in all good index sequences.

Sample Input 3

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

Sample Output 3

5

Problem Statement

You are given a weighted undirected graph G with N vertices, numbered 1 to N. Initially, G has no edges.

You will perform M operations to add edges to G. The i-th operation (1 \leq i \leq M) is as follows:

• You are given a subset of vertices S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace consisting of K_i vertices. For every pair u, v such that u, v \in S_i and u < v, add an edge between vertices u and v with weight C_i.

After performing all M operations, determine whether G is connected. If it is, find the total weight of the edges in a minimum spanning tree of G.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq K_i \leq N
• \sum_{i=1}^{M} K_i \leq 4 \times 10^5
• 1 \leq A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \leq N
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The left diagram shows G after all M operations, and the right diagram shows a minimum spanning tree of G (the numbers next to the edges indicate their weights).

The total weight of the edges in the minimum spanning tree is 3 + 2 + 4 = 9.

Sample Input 2

3 2
2 1
1 2
2 1
1 2

Sample Output 2

-1

G is not connected even after all M operations.

Sample Input 3

10 5
6 158260522
1 3 6 8 9 10
10 877914575
1 2 3 4 5 6 7 8 9 10
4 602436426
2 6 7 9
6 24979445
2 3 4 5 8 10
4 861648772
2 4 8 9

Sample Output 3

1202115217

Problem Statement

There are N people, numbered 1 to N.

A competition was held among these N people, and they were ranked accordingly. The following information is given about their ranks:

• Each person has a unique rank.
• For each 1 \leq i \leq M, if person A_i is ranked x-th and person B_i is ranked y-th, then x - y = C_i.

The given input guarantees that there is at least one possible ranking that does not contradict the given information.

Answer N queries. The answer to the i-th query is an integer determined as follows:

• If the rank of person i can be uniquely determined, return that rank. Otherwise, return -1.

Constraints

• 2 \leq N \leq 16
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i, B_i \leq N
• 1 \leq C_i \leq N - 1
• (A_i, B_i) \neq (A_j, B_j) (i \neq j)
• There is at least one possible ranking that does not contradict the given information.
• All input values are integers.

Sample Input 1

5 2
2 3 3
5 4 3

Sample Output 1

3 -1 -1 -1 -1

Let X_i be the rank of person i. Then, (X_1, X_2, X_3, X_4, X_5) could be (3, 4, 1, 2, 5) or (3, 5, 2, 1, 4).

Therefore, the answer to the 1-st query is 3, and the answers to the 2-nd, 3-rd, 4-th, and 5-th queries are -1.

Sample Input 2

3 0

Sample Output 2

-1 -1 -1

Sample Input 3

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

Sample Output 3

1 -1 -1 -1 -1 -1 -1 8

Problem Statement

Takahashi has various colors of socks in his chest of drawers. The colors of the socks are represented by integers from 1 to N, and there are A_i\ (\geq 2) socks of color i.

He is about to choose which socks to wear today by performing the following operation:

• Continue to randomly draw one sock at a time from the chest, with equal probability, until he can make a pair of socks of the same color from those he has already drawn. Once a sock is drawn, it will not be returned to the chest.

Find the expected value, modulo 998244353, of the number of times he has to draw a sock from the chest.

Constraints

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

Sample Input 1

2
2 2

Sample Output 1

665496238

For example, the operation could be performed as follows:

1. Draw a sock of color 1 from the chest. There remains one sock of color 1 and two socks of color 2 in the chest.
2. Draw a sock of color 2 from the chest. There remains one sock each of colors 1 and 2 in the chest.
3. Draw a sock of color 1 from the chest. The socks drawn so far are two of color 1 and one of color 2, allowing a pair of color 1 socks to be made, thus ending the operation.

In this example, Takahashi draws a sock from the chest three times.

The expected number of times Takahashi draws a sock from the chest is 3 with probability \frac{2}{3} and 2 with probability \frac{1}{3}, so the expected value is 3\times \frac{2}{3} + 2\times \frac{1}{3} = \frac{8}{3} \equiv 665496238 \pmod {998244353}.

Sample Input 2

1
352

Sample Output 2

2

Sample Input 3

6
1796 905 2768 253 2713 1448

Sample Output 3

887165507