Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.

Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.

Sample Input 3

<>>

Sample Output 3

No

Problem Statement

Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.

Constraints

• -10^{18} \leq X \leq 10^{18}
• X is an integer.

Sample Input 1

27

Sample Output 1

3

The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.

Sample Input 2

-13

Sample Output 2

-1

The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.

Sample Input 3

40

Sample Output 3

4

The smallest integer not less than \frac{40}{10} = 4 is 4 itself.

Sample Input 4

-20

Sample Output 4

-2

Sample Input 5

123456789123456789

Sample Output 5

12345678912345679

Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

• Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

• S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

3

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

• Swapping the 1-st and 2-nd characters of S results in S being bac.
• Swapping the 1-st and 3-rd characters of S results in S being cba.
• Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

1

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.

Problem Statement

There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

• Every cell is covered by exactly one tile.
• It is fine to have unused tiles.
• The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

• 1\leq N\leq 7
• 1 \leq H,W \leq 10
• 1\leq A_i,B_i\leq 10
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

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

Sample Output 4

No

Note that each cell must be covered by exactly one tile.

Problem Statement

There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.

Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.

Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.

Constraints

• 1\leq K<N\leq 2\times 10^5
• K\leq 500
• 1\leq C_i\leq N
• 1\leq V_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

10

After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.

Hence, print 10.

Sample Input 2

3 1
1 10
1 10
1 10

Sample Output 2

-1

No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.

Sample Input 3

3 1
1 1
2 2
3 3

Sample Output 3

5

Note that exactly K balls must be removed.

Problem Statement

There is a simple graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertices u_i and v_i.
Each vertex has one lamp on it. Initially, all the lamps are off.

Determine whether it is possible to turn exactly K lamps on by performing the following operation between 0 and M times, inclusive.

• Choose one edge. Let u and v be the endpoints of the edge. Toggle the states of the lamps on u and v. That is, if the lamp is on, turn it off, and vice versa.

If it is possible to turn exactly K lamps on, print a sequence of operations that achieves this state.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
• 0 \leq K \leq N
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

• Choose edge 3. Turn on the lamps on vertex 2 and vertex 4.
• Choose edge 4. Turn on the lamps on vertex 3 and vertex 5.
• Choose edge 5. Turn on the lamp on vertex 1 and turn off the lamp on vertex 5.

After completing all operations, the lamps on vertices 1, 2, 3, and 4 are on. Therefore, this sequence of operations satisfies the conditions.

Other possible sequences of operations that satisfy the conditions include X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1). (It is allowed to choose the same edge more than once.)

Sample Input 2

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

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes
3
10 9 6

Problem Statement

There is a board game with N+1 squares: square 0, square 1, \dots, square N.
You have a die (dice) that rolls an integer between 1 and K, inclusive, with equal probability for each outcome.
You start on square 0. You repeat the following operation until you reach square N:

• Roll the dice. Let x be the current square and y be the rolled number, then move to square \min(N, x + y).

Let P_i be the probability of reaching square N after exactly i operations. Calculate P_1, P_2, \dots, P_N modulo 998244353.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• N and K are integers.

Sample Input 1

3 2

Sample Output 1

0
249561089
748683265

For example, you reach square N after exactly two operations when the die rolls the following numbers:

• A 1 on the first operation, and a 2 on the second operation.
• A 2 on the first operation, and a 1 on the second operation.
• A 2 on the first operation, and a 2 on the second operation.

Therefore, P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4}. We have 249561089 \times 4 \equiv 3 \pmod{998244353}, so print 249561089 for P_2.

Sample Input 2

5 5

Sample Output 2

598946612
479157290
463185380
682000542
771443236

Sample Input 3

10 6

Sample Output 3

0
166374059
207967574
610038216
177927813
630578223
902091444
412046453
481340945
404612686