Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

• 2 \leq N \leq 100
• -100 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

4
1 -2 -1

Sample Output 1

2

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

• Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
• Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
• Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
• Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
• Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
• Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.

Sample Input 2

3
0 0

Sample Output 2

0

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

• There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

• S is a string of lowercase English letters with a length between 1 and 100, inclusive.

Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

• i=1: two letters (o and t)
• i=2: two letters (c and n)
• i=3: two letters (e and m)
• i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.

Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.

Sample Input 3

ab

Sample Output 3

Yes

Problem Statement

A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:

• Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
• Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append X to the end to form T.

Given strings S and T, determine if T is an airport code for S.

Constraints

• S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
• T is a string of uppercase English letters with a length of 3.

Sample Input 1

narita
NRT

Sample Output 1

Yes

The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.

Sample Input 2

losangeles
LAX

Sample Output 2

Yes

The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.

Sample Input 3

snuke
RNG

Sample Output 3

No

Problem Statement

For non-negative integers l and r (l < r), let S(l, r) denote the sequence (l, l+1, \ldots, r-2, r-1) formed by arranging integers from l through r-1 in order. Furthermore, a sequence is called a good sequence if and only if it can be represented as S(2^i j, 2^i (j+1)) using non-negative integers i and j.

You are given non-negative integers L and R (L < R). Divide the sequence S(L, R) into the fewest number of good sequences, and print that number of sequences and the division. More formally, find the minimum positive integer M for which there is a sequence of pairs of non-negative integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) that satisfies the following, and print such (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M).

• L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R
• S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M) are good sequences.

It can be shown that there is only one division that minimizes M.

Constraints

• 0 \leq L < R \leq 2^{60}
• All input values are integers.

Sample Input 1

3 19

Sample Output 1

5
3 4
4 8
8 16
16 18
18 19

S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) can be divided into the following five good sequences, which is the minimum possible number:

• S(3,4)=S(2^0\cdot 3,2^0\cdot4)=(3)
• S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)
• S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)
• S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)
• S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)

Sample Input 2

0 1024

Sample Output 2

1
0 1024

Sample Input 3

3940649673945088 11549545024454656

Sample Output 3

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

Problem Statement

There is a 3 \times 3 grid. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left (1 \leq i, j \leq 3). Cell (i, j) contains an integer A_{i,j}. It is guaranteed that \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd. Additionally, all cells are initially painted white.

Takahashi and Aoki will play a game using this grid. Takahashi goes first, and they take turns performing the following operation:

• Choose a cell (i, j) (1\leq i, j \leq 3) that is still painted white (it can be shown that such a cell always exists at the time of the operation). The player performing the operation scores A_{i,j} points. Then, if the player is Takahashi, he paints the cell (i, j) red; if the player is Aoki, he paints it blue.

After each operation, the following checks are made:

• Check if there are three consecutive cells painted the same color (red or blue) in any row, column, or diagonal. If such a sequence exists, the game ends immediately, and the player whose color forms the sequence wins.
• Check if there are white cells left. If no white cells remain, the game ends, and the player with the higher total score wins.

It can be shown that the game will always end after a finite number of moves, and either Takahashi or Aoki will win. Determine which player wins if both play optimally for victory.

Constraints

• |A_{i,j}| \leq 10^9
• \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd.
• All input values are integers.

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell (2,2) in his first move, no matter how Aoki plays afterward, Takahashi can always act to prevent three consecutive blue cells. If three consecutive red cells are formed, Takahashi wins. If the game ends without three consecutive red cells, at that point, Takahashi has scored 1 point and Aoki 0 points, so Takahashi wins either way.

Sample Input 2

-1 1 0
-4 -2 -5
-4 -1 -5

Sample Output 2

Aoki

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer M. Find the number, modulo 998244353, of non-empty and not necessarily contiguous subsequences of A such that the least common multiple (LCM) of the elements in the subsequence is M. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences. Also, the LCM of a sequence with a single element is that element itself.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^{16}
• 1 \leq A_i \leq 10^{16}
• All input values are integers.

Sample Input 1

4 6
2 3 4 6

Sample Output 1

5

The subsequences of A whose elements have an LCM of 6 are (2,3),(2,3,6),(2,6),(3,6),(6); there are five of them.

Sample Input 2

5 349
1 1 1 1 349

Sample Output 2

16

Note that even if some subsequences coincide as sequences, they are distinguished if they are taken from different positions.

Sample Input 3

16 720720
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 3

2688

Problem Statement

A sequence of positive integers T=(T_1,T_2,\dots,T_M) of length M is a palindrome if and only if T_i=T_{M-i+1} for each i=1,2,\dots,M.

You are given a sequence of non-negative integers A = (A_1,A_2,\dots,A_N) of length N. Determine if there is a sequence of positive integers S=(S_1,S_2,\dots,S_N) of length N that satisfies the following condition, and if it exists, find the lexicographically smallest such sequence.

• For each i=1,2,\dots,N, both of the following hold:
  • The sequence (S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i}) is a palindrome.
  • If 2 \leq i-A_i and i+A_i \leq N-1, the sequence (S_{i-A_i-1},S_{i-A_i},\dots,S_{i+A_i+1}) is not a palindrome.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq \min\{i-1,N-i\}
• All input values are integers.

Sample Input 1

7
0 0 2 0 2 0 0

Sample Output 1

Yes
1 1 2 1 1 1 2

S = (1,1,2,1,1,1,2) satisfies the condition:

• i=1: (A_1)=(1) is a palindrome.
• i=2: (A_2)=(1) is a palindrome, but (A_1,A_2,A_3)=(1,1,2) is not.
• i=3: (A_1,A_2,\dots,A_5)=(1,1,2,1,1) is a palindrome.
• i=4: (A_4)=(1) is a palindrome, but (A_3,A_4,A_5)=(2,1,1) is not.
• i=5: (A_3,A_4,\dots,A_7)=(2,1,1,1,2) is a palindrome.
• i=6: (A_6)=(1) is a palindrome, but (A_5,A_6,A_7)=(1,1,2) is not.
• i=7: (A_7)=(2) is a palindrome.

There are other sequences like S=(2,2,1,2,2,2,1) that satisfy the condition, but print the lexicographically smallest one, which is (1,1,2,1,1,1,2).

Sample Input 2

7
0 1 2 3 2 1 0

Sample Output 2

Yes
1 1 1 1 1 1 1

Sample Input 3

7
0 1 2 0 2 1 0

Sample Output 3

No