Problem Statement

There is a train consisting of N cars. What is the position, counted from the back, of the car that is K-th from the front of this train?

Constraints

• 1 \leq K \leq N \leq 100
• All input values are integers.

Sample Input 1

5 2

Sample Output 1

4

For a train consisting of five cars, the car that is second from the front is fourth from the back.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

99 50

Sample Output 3

50

Problem Statement

You are given a string S of length N consisting of o and x.
N chairs are arranged in a row from left to right. If the i-th character of S is o, a person is sitting in the i-th chair from the left; if it is x, no person is sitting there.
Find the number of chairs that satisfy all of the following conditions.

• No person is sitting in it.
• There is no chair to its left, or no person is sitting in the chair to its left.
• There is no chair to its right, or no person is sitting in the chair to its right.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of o and x.

Sample Input 1

8
xxoxxxox

Sample Output 1

2

Only the first and fifth chairs from the left satisfy the conditions.

Sample Input 2

5
ooooo

Sample Output 2

0

Sample Input 3

1
x

Sample Output 3

1

Problem Statement

You are given a string S of length N consisting of o and x.
N bags are arranged in a row, and each bag contains one sweet.
On the i-th bag, "hit" is written if the i-th character of S is o, and "miss" is written if it is x.
For each k=1,2,\dots,N, solve the following problem.

Takahashi receives the first k bags from the front of the row, eats the sweets inside them, and keeps the bags.
Then, he repeats the following action as many times as possible.

• He discards one bag marked "hit" that he is holding, receives the bag at the front of the row, eats the sweet inside it, and keeps that bag. This action can only be performed when there is still a bag remaining in the row and he is holding a bag marked "hit".

Find the number of sweets he can eat.
Note that when he receives a bag, that bag is removed from the row.

Constraints

• 1 \leq N \leq 8 \times 10^5
• N is an integer.
• S is a string of length N consisting of o and x.

Sample Input 1

5
oxoxo

Sample Output 1

2
4
5
5
5

For k=1, the bag he receives is marked "hit". He discards it, and the bag he then receives is marked "miss", so he cannot perform any further actions.

Sample Input 2

3
ooo

Sample Output 2

3
3
3

Sample Input 3

1
x

Sample Output 3

1

Problem Statement

There is a game with N players 1,2,\dots,N.
This game is played in a format where two players face each other one-on-one.
A tournament among the N players was held M times, and the two players A_m and B_m advanced to the final of the m-th tournament.
Find the number of pairs of integers x and y satisfying the following conditions.

• 1 \leq x \lt y \leq N
• In every tournament, at least one of players x and y advanced to the final.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

1

The conditions are satisfied when (x,y)=(2,3), and not satisfied otherwise.
For example, in the fourth tournament, neither player 1 nor player 4 advanced to the final, so (x,y)=(1,4) does not satisfy the conditions.

Sample Input 2

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

Sample Output 2

2

There are two pairs (x,y) satisfying the conditions: (1,2) and (1,4).

Sample Input 3

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

Sample Output 3

2

Problem Statement

You are given a string S of length N consisting of o and x.
It is guaranteed that S contains at least K occurrences of o.
Takahashi played a certain game N times.
In the i-th game, he won if the i-th character of S is o, and lost if it is x.

Takahashi chooses a pair of integers l and r satisfying the following conditions.

• 1 \leq l \leq r \leq N
• He won at least K times in the games from the l-th through the r-th.

Find the maximum possible value of the win rate in the games from the l-th through the r-th.

Constraints

• 1 \leq K \leq N \leq 10^6
• N and K are integers.
• S is a string of length N consisting of o and x.
• S contains at least K occurrences of o.

Sample Input 1

10 4
oxooxoxxox

Sample Output 1

0.6666666666

Choosing (1,6) as (l,r) gives a win rate of \frac{2}{3}.
It is impossible to make the win rate larger than this while satisfying the conditions.

Sample Input 2

5 1
xxoxx

Sample Output 2

1

Sample Input 3

16 10
xxxoxooooxoxoooo

Sample Output 3

0.769230769230769

Problem Statement

You are given a sequence of positive integers A of length N.
There is a weighted complete undirected graph with N vertices.
The vertices are numbered 1,2,\dots,N.
For i and j satisfying 1 \leq i \lt j \leq N, the weight of the edge connecting vertices i and j is the greatest common divisor of A_i and A_j.
Find the maximum possible value of the sum of the weights of the edges included in a spanning tree of this graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6
• All input values are integers.

Sample Input 1

3
4 6 12

Sample Output 1

10

The complete graph has the following three edges.

• The edge connecting vertices 1 and 2 with weight 2
• The edge connecting vertices 1 and 3 with weight 4
• The edge connecting vertices 2 and 3 with weight 6

Choosing the second and third edges gives a sum of weights of 10, which is the maximum possible value.

Sample Input 2

5
5 14 15 21 42

Sample Output 2

43

Sample Input 3

2
1 1000000

Sample Output 3

1

Problem Statement

You are given K strings S_1, S_2, \ldots, S_K consisting of a and b. Also, for an integer i > K, define the string S_i as the concatenation of S_{i-1}, S_{i-2}, \ldots, S_{i-K} in this order.

You perform the following operation on a string T.

• Perform the following operations for j = 1, 2, \ldots, |S_N| in order, where |S_N| is the length of S_N.
  • If the j-th character of S_N is a, move the first character of T to the end.
  • If the j-th character of S_N is b, reverse T entirely. That is, reverse the order of the characters of T.

Find the string T after the series of operations.

Constraints

• 2 \leq K \leq 100
• K is an integer.
• S_i is a non-empty string consisting of a and b. (1 \leq i \leq K)
• The sum of the lengths of S_1, S_2, \ldots, S_K is at most 2 \times 10^5.
• 1 \leq N \leq 10^{18}
• N is an integer.
• T is a string consisting of lowercase English letters with length between 1 and 2 \times 10^5, inclusive.

Sample Input 1

3
a
aa
b
5
abc

Sample Output 1

cab

S_1 = a, S_2 = aa, S_3 = b, S_4 = baaa, and S_5 = baaabaa.

Through the operations, the string T changes as abc → cba → bac → acb → cba → abc → bca → cab, so the string T after the series of operations is cab.

Sample Input 2

2
a
ba
6
fibonacci

Sample Output 2

canobific

Sample Input 3

5
aba
a
bb
ba
aab
1000000000000000000
abcba

Sample Output 3

aabcb