Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

• 1 \leq a, b, c \leq 100
• All values in input are integers.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

• 2 \leq H, W \leq 100
• H and W are integers.
• S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
• There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

4

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

Find the sum of integers between 1 and N (inclusive) that are not multiples of A or B.

Constraints

• 1 \leq N, A,B \leq 10^9
• All values in input are integers.

Sample Input 1

10 3 5

Sample Output 1

22

The integers between 1 and 10 (inclusive) that are not multiples of 3 or 5 are 1,2,4,7, and 8, whose sum is 1+2+4+7+8 =22.

Sample Input 2

1000000000 314 159

Sample Output 2

495273003954006262

Problem Statement

How many integer sequences A=(A_1,\ldots,A_N) of length N satisfy all the conditions below?

• 1\le A_i \le M (1 \le i \le N)

• |A_i - A_{i+1}| \geq K (1 \le i \le N - 1)

Since the count can be enormous, find it modulo 998244353.

Constraints

• 2 \leq N \leq 1000
• 1 \leq M \leq 5000
• 0 \leq K \leq M-1
• All values in input are integers.

Sample Input 1

2 3 1

Sample Output 1

6

The following 6 sequences satisfy the conditions.

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

Sample Input 2

3 3 2

Sample Output 2

2

The following 2 sequences satisfy the conditions.

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

Sample Input 3

100 1000 500

Sample Output 3

657064711

Print the count modulo 998244353.

Problem Statement

We have an N \times M matrix, whose elements are initially all 0.

Process Q given queries. Each query is in one of the following formats.

• 1 l r x : Add x to every element in the l-th, (l+1)-th, \ldots, and r-th column.
• 2 i x: Replace every element in the i-th row with x.
• 3 i j: Print the (i, j)-th element.

Constraints

• 1 \leq N, M, Q \leq 2 \times 10^5
• Every query is in one of the formats listed in the Problem Statement.
• For each query in the format 1 l r x, 1 \leq l \leq r \leq M and 1 \leq x \leq 10^9.
• For each query in the format 2 i x, 1 \leq i \leq N and 1 \leq x \leq 10^9.
• For each query in the format 3 i j, 1 \leq i \leq N and 1 \leq j \leq M.
• At least one query in the format 3 i j is given.
• All values in input are integers.

Sample Input 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

Sample Output 1

1
2
2
5
3
4

The matrix transitions as follows.

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

Sample Input 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

Sample Output 2

9000000000

Sample Input 3

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

Sample Output 3

6
5
5
13
10
0

Problem Statement

For an integer N greater than or equal to 2, there are \frac{N(N - 1)}{2} pairs of integers (x, y) such that 1 \leq x \lt y \leq N.

Consider the sequence of these pairs sorted in the increasing lexicographical order. Let (x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1}) be its L-th, (L+1)-th, \ldots, and R-th elements, respectively. On a sequence A = (1, \dots, N), We will perform the following operation for i = 1, \dots, R-L+1 in this order:

• Swap A_{x_i} and A_{y_i}.

Find the final A after all the operations.

We say that (a, b) is smaller than (c, d) in the lexicographical order if and only if one of the following holds:

• a \lt c
• a = c and b \lt d

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq L \leq R \leq \frac{N(N-1)}{2}
• All values in input are integers.

Sample Input 1

5 3 6

Sample Output 1

5 1 2 3 4

Consider the sequence of pairs of integers such that 1 \leq x \lt y \leq N sorted in the increasing lexicographical order. Its 3-rd, 4-th, 5-th, and 6-th elements are (1, 4), (1, 5), (2, 3), (2, 4), respectively.

Corresponding to these pairs, A transitions as follows.

(1, 2, 3, 4, 5) \rightarrow (4, 2, 3, 1, 5) \rightarrow (5, 2, 3, 1, 4) \rightarrow (5, 3, 2, 1, 4) \rightarrow (5, 1, 2, 3, 4)

Sample Input 2

10 12 36

Sample Output 2

1 10 9 8 7 4 3 2 5 6

Problem Statement

We have a graph G with N vertices numbered 1 through N and 0 edges. You are given sequences u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M) of length M.

You will perform the following operation (N-1) times.

• Choose i (1 \leq i \leq M) uniformly at random. Add to G an undirected edge connecting Vertices u_i and v_i.

Note that the operation above will add a new edge connecting Vertices u_i and v_i even if G already has one or more edges between them. In other words, the resulting G may contain multiple edges.

For each K=1,2,\ldots,N-1, find the probability, modulo 998244353, that G is a forest after the K-th operation.

Constraints

• 2 \leq N \leq 14
• N-1 \leq M \leq 500
• 1 \leq u_i,v_i \leq N
• u_i\neq v_i
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1
499122177

Let us denote by (u, v) the edge connecting Vertices u and v.

After the 1-st operation, G will have:

• Edge (1, 2) with a probability of 1/2;
• Edge (2, 3) with a probability of 1/2.

In both cases, G is a forest, so the answer for K=1 is 1.

After the 2-nd operation, G will have:

• Edges (1, 2) and (1, 2) with a probability of 1/4;
• Edges (2, 3) and (2, 3) with a probability of 1/4;
• Edges (1, 2) and (2, 3) with a probability of 1/2.

G is a forest only when G has Edges (1, 2) and (2, 3). Therefore, the sought probability is 1/2; when represented modulo 998244353, it is 499122177, which should be printed.

Sample Input 2

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

Sample Output 2

1
758665709
918384805