A - Jogging

### 制約

• 1 \leq A, B, C, D, E, F, X \leq 100
• 入力は全て整数

### 入力

A B C D E F X


### 入力例 1

4 3 3 6 2 5 10


### 出力例 1

Takahashi


• 高橋君は 4 秒間歩き、3 秒間休んだ後、再び 3 秒間歩く。合計 (4 + 3) \times 3 = 21 メートル歩く。
• 青木君は 6 秒間歩き、4 秒間休む。合計 6 \times 2 = 12 メートル歩く。

### 入力例 2

3 1 4 1 5 9 2


### 出力例 2

Aoki


### 入力例 3

1 1 1 1 1 1 1


### 出力例 3

Draw


Score : 100 points

### Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

### Constraints

• 1 \leq A, B, C, D, E, F, X \leq 100
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

A B C D E F X


### Output

When X seconds have passed since they simultaneously started to jog, if Takahashi goes ahead of Aoki, print Takahashi; if Aoki goes ahead of Takahashi, print Aoki; if they have advanced the same distance, print Draw.

### Sample Input 1

4 3 3 6 2 5 10


### Sample Output 1

Takahashi


During the first 10 seconds after they started to jog, they move as follows.

• Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
• Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

### Sample Input 2

3 1 4 1 5 9 2


### Sample Output 2

Aoki


### Sample Input 3

1 1 1 1 1 1 1


### Sample Output 3

Draw

B - Perfect String

### 問題文

• 英大文字が文字列の中に現れる。
• 英小文字が文字列の中に現れる。
• 全ての文字が相異なる。

### 制約

• 1 \le |S| \le 100
• S は英大文字と英小文字からなる文字列である。

### 入力

S


### 出力

S が素晴らしい文字列ならば Yes を、そうでないならば No を出力せよ。

### 入力例 1

AtCoder


### 出力例 1

Yes


AtCoder は、英大文字が含まれ、英小文字も含まれ、かつ全ての文字が相異なるため素晴らしい文字列です。

### 入力例 2

Aa


### 出力例 2

Yes


Aa は違う文字であることに注意してください。この文字列は素晴らしい文字列です。

### 入力例 3

atcoder


### 出力例 3

No


### 入力例 4

Perfect


### 出力例 4

No


2 文字目と 5 文字目が等しいため、素晴らしい文字列ではありません。

Score : 200 points

### Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

### Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

### Input

Input is given from Standard Input in the following format:

S


### Output

If S is a wonderful string, print Yes; otherwise, print No.

### Sample Input 1

AtCoder


### Sample Output 1

Yes


AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

### Sample Input 2

Aa


### Sample Output 2

Yes


Note that A and a are different characters. This string is a wonderful string.

### Sample Input 3

atcoder


### Sample Output 3

No


It is not a wonderful string because it does not contain an uppercase English alphabet.

### Sample Input 4

Perfect


### Sample Output 4

No


It is not a wonderful string because the 2-nd and the 5-th characters are the same.

C - Just K

### 問題文

S_1,S_2,\dots,S_N から文字列を好きな個数選ぶことを考えます。

このとき、「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。

### 制約

• 1 \le N \le 15
• 1 \le K \le N
• N,K は整数
• S_i は英小文字からなる空でない文字列である。
• 1 \le i \le N を満たす整数 i に対し、S_i に同じ文字は 2 個以上含まれない。
• i \neq j ならば S_i \neq S_j である。

### 入力

N K
S_1
S_2
\vdots
S_N


### 入力例 1

4 2
abi
aef
bc
acg


### 出力例 1

3


S_1,S_3,S_4 を選んだ場合、a,b,c がちょうど 2 個の文字列に含まれます。

4 個以上の文字がちょうど 2 個の文字列に含まれるような選び方は存在しないため、答えは 3 です。

### 入力例 2

2 2
a
b


### 出力例 2

0


### 入力例 3

5 2
abpqxyz
az
pq
bc
cy


### 出力例 3

7


Score : 300 points

### Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

### Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

### Input

Input is given from Standard Input in the following format:

N K
S_1
S_2
\vdots
S_N


### Sample Input 1

4 2
abi
aef
bc
acg


### Sample Output 1

3


When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

### Sample Input 2

2 2
a
b


### Sample Output 2

0


You cannot choose the same string more than once.

### Sample Input 3

5 2
abpqxyz
az
pq
bc
cy


### Sample Output 3

7

D - Index Trio

### 問題文

• 1 \leq i, j, k \leq N
• \frac{A_i}{A_j} = A_k

### 制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• 入力は全て整数

### 入力

N
A_1 \ldots A_N


### 入力例 1

3
6 2 3


### 出力例 1

2


(i, j, k) = (1, 2, 3), (1, 3, 2) が条件を満たします。

### 入力例 2

1
2


### 出力例 2

0


### 入力例 3

10
1 3 2 4 6 8 2 2 3 7


### 出力例 3

62


Score : 400 points

### Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N.

Find the number of triplets of integers (i, j, k) satisfying all of the conditions below.

• 1 \leq i, j, k \leq N
• \frac{A_i}{A_j} = A_k

### Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N


### Sample Input 1

3
6 2 3


### Sample Output 1

2


(i, j, k) = (1, 2, 3), (1, 3, 2) satisfy the conditions.

### Sample Input 2

1
2


### Sample Output 2

0


### Sample Input 3

10
1 3 2 4 6 8 2 2 3 7


### Sample Output 3

62

E - RLE

### 問題文

• X を異なる文字が隣り合っている部分で分割する。
• 分割した各文字列 Y に対して、YY を構成する文字と Y の長さを繋げた文字列に置き換える。
• 元の順番を保ったまま、置き換えた文字列をすべて繋げる。

### 制約

• 1 \le N \le 3000
• 10^8 \le P \le 10^9
• N,P は整数
• P は素数

### 入力

N P


### 入力例 1

3 998244353


### 出力例 1

26


1,2,3 文字目が全て等しい文字列のみが条件を満たします。

### 入力例 2

2 998244353


### 出力例 2

0


aaa2 のように、長さが等しいものは条件を満たさないことに注意してください。

### 入力例 3

5 998244353


### 出力例 3

2626


aaabbaaaaa などが条件を満たします。

### 入力例 4

3000 924844033


### 出力例 4

607425699


Score : 500 points

### Problem Statement

Consider the following procedure of, given a string X consisting of lowercase English alphabets, obtaining a new string:

• Split the string X off at the positions where two different characters are adjacent to each other.
• For each string Y that has been split off, replace Y with a string consisting of the character which Y consists of, followed by the length of Y.
• Concatenate the replaced strings without changing the order.

For example, aaabbcccc is divided into aaa,bb,cccc, which are replaced by a3,b2,c4, respectively, which in turn are concatenated without changing the order, resulting in a3b2c4.If the given string is aaaaaaaaaa , the new string is a10 .

Find the number, modulo P, of strings S of lengths N consisting of lowercase English alphabets, such that the length of T is smaller than that of S, where T is the string obtained by the procedure above against the string S.

### Constraints

• 1 \le N \le 3000
• 10^8 \le P \le 10^9
• N and P are integers.
• P is a prime.

### Input

Input is given from Standard Input in the following format:

N P


### Sample Input 1

3 998244353


### Sample Output 1

26


Those strings of which the 1-st, 2-nd, and 3-rd characters are all the same satisfy the condition.

For example, aaa becomes a3, which satisfies the condition, while abc becomes a1b1c1, which does not.

### Sample Input 2

2 998244353


### Sample Output 2

0


Note that if a string is transformed into another string of the same length, such as aa that becomes a2, it does not satisfy the condition.

### Sample Input 3

5 998244353


### Sample Output 3

2626


Strings like aaabb and aaaaa satisfy the condition.

### Sample Input 4

3000 924844033


### Sample Output 4

607425699


Find the number of strings satisfying the condition modulo P.

F - Ignore Operations

### 問題文

N 個の操作があります。i \, (1 \leq i \leq N) 個目の操作は整数 t_i, y_i を用いて以下のように表されます。

• t_i = 1 のとき、xy_i で置き換える。
• t_i = 2 のとき、xx + y_i で置き換える。

### 制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• t_i \in \{1,2\} \, (1 \leq i \leq N)
• |y_i| \leq 10^9 \, (1 \leq i \leq N)
• 入力は全て整数

### 入力

N K
t_1 y_1
\vdots
t_N y_N


### 入力例 1

5 1
2 4
2 -3
1 2
2 1
2 -3


### 出力例 1

3


5 個目の操作を無視すると、x0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 と変化し、最終的な x の値は 3 となります。これが最大です。

### 入力例 2

1 0
2 -1000000000


### 出力例 2

-1000000000


### 入力例 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3


### 出力例 3

15


Score : 500 points

### Problem Statement

Takahashi has an integer x. Initially, x = 0.

There are N operations. The i-th operation (1 \leq i \leq N) is represented by two integers t_i and y_i as follows:

• If t_i = 1, replace x with y_i.
• If t_i = 2, replace x with x + y_i.

Takahashi may skip any number between 0 and K (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of x.

### Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• t_i \in \{1,2\} \, (1 \leq i \leq N)
• |y_i| \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N K
t_1 y_1
\vdots
t_N y_N


### Sample Input 1

5 1
2 4
2 -3
1 2
2 1
2 -3


### Sample Output 1

3


If he skips the 5-th operation, x changes as 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3, so x results in 3. This is the maximum.

### Sample Input 2

1 0
2 -1000000000


### Sample Output 2

-1000000000


### Sample Input 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3


### Sample Output 3

15

G - Xor Cards

### 問題文

N 枚のカードがあり、1, \dots, N の番号が付けられています。カード i \, (1 \leq i \leq N) の表には整数 A_i、裏には整数 B_i が書かれています。

• a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

### 制約

• 1 \leq N \leq 1000
• 0 \leq K \lt 2^{30}
• 0 \leq A_i, B_i \lt 2^{30} \, (1 \leq i \leq N)
• 入力は全て整数

### 入力

N K
A_1 B_1
\vdots
A_N B_N


### 入力例 1

4 2
1 1
3 2
2 2
0 1


### 出力例 1

3


カード 1, 2 を選ぶことで、表に書かれた整数の排他的論理和は 2、裏に書かれた整数の排他的論理和は 3 となり、これが最大です。

### 入力例 2

1 2
3 4


### 出力例 2

-1


### 入力例 3

10 326872757
487274679 568989827
267359104 968688210
669234369 189421955
1044049637 253386228
202278801 233212012
436646715 769734012
478066962 376960084
491389944 1033137442
214977048 1051768288
803550682 1053605300


### 出力例 3

1064164329


Score : 600 points

### Problem Statement

There are N cards numbered 1, \dots, N. Card i \, (1 \leq i \leq N) has an integer A_i written on the front and an integer B_i written on the back.

Consider choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most K. Find the maximum possible exclusive logical sum of the integers written on the back of the chosen cards.

What is the exclusive logical sum? The exclusive logical sum a \oplus b of two integers a and b is defined as follows.
• The 2^k's place (k \geq 0) in the binary notation of a \oplus b is 1 if exactly one of the 2^k's places in the binary notation of a and b is 1; otherwise, it is 0.
For example, 3 \oplus 5 = 6 (In binary notation: 011 \oplus 101 = 110).
In general, the exclusive logical sum of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). We can prove that it is independent of the order of p_1, \dots, p_k.

### Constraints

• 1 \leq N \leq 1000
• 0 \leq K \lt 2^{30}
• 0 \leq A_i, B_i \lt 2^{30} \, (1 \leq i \leq N)
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N K
A_1 B_1
\vdots
A_N B_N


### Output

Print the maximum possible exclusive logical sum of the integers written on the back of the chosen cards when choosing one or more cards so that the exclusive logical sum of the integers written on the front of the chosen cards is at most K. If it is impossible to choose cards in such way, print -1 instead.

### Sample Input 1

4 2
1 1
3 2
2 2
0 1


### Sample Output 1

3


By choosing Cards 1 and 2, the exclusive logical sum of the integers written on the front of them is 2, and that on the back of them is 3, which is the maximum.

### Sample Input 2

1 2
3 4


### Sample Output 2

-1


It is impossible to choose cards so that the condition is satisfied.

### Sample Input 3

10 326872757
487274679 568989827
267359104 968688210
669234369 189421955
1044049637 253386228
202278801 233212012
436646715 769734012
478066962 376960084
491389944 1033137442
214977048 1051768288
803550682 1053605300


### Sample Output 3

1064164329

Ex - Dye Color

### 問題文

N 個のボールがあり、ボールには 1 から N の番号がついています。初め、ボール i は色 A_i で塗られています。

• N 個のボールからなる集合の部分集合(空集合を含む)は 2^N 個あるが、そこから 1 個の集合を一様ランダムに選ぶ。選んだ集合に含まれるボールの index を昇順に X_1,X_2,...,X_K とする。次に、(1,2,\dots,N) から K 個を選んで得られる順列を一様ランダムに 1 個選び P=(P_1,P_2,\dots,P_K) とする。そして、1 \le i \le K を満たす整数 i に対し、ボール X_i の色を P_i に変更する。

ここで、(1,2,\dots,N) から K 個を選んで得られる順列とは、1 以上 N 以下の整数 K 個からなる数列であって、要素が相異なるもののことです。

### 制約

• 2 \le N \le 2000
• 1 \le A_i \le N
• 入力は全て整数である。

### 入力

N
A_1 A_2 \dots A_N


### 入力例 1

2
1 2


### 出力例 1

4


### 入力例 2

3
1 1 1


### 出力例 2

0


### 入力例 3

10
3 1 4 1 5 9 2 6 5 3


### 出力例 3

900221128


Score : 600 points

### Problem Statement

There are N balls numbered 1 through N. Initially, Ball i is painted in Color A_i.

Colors are represented by integers between 1 and N, inclusive.

Consider repeating the following operation until all the colors of the balls become the same.

• There are 2^N subsets (including the empty set) of the set consisting of the N balls; choose one of the subsets uniformly at random. Let X_1,X_2,...,X_K be the indices of the chosen balls. Next, choose a permutation obtained by choosing K integers out of integers (1,2,\dots,N) uniformly at random. Let P=(P_1,P_2,\dots,P_K) be the chosen permutation. For each integer i such that 1 \le i \le K, change the color of Ball X_i to P_i.

Find the expected value of number of operations, modulo 998244353.

Here a permutation obtained by choosing K integers out of integers (1,2,\dots,N) is a sequence of K integers between 1 and N, inclusive, whose elements are pairwise distinct.

### Notes

We can prove that the sought expected value is always a rational number. Also, under the Constraints of this problem, when the value is represented by two coprime integers P and Q as \frac{P}{Q}, we can prove that there exists a unique integer R such that R \times Q \equiv P(\bmod\ 998244353) and 0 \le R < 998244353. Find this R.

### Constraints

• 2 \le N \le 2000
• 1 \le A_i \le N
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N


### Sample Input 1

2
1 2


### Sample Output 1

4


The operation is repeated until a subset of size 1 is chosen and the color of the ball is changed to the color of the ball not contained in the subset. The probability is \displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4}, so the expected value is 4.

### Sample Input 2

3
1 1 1


### Sample Output 2

0


The operation is never performed, since the colors of the balls are already the same.

### Sample Input 3

10
3 1 4 1 5 9 2 6 5 3


### Sample Output 3

900221128