Problem Statement

You are given the name S of a certain person. The first character of S is an uppercase English letter, and the other characters are lowercase English letters.

The name of this person's handmaid is the string obtained by converting the first letter of S to lowercase and adding Of to the beginning. Find the name of this handmaid.

Constraints

• S is a string of length between 1 and 10, inclusive.
• The first character of S is an uppercase English letter.
• The characters of S other than the first are lowercase English letters.

Sample Input 1

Glen

Sample Output 1

Ofglen

Converting the first letter of Glen to lowercase gives glen, and adding Of to the beginning gives Ofglen.

Sample Input 2

I

Sample Output 2

Ofi

Sample Input 3

Fred

Sample Output 3

Offred

Problem Statement

There are N customers numbered 1 to N, and M canned juices numbered 1 to M.

Customer i (1 \leq i \leq N) has a wish list of length L_i. The j-th item (1 \leq j \leq L_i) from the top of customer i's wish list is canned juice X_{i,j}. For any customer i, the numbers X_{i, 1}, \dots, X_{i, L_i} on customer i's wish list are distinct.

Customers 1, \dots, N, in this order, will now choose their beverages, following the procedure below.

• If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq L_i \leq M (1 \leq i \leq N)
• 1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
• X_{i, 1}, \dots, X_{i, L_i} are distinct. (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
0
5

Among the numbers on customer 1's wish list, the canned juices not yet chosen by anyone are 3, 1, 2. The one appearing earliest in the list is 3, so customer 1 chooses canned juice 3.

Among the numbers on customer 2's wish list, the canned juices not yet chosen by anyone are 2, 1. The one appearing earliest in the list is 2, so customer 2 chooses canned juice 2.

For the numbers on customer 3's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 3 chooses water.

Among the numbers on customer 4's wish list, the canned juices not yet chosen by anyone are 5, 1. The one appearing earliest in the list is 5, so customer 4 chooses canned juice 5.

Sample Input 2

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

Sample Output 2

3
5
1
4
2
0

Problem Statement

AtCoder Restaurant was open for N days after opening.

On day i (1\leq i\leq N) after opening, the following actions were performed.

• In the morning of day i, A_i eggs are purchased.
• At noon on day i, B_i eggs are used. Here, eggs in stock are used in the order they were purchased.
• In the evening of day i, all eggs that have been stocked for D or more days are discarded.

There were no eggs in stock before the morning of day 1, and eggs never ran out at noon on any day.

Find how many eggs remain in the restaurant after the evening action on day N.

T test cases are given; solve each.

Constraints

• 1 \leq T\leq 2\times 10^5
• 1 \leq D \leq N \leq 2\times 10^5
• 1 \leq A_i,B_i \leq 10
• Eggs never run out at noon on any of the N days.
• For each input, the sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
3 1
7 2 3
1 3 2
3 2
7 2 3
1 3 2
2 1
2 1
1 2

Sample Output 1

3
5
0

In the first test case, the following actions are performed.

• Initially, AtCoder Restaurant has no eggs.
• In the morning of day 1, 7 eggs are purchased. The restaurant has 7 eggs stocked on day 1.
• At noon on day 1, 1 egg is used. The restaurant has 6 eggs stocked on day 1 remaining.
• In the evening of day 1, no eggs are discarded. The restaurant has 6 eggs stocked on day 1 remaining.
• In the morning of day 2, 2 eggs are purchased. The restaurant has 6 eggs stocked on day 1 and 2 eggs stocked on day 2.
• At noon on day 2, 3 eggs are used. The restaurant has 3 eggs stocked on day 1 and 2 eggs stocked on day 2 remaining.
• In the evening of day 2, the eggs stocked on day 1 are discarded. The restaurant has 2 eggs stocked on day 2 remaining.
• In the morning of day 3, 3 eggs are purchased. The restaurant has 2 eggs stocked on day 2 and 3 eggs stocked on day 3.
• At noon on day 3, 2 eggs are used. The restaurant has 3 eggs stocked on day 3 remaining.
• In the evening of day 3, no eggs are discarded. (This is because all eggs stocked on day 2 have already been used.) The restaurant has 3 eggs stocked on day 3 remaining.

Thus, 3 eggs remain after the evening action on day 3, so output 3 on the first line.

For the second test case, remember to output the number of eggs after discarding the eggs stocked on day 1 in the evening of day 3.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Find the maximum length of a subsequence B=(B_1,B_2,\ldots,B_{|B|}) of integer sequence A that satisfies the following condition.

• B_i+1=B_{i+1} for all integers i satisfying 1\le i\le |B| - 1.

Constraints

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

Sample Input 1

7
3 4 3 5 7 6 2

Sample Output 1

4

B=(3,4,5,6) is a subsequence of A that satisfies the condition, and its length is 4.

There is no subsequence satisfying the condition with length greater than 4, so output 4.

Sample Input 2

5
5 4 3 2 1

Sample Output 2

1

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

10

Problem Statement

Among integer pairs (x, y) satisfying 0 \leq x,y \leq M-1, how many are there such that the infinite sequence (s_1, s_2, \dots) defined by the following recurrence relation contains no multiples of M?

• s_1 = x
• s_2 = y
• s_n = A s_{n-1} + B s_{n-2} (n \geq 3)

Constraints

• 2 \leq M \leq 1000
• 0 \leq A, B \leq M-1
• All input values are integers.

Sample Input 1

4 1 2

Sample Output 1

7

The integer pairs satisfying the condition in the problem statement are (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3), for a total of seven pairs.

For example, when (x,y) = (2,1), the corresponding sequence is (2,1,5,7,17,31,65,127,\dots). This sequence contains no multiples of 4. Thus, (x,y) = (2,1) satisfies the condition in the problem statement.

On the other hand, when (x,y) = (3,2), the corresponding sequence is (3,2,8,12,28,52,108,212,\dots). The third term of this sequence is 8, which is a multiple of 4. Thus, (x,y) = (3,2) does not satisfy the condition in the problem statement.

Sample Input 2

446 1 1

Sample Output 2

0

No integer pairs satisfy the condition in the problem statement.

Sample Input 3

1000 784 385

Sample Output 3

995373

Problem Statement

You are given a directed graph G with N vertices and M edges.
The vertices of G are numbered as vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq M) goes from vertex U_i to vertex V_i.

Solve the following problem for k=1,2,\ldots,N.

Takahashi's goal is to delete some (possibly zero) vertices from G, along with all edges having those vertices as an endpoint, so that the following condition is satisfied.

• The only vertices reachable from vertex 1 by traversing zero or more edges are vertices 1,2,\ldots,k.

Determine whether he can achieve his goal, and if so, find the minimum number of vertices he needs to delete to achieve it.

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 1\leq U_i,V_i\leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
-1
1
0

• For k=1, the goal can be achieved by deleting vertex 2. Note that vertices 3,4,5 are already unreachable from vertex 1 without deleting them. The goal cannot be achieved without deleting at least one vertex, so output 1 on the first line.
• For k=2, the goal can be achieved by deleting vertices 4 and 5. It is impossible to achieve the goal by deleting one or fewer vertices, so output 2 on the second line.
• For k=3, Takahashi cannot achieve the goal no matter how he deletes vertices. Thus, output -1 on the third line.
• For k=4, the goal can be achieved by deleting vertex 5. The goal cannot be achieved without deleting at least one vertex, so output 1 on the fourth line.
• For k=5, the goal can be achieved without deleting any vertices. Thus, output 0 on the fifth line.

Sample Input 2

5 5
1 1
1 2
3 1
3 1
3 5

Sample Output 2

1
0
-1
-1
-1

G is not necessarily connected. Also, G may have multi-edges or self-loops.

Problem Statement

For a sequence X = (X_1, \dots, X_n) of positive integers, we call X a 221 sequence if and only if the length and value are equal for every (length, value) pair in its run-length encoding. More formally, a sequence satisfying the following condition is called a 221 sequence.

• For any integer pair (l, r) satisfying 1 \leq l \leq r \leq n, if all three of the following conditions hold, then (r-l+1) = X_l.
  • l = 1 or (l \geq 2 and X_{l-1} \neq X_l)
  • r = n or (r \leq n-1 and X_{r+1} \neq X_r)
  • X_l = X_{l+1} = \dots = X_r

For example, (2,2,3,3,3,1,2,2) is a 221 sequence, but (1,1) and (4,4,1,4,4) are not 221 sequences.

You are given a sequence A = (A_1, \dots, A_N) of positive integers of length N. Find the number, modulo 998244353, of non-empty (not necessarily contiguous) subsequences of A that are 221 sequences. Even if two subsequences are extracted from different positions, they are counted as one if they are equal as sequences.

Constraints

• 1 \leq N \leq 500\,000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

8
2 1 2 1 1 2 7 2

Sample Output 1

5

The 221 sequences that appear as non-empty subsequences of A are the following five:

• (1)
• (1,2,2)
• (2,2)
• (2,2,1)
• (2,2,1,2,2)

Sample Input 2

5
2 3 4 5 4

Sample Output 2

0

No 221 sequences appear as non-empty subsequences of A.

Sample Input 3

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

Sample Output 3

15