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