Problem D
Nested Shapes

Image by natareal (CanStockPhoto); Used under license

Consider a sequence of $2$-dimensional regions in the plane, $R_1, R_2, \ldots , R_ n$, satisfying the following:

1. Each $R_ i$ has one of three shapes: (i) a circle, (ii) a square (with sides parallel to the $x$-$y$ axes), or (iii) a diamond (a square rotated $45$ degrees). Each $R_ i$ is solid, i.e., it includes its interior.

2. For $i \geq 2$, $R_ i$ and $R_{i-1}$ do not have the same shape.

3. For $i \geq 2$, $R_ i$ is inscribed in $R_{i-1}$. Informally, this means that $R_ i$ fits “snugly” inside $R_{i-1}$. For the shapes in this problem, this is equivalent to saying that $R_ i$ and $R_{i-1}$ share the same center point, and that $R_ i$ is as large as possible without any point in $R_ i$ lying outside $R_{i-1}$.

Given the shapes of $R_1, R_2, \ldots , R_ n$, and either the area or the perimeter (as specified) of the outermost region $(R_1)$, find either the area or the perimeter (as required) of the innermost region $(R_ n)$.

Figure 1: Illustration of Sample Input $1$

Input

There are three lines of input. The first line contains an integer, $n$, the number of regions $(1 \leq n \leq 10)$, followed by a space, followed by a string of length $n$ consisting entirely of characters from $\{ $ ‘C’, ‘S’, ‘D’ $\} $, denoting circle, square, and diamond, respectively. These characters specify the shapes of $R_1, R_2, \ldots , R_ n$ in the same order (so the first character specifies the shape of $R_1$, the second character specifies the shape of $R_2$, etc.). The second line contains a single character, $t_1$, either ‘A’ or ‘P’, followed by a space, followed by an integer, $m$ $(1 \leq m \leq 200)$. If $t_1 =$ ‘A’, then $m$ is the area of $R_1$; if $t_1 =$ ‘P’, then $m$ is the perimeter of $R_1$. The third line contains a single character, $t_ n$, either ‘A’ or ‘P’, specifying whether you are required to compute the area or the perimeter of $R_ n$, respectively.

Output

Output a single real number that is either the area of $R_ n$ (if $t_ n =$ ‘A’) or the perimeter of $R_ n$ (if $t_ n =$ ‘P’). Your answer will be considered correct if it is within $10^{-6}$ of the official answer.

3 CSD
A 12
P

7.817640190446719