Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

Given a string S of length N consisting of lowercase English alphabets, print the last character of S.

Constraints

• N is an integer.
• 1 ≤ N ≤ 1000
• S is a string of length N consisting of lowercase English alphabets.

Sample Input 1

5
abcde

Sample Output 1

e

The last character of S = {}abcde is e, so e should be printed.

Sample Input 2

1
a

Sample Output 2

a

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• 1\leq N\leq 100
• 1\leq K\leq 100
• 1\leq A_i\leq K\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
• Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
• After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
• Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

8

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

You are given a string S of length N consisting of characters A, B, and ?.

You are also given a positive integer K. A string T consisting of A and B is considered a good string if it satisfies the following condition:

• No contiguous substring of length K in T is a palindrome.

Let q be the number of ? characters in S. There are 2^q strings that can be obtained by replacing each ? in S with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo 998244353.

Constraints

• 2 \leq K \leq N \leq 1000
• K \leq 10
• S is a string consisting of A, B, and ?.
• The length of S is N.
• N and K are integers.

Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

• ABAAABA
• ABAABBA
• ABBAABA
• ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.

Sample Input 2

40 7
????????????????????????????????????????

Sample Output 2

116295436

Ensure to find the number of good strings modulo 998244353.

Sample Input 3

15 5
ABABA??????????

Sample Output 3

0

It is possible that there is no way to replace the ?s to obtain a good string.

Sample Input 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

Sample Output 4

259240

Problem Statement

There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.

Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.

Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.

Find the minimum number of punches needed for Takahashi to reach the fish market.

Constraints

• 2 \leq H,W \leq 500
• H and W are integers.
• S_{i,j} is . or #.
• S_{1,1} and S_{H,W} are ..

Sample Input 1

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Sample Output 1

1

He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.

..#..
#.**#
##**#
#.#.#
..#..

It is not required that all of the 2\times 2 cells in the region to punch are blocks.

Sample Input 2

5 7
.......
######.
.......
.######
.......

Sample Output 2

0

He can reach the fish market without destroying blocks, though he has to go a long way around.

Sample Input 3

8 8
.#######
########
########
########
########
########
########
#######.

Sample Output 3

5

Problem Statement

There are N items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The i-th item is described by an integer pair (T_i, X_i) as follows:

• If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i.
• If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i.
• If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans.

Find the maximum total happiness that you get by obtaining M items out of N.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• T_i is 0, 1, or 2.
• 1 \leq X_i \leq 10^9
• All input values are integers.

Sample Input 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

Sample Output 1

27

If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27.
There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above.

Sample Input 2

5 5
1 5
1 5
1 5
1 5
1 5

Sample Output 2

0

Sample Input 3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

Sample Output 3

30