Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

• 2 \leq H, W \leq 100
• H and W are integers.
• S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
• There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

4

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

The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1. Road i connects City A_i and City B_i bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.

Takahashi will depart City 1 and have a journey by repeating the following.

• If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
• Otherwise,
  • if he is in City 1, he ends the journey;
  • otherwise, he goes to the city he was in just before visiting the current city for the first time.

Find the sequence of cities visited by Takahashi in the order he visits them.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq N
• It is possible to travel between every pair of cities using roads.

Sample Input 1

4
1 2
4 2
3 1

Sample Output 1

1 2 4 2 1 3 1

His journey will be as follows.

• Start in City 1.
• The unvisited cities directly connected to City 1 are City 2 and 3. Go to the city with the smaller number, that is, City 2.
• The unvisited city directly connected to City 2 is City 4. Go there.
• There is no unvisited city directly connected to City 4. Go back to City 2.
• There is no unvisited city directly connected to City 2. Go to City 1, where he was in just before visiting City 2 for the first time.
• The unvisited city directly connected to City 1 is City 3. Go there.
• There is no unvisited city directly connected to City 3. Go back to City 1.
• There is no unvisited city directly connected to City 1. End the journey.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

1 2 1 3 1 4 1 5 1