Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

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

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
• a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

1

Problem Statement

Takahashi and Aoki played rock-paper-scissors N times. [Note: In this game, Rock beats Scissors, Scissors beats Paper, and Paper beats Rock.]

Aoki's moves are represented by a string S of length N consisting of the characters R, P, and S. The i-th character of S indicates Aoki's move in the i-th game: R for Rock, P for Paper, and S for Scissors.

Takahashi's moves satisfy the following conditions:

• Takahashi never lost to Aoki.
• For i=1,2,\ldots,N-1, Takahashi's move in the i-th game is different from his move in the (i+1)-th game.

Determine the maximum number of games Takahashi could have won.

It is guaranteed that there exists a sequence of moves for Takahashi that satisfies these conditions.

Constraints

• 1\leq N\leq2\times10 ^ 5
• S is a string of length N consisting of R, P, and S.
• N is an integer.

Sample Input 1

6
PRSSRS

Sample Output 1

5

In the six games of rock-paper-scissors, Aoki played Paper, Rock, Scissors, Scissors, Rock, and Scissors.

Takahashi can play Scissors, Paper, Rock, Scissors, Paper, and Rock to win the 1st, 2nd, 3rd, 5th, and 6th games.

There is no sequence of moves for Takahashi that satisfies the conditions and wins all six games, so print 5.

Sample Input 2

10
SSSSSSSSSS

Sample Output 2

5

Sample Input 3

24
SPRPSRRRRRPPRPRPSSRSPRSS

Sample Output 3

18

Problem Statement

We have a grid with 2 rows and L columns. Let (i,j) denote the square at the i-th row from the top (i\in\lbrace1,2\rbrace) and j-th column from the left (1\leq j\leq L). (i,j) has an integer x _ {i,j} written on it.

Find the number of integers j such that x _ {1,j}=x _ {2,j}.

Here, the description of x _ {i,j} is given to you as the run-length compressions of (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) and (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) into sequences of lengths N _ 1 and N _ 2, respectively: ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence A is a sequence of pairs (v _ i,l _ i) of an element v _ i of A and a positive integer l _ i obtained as follows.

1. Split A between each pair of different adjacent elements.
2. For each sequence B _ 1,B _ 2,\ldots,B _ k after the split, let v _ i be the element of B _ i and l _ i be the length of B _ i.

Constraints

• 1\leq L\leq 10 ^ {12}
• 1\leq N _ 1,N _ 2\leq 10 ^ 5
• 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
• l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
• All values in the input are integers.

Sample Input 1

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3

Sample Output 1

4

The grid is shown below.

We have four integers j such that x _ {1,j}=x _ {2,j}: j=1,2,5,8. Thus, you should print 4.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

Note that the answer may not fit into a 32-bit integer.

Sample Input 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

Sample Output 3

380

Problem Statement

You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.

The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

ababbaba

Sample Output 1

8

The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.

Sample Input 2

zzz

Sample Output 2

1

The only string satisfying the condition is z. Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.

Sample Input 3

ppppqqppqqqpqpqppqpqqqqpppqppq

Sample Output 3

580