Problem Statement

You are given a string S of length N consisting of lowercase English letters, along with lowercase English letters c_1 and c_2.

Find the string obtained by replacing every character of S that is not c_1 with c_2.

Constraints

• 1\le N\le 100
• N is an integer.
• c_1 and c_2 are lowercase English letters.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3 b g
abc

Sample Output 1

gbg

Replacing a and c (which are not b) with g in S= abc results in gbg, so print gbg.

Sample Input 2

1 s h
s

Sample Output 2

s

It is possible that the resulting string after replacement is the same as the original string.

Sample Input 3

7 d a
atcoder

Sample Output 3

aaaadaa

Sample Input 4

10 b a
acaabcabba

Sample Output 4

aaaabaabba

Problem Statement

You are given a positive integer N.

For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.

That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Constraints

• N is an integer between 1 and 10, inclusive.

Sample Input 1

3

Sample Output 1

-20

• When i=1: (-1)^i\times i^3=-1.
• When i=2: (-1)^i\times i^3=8.
• When i=3: (-1)^i\times i^3=-27.

Therefore, output -1 + 8 - 27 = -20.

Sample Input 2

9

Sample Output 2

-425

Sample Input 3

10

Sample Output 3

575

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:

• for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.

Constraints

• 1 \leq N \leq 100
• Each element of A and B is 0 or 1.
• All values in the input are integers.

Sample Input 1

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

Sample Output 1

Yes

Initially, A is :

0 1 1
1 0 0
0 1 0

After performing the operation once, A is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, A is :

0 1 0
0 0 1
1 1 0

Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.

Sample Input 2

2
0 0
0 0
1 1
1 1

Sample Output 2

Yes

Sample Input 3

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

Sample Output 3

No

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

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 simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertices 1,2,\ldots,N and edges 1,2,\ldots,M, respectively, and edge i connects vertices U_i and V_i.
You can move bidirectionally between vertices connected by an edge in time 1.

Additionally, each vertex is either safe or dangerous, and this state is given by a string S of length N consisting of S and D.
Specifically, vertex i is safe when the i-th character (1\leq i\leq N) of S is S, and vertex i is dangerous when it is D.
It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex v, find the following value:

The minimum possible time to start from some safe vertex, pass through v, and move to a safe vertex different from the starting vertex.

Constraints

• 3\leq N\leq 2\times 10^5
• N-1\leq M\leq 2\times 10^5
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i\neq j, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.
• S is a string of length N consisting of S and D.
• N,M,U_i,V_i are all integers.
• G is connected.
• There are at least two safe vertices.
• There is at least one dangerous vertex.

Sample Input 1

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

Sample Output 1

2
3

The dangerous vertices are (in ascending order of vertex number) vertices 3 and 4.

For vertex 3, moving from vertex 1 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 2, and this is the minimum.
Therefore, print 2 on the 1st line.

For vertex 4, moving from vertex 1 \to vertex 3 \to vertex 4 \to vertex 5 (for example) satisfies the condition.
The time required for this movement is 3, and there is no way to move that satisfies the condition with time 2 or less, so this is the minimum.
Therefore, print 3 on the 2nd line.

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

The dangerous vertex is vertex 3.

Moving from vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 3, and this is the minimum.
Note that movements such as vertex 2 \to vertex 3 \to vertex 2 do not satisfy the condition that the destination is "different from the starting vertex".

Problem Statement

You are given an integer N and a string S of length N-1 consisting of L and R.

Consider writing integers into N cells arranged in a row so that the following conditions are satisfied:

• Every cell has one integer written on it.
• Every integer 1,2,\dots,N appears in exactly one cell.
• When the i-th character of S is L, i+1 is written to the left of i.
• When the i-th character of S is R, i+1 is written to the right of i.

Let C_i be the number of integers that can be written in the i-th cell from the left. Find C_1,C_2,\dots,C_N.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 20000
• 2 \le N \le 3 \times 10^5
• S is a string of length N-1 consisting of L and R.
• For a single input, the sum of N does not exceed 3 \times 10^5.

Sample Input 1

5
5
RLLR
3
RL
2
L
3
RR
20
RLLLLLLLLRLRRLLLRLR

Sample Output 1

2 4 3 4 2
2 2 1
1 1
1 1 1
5 9 13 14 15 17 18 19 19 20 20 19 19 18 17 16 14 12 9 5

This input contains five test cases.

• For the first test case, there are 11 possible ways to fill the cells as follows:
  • (1,4,3,2,5)
  • (1,4,3,5,2)
  • (1,4,5,3,2)
  • (4,1,3,2,5)
  • (4,1,3,5,2)
  • (4,1,5,3,2)
  • (4,3,1,2,5)
  • (4,3,1,5,2)
  • (4,3,5,1,2)
  • (4,5,1,3,2)
  • (4,5,3,1,2)
• From this, each value of C_i is determined as follows:
  • The integers that can be written in the 1-st cell from the left are 1,4, which is two integers.
  • The integers that can be written in the 2-nd cell from the left are 1,3,4,5, which is four integers.
  • The integers that can be written in the 3-rd cell from the left are 1,3,5, which is three integers.
  • The integers that can be written in the 4-th cell from the left are 1,2,3,5, which is four integers.
  • The integers that can be written in the 5-th cell from the left are 2,5, which is two integers.
• For the second test case, there are two possible ways to fill the cells as follows:
  • (1,3,2)
  • (3,1,2)
• For the third test case, there is one possible way to fill the cells as follows:
  • (2,1)
• For the fourth test case, there is one possible way to fill the cells as follows:
  • (1,2,3)