Problem Statement

In problems on AtCoder, you are often asked to:

find the answer modulo 998244353.

Here, we have 998244353 = 119 \times 2^{23} + 1. Related to this, solve the following prolem:

You are given an integer N.
Print the minimum possible value of a + b + c for a triple of non-negative integers (a, b, c) satisfying N = a \times 2^b + c.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

998244353

Sample Output 1

143

We have 998244353 = 119 \times 2^{23} + 1, in other words, the triple (a, b, c) = (119, 23, 1) satisfies N = a \times 2^{b} + c.
The value a+b+c for this triple is 143.
There is no such triple where a+b+c \leq 142, so 143 is the correct output.

Sample Input 2

1000000007

Sample Output 2

49483

We have 1000000007 = 30517 \times 2^{15} + 18951, in other words, the triple (a, b, c) = (30517, 15, 18951) satisfies N = a \times 2^{b} + c.
The value a+b+c for this triple is 49483.
There is no such triple where a+b+c \leq 49482, so 49483 is the correct output.

Sample Input 3

1

Sample Output 3

1

Note that we have 2^0 = 1.

Sample Input 4

998984374864432412

Sample Output 4

2003450165

Problem Statement

An electric bulletin board is showing a string S of length N consisting of 0 and 1.

You can do the following operation any number of times, where S_i denotes the i-th character (1 \leq i \leq N) of the string shown in the board.

Operation: choose a pair of integers (l, r) (1 \leq l < r \leq N) satisfying one of the conditions below, and swap S_l and S_r.

• S_l= 0 and S_{l+1}=\cdots=S_r= 1.
• S_{l}=\cdots=S_{r-1}= 1 and S_r= 0.

Determine whether it is possible to make the string shown in the board match T, and find the minimum number of operations needed if it is possible.

Constraints

• 2 \leq N \leq 500000
• S is a string of length N consisting of 0 and 1.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

7
1110110
1010111

Sample Output 1

2

Here is one possible way to make the board show the string 1010111 in two operations:

• Do the operation with (l, r) = (2, 4), changing the string in the board from 1110110 to 1011110.
• Do the operation with (l, r) = (4, 7), changing the string in the board from 1011110 to 1010111.

Sample Input 2

20
11111000000000011111
11111000000000011111

Sample Output 2

0

The board already shows the string T before doing any operation, so the answer is 0.

Sample Input 3

6
111100
111000

Sample Output 3

-1

If there is no sequence of operations that makes the board show the string T, print -1.

Sample Input 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

Sample Output 4

22

Problem Statement

There are N buildings along the AtCoder Street, numbered 1 through N from west to east. Initially, Buildings 1, 2, \ldots, N have the heights of A_1, A_2, \dots, A_N, respectively.

Takahashi, the president of ARC Wrecker, Inc., plans to choose integers l and r (1 \leq l \lt r \leq N) and make the heights of Buildings l, l+1, \dots, r all zero. To do so, he can use the following two kinds of operations any number of times in any order:

• Set an integer x (l \leq x \leq r-1) and increase the heights of Buildings x and x+1 by 1 each.
• Set an integer x (l \leq x \leq r-1) and decrease the heights of Buildings x and x+1 by 1 each. This operation can only be done when both of those buildings have heights of 1 or greater.

Note that the range of x depends on (l,r).

How many choices of (l, r) are there where Takahashi can realize his plan?

Constraints

• 2 \leq N \leq 300000
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

5
5 8 8 6 6

Sample Output 1

3

Takahashi can realize his plan for (l, r) = (2, 3), (4, 5), (2, 5).

For example, for (l, r) = (2, 5), the following sequence of operations make the heights of Buildings 2, 3, 4, 5 all zero.

• Decrease the heights of Buildings 4 and 5 by 1 each, six times in a row.
• Decrease the heights of Buildings 2 and 3 by 1 each, eight times in a row.

For the remaining seven choices of (l, r), there is no sequence of operations that can realize his plan.

Sample Input 2

7
12 8 11 3 3 13 2

Sample Output 2

3

Takahashi can realize his plan for (l, r) = (2, 4), (3, 7), (4, 5).

For example, for (l, r) = (3, 7), the following figure shows one possible solution.

Sample Input 3

10
8 6 3 9 5 4 7 2 1 10

Sample Output 3

1

Takahashi can realize his plan for (l, r) = (3, 8) only.

Sample Input 4

14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

Sample Output 4

8

Problem Statement

We have a canvas represented as a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W). Initially, (i, j) is painted red if s_{i, j}= R and blue if s_{i, j}= B.

For any number of times, you can choose one of the two operations below and do it.

Operation X: Choose a square painted red, and repaint all squares in the row containing that square (including itself) white.
Operation Y: Choose a square painted red, and repaint all squares in the column containing that square (including itself) white.

Show one way that maximizes the number of squares painted white in the end.

Constraints

• 1 \leq H \leq 2500
• 1 \leq W \leq 2500
• s_{i, j} is R or B. (1 \leq i \leq H, 1 \leq j \leq W)
• H and W are integers.

Sample Input 1

4 4
RBBB
BBBB
BBBB
RBRB

Sample Output 1

3
X 1 1
Y 4 3
X 4 1

Here is one sequence of operations that makes 10 squares white:

• First, do Operation X choosing (1, 1).
• Then, do Operation Y choosing (4, 3).
• Then, do Operation X choosing (4, 1).

There is no way to make 11 or more squares white.

Sample Input 2

1 119
BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB

Sample Output 2

4
Y 1 60
Y 1 109
Y 1 46
X 1 11

We can repaint all squares white.

Sample Input 3

10 10
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

Sample Output 3

0

Since there is no red square, we cannot do the operations at all.

Problem Statement

We have a pancake tower which is a pile of N pancakes. Initially, the i-th pancake from the top (1 \leq i \leq N) has a size of A_i. Takahashi, a chef, can do the following operation at most once.

• Choose integers l and r (1 \leq l \lt r \leq N) and turn the l-th through r-th pancakes upside down, reversing the order.

Find the minimum possible ugliness of the tower after the operation is done (or not), defined below:

the ugliness is the sum of the differences of the sizes of adjacent pancakes;
that is, the value |A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N|, where A^{\prime}_i is the size of the i-th pancake from the top.

Constraints

• 2 \leq N \leq 300000
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
7 14 12 2 6

Sample Output 1

17

If we do the operation choosing l = 2 and r = 5, the pancakes will have the sizes of 7, 6, 2, 12, 14 from top to bottom.

The ugliness here is |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17. This is the minimum value possible; there is no way to achieve less ugliness.

Sample Input 2

3
111 119 999

Sample Output 2

888

In this sample, not doing the operation minimizes the ugliness.

In that case, the pancakes will have the sizes of 111, 119, 999 from top to bottom, for the ugliness of |111-119| + |119-999| = 8 + 880 = 888.

Sample Input 3

6
12 15 3 4 15 7

Sample Output 3

19

If we do the operation choosing l = 3 and r = 5, the pancakes will have the sizes of 12, 15, 15, 4, 3, 7 from top to bottom.

The ugliness here is |12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19, which is the minimum value possible.

Sample Input 4

7
100 800 500 400 900 300 700

Sample Output 4

1800

If we do the operation choosing l = 2 and r = 4, the pancakes will have the sizes of 100, 400, 500, 800, 900, 300, 700 from top to bottom, for the ugliness of 1800.

Sample Input 5

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

Sample Output 5

2576376600

Problem Statement

There are N+1 stations along the AtCoder Line, numbered 0 through N. Formerly, it only had Local Trains, which run between Stations i and i + 1 in one minute in either direction for each i (0 \leq i \leq N-1).

One day, however, the railway company broke into two groups, called Ko-soku (light speed) and Jun-kyu (semi express). They decided that each station other than Stations 0 and N should be administered by one of the groups. The group that administers Station j (1 \leq j \leq N-1) is represented by a character c_j: A means that Ko-soku administers the station, B means Jun-kyu administers the station, and ? means it is undecided. Since Stations 0 and N are so important, both groups will administer them.

Now, Ko-soku and Jun-kyu have decided to run two new types of trains, in addition to the local trains.

Ko-soku Trains: Let Stations a_0, a_1, \dots, a_s be the stations administered by Ko-soku in ascending order. These trains run between Stations a_k and a_{k+1} in one minute in either direction for each k.

Jun-kyu Trains: Let Stations b_0, b_1, \dots, b_t be the stations administered by Jun-kyu in ascending order. These trains run between Stations b_k and b_{k+1} in one minute in either direction for each k.

There are 2^q ways in which these trains run, where q is the number of ?s. Among them, how many enables us to go from Station 0 to Station N in no more than K minutes' ride? Find this count modulo (10^9+7).

Constraints

• 2 \leq N \leq 4000
• 1 \leq K \leq \frac{N+1}{2}
• N and K are integers.
• Each of c_1, c_2, \dots, c_{N-1} is A, B, or ?.

Sample Input 1

8 3
A??AB?B

Sample Output 1

4

Here, there are 2^3 = 8 possible ways in which the trains run. Among them, the following four enable us to go from Station 0 to Station 8 in no more than 3 minutes' ride.

• If Ko-soku administers Stations 2, 3, 6, we can go Station 0 \rightarrow 5 \rightarrow 7 \rightarrow 8, as shown at #1 in the figure below.
• If Ko-soku administers Stations 2, 3 and Jun-kyu administers Station 6, we can go Station 0 \rightarrow 5 \rightarrow 4 \rightarrow 8, as shown at #2 in the figure below.
• If Ko-soku administers Station 2 and Jun-kyu administers Stations 3, 6, we can go Station 0 \rightarrow 3 \rightarrow 4 \rightarrow 8, as shown at #4 in the figure below.
• If Jun-kyu administers Stations 2, 3, 6, we can go Station 0 \rightarrow 1 \rightarrow 4 \rightarrow 8, as shown at #8 in the figure below.

Therefore, the answer is 4. The figure below shows all the possible ways, where red stations and railways are administered only by Ko-soku, and blue stations and railways are administered only by Jun-kyu.

Sample Input 2

11 6
???B??A???

Sample Output 2

256

Here, all of the 2^8 = 256 ways enable us to go from Station 0 to Station 11 in no more than 6 minutes' ride.

Sample Input 3

16 5
?A?B?A?B?A?B?A?

Sample Output 3

10

10 ways shown in the figure below enable us to go from Station 0 to Station 16 in no more than 5 minutes' ride.

Sample Input 4

119 15
????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????

Sample Output 4

313346281

There are 1623310324709451 desirable ways. Print this count modulo (10^9 + 7), that is, 313346281.