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