Problem Statement

You are given a string S consisting of lowercase English letters and digits.

Extract only the digit characters from S and output the string formed by arranging them in their original order.

Constraints

• S is a string of length between 1 and 50, inclusive, consisting of lowercase English letters and digits.

Sample Input 1

abc462

Sample Output 1

462

The digits contained in abc462 are 4, 6, 2. Concatenating them in their original order gives 462. Thus, output 462.

Sample Input 2

codequeen

Sample Output 2

codequeen contains no digits, so output the empty string.

Sample Input 3

31415

Sample Output 3

31415

Sample Input 4

10plus2is12

Sample Output 4

10212

Problem Statement

N people, numbered 1 through N, exchanged gifts with each other.

Person i sent gifts to K_i people: persons A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

For each i = 1, 2, \ldots, N, find all people who sent a gift to person i.

Constraints

• 2\le N\le 100
• 1\le K_i\le N-1
• 1\le A_{i,1} < A_{i,2} < \cdots < A_{i,K_i}\le N
• A_{i,j} \neq i
• All input values are integers.

Sample Input 1

4
1 2
1 3
1 2
3 1 2 3

Sample Output 1

1 4
3 1 3 4
2 2 4
0

Person 1 sent a gift to person 2, person 2 sent a gift to person 3, person 3 sent a gift to person 2, and person 4 sent gifts to persons 1, 2, 3.

Person 1 received a gift from person 4. Thus, output 1 4 on the first line.

Person 2 received gifts from persons 1, 3, 4. Thus, output 3 1 3 4 on the second line.

Person 3 received gifts from persons 2, 4. Thus, output 2 2 4 on the third line.

Person 4 did not receive any gifts. Thus, output 0 on the fourth line.

Sample Input 2

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

Sample Output 2

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

Sample Input 3

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

Sample Output 3

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

Problem Statement

There are N points numbered 1 through N on a two-dimensional plane. Point i (1\le i\le N) has coordinates (X_i,Y_i). Here, it is guaranteed that X and Y are each permutations of (1,2,\ldots,N).

Find the number of values of i such that the interior (not including the boundary) of the rectangle with sides parallel to the x-axis and y-axis, with lower-left vertex (0,0) and upper-right vertex (X_i,Y_i), contains none of the N points numbered 1 through N.

Constraints

• 1\le N\le 3\times 10^5
• 1\le X_i,Y_i\le N
• X and Y are each permutations of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

3
2 1
1 3
3 2

Sample Output 1

2

The two values i=1,2 satisfy the condition.

For i=3, the interior (not including the boundary) of the rectangle with sides parallel to the x-axis, with lower-left vertex (0,0) and upper-right vertex (3,2), contains point 1.

Sample Input 2

5
1 1
4 2
2 3
5 5
3 4

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2

Problem Statement

A murder occurred at a certain mansion. There are N suspects, called person 1, person 2, \dots, person N.

Person i entered the mansion at time S_i, left the mansion at time T_i, and did not enter or leave at any other times.

The following facts are known about the crime:

• There are exactly two culprits.
• The crime started at some integer time x, took D units of time, and was completed at time x + D.
• Both culprits were in the mansion at all times from the start to the completion of the crime. (They may have entered the mansion exactly when the crime started, or left exactly when it was completed.)

Assuming that both culprits are among the N suspects, how many combinations of the two culprits and the crime start time are possible? Here, the order of the two culprits does not matter.

Constraints

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

Sample Input 1

3 2
9 17
10 12
13 20

Sample Output 1

4

In this sample, there are three suspects, and the crime took two units of time.

• If persons 1 and 2 are the culprits, they were both in the mansion from time 10 to time 12. If the crime start time is time 10, the crime can be committed in two units of time.
• If persons 1 and 3 are the culprits, they were both in the mansion from time 13 to time 17. If the crime start time is 13, 14, or 15, the crime can be committed in two units of time.
• If persons 2 and 3 are the culprits, they were never in the mansion at the same time, so this pair cannot have committed the crime.

Thus, the possible combinations of the two culprits and the crime start time are (persons 1, 2, time 10), (persons 1, 3, time 13), (persons 1, 3, time 14), (persons 1, 3, time 15), giving four combinations.

Sample Input 2

3 5
9 17
10 12
13 20

Sample Output 2

0

The suspects are the same as in Sample Input 1, but this time the crime took five units of time.

No matter which two persons are the culprits, the time they were both in the mansion is shorter than the time required for the crime, so the crime is impossible.

Thus, the number of possible combinations of the two culprits and the crime start time is zero. (In other words, our assumption is wrong, and the real culprit has escaped us.)

Sample Input 3

4 1
1 1000000
1 1000000
1 1000000
1 1000000

Sample Output 3

5999994

Beware of overflow for larger cases.

Problem Statement

You are given integers A,B,X,Y.

A piece is placed on a two-dimensional plane. Initially, the piece is at coordinate (0,0).

You can perform the following operation zero or more times:

• Let the current coordinate of the piece be (x,y). Move the piece to one of the coordinates (x-1,y),(x+1,y),(x,y-1),(x,y+1).

The cost of the k-th operation (k \geq 1) depends on the parity of k, as follows:

• If k is odd: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is A, and the cost of moving to (x,y-1) or (x,y+1) is B.
• If k is even: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is B, and the cost of moving to (x,y-1) or (x,y+1) is A.

Find the minimum total cost required to move the piece to coordinate (X,Y).

T test cases are given; solve each one.

Constraints

• 1\le T\le 2\times 10^5
• 1\le A,B\le 10^9
• -10^9\le X,Y\le 10^9
• All input values are integers.

Sample Input 1

5
1 2 -1 2
8 5 0 0
7 13 9 4
1 1 0 100
31 9 -74 -60

Sample Output 1

4
0
103
100
1332

Consider the first test case.

The following moves cost 4 in total:

• Move the piece from (0,0) to (-1,0). This costs 1.
• Move the piece from (-1,0) to (-1,1). This costs 1.
• Move the piece from (-1,1) to (-1,2). This costs 2.

It is impossible to move the piece to (-1,2) with a total cost less than 4, so output 4 on the first line.

Problem Statement

You are given a string S consisting of uppercase English letters.
Takahashi's goal is to increase the number of occurrences of ABC as a substring of S by exactly K, by replacing some characters of S.

Determine whether this is possible, and if so, find the minimum number of characters Takahashi needs to replace to achieve his goal.

T test cases are given; solve each one.

Constraints

• 1\leq T\leq 10^5
• S is a string of length between 3 and 3\times 10^5, inclusive, consisting of uppercase English letters.
• 1\leq K \leq 10
• In each input, the total length of S over all test cases is at most 3\times 10^5.
• T and K are integers.

Sample Input 1

5
ATCABC
1
ABABC
1
XABCYZ
1
ZZZZZ
1
ABCBABCAEFCABAABC
2

Sample Output 1

1
-1
6
3
3

In the first test case, the given string S=ATCABC contains ABC as a substring once.
Replacing the second character of S with B gives S=ABCABC, which contains ABC as a substring twice.
Thus, replacing one character increases the number of occurrences of ABC as a substring by 1, achieving the goal. Therefore, output 1 on the first line.

In the second test case, the given string S=ABABC contains ABC as a substring once; no matter how the characters of S are replaced, it is impossible to make S contain ABC as a substring twice.
Therefore, output -1 on the second line.

In the third test case, the given string S=XABCYZ contains ABC as a substring once.
To make S contain ABC as a substring twice, all characters of S must be replaced, giving S=ABCABC.
Therefore, output 6 on the third line.

Problem Statement

There is a box containing N balls numbered 1 through N. Each ball is painted with a color represented as an integer, and ball i is painted with color C_i.

Takahashi performed N operations. The k-th operation (1\le k\le N) is as follows:

• Draw one ball uniformly at random from the box and discard it. If the drawn ball has color G_k, gain 1 point.

Find the probability, modulo 998244353, that the total score over N operations is 0 points.

Constraints

• 1\le N\le 2\times 10^5
• 1\le C_i,G_k\le N
• All input values are integers.

Sample Input 1

3
1 2 3
1 1 2

Sample Output 1

332748118

For example, the operations may proceed as follows:

• First operation: A ball with color 2 is drawn from the box.
• Second operation: A ball with color 1 is drawn from the box. Gain 1 point.
• Third operation: A ball with color 3 is drawn from the box.

In this case, the total score is 1 point.

The probability that Takahashi's total score is 0 is \displaystyle \frac13.

Sample Input 2

3
1 1 3
3 3 3

Sample Output 2

0

Takahashi's total score is always 1 point.

Sample Input 3

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

Sample Output 3

316110712