Problem Statement

Given are two permutations of 1,\dots,n: R_1,\dots,R_n and C_1,\dots,C_n.

We have a grid with n horizontal rows and n vertical columns. You will paint each square black or white to satisfy the following conditions.

• For each i=1,\dots,n, the i-th row from the top has exactly R_i black squares.
• For each j=1,\dots,n, the j-th column from the left has exactly C_j black squares.

It can be proved that, under the Constraints of this problem, there is exactly one way to paint the grid to satisfy the conditions.

You are given q queries (r_1,c_1),\dots,(r_q,c_q). For each i=1,\dots,q, print # if the square at the r_i-th row from the top and c_i-th column from the left is painted black; print . if that square is painted white.

Constraints

• 1\le n,q\le 10^5
• R_1,\dots,R_n and C_1,\dots,C_n are each permutations of 1,\dots,n.
• 1\le r_i,c_i \le n
• All values in input are integers.

Sample Input 1

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

Sample Output 1

#.#.#.#

The conditions are satisfied by painting the grid as follows.

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

Problem Statement

Given is a permutation p_1,\dots,p_n of 1,\dots,n. On this permutation, you can do the operations below any number of times in any order.

• Reverse the entire permutation. That is, rearrange p_1,p_2,\dots,p_n to p_n,p_{n-1},\dots,p_1.
• Move the term at the beginning to the end. That is, rearrange p_1,p_2,\dots,p_n to p_2,\dots, p_n, p_1.

Find the minimum number of operations needed to sort the permutation in ascending order. In the given input, it is guaranteed that these operations can sort the permutation in ascending order.

Constraints

• 2 \leq n \leq 10^5
• p_1,\dots,p_n is a permutation of 1,\dots,n.
• The operations in Problem Statement can sort p_1,\dots,p_n in ascending order.

Sample Input 1

3
1 3 2

Sample Output 1

2

You can sort it in ascending order in two operations as follows.

1. Move the term at the beginning to the end: now you have 3, 2, 1.
2. Reverse the whole permutation: now you have 1, 2, 3.

You cannot sort it in less than two operations, so the answer is 2.

Sample Input 2

2
2 1

Sample Output 2

1

Doing either operation once will sort it in ascending order.

You cannot sort it in less than one operation, so the answer is 1.

Sample Input 3

10
2 3 4 5 6 7 8 9 10 1

Sample Output 3

3

You can sort it in ascending order in three operations as follows.

1. Reverse the whole permutation: now you have 1,10,9,8,7,6,5,4,3,2.
2. Move the term at the beginning to the end: now you have 10,9,8,7,6,5,4,3,2,1.
3. Reverse the whole permutation: now you have 1,2,3,4,5,6,7,8,9,10.

You cannot sort it in less than three operations, so the answer is 3.

Sample Input 4

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

Sample Output 4

0

No operation is needed.

Problem Statement

Given is a sequence a_1,\dots,a_n consisting of 1,\dots, n and -1, along with an integer d. How many sequences p_1,\dots,p_n satisfy the conditions below? Print the count modulo 998244353.

• p_1,\dots,p_n is a permutation of 1,\dots, n.
• For each i=1,\dots,n, a_i=p_i if a_i\neq -1. (That is, p_1,\dots,p_n can be obtained by replacing the -1s in a_1,\dots,a_n in some way.)
• For each i=1,\dots,n, |p_i - i|\le d.

Constraints

• 1 \le d \le 5
• d < n \le 500
• 1\le a_i \le n or a_i=-1.
• |a_i-i|\le d if a_i\neq -1.
• a_i\neq a_j, if i\neq j and a_i, a_j \neq -1.
• All values in input are integers.

Sample Input 1

4 2
3 -1 1 -1

Sample Output 1

2

The conditions are satisfied by (3,2,1,4) and (3,4,1,2).

Sample Input 2

5 1
2 3 4 5 -1

Sample Output 2

0

The only permutation of 1,2,3,4,5 that can be obtained by replacing the -1 is (2,3,4,5,1), whose fifth term violates the condition, so the answer is 0.

Sample Input 3

16 5
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 3

794673086

Print the count modulo 998244353.

Problem Statement

Let us define the beauty of the string as the number of positions where two adjacent characters are the same. For example, the beauty of 00011 is 3, and the beauty of 10101 is 0.

Let S_{n,m} be the set of all strings of length n+m formed of n 0s and m 1s.

For s_1,s_2 \in S_{n,m}, let us define the distance of s_1 and s_2, d(s_1,s_2), as the minimum number of swaps needed when rearranging the string s_1 to s_2 by swaps of two adjacent characters.

Additionally, for s_1,s_2,s_3\in S_{n,m}, s_2 is said to be between s_1 and s_3 when d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3).

Given s,t\in S_{n,m}, print the greatest beauty of a string between s and t.

Constraints

• 2 \le n + m\le 3\times 10^5
• 0 \le n,m
• Each of s and t is a string of length n+m formed of n 0s and m 1s.

Sample Input 1

2 3
10110
01101

Sample Output 1

2

Between 10110 and 01101, whose distance is 2, we have the following strings: 10110, 01110, 01101, 10101. Their beauties are 1, 2, 1, 0, respectively, so the answer is 2.

Sample Input 2

4 2
000011
110000

Sample Output 2

4

Between 000011 and 110000, whose distance is 8, the strings with the greatest beauty are 000011 and 110000, so the answer is 4.

Sample Input 3

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

Sample Output 3

22

Problem Statement

There are n squares arranged in a row. Each square has a left- or right-pointing footprint or a hole. The initial state of each square is described by a string s consisting of ., <, >. If the i-th character of s is ., the i-th square from the left has a hole; if that character is <, that square has a left-pointing footprint; if that character is >, that square has a right-pointing footprint.

Snuke, the cat, will repeat the following procedure until there is no more square with a hole.

• Step 1: Choose one square with a hole randomly with equal probability.
• Step 2: Fill the hole in the chosen square, stand there, and face to the left or right randomly with equal probability.
• Step 3: Keep walking in the direction Snuke is facing until he steps on a square with a hole or exits the row of squares.

Here, the choices of squares and directions are independent of each other.

When Snuke walks on a square (without a hole), that square gets a footprint in the direction he walks in. If the square already has a footprint, it gets erased and replaced by a new one. For example, in the situation >.<><.><, if Snuke chooses the 6-th square from the left and faces to the left, the 6-th, 5-th, 4-th, 3-rd squares get left-pointing footprints: >.<<<<><.

Find the expected value of the number of left-pointing footprints when Snuke finishes the procedures, modulo 998244353.

Notes

When the sought expected value is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq\equiv p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353 under the Constraints of this problem. This r is the value to be found.

Constraints

• 1 \leq n \leq 10^5
• s is a string of length n consisting of ., <, >.
• s contains at least one ..

Sample Input 1

5
><.<<

Sample Output 1

3

In Step 1, Snuke always chooses the only square with a hole.

If Snuke faces to the left in Step 2, the squares become <<<<<, where 5 squares have left-pointing footprints.

If Snuke faces to the right in Step 2, the squares become ><>>>, where 1 square has a left-pointing footprint.

Therefore, the answer is \frac{5+1}{2}=3.

Sample Input 2

20
>.>.<>.<<.<>.<..<>><

Sample Output 2

848117770

Problem Statement

Takahashi, Aoki, and Snuke will play a game with k rounds of rock-paper-scissors.

Let us call a string of length k consisting of P, R, S a strategy. The game proceeds as follows.

• Each participant chooses a strategy.
• Play k rounds of rock-paper-scissors. In the i-th round, each participant plays the hand corresponding to the i-th character in the chosen strategy: paper for P, rock for R, and scissors for S.

Aoki will randomly choose one strategy from the n strategies a_1,\dots,a_n with equal probability. Snuke will randomly choose one strategy from the m strategies b_1,\dots,b_m with equal probability. Their choices are independent of each other.

Takahashi will be happy if he is the only winner in at least one of the k rounds. For each of the 3^k possible strategies, find the probability that he becomes happy when choosing that strategy and print it multiplied by nm as an integer (it can be proved that this value is an integer).

Notes

In the game of rock-paper-scissors with three players, the following three scenarios make Takahashi the only winner.

• Takahashi plays paper, while Aoki and Snuke play rock.
• Takahashi plays rock, while Aoki and Snuke play scissors.
• Takahashi plays scissors, while Aoki and Snuke play paper.

Constraints

• 1 \leq k \leq 12
• 1 \leq n,m \leq 3^k
• Each of a_i and b_i is a string of length k consisting of P, R, S.
• a_1,\dots,a_n are distinct.
• b_1,\dots,b_m are distinct.

Sample Input 1

2 1 3
RS
RP
RR
RS

Sample Output 1

3
3
3
0
1
0
0
1
0

Aoki chooses the strategy RS.

If Snuke chooses the strategy RP, the strategies that can meet Takahashi's objective are PP, PR, PS.

If Snuke chooses the strategy RR, the strategies that can meet Takahashi's objective are PP, PR, PS.

If Snuke chooses the strategy RS, the strategies that can meet Takahashi's objective are PP, PR, PS, RR, SR.

Therefore, the probabilities when Takahashi chooses PP, PR, PS, RP, RR, RS, SP, SR, SS are 1, 1, 1, 0, \frac 13, 0, 0, \frac 13, 0, respectively. Print them multiplied by 3.

Sample Input 2

3 5 4
RRP
SSS
RSR
PPP
RSS
PPS
SRP
SSP
RRS

Sample Output 2

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