Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

• The length of s is between 1 and 10, inclusive.
• s consists of two kinds of characters, 0 and 1.

Sample Input 1

01

Sample Output 1

10

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

1011

Sample Output 2

0100

Sample Input 3

100100001

Sample Output 3

011011110

Problem Statement

You are given a string S of length 3 consisting of lowercase English letters.

How many different strings can be obtained by permuting the characters in S?

Constraints

• S is a string S of length 3 consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.

Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.

Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.

Problem Statement

There are N people numbered 1 through N.
There are M types of clothes numbered 1 through M. Person i is wearing clothes F_i.
Answer the following two questions with Yes or No.

• Question 1: Are all N people wearing different types of clothes?
• Question 2: For every one of the M types of clothes, is there at least one person wearing that type?

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq F_i \leq M
• All input values are integers.

Sample Input 1

3 4
1 2 4

Sample Output 1

Yes
No

Everyone is wearing a different type of clothes, so the answer to question 1 is Yes.
There is no person wearing clothes 3, so the answer to question 2 is No.

Sample Input 2

4 2
1 2 1 2

Sample Output 2

No
Yes

Sample Input 3

4 4
1 3 2 1

Sample Output 3

No
No

Sample Input 4

5 5
1 3 4 2 5

Sample Output 4

Yes
Yes

Problem Statement

At the entrance of AtCoder Land, there is a single ticket booth where visitors line up to purchase tickets one by one. The purchasing process takes A seconds per person. Once the person at the front of the line finishes purchasing their ticket, the next person (if any) immediately starts their purchasing process.

Currently, there is no one in line at the ticket booth, and N people will come to buy tickets one after another. Specifically, the i-th person will arrive at the ticket booth T_i seconds from now. If there is already a line, they will join the end of it; if not, they will start the purchasing process immediately. Here, T_1 < T_2 < \dots < T_N.

For each i\ (1 \leq i \leq N), determine how many seconds from now the i-th person will finish purchasing their ticket.

Constraints

• 1 \leq N \leq 100
• 0 \leq T_1 < T_2 < \dots < T_N \leq 10^6
• 1 \leq A \leq 10^6
• All input values are integers.

Sample Input 1

3 4
0 2 10

Sample Output 1

4
8
14

The events proceed in the following order:

• At 0 seconds: The 1st person arrives at the ticket booth and starts the purchasing process.
• At 2 seconds: The 2nd person arrives at the ticket booth and joins the line behind the 1st person.
• At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person starts the purchasing process.
• At 8 seconds: The 2nd person finishes purchasing their ticket.
• At 10 seconds: The 3rd person arrives at the ticket booth and starts the purchasing process.
• At 14 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 2

3 3
1 4 7

Sample Output 2

4
7
10

The events proceed in the following order:

• At 1 second: The 1st person arrives at the ticket booth and starts the purchasing process.
• At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person arrives at the ticket booth and starts the purchasing process.
• At 7 seconds: The 2nd person finishes purchasing their ticket, and the 3rd person arrives at the ticket booth and starts the purchasing process.
• At 10 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 3

10 50000
120190 165111 196897 456895 540000 552614 561627 743796 757613 991216

Sample Output 3

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216

Problem Statement

There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.

Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.

Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?

If the subsidy limit can be made infinitely large, report that instead.

Constraints

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

Sample Input 1

4 8
1 3 2 4

Sample Output 1

2

If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.

If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.

Therefore, the maximum possible value of the subsidy limit is 2 yen.

Sample Input 2

3 20
5 3 2

Sample Output 2

infinite

The subsidy limit can be made infinitely large.

Sample Input 3

10 23
2 5 6 5 2 1 7 9 7 2

Sample Output 3

2

Problem Statement

You are given a positive integer N.

Find the maximum value of a palindromic cube number not greater than N.

Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:

• There is a positive integer x such that x^3 = K.
• The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.

Constraints

• N is a positive integer not greater than 10^{18}.

Sample Input 1

345

Sample Output 1

343

343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.

Sample Input 2

6

Sample Output 2

1

Sample Input 3

123456789012345

Sample Output 3

1334996994331

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\dots,A_N). The following action on this sequence is called an operation.

• First, choose an integer i such that 1 \le i \le N.
• Next, choose and do one of the following.
  • Add 1 to A_i.
  • Subtract 1 from A_i.

Answer Q questions.
The i-th question is the following.

• Consider performing zero or more operations to change every element of A to X_i. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 0 \le X_i \le 10^9

Sample Input 1

5 3
6 11 2 5 5
5
20
0

Sample Output 1

10
71
29

We have A=(6,11,2,5,5) and three questions in this input.

For the 1-st question, you can change every element of A to 5 in 10 operations as follows.

• Subtract 1 from A_1.
• Subtract 1 from A_2 six times.
• Add 1 to A_3 three times.

It is impossible to change every element of A to 5 in 9 or fewer operations.

For the 2-nd question, you can change every element of A to 20 in 71 operations.

For the 3-rd question, you can change every element of A to 0 in 29 operations.

Sample Input 2

10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

Sample Output 2

3316905982
2811735560
5542639502
4275864946
4457360498

The output may not fit into 32-bit integers.

Problem Statement

You are given strings X and Y. Define a sequence of strings S_1, S_2, \dots as follows.

• S_1 = X
• S_2 = Y
• For i \geq 3, S_i is the concatenation of S_{i-1} and S_{i-2} in this order.

For each i = 1, 2, \ldots, Q, answer the following problem.

Problem: You are given integers L_i, R_i and a character C_i. Find how many times character C_i appears in the L_i-th through R_i-th characters of S_{10^{18}}.

Constraints

• X and Y are strings of lowercase English letters of length between 1 and 10^4, inclusive.
• 1 \leq Q \leq 10^5
• 1 \leq L_i \leq R_i \leq 10^{18}
• C_i is a lowercase English letter.
• All given numerical values are integers.

Sample Input 1

a
b
6
2 7 a
1 3 b
3 7 b
1 9 c
1 1000000000000000000 b
1000000000000000000 1000000000000000000 a

Sample Output 1

3
2
3
0
618033988749894848
1

S_3, S_4, S_5 are ba, bab, babba, respectively.

S_{10^{18}} is babbababbabba..., and the second through seventh characters contain three occurrences of a.

Problem Statement

There are N teapots arranged in a row, numbered from 1 to N from left to right.

There is a sequence of integers (a_1, \dots, a_N), initially with values a_1 = \dots = a_N = -1.

You will fill each teapot with either tea or coffee so that the following conditions are all satisfied:

• For any two adjacent teapots, at least one of them contains tea.
• For any integer i satisfying 1 \leq i \leq N, if a_i \neq -1, then exactly a_i of teapots 1, \dots, i contain coffee.

You are given Q queries, which you should process in the given order.

The j-th query (1 \leq j \leq Q) is as follows:

• Change the value of a_{X_j} to Y_j. Then, print the number, modulo 998244353, of ways to fill the teapots satisfying the conditions.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• -1 \leq Y_j \leq X_j (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

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

Sample Output 1

5
3
1
8
4
0

• After the operation in the first query, a = (1,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following five ways:
  • Put coffee in teapot 1, and tea in the others.
  • Put coffee in teapots 1, 3, and tea in the others.
  • Put coffee in teapots 1, 3, 5, and tea in the others.
  • Put coffee in teapots 1, 4, and tea in the others.
  • Put coffee in teapots 1, 5, and tea in the others.
• After the operation in the second query, a = (1,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following three ways:
  • Put coffee in teapots 1, 3, and tea in the others.
  • Put coffee in teapots 1, 3, 5, and tea in the others.
  • Put coffee in teapots 1, 4, and tea in the others.
• After the operation in the third query, a = (0,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following one way:
  • Put coffee in teapots 2, 4, and tea in the others.
• After the operation in the fourth query, a = (0,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following eight ways:
  • Put coffee in none of the teapots and tea in all of them.
  • Put coffee in teapot 2, and tea in the others.
  • Put coffee in teapots 2, 4, and tea in the others.
  • Put coffee in teapots 2, 5, and tea in the others.
  • Put coffee in teapot 3, and tea in the others.
  • Put coffee in teapots 3, 5, and tea in the others.
  • Put coffee in teapot 4, and tea in the others.
  • Put coffee in teapot 5, and tea in the others.
• After the operation in the fifth query, a = (0,\ -1,\ -1,\ -1,\ 1). The ways to fill the teapots satisfying the conditions are the following four ways:
  • Put coffee in teapot 2, and tea in the others.
  • Put coffee in teapot 3, and tea in the others.
  • Put coffee in teapot 4, and tea in the others.
  • Put coffee in teapot 5, and tea in the others.
• After the operation in the sixth query, a = (0,\ -1,\ -1,\ -1,\ 5). The number of ways to fill the teapots satisfying the conditions is zero.