Problem Statement

Ringo is giving a present to Snuke.

Ringo has found out that Snuke loves yakiniku (a Japanese term meaning grilled meat. yaki: grilled, niku: meat). He supposes that Snuke likes grilled things starting with YAKI in Japanese, and does not like other things.

You are given a string S representing the Japanese name of Ringo's present to Snuke. Determine whether S starts with YAKI.

Constraints

• 1 \leq |S| \leq 10
• S consists of uppercase English letters.

Sample Input 1

YAKINIKU

Sample Output 1

Yes

YAKINIKU starts with YAKI.

Sample Input 2

TAKOYAKI

Sample Output 2

No

TAKOYAKI (a Japanese snack. tako: octopus) does not start with YAKI.

Sample Input 3

YAK

Sample Output 3

No

Problem Statement

We have a grid with N rows and M columns of squares. Initially, all the squares are white.

There is a button attached to each row and each column. When a button attached to a row is pressed, the colors of all the squares in that row are inverted; that is, white squares become black and vice versa. When a button attached to a column is pressed, the colors of all the squares in that column are inverted.

Takahashi can freely press the buttons any number of times. Determine whether he can have exactly K black squares in the grid.

Constraints

• 1 \leq N,M \leq 1000
• 0 \leq K \leq NM

Sample Input 1

2 2 2

Sample Output 1

Yes

Press the buttons in the order of the first row, the first column.

Sample Input 2

2 2 1

Sample Output 2

No

Sample Input 3

3 5 8

Sample Output 3

Yes

Press the buttons in the order of the first column, third column, second row, fifth column.

Sample Input 4

7 9 20

Sample Output 4

No

Problem Statement

We have an H-by-W matrix. Let a_{ij} be the element at the i-th row from the top and j-th column from the left. In this matrix, each a_{ij} is a lowercase English letter.

Snuke is creating another H-by-W matrix, A', by freely rearranging the elements in A. Here, he wants to satisfy the following condition:

• Every row and column in A' can be read as a palindrome.

Determine whether he can create a matrix satisfying the condition.

Note

A palindrome is a string that reads the same forward and backward. For example, a, aa, abba and abcba are all palindromes, while ab, abab and abcda are not.

Constraints

• 1 ≤ H, W ≤ 100
• a_{ij} is a lowercase English letter.

Sample Input 1

3 4
aabb
aabb
aacc

Sample Output 1

Yes

For example, the following matrix satisfies the condition.

abba
acca
abba

Sample Input 2

2 2
aa
bb

Sample Output 2

No

It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in A.

Sample Input 3

5 1
t
w
e
e
t

Sample Output 3

Yes

For example, the following matrix satisfies the condition.

t
e
w
e
t

Sample Input 4

2 5
abxba
abyba

Sample Output 4

No

Sample Input 5

1 1
z

Sample Output 5

Yes

Problem Statement

We have a grid with H rows and W columns of squares. We will represent the square at the i-th row from the top and j-th column from the left as (i,\ j). Also, we will define the distance between the squares (i_1,\ j_1) and (i_2,\ j_2) as |i_1 - i_2| + |j_1 - j_2|.

Snuke is painting each square in red, yellow, green or blue. Here, for a given positive integer d, he wants to satisfy the following condition:

• No two squares with distance exactly d have the same color.

Find a way to paint the squares satisfying the condition. It can be shown that a solution always exists.

Constraints

• 2 ≤ H, W ≤ 500
• 1 ≤ d ≤ H + W - 2

Sample Input 1

2 2 1

Sample Output 1

RY
GR

There are four pairs of squares with distance exactly 1. As shown below, no two such squares have the same color.

• (1,\ 1), (1,\ 2) : R, Y
• (1,\ 2), (2,\ 2) : Y, R
• (2,\ 2), (2,\ 1) : R, G
• (2,\ 1), (1,\ 1) : G, R

Sample Input 2

2 3 2

Sample Output 2

RYB
RGB

There are six pairs of squares with distance exactly 2. As shown below, no two such squares have the same color.

• (1,\ 1) , (1,\ 3) : R , B
• (1,\ 3) , (2,\ 2) : B , G
• (2,\ 2) , (1,\ 1) : G , R
• (2,\ 1) , (2,\ 3) : R , B
• (2,\ 3) , (1,\ 2) : B , Y
• (1,\ 2) , (2,\ 1) : Y , R

Problem Statement

Ringo got interested in modern art. He decided to draw a big picture on the board with N+2 rows and M+2 columns of squares constructed in the venue of CODE FESTIVAL 2017, using some people.

The square at the (i+1)-th row and (j+1)-th column in the board is represented by the pair of integers (i,j). That is, the top-left square is (0,0), and the bottom-right square is (N+1,M+1). Initially, the squares (x,y) satisfying 1 \leq x \leq N and 1 \leq y \leq M are painted white, and the other (outermost) squares are painted black.

Ringo arranged people at some of the outermost squares, facing inward. More specifically, the arrangement of people is represented by four strings A, B, C and D, as follows:

• For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in A is 1, place a person facing right at the square (i,0); otherwise, do nothing.
• For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in B is 1, place a person facing left at the square (i,M+1); otherwise, do nothing.
• For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in C is 1, place a person facing down at the square (0,i); otherwise, do nothing.
• For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in D is 1, place a person facing up at the square (N+1,i); otherwise, do nothing.

Each person has a sufficient amount of non-white paint. No two people have paint of the same color.

An example of an arrangement of people (For convenience, black squares are displayed in gray)

Ringo repeats the following sequence of operations until all people are dismissed from the venue.

• Select a person who is still in the venue.
• The selected person repeats the following action while the square in front of him/her is white: move one square forward, and paint the square he/she enters with his/her paint. When the square in front of him/her is not white, he/she stops doing the action.
• The person is now dismissed from the venue.

An example of a way the board is painted

How many different states of the board can Ringo obtain at the end of the process? Find the count modulo 998244353.

Two states of the board are considered different when there is a square painted in different colors.

Constraints

• 1 \leq N,M \leq 10^5
• |A|=|B|=N
• |C|=|D|=M
• A, B, C and D consist of 0 and 1.

Sample Input 1

2 2
10
01
10
01

Sample Output 1

6

There are six possible states as shown below.

Sample Input 2

2 2
11
11
11
11

Sample Output 2

32

Sample Input 3

3 4
111
111
1111
1111

Sample Output 3

1276

Sample Input 4

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111

Sample Output 4

548356548

Be sure to find the count modulo 998244353.

Sample Input 5

3 4
000
101
1111
0010

Sample Output 5

21

Sample Input 6

9 13
111100001
010101011
0000000000000
1010111111101

Sample Output 6

177856

Sample Input 7

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000

Sample Output 7

734524988

Problem Statement

There are A slimes lining up in a row. Initially, the sizes of the slimes are all 1.

Snuke can repeatedly perform the following operation.

• Choose a positive even number M. Then, select M consecutive slimes and form M / 2 pairs from those slimes as follows: pair the 1-st and 2-nd of them from the left, the 3-rd and 4-th of them, ..., the (M-1)-th and M-th of them. Combine each pair of slimes into one larger slime. Here, the size of a combined slime is the sum of the individual slimes before combination. The order of the M / 2 combined slimes remain the same as the M / 2 pairs of slimes before combination.

Snuke wants to get to the situation where there are exactly N slimes, and the size of the i-th (1 ≤ i ≤ N) slime from the left is a_i. Find the minimum number of operations required to achieve his goal.

Note that A is not directly given as input. Assume A = a_1 + a_2 + ... + a_N.

Constraints

• 1 ≤ N ≤ 10^5
• a_i is an integer.
• 1 ≤ a_i ≤ 10^9

Sample Input 1

2
3 3

Sample Output 1

2

One way to achieve Snuke's goal is as follows. Here, the selected slimes are marked in bold.

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

Sample Input 2

4
2 1 2 2

Sample Output 2

2

One way to achieve Snuke's goal is as follows.

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

Sample Input 3

1
1

Sample Output 3

0

Sample Input 4

10
3 1 4 1 5 9 2 6 5 3

Sample Output 4

10