Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

• 1\leq H,W \leq 10^5
• H \times W \leq 10^5
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 3
1 2 3
4 5 6
7 8 9
10 11 12

Sample Output 1

1 4 7 10
2 5 8 11
3 6 9 12

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.
• The lost integer is uniquely determined.

Sample Input 1

3
2 3 5

Sample Output 1

4

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

7

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

151

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

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

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

• The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
  • That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

• N is an integer.
• 0 \le N < 2^{60}
• In the binary representation of N, at most 15 digit positions contain 1.

Sample Input 1

11

Sample Output 1

0
1
2
3
8
9
10
11

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

• 0000_{(2)}=0_{(10)}
• 0001_{(2)}=1_{(10)}
• 0010_{(2)}=2_{(10)}
• 0011_{(2)}=3_{(10)}
• 1000_{(2)}=8_{(10)}
• 1001_{(2)}=9_{(10)}
• 1010_{(2)}=10_{(10)}
• 1011_{(2)}=11_{(10)}

Sample Input 2

0

Sample Output 2

0

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

Problem Statement

You are given a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

• Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

Constraints

• 2\leq N\leq3\times10^5
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

9
1 2
2 3
2 4
2 5
1 6
6 7
7 8
7 9

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

Sample Output 3

12