Bar Code

Time limit1sMemory limit128 MB

Summary
Reconstruct the unique binary digit sequence from a partially unreadable bar code grid of black/white/unknown squares, or report it cannot be determined.
Level

Medium6 of 10

Topics
Backtracking, String, Simulation
Solved
No attempts yet

Problem

To speed up the work of cashiers, each product is marked with a series of black and white vertical bars called a bar code. An optical reader can turn it into a sequence of zeros and ones that represents the product's code.

A bar code consists of black and white vertical bars, each of which can be thin or thick. White and black bars alternate; that is, no two adjacent bars have the same color. Regardless of its color, a thin bar represents 0 and a thick bar represents 1. Thus a bar code represents a sequence of binary digits.

Each bar is drawn as a column that is five 'squares' tall (see the picture below). A thin bar is one 'square' wide and a thick bar is two 'squares' wide. For example, the bar code shown below represents the sequence 010001.

The bar code reader used here was dropped on the floor, and since then it fails to recognize the color of some 'squares'.

Write a program that, given a scan produced by this faulty reader, determines which sequence of binary digits it represents, provided that sequence can be determined uniquely.

Input

The first line contains an integer N (1 ≤ N ≤ 100), the total width of the scanned bar code.

Each of the next five lines contains N characters. Each character is X, . (a dot), or ? (a question mark): X is a 'square' successfully recognized as black, . is a 'square' successfully recognized as white, and ? means the reader could not determine the color of that 'square'.

Output

Print a single line containing the sequence of binary digits represented by the bar code, if it can be determined uniquely. If the sequence cannot be determined uniquely, print the word UNDETERMINABLE instead.

Examples3

  1. Example 1

    Input
    4
    .X??
    .??.
    ??.?
    ?X.?
    .X?.
    
    Expected output
    001
    
  2. Example 2

    Input
    8
    ?.?X?X??
    ??.X??..
    ????????
    ?.???X..
    ?..X?X??
    
    Expected output
    010001
    
  3. Example 3

    Input
    9
    XX.?X..?X
    ?X.?X?.?X
    XX.?X..??
    X?.?X..?X
    XX.?X?.?X
    
    Expected output
    UNDETERMINABLE