Problem Statement

There are three dice, each with six faces.
Each die has 1,2,3,4,5,6 written on its faces.

When these dice are rolled simultaneously, is it possible for the sum of the rolled values to be X?

Constraints

• X is an integer between 1 and 20, inclusive.

Sample Input 1

15

Sample Output 1

Yes

For example, if the rolled values are 4,5,6, the sum is 15.

Sample Input 2

2

Sample Output 2

No

Problem Statement

There are three dice, each with six faces.
The j-th face of the i-th die has A_{i,j} written on it.
For each die, each face comes up with probability \frac{1}{6}.

When these dice are rolled simultaneously, find the probability that the values 4,5,6 each appear exactly once.

Constraints

• A_{i,j} is an integer between 1 and 6, inclusive.

Sample Input 1

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

Sample Output 1

0.0277777778

The desired probability is \frac{1}{36}. An output such as 0.027778 is also accepted.

Sample Input 2

4 5 6 4 5 6
4 4 5 5 6 6
6 5 4 4 5 6

Sample Output 2

0.2222222222

The desired probability is \frac{2}{9}.

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty substrings of S in which no two adjacent characters are the same, modulo 998244353.

Two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Constraints

• S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of a, b, c.

Sample Input 1

abbc

Sample Output 1

6

The substrings in which no two adjacent characters are the same are the following six:

• a (from the 1st to the 1st character of S)
• b (from the 2nd to the 2nd character of S)
• b (from the 3rd to the 3rd character of S)
• c (from the 4th to the 4th character of S)
• ab (from the 1st to the 2nd character of S)
• bc (from the 3rd to the 4th character of S)

Note that, as with the 2nd and 3rd entries, two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

760

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty subsequences of S in which no two adjacent characters are the same, modulo 998244353.

Two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.

Constraints

• S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of a, b, c.

Sample Input 1

abbc

Sample Output 1

11

The subsequences in which no two adjacent characters are the same are the following 11:

• a (the 1st character of S)
• b (the 2nd character of S)
• b (the 3rd character of S)
• c (the 4th character of S)
• ab (the 1st, 2nd characters of S)
• ab (the 1st, 3rd characters of S)
• ac (the 1st, 4th characters of S)
• bc (the 2nd, 4th characters of S)
• bc (the 3rd, 4th characters of S)
• abc (the 1st, 2nd, 4th characters of S)
• abc (the 1st, 3rd, 4th characters of S)

Note that, as with the 2nd and 3rd entries, two subsequences are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

378217423

Output the count modulo 998244353.

Problem Statement

The Kingdom of AtCoder has N cities, called city 1,2,\dots,N. There are M bidirectional roads connecting pairs of cities, where the i-th road connects cities U_i and V_i. Any pair of cities can be reached from each other by traversing some roads.

In the Kingdom of AtCoder, a week consists of W days. A week proceeds through days 1,2,\dots,W, and the day after day W is day 1.

Each city has certain days of the week that are holidays. The holiday information for city i is given as a string S_i of length W: if the j-th character of S_i is o, day j is a holiday; if it is x, day j is a weekday.

Takahashi chooses a city he likes and visits it at noon on day 1. Each night thereafter, he repeatedly chooses to either stay in his current city or move to a city directly connected by a road. Output Yes if it is possible for him to keep moving so that the city he is in at noon every day is a holiday, and No otherwise.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• N-1 \leq M \leq 10^5
• 1 \leq U_i \lt V_i \leq N
• Any pair of cities can be reached from each other by traversing some roads.
• 2 \leq W \leq 10
• T,N,M,U_i,V_i,W are integers.
• S_i is a string of length W consisting of o, x.
• The sum of N over all test cases is at most 10^5.
• The sum of M over all test cases is at most 10^5.

Sample Input 1

3
4 4
1 2
1 4
2 4
2 3
3
xxo
xox
oxo
oxx
1 0
4
oooo
5 5
1 4
2 3
4 5
3 4
2 5
7
oxxxxxx
xxoxxxo
xxxoxox
xoxxoxx
oxxxoxx

Sample Output 1

Yes
Yes
No

For the first test case, for example, the condition can be satisfied by repeatedly moving along cities 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \cdots. Alternatively, the condition can also be satisfied by repeatedly moving along cities 3 \to 2 \to 3 \to 3 \to 2 \to 3 \to \cdots.

For the second test case, the condition can be satisfied by staying in city 1 indefinitely.

For the third test case, it is impossible to keep moving while satisfying the condition.

Problem Statement

Takahashi is trying to decide his schedule for N days. Initially, none of the days are holidays.

He can repeat either of the following operations any number of times:

• Choose an integer i between 1 and N, inclusive, and make day i a holiday. This operation costs A_i.
• Choose an integer i between 2 and N-1, inclusive, such that both day i-1 and day i+1 are already holidays, and make day i a holiday. This operation is free.

Find the minimum total cost required to create a consecutive block of K or more holidays.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.
• The sum of N over all test cases is at most 2\times 10^5.

Sample Input 1

3
5 2
3 1 4 1 5
6 4
24 3 22 39 4 29
15 7
220651272 302798780 874479994 657822311 613294668 479624013 241168404 610547619 762548286 256160531 823041612 951553052 226556081 649525901 153805947

Sample Output 1

2
29
1902064780

For the first test case, a consecutive block of at least two holidays can be created by performing operations as follows:

• Make day 2 a holiday using the first type of operation. This costs 1.
• Make day 4 a holiday using the first type of operation. This costs 1.
• Make day 3 a holiday using the second type of operation. This is free.

The total cost of this sequence of operations is 2. It is impossible to create a consecutive block of two or more holidays with a cost less than 2, so output 2.

Problem Statement

Takahashi is creating a work schedule for N days by designating each day as a workday or a holiday.

You are given a string S of length N representing the constraints on work days. If the i-th character of S is x, day i must be a workday. If it is ., day i can be either a workday or a holiday.

There are 2^q valid work schedules satisfying the constraints, where q is the number of . characters in S. For each k=1,2,\dots,N, solve the following problem:

Among the 2^q valid work schedules satisfying the constraints, find the number, modulo 998244353, of schedules in which the longest consecutive block of holidays is exactly k days.

Constraints

• N is an integer between 1 and 2 \times 10^5, inclusive.
• S is a string of length N consisting of ., x.

Sample Input 1

5
.x...

Sample Output 1

9
4
2
0
0

Denoting holidays as o, the valid work schedules are as follows:

• k=1: oxxxx, oxoxx, oxoxo, oxxox, oxxxo, xxoxx, xxoxo, xxxox, xxxxo
• k=2: oxoox, oxxoo, xxoox, xxxoo
• k=3: oxooo, xxooo

Sample Input 2

7
.......

Sample Output 2

33
47
27
12
5
2
1

Sample Input 3

20
.....x...x..........

Sample Output 3

9359
75312
94664
46840
23680
7168
3072
1280
512
256
0
0
0
0
0
0
0
0
0
0