Problem Statement

Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.

Constraints

• 1 \le |S| \le 15
• S consists of English lowercase letters, English uppercase letters, ,, and !.

Sample Input 1

Hello,World!

Sample Output 1

AC

The string S perfectly matches Hello,World!.

Sample Input 2

Hello,world!

Sample Output 2

WA

The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.

Sample Input 3

Hello!World!

Sample Output 3

WA

Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

• N is an integer satisfying 1 \le N \le 10^{18}.

Sample Input 1

6

Sample Output 1

2

• k=2 satisfies 2^2=4 \le 6.
• For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

1

Sample Output 2

0

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

59

The input value may not fit into a 32-bit integer.

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

Given a sequence of N positive integers A=(A_1,A_2,\dots,A_N), find every integer k between 1 and M (inclusive) that satisfies the following condition:

• \gcd(A_i,k)=1 for every integer i such that 1 \le i \le N.

Constraints

• All values in input are integers.
• 1 \le N,M \le 10^5
• 1 \le A_i \le 10^5

Sample Input 1

3 12
6 1 5

Sample Output 1

3
1
7
11

For example, 7 has the properties \gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1, so it is included in the set of integers satisfying the requirement.
On the other hand, 9 has the property \gcd(6,9)=3, so it is not included in that set.
We have three integers between 1 and 12 that satisfy the condition: 1, 7, and 11. Be sure to print them in ascending order.

Problem Statement

AtCoder in another world holds 10 types of contests called AAC, ..., AJC. There will be N contests from now on.
The types of these N contests are given to you as a string S: if the i-th character of S is x, the i-th contest will be AxC.
AtCoDeer will choose and participate in one or more contests from the N so that the following condition is satisfied.

• In the sequence of contests he will participate in, the contests of the same type are consecutive.
  • Formally, when AtCoDeer participates in x contests and the i-th of them is of type T_i, for every triple of integers (i,j,k) such that 1 \le i < j < k \le x, T_i=T_j must hold if T_i=T_k.

Find the number of ways for AtCoDeer to choose contests to participate in, modulo 998244353.
Two ways to choose contests are considered different when there is a contest c such that AtCoDeer participates in c in one way but not in the other.

Constraints

• 1 \le N \le 1000
• |S|=N
• S consists of uppercase English letters from A through J.

Sample Input 1

4
BGBH

Sample Output 1

13

For example, participating in the 1-st and 3-rd contests is valid, and so is participating in the 2-nd and 4-th contests.
On the other hand, participating in the 1-st, 2-nd, 3-rd, and 4-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple (i,j,k)=(1,2,3).
Additionally, it is not allowed to participate in zero contests.
In total, there are 13 valid ways to participate in some contests.

Sample Input 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

Sample Output 2

330219020

Be sure to find the count modulo 998244353.

Problem Statement

Given are N distinct points in a two-dimensional plane. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

Let us define the distance between two points i and j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): the smaller of the difference in the x-coordinates and the difference in the y-coordinates.

Find the maximum distance between two different points.

Constraints

• 2 \leq N \leq 200000
• 0 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points 1 and 2, between Points 1 and 3, and between Points 2 and 3 are 2, 4, and 1, respectively, so your output should be 4.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801

Problem Statement

There are N candies arranged in a row from left to right.
Each candy has one of the following 10^9 colors: Color 1, Color 2, \ldots, Color 10^9.
For each i = 1, 2, \ldots, N, the i-th candy from the left has Color c_i.

Takahashi will choose K from the N candies and get those K candies.
There are \binom{N}{K} ways to choose K from the N candies, where \binom{N}{K} is a binomial coefficient. Takahashi will randomly select one of these \binom{N}{K} ways with equal probability.

Because Takahashi wants to eat colorful candies, the more variety of colors his candies have, the happier he will be.
For each scenario K = 1, 2, \ldots, N, find the expected value of the number of different colors Takahashi's candies will have.
We can prove that the sought value is a rational number. Print this rational number modulo 998244353, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 998244353 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and P - 1, inclusive, that satisfies xz \equiv y \pmod{998244353}.

Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 2 2

Sample Output 1

1
665496237
2

When K = 1, he will get the 1-st candy, 2-nd candy, or 3-rd candy. In any case, his candy will have one color, so the expected value of the number of different colors is 1.

When K = 2, he will get the 1-st and 2-nd candies, 2-nd and 3-rd candies, or 1-st and 3-rd candies.

• If he gets the 1-st and 2-nd candies, they have two different colors.
• If he gets the 2-nd and 3-rd candies, they have one color.
• If he gets the 1-st and 3-rd candies, they have two different colors.

Thus, the expected value of the number of different colors is \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}.
Be sure to print it modulo 998244353 as described in Notes.

When K = 3, he will always get the 1-st, 2-nd, and 3-rd candies, which have two different colors, so the expected value of the number of different colors is 2.

Sample Input 2

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

Sample Output 2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

Problem Statement

Takahashi, a cabbage farmer, has grown N brands of cabbages, called Brand 1 through Brand N. He has A_i heads of cabbage of Brand i (1 \leq i \leq N). Here, all heads of cabbages are distinguishable.
He has M clients called Company 1 through Company M. Company j (1 \leq j \leq M) has ordered B_j heads of cabbages.
Different companies accept different brands of cabbages. For each pair i, j (1 \leq i \leq N, 1 \leq j \leq M),

• if c_{i, j} = 1, cabbage of Brand i can be shipped to Company j;
• if c_{i, j} = 0, cabbage of Brand i cannot be shipped to Company j.

Takahashi will be called a Cabbage Master if he succeeds in deciding where to ship the heads of cabbages so that B_j or more heads of cabbages will be shipped to every company j (1 \leq j \leq M).

Snuke has decided to choose and eat zero or more heads of cabbages so that Takahashi cannot get the title of Cabbage Master, regardless of where to ship his cabbages. He does not like cabbage very much, so he will choose to eat the minimum number of heads of cabbages needed to achieve his objective.

Print the number of heads of cabbages Snuke will eat, and the number of ways, modulo 998244353, for Snuke to choose heads of cabbages to eat. Two ways to choose heads of cabbages are considered different when there is a head of cabbage that is eaten in one way but not in the other. Here, remember that any two heads of cabbages are distinguishable even if they are of the same brand.

Constraints

• 1 \leq N \leq 20
• 1 \leq M \leq 10^4
• 1 \leq A_i \leq 10^5
• 1 \leq B_j \leq 10^5
• c_{i, j} \in \lbrace 0, 1 \rbrace
• For every 1 \leq j \leq M, there exists 1 \leq i \leq N such that c_{i, j} = 1.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2 6

Snuke will eat two heads of cabbages to prevent Takahashi from becoming a Cabbage Master. There are six such ways to choose heads of cabbages to eat, as shown below, where (i, j) denotes the j-th head of cabbage of Brand i.

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

Sample Input 2

1 1
3
4
1

Sample Output 2

0 1

It is possible that Takahashi is unable to become a Cabbage Master even if Snuke eats no cabbage. Then, Snuke will eat zero heads of cabbages, and there is just one way for him to choose heads of cabbages to eat: do not eat anything.

Sample Input 3

1 3
100
30 30 30
1 1 1

Sample Output 3

11 892328666

For the number of ways for Snuke to choose heads of cabbages to eat, be sure to print it modulo 998244353.