Problem Statement

Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.

There are integers ~A~ and ~B~ , which satisfy ~1 \leq A \leq 10~ and ~0 \leq B \leq A~ .
Let ~S~ be the string obtained as follows.

• Round off ~\dfrac{B}{A}~ to three decimal digits, then write the integer part ( ~1~ digit), . (the decimal point), and the decimal part ( ~3~ digits) in this order, with trailing zeros.

For example, if ~A=7~ and ~B=4~ , then ~\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots~ rounded off to three decimal digits is ~0.571~ . Thus, ~S~ is 0.571 .

You are given ~A~ and ~B~ as the input and asked to print ~S~ .

Constraints

• ~1 \leq A \leq 10~
• ~0 \leq B \leq A~
• ~A~ and ~B~ are integers.

Input

The input is given from Standard Input in the following format:

~A~ ~B~

Output

Print ~S~ in the format specified in the Problem Statement. Note that answers in different formats will be considered wrong.

Sample Input 1

7 4

Sample Output 1

0.571

As explained in the Problem Statement, ~\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots~ rounded off to three decimal digits is ~0.571~ . Thus, ~S~ is 0.571 .

Sample Input 2

7 3

Sample Output 2

0.429

~\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots~ rounded off to three decimal digits is ~0.429~ . (Note that it got rounded up.)
Thus, ~S~ is 0.429 .

Sample Input 3

2 1

Sample Output 3

0.500

~\dfrac{B}{A} = \dfrac{1}{2} = 0.5~ rounded off to three decimal digits is again ~0.5~ .
Thus, ~S~ is 0.500 . Note that it must have three decimal places.

Sample Input 4

10 10

Sample Output 4

1.000

Sample Input 5

1 0

Sample Output 5

0.000

Problem Statement

There is a grid with ~H~ rows from top to bottom and ~W~ columns from left to right. Let ~(i, j)~ denote the square at the ~i~ -th row from the top and ~j~ -th column from the left.
The squares are described by characters ~C_{i,j}~ . If ~C_{i,j}~ is . , ~(i, j)~ is empty; if it is # , ~(i, j)~ contains a box.

For integers ~j~ satisfying ~1 \leq j \leq W~ , let the integer ~X_j~ defined as follows.

• ~X_j~ is the number of boxes in the ~j~ -th column. In other words, ~X_j~ is the number of integers ~i~ such that ~C_{i,j}~ is # .

Find all of ~X_1, X_2, \dots, X_W~ .

Constraints

• ~1 \leq H \leq 1000~
• ~1 \leq W \leq 1000~
• ~H~ and ~W~ are integers.
• ~C_{i, j}~ is . or # .

Input

The input is given from Standard Input in the following format:

~H~ ~W~

~C_{1,1}C_{1,2}\dots C_{1,W}~

~C_{2,1}C_{2,2}\dots C_{2,W}~

~\vdots~

~C_{H,1}C_{H,2}\dots C_{H,W}~

Output

Print ~X_1, X_2, \dots, X_W~ in the following format:

~X_1~ ~X_2~ ~\dots~ ~X_W~

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the ~1~ -st column, one square, ~(1, 1)~ , contains a box. Thus, ~X_1 = 1~ .
In the ~2~ -nd column, two squares, ~(2, 2)~ and ~(3, 2)~ , contain a box. Thus, ~X_2 = 2~ .
In the ~3~ -rd column, no squares contain a box. Thus, ~X_3 = 0~ .
In the ~4~ -th column, three squares, ~(1, 4)~ , ~(2, 4)~ , and ~(3, 4)~ , contain a box. Thus, ~X_4 = 3~ .
Therefore, the answer is ~(X_1, X_2, X_3, X_4) = (1, 2, 0, 3)~ .

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered ~1~ .

You made ~N~ records. According to the ~i~ -th record, the amoeba numbered ~A_i~ disappeared by dividing itself into two new amoebae, which were then numbered ~2i~ and ~2i+1~ .
Here, amoeba ~A_i~ is said to be the parent of amoebae ~2i~ and ~2i+1~ .

For each ~k=1,\ldots,2N+1~ , how many generations away is amoeba ~k~ from amoeba ~1~ ?

Constraints

• ~1 \leq N \leq 2\times 10^5~
• The records are consistent. That is:
  • ~1\leq A_i \leq 2i-1~ .
  • ~A_i~ are distinct integers.

Input

The input is given from Standard Input in the following format:

~N~

~A_1~ ~A_2~ ~\ldots~ ~A_N~

Output

Print ~2N+1~ lines. The ~k~ -th line should contain the generation distance between amoeba ~1~ and amoeba ~k~ .

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba ~1~ , amoebae ~2~ and ~3~ were born. From amoeba ~2~ , amoebae ~4~ and ~5~ were born.

• Amoeba ~1~ is zero generations away from amoeba ~1~ .
• Amoeba ~2~ is one generation away from amoeba ~1~ .
• Amoeba ~3~ is one generation away from amoeba ~1~ .
• Amoeba ~4~ is one generation away from amoeba ~2~ , and two generations away from amoeba ~1~ .
• Amoeba ~5~ is one generation away from amoeba ~2~ , and two generations away from amoeba ~1~ .

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

You are given a sequence ~A = (A_1, A_2, \dots, A_N)~ of length ~N~ consisting of positive integers, and integers ~x~ and ~y~ .
Determine whether it is possible to place ~N+1~ points ~p_1, p_2, \dots, p_N, p_{N+1}~ in the ~xy~ -coordinate plane to satisfy all of the following conditions. (It is allowed to place two or more points at the same coordinates.)

• ~p_1 = (0, 0)~ .
• ~p_2 = (A_1, 0)~ .
• ~p_{N+1} = (x, y)~ .
• The distance between the points ~p_i~ and ~p_{i+1}~ is ~A_i~ . ( ~1 \leq i \leq N~ )
• The segments ~p_i p_{i+1}~ and ~p_{i+1} p_{i+2}~ form a ~90~ degree angle. ( ~1 \leq i \leq N - 1~ )

Constraints

• ~2 \leq N \leq 10^3~
• ~1 \leq A_i \leq 10~
• ~|x|, |y| \leq 10^4~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~x~ ~y~ ~A_1~ ~A_2~ ~\dots~ ~A_N~

Output

If it is possible to place ~p_1, p_2, \dots, p_N, p_{N+1}~ to satisfy all of the conditions in the Problem Statement, print Yes ; otherwise, print No .

Sample Input 1

3 -1 1
2 1 3

Sample Output 1

Yes

The figure below shows a placement where ~p_1 = (0, 0)~ , ~p_2 = (2, 0)~ , ~p_3 = (2, 1)~ , and ~p_4 = (-1, 1)~ . All conditions in the Problem Statement are satisfied.

Sample Input 2

5 2 0
2 2 2 2 2

Sample Output 2

Yes

Letting ~p_1 = (0, 0)~ , ~p_2 = (2, 0)~ , ~p_3 = (2, 2)~ , ~p_4 = (0, 2)~ , ~p_5 = (0, 0)~ , and ~p_6 = (2, 0)~ satisfies all the conditions. Note that multiple points may be placed at the same coordinates.

Sample Input 3

4 5 5
1 2 3 4

Sample Output 3

No

Sample Input 4

3 2 7
2 7 4

Sample Output 4

No

Sample Input 5

10 8 -7
6 10 4 1 5 9 8 6 5 1

Sample Output 5

Yes