Problem Statement

A mayoral election is being held in AtCoder City. The candidates are Takahashi and Aoki.

There are N valid votes cast for either of the two candidates, and the counting is currently underway. Here, N is an odd number.

The current vote count is T votes for Takahashi and A votes for Aoki.

Determine if the outcome of the election is already decided at this point.

Constraints

• 1 \leq N \leq 99
• N is an odd number.
• 0 \leq T, A \leq N
• T + A \leq N
• All input values are integers.

Sample Input 1

7 4 2

Sample Output 1

Yes

Even if the remaining one vote goes to Aoki, Takahashi will still win. That is, his victory is decided, so print Yes.

Sample Input 2

99 12 48

Sample Output 2

No

Although Aoki currently has more votes, Takahashi would win if he receives the remaining 39 votes. Therefore, print No.

Sample Input 3

1 0 0

Sample Output 3

No

Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

• 1\leq N \leq 100
• 1\leq P_i \leq 100
• All input values are integers.

Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

1

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

• If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• A_i \neq i
• All values in the input are integers.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

• Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
• Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
• Person 3's ID has already been called out by person 1, so nothing happens.
• Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
• Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

• Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i, C_i \leq 10^9
• A_1, A_2, \dots ,A_N are all distinct.
• C_1, C_2, \dots ,C_N are all distinct.
• All input values are integers.

Sample Input 1

3
2 4
1 1
3 2

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

5
1 1
10 2
100 3
1000 4
10000 5

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

6
32 101
65 78
2 29
46 55
103 130
52 40

Sample Output 3

4
2 3 5 6

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W).

Cell (i,j)\ (1\leq i\leq H,1\leq j\leq W) has a non-negative integer A_{i,j} written on it.

Let us place zero or more dominoes on the grid. A domino covers two adjacent cells, namely one of the following pairs:

• cells (i,j) and (i,j+1) for 1\leq i\leq H,1\leq j\lt W;
• cells (i,j) and (i+1,j) for 1\leq i\lt H,1\leq j\leq W.

No cell may be covered by more than one domino.

For a placement of dominoes, define its score as the bitwise XOR of all integers written in cells not covered by any domino.

Find the maximum possible score.

Constraints

• 1 \le H
• 1 \le W
• HW \le 20
• 0 \le A_{i,j} < 2^{60} (1 \le i \le H,\ 1 \le j \le W)
• All input values are integers.

Sample Input 1

3 4
1 2 3 8
4 0 7 10
5 2 4 2

Sample Output 1

15

The grid is as follows:

For example, the placement below yields a score of 15.

No placement achieves a score of 16 or higher, so output 15.

Sample Input 2

1 11
1 2 4 8 16 32 64 128 256 512 1024

Sample Output 2

2047

You may also choose to place no dominoes.

Sample Input 3

4 5
74832 16944 58683 32965 97236
52995 43262 51959 40883 58715
13846 24919 65627 11492 63264
29966 98452 75577 40415 77202

Sample Output 3

131067

Problem Statement

There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.

You are given Q queries, so answer each of them. The i-th query is as follows:

You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.

Constraints

• 2 \leq N \leq 400
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 3000
• 1 \leq K_i \leq 5
• 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
• All input values are integers.
• It is possible to travel between any two islands using some bridges.

Sample Input 1

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

Sample Output 1

25
70

For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.

For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.

Sample Input 2

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

Sample Output 2

5
3

For each query, you can cross the specified bridges in either direction.

Sample Input 3

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

Sample Output 3

4000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

In Takahashi's chest of drawers, there are socks of N colors, with A_i socks of color i.

Initially, Takahashi has one sock of color C outside the chest of drawers, separate from these socks, and repeats the following operation until the termination condition is met:

• Uniformly randomly choose and draw 1 sock from the chest of drawers. Then, if the two socks he has outside the chest of drawers are the same color, terminate the operation. Otherwise, choose one of the socks and put it back in the chest of drawers. He always chooses the sock to put back so as to minimize the expected number of future sock draws.

Find the expected number, modulo 998244353, of sock draws until the operation terminates.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq C \leq N
• 1 \leq A_i \leq 3000
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

249561092

The expected number of sock draws is \frac{15}{4}.

Sample Input 2

8 4
4 1 6 2 5 1 7 3

Sample Output 2

393623786