G. Number of Faces
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Two planes, $$$H_1$$$ and $$$H_2,$$$ are in a three-dimensional Euclidean space with axes, $$$x, y,$$$ and $$$z,$$$ where $$$H_1$$$ is defined by $$$z=1$$$ and $$$H_2$$$ by $$$z=2.$$$

You are given $$$n$$$ real numbers, $$$d_1, \ldots, d_n,$$$ and $$$m$$$ real numbers, $$$d'_1, \ldots, d'_m$$$. These real numbers are positive and strictly less than $$$180.$$$ Consider drawing the following convex polygons on the planes $$$H_1$$$ and $$$H_2$$$.

  • On $$$H_1$$$, you draw an $$$n$$$-sided polygon. The interior angles at its vertices are $$$d_1, \ldots, d_n$$$ degrees in counterclockwise order as viewed from the origin.
  • Similarly, on $$$H_2$$$, you draw an $$$m$$$-sided polygon. The interior angles at its vertices are $$$d'_1, \ldots, d'_m$$$ degrees in counterclockwise order as viewed from the origin.
Here, only the interior angles of the polygons are specified; the lengths of their edges and the positions of their vertices are not.

Once the positions of the two polygons are fixed, the convex polyhedron whose vertex set is these $$$n+m$$$ vertices is uniquely determined. Write a program that enumerates all the possible numbers of faces that such a convex polyhedron can have.

Here, all the dihedral angles (angles between two adjacent faces) of a convex polyhedron must be strictly less than $$$180$$$ degrees.

In the first test case of Sample Input 1, quadrilaterals whose interior angles are all $$$90$$$ degrees are drawn on $$$H_1$$$ and $$$H_2$$$. For example, a rectangular cuboid can be constructed as in Figure G.1 (a), which has six faces. By rotating one of the quadrilaterals as shown in Figure G.1 (b), a convex polyhedron with ten faces can be constructed. The possible numbers of faces are six and ten.

Figure G.1: The first test case of Sample Input 1
Input

The input consists of at most $$$50$$$ test cases, each in the following format.

$$$n$$$
$$$d_1$$$
$$$\vdots$$$
$$$d_n$$$
$$$m$$$
$$$d'_1$$$
$$$\vdots$$$
$$$d'_m$$$

The integer $$$n$$$ represents the number of vertices of the polygon drawn on $$$H_1$$$ ($$$3 \le n \le 50$$$). The real numbers, $$$d_1, \ldots, d_n$$$, represent the interior angles. They are at least $$$10^{-9}$$$ and strictly less than $$$180,$$$ and are given with exactly nine digits after the decimal point. They satisfy $$$d_1 + \cdots + d_n = (n-2)\times 180.$$$

Similarly, the integer $$$m$$$ represents the number of vertices of the polygon drawn on $$$H_2$$$ ($$$3 \le m \le 50$$$). The real numbers, $$$d'_1, \ldots, d'_m$$$, represent the interior angles. They are at least $$$10^{-9}$$$ and strictly less than $$$180,$$$ and are given with exactly nine digits after the decimal point. They satisfy $$$d'_1 + \cdots + d'_m = (m-2)\times 180.$$$

The end of the input is indicated by a line consisting only of a zero.

Output

For each test case, output in a line all possible numbers of faces that the convex polyhedron can have, in ascending order, separated by a space.

Example
Input
4
90.000000000
90.000000000
90.000000000
90.000000000
4
90.000000000
90.000000000
90.000000000
90.000000000
3
33.333333333
66.666666666
80.000000001
3
80.000000001
66.666666666
33.333333333
3
59.165980540
68.504848124
52.329171336
5
87.702342452
144.626828884
97.879972796
169.296126888
40.494728980
0
Output
6 10
6 7 8
8 9 10