Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

• Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
• Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
  • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

Problem Statement

A superman, Takahashi, is about to jump off the roof of a building to help a person in trouble on the ground. Takahashi's planet has a constant value g that represents the strength of gravity, and the time it takes for him to reach the ground after starting to fall is \frac{A}{\sqrt{g}}.

It is now time 0, and g = 1. Takahashi will perform the following operation as many times as he wants (possibly zero).

• Use a superpower to increase the value of g by 1. This takes a time of B.

Then, he will jump off the building. After starting to fall, he cannot change the value of g. Additionally, we only consider the time it takes to perform the operation and fall.

Find the earliest time Takahashi can reach the ground.

Constraints

• 1 \leq A \leq 10^{18}
• 1 \leq B \leq 10^{18}
• All values in the input are integers.

Sample Input 1

10 1

Sample Output 1

7.7735026919

• If he performs the operation zero times, he will reach the ground at time 1\times 0+\frac{10}{\sqrt{1}} = 10.
• If he performs the operation once, he will reach the ground at time 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07.
• If he performs the operation twice, he will reach the ground at time 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77.
• If he performs the operation three times, he will reach the ground at time 1\times 3+\frac{10}{\sqrt{4}} = 8.

Performing the operation four or more times will only delay the time to reach the ground. Therefore, it is optimal to perform the operation twice before jumping off, and the answer is 2+\frac{10}{\sqrt{3}}.

Sample Input 2

5 10

Sample Output 2

5.0000000000

It is optimal not to perform the operation at all.

Sample Input 3

1000000000000000000 100

Sample Output 3

8772053214538.5976562500

Problem Statement

You are given a sequence of length M consisting of integers between 1 and N-1, inclusive: A=(A_1,A_2,\dots,A_M). Answer the following question for i=1, 2, \dots, M.

• There is a sequence B=(B_1,B_2,\dots,B_N). Initially, we have B_j=j for each j. Let us perform the following operation for k=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers k between 1 and M except i in ascending order).
  • Swap the values of B_{A_k} and B_{A_k+1}.
• After all the operations, let S_i be the value of j such that B_j=1. Find S_i.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq A_i \leq N-1\ (1\leq i \leq M)
• All values in the input are integers.

Sample Input 1

5 4
1 2 3 2

Sample Output 1

1
3
2
4

For i = 2, the operations change B as follows.

• Initially, B = (1,2,3,4,5).
• Perform the operation for k=1. That is, swap the values of B_1 and B_2, making B = (2,1,3,4,5).
• Perform the operation for k=3. That is, swap the values of B_3 and B_4, making B = (2,1,4,3,5).
• Perform the operation for k=4. That is, swap the values of B_2 and B_3, making B = (2,4,1,3,5).

After all the operations, we have B_3=1, so S_2 = 3.

Similarly, we have the following.

• For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so S_1=1.
• For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so S_3=2.
• For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so S_4=4.

Sample Input 2

3 3
2 2 2

Sample Output 2

1
1
1

Sample Input 3

10 10
1 1 1 9 4 4 2 1 3 3

Sample Output 3

2
2
2
3
3
3
1
3
4
4

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.

Problem Statement

There is a grid with 1 \times N squares, numbered 1,2,\dots,N from left to right.

Takahashi prepared paints of C colors and painted each square in one of the C colors.
Then, there were at most two colors in any consecutive K squares.
Formally, for every integer i such that 1 \le i \le N-K+1, there were at most two colors in squares i,i+1,\dots,i+K-1.

In how many ways could Takahashi paint the squares?
Since this number can be enormous, find it modulo 998244353.

Constraints

• All values in the input are integers.
• 2 \le K \le N \le 10^6
• 1 \le C \le 10^9

Sample Input 1

3 3 3

Sample Output 1

21

In this input, we have a 1 \times 3 grid.
Among the 27 ways to paint the squares, there are 6 ways to paint all squares in different colors, and the remaining 21 ways are such that there are at most two colors in any consecutive three squares.

Sample Input 2

10 5 2

Sample Output 2

1024

Since C=2, no matter how the squares are painted, there are at most two colors in any consecutive K squares.

Sample Input 3

998 244 353

Sample Output 3

952364159

Print the number modulo 998244353.

Problem Statement

You are given positive integers N and M. Here, it is guaranteed that N\leq M \leq 2N.

Print the sum, modulo 200\ 003 (a prime), of the following value over all sequences of positive integers S=(S_1,S_2,\dots,S_N) such that \displaystyle \sum_{i=1}^{N} S_i = M (notice the unusual modulo):

• \displaystyle \prod_{k=1}^{N} \min(k,S_k).

Constraints

• 1 \leq N \leq 10^{12}
• N \leq M \leq 2N
• All values in the input are integers.

Sample Input 1

3 5

Sample Output 1

14

There are six sequences S that satisfy the condition: S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1).

The value \displaystyle \prod_{k=1}^{N} \min(k,S_k) for each of those S is as follows.

• S=(1,1,3) : 1\times 1 \times 3 = 3
• S=(1,2,2) : 1\times 2 \times 2 = 4
• S=(1,3,1) : 1\times 2 \times 1 = 2
• S=(2,1,2) : 1\times 1 \times 2 = 2
• S=(2,2,1) : 1\times 2 \times 1 = 2
• S=(3,1,1) : 1\times 1 \times 1 = 1

Thus, you should print their sum: 14.

Sample Input 2

1126 2022

Sample Output 2

40166

Print the sum modulo 200\ 003.

Sample Input 3

1000000000000 1500000000000

Sample Output 3

180030