Problem Statement

Takahashi is wearing armor.

This armor blocks all attacks with power (strength represented as an integer) of D or less, but does not block attacks with power greater than D.

Does this armor block an attack with power A?

Constraints

• 1 \leq A \leq 100
• 1 \leq D \leq 100
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In this sample, A = 4 and D = 5. Since A = 4 is at most D = 5, the armor blocks the attack, so the answer is Yes.

Sample Input 2

5 5

Sample Output 2

Yes

In this sample, A = 5 and D = 5. Since A = 5 is at most D = 5, the armor blocks the attack, so the answer is Yes.

Sample Input 3

6 5

Sample Output 3

No

In this sample, A = 6 and D = 5. Since A = 6 is not at most D = 5, the armor does not block the attack, so the answer is No.

Problem Statement

N woodcutters 1, 2, \dots, N each have one axe. All of them dropped their axes into a pond.
N axes 1, 2, \dots, N were found sunk in the pond.
Each woodcutter i claims that "I owned axe A_i."
On the other hand, the goddess of this pond knows that the woodcutter who owned axe i is woodcutter B_i.

Determine whether all N woodcutters are telling the truth.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq N
• 1 \leq B_i \leq N
• A_i \neq A_j\;(i \neq j)
• B_i \neq B_j\;(i \neq j)
• All input values are integers.

Sample Input 1

3
3 1 2
2 3 1

Sample Output 1

Yes

All N woodcutters are telling the truth.

Sample Input 2

4
1 2 3 4
1 3 2 4

Sample Output 2

No

Woodcutters 2 and 3 are lying.

Sample Input 3

5
2 4 5 1 3
4 1 5 2 3

Sample Output 3

Yes

Problem Statement

There are N gems. The color (represented as an integer) of the i-th gem is C_i and its value is V_i.

Choose K gems from these N gems. Here, the chosen gems must have at least M distinct colors.

Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)

Constraints

• 1 \leq M \leq K \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq N
• 1 \leq V_i \leq 10^9
• There exist gems of at least M distinct colors.
• All input values are integers.

Sample Input 1

5 3 2
1 30
1 40
1 50
2 10
3 20

Sample Output 1

110

In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.

Choosing gems 2, 3, 5 gives colors 1, 1, 3, which are two distinct colors. Their total value is 40 + 50 + 20 = 110, and this is the maximum possible value.

Sample Input 2

5 3 3
1 30
1 40
1 50
2 10
3 20

Sample Output 2

80

The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.

Choosing gems 3, 4, 5 gives colors 1, 2, 3, which are three distinct colors. Their total value is 50 + 10 + 20 = 80, and this is the maximum possible value.

Sample Input 3

5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000

Sample Output 3

5000000000

Beware of overflow.

Problem Statement

There is an H \times W grid, and each cell contains an integer 0 or 1.
The information of the integer written in each cell is given as H strings S_1, S_2, \dots, S_H of length W. If the j-th character of S_i is 0, then 0 is written in the cell at the i-th row from the top and the j-th column from the left of the grid; if the j-th character of S_i is 1, then 1 is written in that cell.

Find the number of rectangular regions where the sum of the written integers equals K.
More formally, find the number of quadruples of integers (r_1, c_1, r_2, c_2) satisfying all of the following conditions:

• 1 \le r_1 \le r_2 \le H
• 1 \le c_1 \le c_2 \le W
• The sum of the integers written in the cell at the i-th row from the top and the j-th column from the left, over all pairs of integers (i, j) satisfying r_1 \le i \le r_2, c_1 \le j \le c_2, equals K.

Constraints

• H and W are integers between 1 and 500, inclusive.
• K is an integer between 0 and HW, inclusive.
• S_i is a string of length W consisting of 0 and 1.

Sample Input 1

3 4 3
1001
1101
0110

Sample Output 1

8

There are eight rectangular regions where the sum of the written integers equals K:

• The rectangular region extracted from row 1 to row 2 from the top and column 1 to column 2 from the left
• The rectangular region extracted from row 1 to row 2 from the top and column 1 to column 3 from the left
• The rectangular region extracted from row 1 to row 2 from the top and column 2 to column 4 from the left
• The rectangular region extracted from row 1 to row 3 from the top and column 2 to column 3 from the left
• The rectangular region extracted from row 1 to row 3 from the top and column 3 to column 4 from the left
• The rectangular region extracted from row 2 to row 2 from the top and column 1 to column 4 from the left
• The rectangular region extracted from row 2 to row 3 from the top and column 1 to column 2 from the left
• The rectangular region extracted from row 2 to row 3 from the top and column 2 to column 3 from the left

Sample Input 2

5 4 20
0101
1010
0101
1010
0101

Sample Output 2

0

Sample Input 3

15 20 17
10111101101100000100
01100000000010000011
01110010111000111000
11001100000111011000
10100001100011100010
01101000101010000101
10110001111110000100
10110011101100101101
01010001110011001001
01010110010001100110
01110100011110011110
01100000100111010010
11001101100111101100
10111100010101111011
00101101011100010000

Sample Output 3

448

Problem Statement

There is an N \times N grid. Initially, all cells are painted white.

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

• Type 1: An integer R is given. Paint all cells in the R-th row from the top of the grid black.
• Type 2: An integer C is given. Paint all cells in the C-th column from the left of the grid white.

After processing each query, output the number of black cells in the grid at that point.

Constraints

• 1 \leq N, Q \leq 3 \times 10^5
• For type 1 queries, 1 \leq R \leq N.
• For type 2 queries, 1 \leq C \leq N.
• All input values are integers.

Sample Input 1

3 4
1 1
1 3
2 2
1 1

Sample Output 1

3
6
4
5

The changes in the grid are shown using characters. . represents a white cell, and # represents a black cell.

...    ###    ###    #.#    ###
... -> ... -> ... -> ... -> ...
...    ...    ###    #.#    #.#

Sample Input 2

300000 1
2 300000

Sample Output 2

0

Beware of overflow in larger cases.

Problem Statement

You are given a positive integer N.
We call a non-empty sequence of positive integers A a good sequence if it satisfies all of the following conditions:

• All elements of A are distinct.
• The product of all elements of A equals N.

The score of a sequence is defined as the sum of all elements of the sequence.
Find the sum, modulo 998244353, of the scores of all good sequences.

Constraints

• 1 \leq N \leq 10^{10}
• The input value is an integer.

Sample Input 1

8

Sample Output 1

80

There are 11 good sequences: (1,2,4),(1,4,2),(1,8),(2,1,4),(2,4),(2,4,1),(4,1,2),(4,2),(4,2,1),(8),(8,1).
The sum of their scores is 7+7+9+7+6+7+7+6+7+8+9=80.

Sample Input 2

461

Sample Output 2

1385

Sample Input 3

100

Sample Output 3

1702

Problem Statement

There is a simple undirected graph with N vertices and M edges.
The vertices are numbered 1 through N and the edges are numbered 1 through M; edge i connects vertices u_i and v_i.
Assign a non-negative integer weight W_j not greater than 2026 to each vertex j so that the following condition is satisfied:

• W_{u_i}+W_{v_i} \leq 2026 for each edge i.

Find the maximum possible value of the sum of all vertex weights (that is, \sum_{j=1}^{N}{W_j}).

Constraints

• 1 \leq N \leq 5 \times 10^4
• 0 \leq M \leq 5 \times 10^4
• 1 \leq u_i \lt v_i \leq N
• (u_1,v_1),(u_2,v_2),\dots,(u_M,v_M) are pairwise distinct.
• All input values are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

4052

By assigning weights 2026, 0, 2026 to vertices 1, 2, 3, respectively, the sum of all vertex weights becomes 4052, and it is impossible to make it larger, so the answer is 4052.

Sample Input 2

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

Sample Output 2

4052

Sample Input 3

2 1
1 2

Sample Output 3

2026