Problem Statement

We have N cards arranged in a row from left to right. We will write an integer between 1 and K (inclusive) on each of these cards, which are initially blank.

Given are K restrictions numbered 1 through K. Restriction i is composed of a character c_i and an integer k_i. If c_i is L, the k_i-th card from the left in the row must be the leftmost card on which we write i. If c_i is R, the k_i-th card from the left in the row must be the rightmost card on which we write i.

Note that for each integer i from 1 through K, there must be at least one card on which we write i.

Find the number of ways to write integers on the cards under the K restrictions, modulo 998244353.

Constraints

• 1 \leq N,K \leq 1000
• c_i is L or R.
• 1 \leq k_i \leq N
• k_i \neq k_j if i \neq j.

Sample Input 1

3 2
L 1
R 2

Sample Output 1

1

• The only way to meet the two restrictions is to write 1, 2, 1 from left to right on the three cards.

Sample Input 2

30 10
R 6
R 8
R 7
R 25
L 26
L 13
R 14
L 11
L 23
R 30

Sample Output 2

343921442

• Be sure to find the count modulo 998244353.

Problem Statement

Given are sequences a and b, each of length N, consisting of non-negative integers. The i-th elements of a and b are a_i and b_i, respectively.

A non-negative integer x is said to be good when the following condition is satisfied:

• Condition: It is possible to permute b so that a_i \text{ XOR } b_i = x holds for every integer i such that 1 \leq i \leq N, where \text{XOR } is the bitwise XOR.

List all good integers in ascending order.

Constraints

• All values in input are integers.
• 1 \leq N \leq 2000
• 0 \leq a_i, b_i < 2^{30}

Sample Input 1

3
1 2 3
6 4 7

Sample Output 1

1
5

• If we permute b into (4, 7, 6), we have a_1 \text{ XOR } b_1 = a_2 \text{ XOR } b_2 = a_3 \text{ XOR } b_3 = 5, so 5 is a good integer. There are no other good integers.

Sample Input 2

2
0 1
0 2

Sample Output 2

0

Sample Input 3

24
14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481
805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010

Sample Output 3

8
107543995
129376201
139205201
160626723
312334911
323172429
481902037
493346727

Problem Statement

We have a red bag, a blue bag, and N card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the i-th card pack contains a card with a_i and another with b_i.

For each card pack, we will put one of its cards in the red bag, and the other in the blue bag.

After we put all cards in the bags, let X be the greatest common divisor of all integers written on cards in the red bag. Similarly, let Y be the greatest common divisor of all integers written on cards in the blue bag. Our score will be the least common multiple of X and Y.

Find the maximum possible score.

Constraints

• All values in input are integers.
• 1 \leq N \leq 50
• 1 \leq a_i, b_i \leq 10^9

Sample Input 1

2
2 15
10 6

Sample Output 1

10

• One optimal move is to put the card with 2 in the red bag, the card with 15 in the blue bag, the card with 6 in the red bag, and the card with 10 in the blue bag.
• Then, the greatest common divisor of all integers written on cards in the red bag will be 2, and the greatest common divisor of all integers written on cards in the blue bag will be 5.
• The score here will be 10.

Sample Input 2

5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

Sample Output 2

238630

Sample Input 3

20
557057460 31783488
843507940 794587200
640711140 620259584
1901220 499867584
190122000 41414848
349507610 620259584
890404700 609665088
392918800 211889920
507308870 722352000
156850650 498904448
806117280 862969856
193607570 992030080
660673950 422816704
622015810 563434560
207866720 316871744
63057130 117502592
482593010 366954816
605221700 705015552
702500790 900532160
171743540 353470912

Sample Output 3

152594452160

Problem Statement

Given is a sequence p of length N+M, which is a permutation of (1,2 \ldots, N+M). The i-th term of p is p_i.

You can do the following Operation any number of times.

Operation: Choose an integer n between 1 and N (inclusive), and an integer m between 1 and M (inclusive). Then, swap p_{n} and p_{N+m}.

Find the minimum number of Operations needed to sort p in ascending order. We can prove that it is possible to sort p in ascending order under the Constraints of this problem.

Constraints

• All values in input are integers.
• 1 \leq N,M \leq 10^5
• 1 \leq p_i \leq N+M
• p is a permutation of (1,2 \ldots, N+M).

Sample Input 1

2 3
1 4 2 5 3

Sample Output 1

3

Sample Input 2

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

Sample Output 2

10

Problem Statement

N people called Person 1, 2, \ldots, N are standing in a circle.

For each 1 \leq i \leq N-1, Person i's neighbor to the right is Person i+1, and Person N's neighbor to the right is Person 1.

Person i initially has a_i balls.

They will do the following procedure just once.

• Each person chooses some (possibly zero) of the balls they have.
• Then, each person simultaneously hands the chosen balls to the neighbor to the right.
• Now, make a sequence of length N, where the i-th term is the number of balls Person i has at the moment.

Let S be the set of all sequences that can result from the procedure. For example, when a=(1,1,1), we have S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \}.

Compute \sum_{x \in S} \prod_{i=1}^{N} x_i, modulo 998244353.

Constraints

• All values in input are integers.
• 3 \leq N \leq 10^5
• 0 \leq a_i \leq 10^9

Sample Input 1

3
1 1 1

Sample Output 1

1

• We have S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \}.
• \sum_{x \in S} \prod_{i=1}^{N} x_i is 1.

Sample Input 2

3
2 1 1

Sample Output 2

6

Sample Input 3

20
5644 493 8410 8455 7843 9140 3812 2801 3725 6361 2307 1522 1177 844 654 6489 3875 3920 7832 5768

Sample Output 3

864609205

• Be sure to compute it modulo 998244353.

Problem Statement

Given is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Initially, a camel is on (1, 1), and a cat is on (H, 1).

You can send the following four kinds of orders.

• R: Move the camel on (i, j) to (i, j+1).
• D: Move the camel on (i, j) to (i+1, j).
• r: Move the cat on (i, j) to (i, j+1).
• u: Move the cat on (i, j) to (i-1, j).

A sequence of orders satisfying all of the four conditions below is said to be good. Find the number of good sequences of orders, modulo 998244353.

1. The final position of the camel will be (H, W).
2. The final position of the cat will be (1, W).
3. The following will happen exactly once: the camel and the cat are on the same square after an order is processed.
4. Neither the camel nor the cat will leave the grid.

Constraints

• All values in input are integers.
• 2 \leq H,W \leq 2 \times 10^{5}

Sample Input 1

2 2

Sample Output 1

16

• The good sequences of orders include DRur, DurR, RruD, RDru, but not DRru, RRR.

Sample Input 2

200000 200000

Sample Output 2

412709667

• Be sure to print the count modulo 998244353.