Problem Statement

There are two 100-story buildings, called A and B. (In this problem, the ground floor is called the first floor.)

For each i = 1,\dots, 100, the i-th floor of A and that of B are connected by a corridor. Also, for each i = 1,\dots, 99, there is a corridor that connects the (i+1)-th floor of A and the i-th floor of B. You can traverse each of those corridors in both directions, and it takes you x minutes to get to the other end.

Additionally, both of the buildings have staircases. For each i = 1,\dots, 99, a staircase connects the i-th and (i+1)-th floors of a building, and you need y minutes to get to an adjacent floor by taking the stairs.

Find the minimum time needed to reach the b-th floor of B from the a-th floor of A.

Constraints

• 1 \leq a,b,x,y \leq 100
• All values in input are integers.

Sample Input 1

2 1 1 5

Sample Output 1

1

There is a corridor that directly connects the 2-nd floor of A and the 1-st floor of B, so you can travel between them in 1 minute. This is the fastest way to get there, since taking the stairs just once costs you 5 minutes.

Sample Input 2

1 2 100 1

Sample Output 2

101

For example, if you take the stairs to get to the 2-nd floor of A and then use the corridor to reach the 2-nd floor of B, you can get there in 1+100=101 minutes.

Sample Input 3

1 100 1 100

Sample Output 3

199

Using just corridors to travel is the fastest way to get there.

Problem Statement

Snuke is visiting a shop in Tokyo called 109 to buy some logs. He wants n logs: one of length 1, one of length 2, ..., and one of length n. The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).

He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.

Snuke wants to spend as little money as possible to get the logs he wants. Find the minimum amount of money needed to get n logs of length 1 to n.

Constraints

• 1 \leq n \leq 10^{18}

Sample Input 1

4

Sample Output 1

3

One way to get the logs he wants with 3 yen is:

• Buy logs of length 2, 4, and 5.
• Cut the log of length 5 into two logs of length 1 each and a log of length 3.
• Throw away one of the logs of length 1.

Sample Input 2

109109109109109109

Sample Output 2

109109108641970782

Problem Statement

To decide which is the strongest among Rock, Paper, and Scissors, we will hold an RPS tournament. There are 2^k players in this tournament, numbered 0 through 2^k-1. Each player has his/her favorite hand, which he/she will use in every match.

A string s of length n consisting of R, P, and S represents the players' favorite hands. Specifically, the favorite hand of Player i is represented by the ((i\text{ mod } n) + 1)-th character of s; R, P, and S stand for Rock, Paper, and Scissors, respectively.

For l and r such that r-l is a power of 2, the winner of the tournament held among Players l through r-1 will be determined as follows:

• If r-l=1 (that is, there is just one player), the winner is Player l.
• If r-l\geq 2, let m=(l+r)/2, and we hold two tournaments, one among Players l through m-1 and the other among Players m through r-1. Let a and b be the respective winners of these tournaments. a and b then play a match of rock paper scissors, and the winner of this match - or a if the match is drawn - is the winner of the tournament held among Players l through r-1.

Find the favorite hand of the winner of the tournament held among Players 0 through 2^k-1.

Notes

• a\text{ mod } b denotes the remainder when a is divided by b.
• The outcome of a match of rock paper scissors is determined as follows:
  • If both players choose the same hand, the match is drawn;
  • R beats S;
  • P beats R;
  • S beats P.

Constraints

• 1 \leq n,k \leq 100
• s is a string of length n consisting of R, P, and S.

Sample Input 1

3 2
RPS

Sample Output 1

P

• The favorite hand of the winner of the tournament held among Players 0 through 1 is P.
• The favorite hand of the winner of the tournament held among Players 2 through 3 is R.
• The favorite hand of the winner of the tournament held among Players 0 through 3 is P.

Thus, the answer is P.

   P
 ┌─┴─┐
 P   R
┌┴┐ ┌┴┐
R P S R

Sample Input 2

11 1
RPSSPRSPPRS

Sample Output 2

P

Sample Input 3

1 100
S

Sample Output 3

S

Problem Statement

We have three stones at points (0, 0), (1,0), and (0,1) on a two-dimensional plane.

These three stones are said to form an L when they satisfy the following conditions:

• Each of the stones is at integer coordinates.
• Each of the stones is adjacent to another stone. (That is, for each stone, there is another stone whose distance from that stone is 1.)
• The three stones do not lie on the same line.

Particularly, the initial arrangement of the stone - (0, 0), (1,0), and (0,1) - forms an L.

You can do the following operation any number of times: choose one of the stones and move it to any position. However, after each operation, the stones must form an L. You want to do as few operations as possible to put stones at points (ax, ay), (bx, by), and (cx, cy). How many operations do you need to do this?

It is guaranteed that the desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L. Under this condition, it is always possible to achieve the objective with a finite number of operations.

You will be given T cases of this problem. Solve each of them.

Notes

We assume that the three stones are indistinguishable. For example, the stone that is initially at point (0,0) may be at any of the points (ax, ay), (bx, by), and (cx, cy) in the end.

Constraints

• 1 \leq T \leq 10^3
• |ax|,|ay|,|bx|,|by|,|cx|,|cy| \leq 10^9
• The desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L.

Sample Input 1

1
3 2 2 2 2 1

Sample Output 1

4

Let us use # to represent a stone. You can move the stones to the specified positions with four operations, as follows:

....    ....    ....    ..#.    ..##
#... -> ##.. -> .##. -> .##. -> ..#.
##..    .#..    .#..    ....    ....

Sample Input 2

10
0 0 1 0 0 1
1 0 0 1 1 1
2 -1 1 -1 1 0
1 -2 2 -1 1 -1
-1 2 0 2 -1 3
-1 -2 -2 -2 -2 -3
-2 4 -3 3 -2 3
3 1 4 2 4 1
-4 2 -4 3 -3 3
5 4 5 3 4 4

Sample Output 2

0
1
2
3
4
5
6
7
8
9

Problem Statement

Kuro and Shiro are playing with a board composed of n squares lining up in a row. The squares are numbered 1 to n from left to right, and Square s has a mark on it.

First, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square s a stone of the same color as the square.

Kuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:

1. Choose an empty square adjacent to a square with a stone on it. Let us say Square i is chosen.
2. Put on Square i a stone of the same color as the square.
3. If there are squares other than Square i that contain a stone of the same color as the stone just placed, among such squares, let Square j be the one nearest to Square i. Change the color of every stone between Square i and Square j to the color of Square i.

The game ends when the board has no empty square.

Kuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.

For each of the cases s=1,\dots,n, find the expected value, modulo 998244353, of the number of black stones at the end of the game.

Notes

When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq=p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353, which we ask you to find.

Constraints

• 1 \leq n \leq 2\times 10^5

Sample Input 1

3

Sample Output 1

499122178
499122178
499122178

Let us use b to represent a black square and w to represent a white square. There are eight possible boards: www, wwb, wbw, wbb, bww, bwb, bbw, and bbb, which are chosen with equal probability.

For each of these boards, there will be 0, 1, 0, 2, 1, 3, 2, and 3 black stones at the end of the game, respectively, regardless of the value of s. Thus, the expected number of stones is (0+1+0+2+1+3+2+3)/8 = 3/2, and the answer is r = 499122178, which satisfies 2r = 3 ~(\text{mod } 998244353) and 0 \leq r \lt 998244353.

Sample Input 2

10

Sample Output 2

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5

Sample Input 3

19

Sample Output 3

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186

Problem Statement

Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer i, Square i and Square i+1 are adjacent. Additionally, each square is painted white or black.

A string s of length n consisting of w and b represents the colors of the squares of this board, as follows:

• For each i = 1, 2, \dots, n, Square i is white if the i-th character of s is w, and black if that character is b;
• For each i \leq 0, Square i is white;
• For each i > n, Square i is black.

Snuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:

• (1) Choose a piece of the color of his choice.
• (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.
  • (2a) If there are such squares, choose one of them and put the piece on it;
  • (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.

The board initially has no piece on it.

You are given a string t of length n consisting of o and _. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square i among Squares 1,..,n such that the i-th character of t is o. It is guaranteed that t has at least one occurrence of o.

Constraints

• 1 \leq n \leq 10^5
• |s| = |t| = n
• s consists of w and b.
• t consists of o and _.
• t has at least one occurrence of o.

Sample Input 1

3
wbb
o_o

Sample Output 1

2

Let us use W to represent a white square that needs a piece on it, B to represent a black square that needs a piece on it, w to represent a white square that does not need a piece on it, and b to represent a black square that does not need a piece on it.

We have the following board:

...wwwwwwWbBbbbbb...

If we put pieces in the following order, two pieces is enough:

...wwwwwwWbBbbbbb...
         2 1

Note that if we put a piece on the white square first, we will need three or more pieces:

...wwwwwwWbBbbbbb...
         123

Sample Input 2

4
wwww
o__o

Sample Output 2

3

If we put pieces in the following order, three pieces is enough:

...wwwwwWwwWbbbbb...
        1  32

Sample Input 3

9
bbwbwbwbb
_o_o_o_o_

Sample Output 3

5

If we put pieces in the following order, five pieces is enough:

...wwwwwbBwBwBwBbbbbbb...
        12 3 4 5

Sample Input 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

Sample Output 4

11