Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

• 2 \le |S| \le 20
• S consists of lowercase English letters.
• S ends with er or ist.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

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

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq D \leq 100
• N and D are integers.
• S_i is a string of length D consisting of o and x.

Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.

Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)

Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.

Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq K \leq 10^9
• 1 \leq A_i,B_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

• k is represented as k=p \times q^3 with primes p<q.

How many integers less than or equal to N are "similar to 250"?

Constraints

• N is an integer between 1 and 10^{18} (inclusive)

Sample Input 1

250

Sample Output 1

2

• 54 = 2 \times 3^3 is "similar to 250".
• 250 = 2 \times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

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

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

• (1,2)
• (1,2,3)
• (2,3,4)
• (3,4,5)
• (1,2,3,4)
• (2,3,4,5)
• (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

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

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

• 1 x c : replace the x-th character of S by the character c.
• 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.

Constraints

• 1\leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq Q \leq 10^5
• For each query of the first kind, 1 \leq x \leq N.
• For each query of the first kind, c is a lowercase English letter.
• For each query of the second kind, 1 \leq l \leq r \leq N.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes

• In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
• In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
• The 3-rd query sets the 5-th character of S to e, making S abcdef.
• In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.