Problem Statement

You are given a string S of length N consisting of A, B and C, and an integer K which is between 1 and N (inclusive). Print the string S after lowercasing the K-th character in it.

Constraints

• 1 ≤ N ≤ 50
• 1 ≤ K ≤ N
• S is a string of length N consisting of A, B and C.

Sample Input 1

3 1
ABC

Sample Output 1

aBC

Sample Input 2

4 3
CABA

Sample Output 2

CAbA

Problem Statement

You have a digit sequence S of length 4. You are wondering which of the following formats S is in:

• YYMM format: the last two digits of the year and the two-digit representation of the month (example: 01 for January), concatenated in this order
• MMYY format: the two-digit representation of the month and the last two digits of the year, concatenated in this order

If S is valid in only YYMM format, print YYMM; if S is valid in only MMYY format, print MMYY; if S is valid in both formats, print AMBIGUOUS; if S is valid in neither format, print NA.

Constraints

• S is a digit sequence of length 4.

Sample Input 1

1905

Sample Output 1

YYMM

May XX19 is a valid date, but 19 is not valid as a month. Thus, this string is only valid in YYMM format.

Sample Input 2

0112

Sample Output 2

AMBIGUOUS

Both December XX01 and January XX12 are valid dates. Thus, this string is valid in both formats.

Sample Input 3

1700

Sample Output 3

NA

Neither 0 nor 17 is valid as a month. Thus, this string is valid in neither format.

Problem Statement

Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:

1. Throw the die. The current score is the result of the die.
2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.
3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.

You are given N and K. Find the probability that Snuke wins the game.

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ K ≤ 10^5
• All values in input are integers.

Sample Input 1

3 10

Sample Output 1

0.145833333333

• If the die shows 1, Snuke needs to get four consecutive heads from four coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}.
• If the die shows 2, Snuke needs to get three consecutive heads from three coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}.
• If the die shows 3, Snuke needs to get two consecutive heads from two coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}.

Thus, the probability that Snuke wins is \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333.

Sample Input 2

100000 5

Sample Output 2

0.999973749998

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

• For any two vertices painted in the same color, the distance between them is an even number.

Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^5
• 1 \leq u_i < v_i \leq N
• 1 \leq w_i \leq 10^9

Sample Input 1

3
1 2 2
2 3 1

Sample Output 1

0
0
1

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1
0
1
0
1

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

• For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq X_i < Y_i \leq N
• 1 \leq Z_i \leq 100
• The pairs (X_i, Y_i) are distinct.
• There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999

Problem Statement

Construct a sequence a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} of length 2^{M + 1} that satisfies the following conditions, if such a sequence exists.

• Each integer between 0 and 2^M - 1 (inclusive) occurs twice in a.
• For any i and j (i < j) such that a_i = a_j, the formula a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K holds.

Constraints

• All values in input are integers.
• 0 \leq M \leq 17
• 0 \leq K \leq 10^9

Sample Input 1

1 0

Sample Output 1

0 0 1 1

For this case, there are multiple sequences that satisfy the condition.

For example, when a = {0, 0, 1, 1}, there are two pairs (i,\ j)\ (i < j) such that a_i = a_j: (1, 2) and (3, 4). Since a_1 \ xor \ a_2 = 0 and a_3 \ xor \ a_4 = 0, this sequence a satisfies the condition.

Sample Input 2

1 1

Sample Output 2

-1

No sequence satisfies the condition.

Sample Input 3

5 58

Sample Output 3

-1

No sequence satisfies the condition.