Fractal#1676
A square of size 1 \times 1 is painted either black or white. This square is divided into N^2 equal smaller squares using horizontal and vertical lines, and each small square is painted black or white according to a given pattern. Then, this operation is repeated for every small square: each is again divided into even smaller squares and repainted according to the color of the square being divided. Black squares are repainted using one pattern, and white squares using another. This process is repeated times.
Write a program to calculate the total area covered by black squares.
The first line contains two integers: , the number of divisions, and , the number of division operations (1 \leq N \leq 10, 0 \leq K \leq 10^9).
The second line contains the color of the initial square: for black, for white.
The following lines, each containing numbers, describe the pattern for repainting black squares after division.
The next lines, each containing numbers, describe the pattern for repainting white squares.
Output one number — the total area of black squares, with precision at least 10^{-7}.
Example 1
In the example, the sequence of divisions and repaintings is as follows:
In the resulting figure, the black area consists of small squares with side length .