Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

• N is an integer between 1 and 7 (inclusive).
• S is a string of length 7 consisting of o and x.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

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

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

• 0 \leq S \leq 100
• 0 \leq T \leq 10000
• S and T are integers.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

Problem Statement

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

1. Mark square 0.
2. Repeat the following steps i - iii (N-1) times.
   1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
   2. While square x is marked, repeat replacing x with (x+1) \bmod N.
   3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

• 1\leq T \leq 10^5
• 1\leq K\leq N \leq 10^9
• 1\leq D \leq 10^9
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

0
2
1
3
0
3
1
4
2

If N=4 and D=2, Snuke marks the squares as follows.

1. Mark square 0.
2. (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
   (2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
   (3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

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

Sample Input 1

3
3 1 4

Sample Output 1

8

The sought value is

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8.

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

53

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

592622

Problem Statement

N players, player 1, player 2, ..., player N, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are N teams in total.

The tournament has a total of N-1 matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each i = 1, 2, \ldots, N-1, the i-th match proceeds as follows.

• The team with player p_i goes first, and the team with player q_i goes second.
• Let a and b be the numbers of players in the first and second teams, respectively. The first team wins with probability \frac{a}{a+b}, and the second team wins with probability \frac{b}{a+b}.
• Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the N players, print the expected number of times the team with that player wins throughout the tournament, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• Just before the i-th match, player p_i and player q_i belong to different teams.
• All input values are integers.

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player x_1, player x_2, \ldots, player x_k as team \lbrace x_1, x_2, \ldots, x_k \rbrace.

• The first match is played by team \lbrace 1 \rbrace, with player 1, and team \lbrace 2 \rbrace, with player 2. Team \lbrace 1 \rbrace wins with probability \frac{1}{2}, and team \lbrace 2 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 1, 2 \rbrace.
• The second match is played by team \lbrace 4 \rbrace, with player 4, and team \lbrace 3 \rbrace, with player 3. Team \lbrace 4 \rbrace wins with probability \frac{1}{2}, and team \lbrace 3 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 3, 4 \rbrace.
• The third match is played by team \lbrace 5 \rbrace, with player 5, and team \lbrace 3, 4 \rbrace, with player 3. Team \lbrace 5 \rbrace wins with probability \frac{1}{3}, and team \lbrace 3, 4 \rbrace wins with probability \frac{2}{3}. Then, the two teams are combined into a single team \lbrace 3, 4, 5 \rbrace.
• The fourth match is played by team \lbrace 1, 2 \rbrace, with player 1, and team \lbrace 3, 4, 5 \rbrace, with player 4. Team \lbrace 1, 2 \rbrace wins with probability \frac{2}{5}, and team \lbrace 3, 4, 5 \rbrace wins with probability \frac{3}{5}. Then, the two teams are combined into a single team \lbrace 1, 2, 3, 4, 5 \rbrace.

The expected numbers of times the teams with players 1, 2, 3, 4, 5 win throughout the tournament, E_1, E_2, E_3, E_4, E_5, are \frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}, respectively.

Sample Input 2

15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8

Sample Output 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290