Problem Statement

We have a grid board with N rows and N columns.

Paint every square black or white to satisfy all of the conditions below.

• For each row, exactly three of the squares in that row are painted black.
• For each column, exactly three of the squares in that column are painted black.
• There are exactly N connected components of black squares. Here, two black squares x and y are considered connected when it is possible to start at x and reach y by repeatedly moving up, down, left, or right to a black square.

It can be proved that the Constraints of the problem guarantee the existence of a solution.

Constraints

• 6 \leq N \leq 500
• All values in input are integers.

Sample Input 1

6

Sample Output 1

##..#.
##..#.
..##.#
..##.#
##...#
..###.

Here, there are exactly 3 #s in each row and column. Additionally, there are exactly 6 connected components of #s.

Problem Statement

Given are an integer N and M pairs of integers. The i-th pair is (L_i,R_i).

Find the number of integer sequences x=(x_1,x_2,\cdots,x_M) that can be generated as follows, modulo 998244353.

• Provide a permutation p=(p_1,p_2,\cdots,p_N) of (1,2,\cdots,N).
• For each i (1 \leq i \leq M), let x_i be the index of the largest element among p_{L_i},p_{L_i+1},\cdots,p_{R_i}. That is, \max(p_{L_i},p_{L_i+1},\cdots,p_{R_i})=p_{x_i}.

Constraints

• 2 \leq N \leq 300
• 1 \leq M \leq N(N-1)/2
• 1 \leq L_i < R_i \leq N
• (L_i,R_i) \neq (L_j,R_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3 2
1 2
1 3

Sample Output 1

4

For example, for p=(2,1,3), we will have x=(1,3).

The four sequences that meet the requirement are x=(1,1),(1,3),(2,2),(2,3).

Sample Input 2

6 3
1 2
3 4
5 6

Sample Output 2

8

Sample Input 3

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

Sample Output 3

1060

Problem Statement

Consider making a string s of length N consisting of 0 and 1, where s must satisfy M conditions. The i-th condition is represented by integers L_i and R_i (1 \leq L_i < R_i \leq N). This means that there should be equal numbers of 0 and 1 between the L_i-th and R_i-th characters (inclusive) of s.

Find the lexicographically smallest string s that satisfies all conditions. It can be proved that the Constraints of the problem guarantee the existence of s that satisfies the conditions.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq M \leq 200000
• 1 \leq L_i < R_i \leq N
• (R_i-L_i+1) \equiv 0 \mod 2
• (L_i,R_i) \neq (L_j,R_j) (i \neq j)
• All values in input are integers.

Sample Input 1

4 2
1 2
3 4

Sample Output 1

0101

Sample Input 2

6 2
1 4
3 6

Sample Output 2

001100

Sample Input 3

20 10
6 17
2 3
14 19
5 14
10 15
7 20
10 19
3 20
6 9
7 12

Sample Output 3

00100100101101001011

Problem Statement

There are N integers written on a blackboard. The i-th integer is A_i. Here, N is even. Additionally, integers L and R are given.

Alice and Bob will play a game. They alternately take turns, with Alice going first. In each turn, the player chooses a number written on the blackboard and erases it.

The game will end in N turns. Then, let s be the sum of the integers erased by Alice. If L \leq s \leq R, Alice wins; otherwise, Bob wins. Find which player will win when both players play optimally.

Constraints

• 2 \leq N \leq 5000
• N is even.
• 1 \leq A_i \leq 10^9
• 0 \leq L \leq R \leq \sum_{1 \leq i \leq N} A_i
• All values in input are integers.

Sample Input 1

4 5 6
3 1 4 5

Sample Output 1

Alice

In this game, Alice will always win. Below is a possible progression of the game.

• Alice erases 1.
• Bob erases 4.
• Alice erases 5.
• Bob erases 3.

Here, the sum of the integers erased by Alice is 6. Since L \leq 6 \leq R, Alice wins.

Sample Input 2

2 2 3
4 1

Sample Output 2

Bob

Sample Input 3

30 655 688
42 95 9 13 91 27 99 56 64 15 3 11 5 16 85 3 62 100 64 79 1 70 8 69 70 28 78 4 33 12

Sample Output 3

Bob

Sample Input 4

30 792 826
81 60 86 57 5 20 26 13 39 64 89 58 43 98 50 79 58 21 27 68 46 47 45 85 88 5 82 90 74 57

Sample Output 4

Alice

Problem Statement

There is a circumference of length N. On this circumference, a point whose distance from a certain fixed point, measured in the clockwise direction, is x has the coordinate x.

For each integer i (0 \leq i \leq N-1), there is a mouse at coordinate i+0.5.

Snuke will throw a piece of cheese N-1 times. More specifically, he repeats the following N-1 times.

• Choose an integer y (0 \leq y \leq N-1) randomly, where y=i is chosen with probability A_i percent. This choice is made independently each time.
• Then, throw cheese from the coordinate y. The cheese travels in the clockwise direction on the circumference. When the cheese meets a mouse, the following happens.
  • If the mouse has not eaten cheese:
    • It eats the cheese with probability 1/2. The cheese disappears.
    • It does nothing with probability 1/2.
  • If the mouse has already eaten cheese:
    • It does nothing.
• The cheese keeps traveling on the circumference until eaten by some mouse.

After N-1 throws of cheese, there will be exactly one mouse that has never eaten cheese. For each k=0,1,\cdots,N-1, find the probability that the mouse at coordinate k+0.5 ends up not eating cheese, modulo 998244353.

Constraints

• 1 \leq N \leq 40
• 0 \leq A_i
• \sum_{0 \leq i \leq N-1} A_i = 100
• All values in input are integers.

Sample Input 1

2
0 100

Sample Output 1

665496236 332748118

y=1 is always chosen. When throwing cheese from this point, the following happens.

• With probability 1/2, the mouse at coordinate 1.5 eats it.
• With probability 1/4, the mouse at coordinate 0.5 eats it.
• With probability 1/8, the mouse at coordinate 1.5 eats it.
• With probability 1/16, the mouse at coordinate 0.5 eats it.
• \vdots

In the end, the mice at coordinates 0.5 and 1.5 eat this cheese with probabilities 1/3 and 2/3, respectively.

Therefore, they end up not eating cheese with probabilities 2/3 and 1/3, respectively.

Sample Input 2

2
50 50

Sample Output 2

499122177 499122177

Sample Input 3

10
1 2 3 4 5 6 7 8 9 55

Sample Output 3

333507001 91405664 419217284 757959653 974851434 806873643 112668439 378659755 979030842 137048051

Problem Statement

Given are integers N and M. Find the number of integer sequences a=(a_1,a_2,\cdots,a_N) that can be generated as follows, modulo 998244353.

• Provide an undirected connected graph G with N vertices and M edges. Here, G may not contain self-loops, but may contain multi-edges.
• Perform DFS on G and let a_i be the degree of the i-th vertex to be visited. More accurately, execute the pseudo-code below to get a.

a = empty array

dfs(v):
    visited[v]=True
    a.append(degree[v])
    for u in g[v]:
        if not visited[u]:
            dfs(u)

dfs(arbitrary root)

Here, the variable g represents the graph G as an adjacency list, where g[v] is the list of vertices adjacent to the vertex v in arbitrary order.

For example, when N=4,M=5, it is possible to generate a=(2,4,1,3), by providing the graph G as follows.

Here, the numbers written on vertices represent the order they are visited in the DFS. (The DFS starts at the vertex labeled 1.) The orange arrows show the transitions in the DFS, and the numbers next to them represent the order the edges are traversed.

Constraints

• 2 \leq N \leq M \leq 10^6
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

1

The only possible result is a=(2,2). Note that G may have multi-edges.

Sample Input 2

3 4

Sample Output 2

9

Sample Input 3

10 20

Sample Output 3

186225754

Sample Input 4

100000 1000000

Sample Output 4

191021899