Problem Statement

You are given an integer N and a string S consisting of lowercase English letters with length less than N.

Print the string obtained by repeatedly adding the lowercase English letter o to the beginning of S until its length becomes N.

Constraints

• 2\leq N \leq 100
• N is an integer.
• S is a string consisting of lowercase English letters with length between 1 and N - 1, inclusive.

Sample Input 1

5
abc

Sample Output 1

ooabc

Since N=5 and the length of S is 3, the answer is the string obtained by adding 5-3=2 os to the beginning of S.

Sample Input 2

2
o

Sample Output 2

oo

Sample Input 3

12
vgxgpuam

Sample Output 3

oooovgxgpuam

Problem Statement

On a certain planet, a year has D days, and contests are held every 7 days. Contests never span across days.

The first contest of a certain year was held on the F-th day of the year. On what day of the next year will the first contest of the next year be held?

The constraints of this problem guarantee that at least one contest will be held in the next year.

Constraints

• 10 \leq D \leq 366
• 1 \leq F \leq 7
• All input values are integers.

Sample Input 1

365 4

Sample Output 1

3

If the first contest of a certain year was held on the 4th day of the year, the first contest of the next year will be held on the 3rd day of the year.

Sample Input 2

10 5

Sample Output 2

2

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

• 1 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

You will perform the following operation zero or more times:

• Choose one edge that has not been deleted yet, and delete it.

Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.

Constraints

• 2\le N\le10
• 1\le M\le\dfrac{N(N-1)}2
• 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
• The given graph is simple.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.

It is impossible to make the graph bipartite by performing one or less operations, so print 2.

Sample Input 2

2 1
1 2

Sample Output 2

0

The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.

Sample Input 3

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

Sample Output 3

5

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

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

You are given a sequence of length N consisting of non-negative integers: A=(A _ 1,A _ 2,\ldots,A _ N) .

Define the score of a sequence of length 1 or more consisting of sequences of non-negative integers, S=(S _ 1,S _ 2,\ldots,S _ k), as the number of sequences S _ i\ (1\le i\le k) whose sum of elements is divisible by K.

Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing A into one or more contiguous subsequences. Here, dividing a sequence A of length N into one or more contiguous subsequences means choosing a sequence of integers l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) of length 1 or more, and forming the following k sequences.

• (A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) (Here, let l _ {k+1}=N+1.)

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le K\le10 ^ 9
• 0\le A _ i\lt K
• All input values are integers.

Sample Input 1

6 10
6 8 2 2 6 4

Sample Output 1

2

For example, A can be divided into four contiguous subsequences as (6),(8,2),(2),(6,4). The sums of the elements of the second and fourth sequences are multiples of 10, so the score of ((6),(8,2),(2),(6,4)) is 2.

A cannot be divided so that the score is 3 or more, so output 2.

Sample Input 2

8 1
0 0 0 0 0 0 0 0

Sample Output 2

8

Sample Input 3

30 8
5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2

Sample Output 3

8

Problem Statement

There is a race through checkpoints 1,2,\dots,N in this order on a coordinate plane.
The coordinates of checkpoint i are (X_i,Y_i), and all checkpoints have different coordinates.

Checkpoints other than checkpoints 1 and N can be skipped.
However, let C be the number of checkpoints skipped, and the following penalty will be imposed:

• \displaystyle 2^{C−1} if C>0, and
• 0 if C=0.

Let s be the total distance traveled (Euclidean distance) from checkpoint 1 to checkpoint N plus the penalty.
Find the minimum achievable value as s.

Constraints

• All input values are integers.
• 2 \le N \le 10^4
• 0 \le X_i,Y_i \le 10^4
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

6
0 0
1 1
2 0
0 1
1 0
2 1

Sample Output 1

5.82842712474619009753

Consider passing through checkpoints 1,2,5,6 and skip checkpoints 3,4.

• Move from checkpoint 1 to 2. The distance between them is \sqrt{2}.
• Move from checkpoint 2 to 5. The distance between them is 1.
• Move from checkpoint 5 to 6. The distance between them is \sqrt{2}.
• Two checkpoints are skipped, so the penalty of 2 is imposed.

In this way, you can achieve s = 3 + 2\sqrt{2} \approx 5.828427.
You cannot make s smaller than this value.

Sample Input 2

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

Sample Output 2

24.63441361516795872523

Sample Input 3

10
34 24
47 60
30 31
12 97
87 93
64 46
82 50
14 7
17 24
3 78

Sample Output 3

110.61238353245736230207