Problem Statement

You are given a string S consisting of lowercase English letters and |. S is guaranteed to contain exactly two |s.

Remove the characters between the two |s, including the |s themselves, and print the resulting string.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and |.
• S contains exactly two |s.

Sample Input 1

atcoder|beginner|contest

Sample Output 1

atcodercontest

Remove all the characters between the two |s and print the result.

Sample Input 2

|spoiler|

Sample Output 2

It is possible that all characters are removed.

Sample Input 3

||xyz

Sample Output 3

xyz

Problem Statement

There are N choices.

You will choose one of these choices. If you choose the i-th choice, your happiness will be X_i.

If your happiness will be negative no matter which choice you choose, output Yes; otherwise, output No.

Constraints

• 2 \leq N \leq 10
• -100 \leq X_i \leq 100
• All input values are integers.

Sample Input 1

4
2 0 -1 2

Sample Output 1

No

If you choose choice 1, 2, or 4, the happiness will not be negative.

Sample Input 2

3
-5 -2 -1

Sample Output 2

Yes

Sample Input 3

4
0 -2 0 -1

Sample Output 3

No

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:

For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.

Constraints

• 1 \leq N \leq 50
• 1 \leq A_i \leq 1000
• All input values are integers.

Sample Input 1

5
8 6 10 5 7

Sample Output 1

6

We have A=(8,6,10,5,7).

For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.

The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

Problem Statement

You are given a positive integer N. Print a string of length (N+1), s_0s_1\ldots s_N, defined as follows.

For each i = 0, 1, 2, \ldots, N,

• if there is a divisor j of N that is between 1 and 9, inclusive, and i is a multiple of N/j, then s_i is the digit corresponding to the smallest such j (s_i will thus be one of 1, 2, ..., 9);
• if no such j exists, then s_i is -.

Constraints

• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

12

Sample Output 1

1-643-2-346-1

We will explain how to determine s_i for some i.

• For i = 0, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 1, 2, 3, 4, 6. The smallest of these is 1, so s_0 = 1.

• For i = 4, the divisors j of N between 1 and 9 such that i is a multiple of N/j are 3, 6. The smallest of these is 3, so s_4 = 3.

• For i = 11, there are no divisors j of N between 1 and 9 such that i is a multiple of N/j, so s_{11} = -.

Sample Input 2

7

Sample Output 2

17777771

Sample Input 3

1

Sample Output 3

11

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

4

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

9

Problem Statement

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

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

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

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

There is a game with N players 1,2,\dots,N.
This game is played in a format where two players face each other one-on-one.
A tournament among the N players was held M times, and the two players A_m and B_m advanced to the final of the m-th tournament.
Find the number of pairs of integers x and y satisfying the following conditions.

• 1 \leq x \lt y \leq N
• In every tournament, at least one of players x and y advanced to the final.

Constraints

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

Sample Input 1

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

Sample Output 1

1

The conditions are satisfied when (x,y)=(2,3), and not satisfied otherwise.
For example, in the fourth tournament, neither player 1 nor player 4 advanced to the final, so (x,y)=(1,4) does not satisfy the conditions.

Sample Input 2

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

Sample Output 2

2

There are two pairs (x,y) satisfying the conditions: (1,2) and (1,4).

Sample Input 3

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

Sample Output 3

2

Problem Statement

There are N six-sided dice. The dice are numbered from 1 to N, and the numbers written on the faces of die i are A_{i,1},A_{i,2},\dots,A_{i,6}.

Now, all N dice will be rolled simultaneously. Find the expected value, modulo 998244353, of the maximum value among the numbers written on the face that comes up on each die.

For any die, the face that comes up when the die is rolled is chosen independently and uniformly at random.

Constraints

• 1\leq N \leq 10^5
• 1\leq A_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

332748121

Let x_i be the number written on the face that comes up on die i.

• Case x_1=1,x_2=1: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 1.
• Case x_1=1,x_2=3: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 3.
• Case x_1=4,x_2=1: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.
• Case x_1=4,x_2=3: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.

Thus, the expected value to be found is \frac{1}{6}\times 1 + \frac{1}{6}\times 3 + \frac{1}{3}\times 4 + \frac{1}{3}\times 4 = \frac{10}{3} \equiv 332748121 \pmod{998244353}.

Sample Input 2

2
1 1 1 1 1 1
2 2 2 2 2 2

Sample Output 2

2

The numbers written on the faces that come up on dice 1,2 are always 1,2, respectively, and their maximum value is always 2.

Sample Input 3

8
55 76 80 21 34 28
82 84 2 32 56 17
11 57 37 28 39 18
47 2 97 25 75 29
72 45 22 75 26 81
6 79 16 68 68 40
31 80 68 57 18 55
49 10 63 91 93 40

Sample Output 3

213725517

Problem Statement

There are N cards numbered 1,\ldots,N. Card i has P_i written on the front and Q_i written on the back.
Here, P=(P_1,\ldots,P_N) and Q=(Q_1,\ldots,Q_N) are permutations of (1, 2, \dots, N).

How many ways are there to choose some of the N cards such that the following condition is satisfied? Find the count modulo 998244353.

Condition: every number 1,2,\ldots,N is written on at least one of the chosen cards.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i,Q_i \leq N
• P and Q are permutations of (1, 2, \dots, N).
• All values in input are integers.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

3

For example, if you choose Cards 1 and 3, then 1 is written on the front of Card 1, 2 on the back of Card 1, and 3 on the front of Card 3, so this combination satisfies the condition.

There are 3 ways to choose cards satisfying the condition: \{1,3\},\{2,3\},\{1,2,3\}.

Sample Input 2

5
2 3 5 4 1
4 2 1 3 5

Sample Output 2

12

Sample Input 3

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

Sample Output 3

1