Tower Floor Display

Time limit2sMemory limit128 MB

Summary

Given an N-digit floor number shown on a lamp display where off lamps may be broken, compute the average of every floor number consistent with the lit lamps.

Level: Medium5 of 10
Topics: Math, Combinatorics, String, Implementation
Solved: No attempts yet

Problem

A tall building has 10^N floors, numbered from floor 0 through floor 10^N - 1. Each floor number is shown with exactly N digits. If a floor number has fewer than N digits, leading zeroes are added.

One digit is displayed using 15 lamps arranged in a grid of height 5 and width 3. The following grid shows the digits from 0 through 9. # means the lamp is on, and . means the lamp is off.

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

You are given the current state of the elevator floor display. Adjacent digits are separated by one column of off lamps. Some lamps may be broken and therefore always remain off. Assuming that some of the currently off lamps may be broken, compute the average of all floor numbers that the display could currently represent.

Input

The first line contains N. N is a positive integer no greater than 9.

The next five lines contain the state of the elevator floor display. Each string has length 4N - 1.

Output

Print the average of all floor numbers that the display could represent. If no floor number is possible, print -1.

An absolute or relative error up to 10^-5 is accepted.

Examples4

Example 1
Input
```
1
###
#.#
###
#.#
###
```
Expected output
```
8.0
```

Example 2

Input

2
###.###
#.#.#.#
#.#.###
#.#...#
###.###

Expected output

48.5

Example 3

Input

2
.......
.......
.......
.......
.......

Expected output

49.5

Example 4
Input
```
1
...
.#.
...
...
...
```
Expected output
```
-1
```