Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

• S is a string of length 16 consisting of 0 and 1.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq D \leq 100
• There is an arithmetic sequence with first term A, last term B, and common difference D.
• All input values are integers.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

10

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

• If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
• If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq R_i \leq 10^9
• i \neq j \implies R_i \neq R_j
• All values in the input are integers.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Problem Statement

N AtCoder users have gathered to play AtCoder RPS 2. The i-th user's name is S_i and their rating is C_i.

AtCoder RPS 2 is played as follows:

• Assign the numbers 0, 1, \dots, N - 1 to the users in lexicographical order of their usernames.
• Let T be the sum of the ratings of the N users. The user assigned the number T \bmod N is the winner.

Print the winner's username.

Constraints

• 1 \leq N \leq 100
• S_i is a string consisting of lowercase English letters with length between 3 and 16, inclusive.
• S_1, S_2, \dots, S_N are all distinct.
• 1 \leq C_i \leq 4229
• C_i is an integer.

Sample Input 1

3
takahashi 2
aoki 6
snuke 5

Sample Output 1

snuke

The sum of the ratings of the three users is 13. Sorting their names in lexicographical order yields aoki, snuke, takahashi, so aoki is assigned number 0, snuke is 1, and takahashi is 2.

Since 13 \bmod 3 = 1, print snuke, who is assigned number 1.

Sample Input 2

3
takahashi 2813
takahashixx 1086
takahashix 4229

Sample Output 2

takahashix

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

...#.
#.#..
.#...
#.#..
...#.

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

Takahashi has decided to enjoy a wired full-course meal consisting of N courses in a restaurant.
The i-th course is:

• if X_i=0, an antidotal course with a tastiness of Y_i;
• if X_i=1, a poisonous course with a tastiness of Y_i.

When Takahashi eats a course, his state changes as follows:

• Initially, Takahashi has a healthy stomach.
• When he has a healthy stomach,
  • if he eats an antidotal course, his stomach remains healthy;
  • if he eats a poisonous course, he gets an upset stomach.
• When he has an upset stomach,
  • if he eats an antidotal course, his stomach becomes healthy;
  • if he eats a poisonous course, he dies.

The meal progresses as follows.

• Repeat the following process for i = 1, \ldots, N in this order.
  • First, the i-th course is served to Takahashi.
  • Next, he chooses whether to "eat" or "skip" the course.
    • If he chooses to "eat" it, he eats the i-th course. His state also changes depending on the course he eats.
    • If he chooses to "skip" it, he does not eat the i-th course. This course cannot be served later or kept somehow.
  • Finally, (if his state changes, after the change) if he is not dead,
    • if i \neq N, he proceeds to the next course.
    • if i = N, he makes it out of the restaurant alive.

An important meeting awaits him, so he must make it out of there alive.
Find the maximum possible sum of tastiness of the courses that he eats (or 0 if he eats nothing) when he decides whether to "eat" or "skip" the courses under that condition.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• X_i \in \{0,1\}
  • In other words, X_i is either 0 or 1.
• -10^9 \le Y_i \le 10^9

Sample Input 1

5
1 100
1 300
0 -200
1 500
1 300

Sample Output 1

600

The following choices result in a total tastiness of the courses that he eats amounting to 600, which is the maximum possible.

• He skips the 1-st course. He now has a healthy stomach.
• He eats the 2-nd course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 300.
• He eats the 3-rd course. He now has a healthy stomach again, and the total tastiness of the courses that he eats amounts to 100.
• He eats the 4-th course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 600.
• He skips the 5-th course. He now has an upset stomach.
• In the end, he is not dead, so he makes it out of the restaurant alive.

Sample Input 2

4
0 -1
1 -2
0 -3
1 -4

Sample Output 2

0

For this input, it is optimal to eat nothing, in which case the answer is 0.

Sample Input 3

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

Sample Output 3

4100000000

The answer may not fit into a 32-bit integer type.

Problem Statement

A box contains N balls, each with an integer between 1 and M-1 written on it. For i = 1, 2, \ldots, N, the integer written on the i-th ball is A_i.

While the box has two or more balls remaining, Takahashi will repeat the following.

• First, choose two balls arbitrarily.
• Then, get a score equal to the remainder when x^y + y^x is divided by M, where x and y are the integers written on the two balls.
• Finally, choose one of the two balls arbitrarily, eat it, and return the other to the box.

Print the maximum possible total score Takahashi will get.

Constraints

• 2 \leq N \leq 500
• 2 \leq M \leq 10^9
• 1 \leq A_i \leq M-1
• All values in the input are integers.

Sample Input 1

4 10
4 2 3 2

Sample Output 1

20

Consider the following scenario. Below, X \bmod Y denotes the remainder when a non-negative integer X is divided by a positive integer Y.

1. Take the first and third balls from the box to score (4^3 + 3^4) \bmod 10 = 5 points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
2. Take the third and fourth balls from the box to score (3^2 + 2^3) \bmod 10 = 7 points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
3. Take the second and fourth balls from the box to score (2^2 + 2^2) \bmod 10 = 8 points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.

Here, Takahashi scores a total of 5 + 7 + 8 = 20 points, which is the maximum possible value.

Sample Input 2

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

Sample Output 2

1733

Problem Statement

A DDoS-type string is a string of length 4 consisting of uppercase and lowercase English letters satisfying both of the following conditions.

• The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
• The first and second characters are equal.

For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.

You are given a string S consisting of uppercase and lowercase English letters and ?. Let q be the number of occurrences of ? in S. There are 52^q strings that can be obtained by independently replacing each ? in S with an uppercase or lowercase English letter. Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo 998244353.

Notes

A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.

Constraints

• S consists of uppercase English letters, lowercase English letters, and ?.
• The length of S is between 4 and 3\times 10^5, inclusive.

Sample Input 1

DD??S

Sample Output 1

676

When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.

Sample Input 2

????????????????????????????????????????

Sample Output 2

858572093

Find the count modulo 998244353.

Sample Input 3

?D??S

Sample Output 3

136604