- 108

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

You are given a line of 95 bits sequence`scanline`representing an image received from a barcode scanner.

The sequence is in EAN-13 format barcode.

**NOTE**The input sequence might be given in reversed order. This relates to a real life scenario when scanning the barcode upside-down.

Your mission is to decode this barcode into its decimal 13-digit representation.

Input binary sequence consist of the following blocks:

**LEFT GUARD**+

**LEFT PART**+

**CENTRAL GUARD**+

**RIGHT PART**+

**RIGHT GUARD**.

**LEFT GUARD**and

**RIGHT GUARD**are 3-bit sequences and both should be equal to

**CENTRAL GUARD**has a length of 5, having value

Guards allow the scanner to identify the start and end of the barcode in an image as well as the width of the bits.

**LEFT PART**and

**RIGHT PART**each consist of 6 7-bit codes.

Left part may have digits coded with both

**L-code**(which have odd parity) and

**G-code**(even parity).

Right part consists of only even parity

**R-codes**.

You may also notice that R-code is a reversed version of G-code and an inverted version of L-code.

DigitL-codeG-codeR-code00001101 0100111 111001010011001 0110011 110011020010011 0011011 110110030111101 0100001 100001040100011 0011101 101110050110001 0111001 100111060101111 0000101 101000070111011 0010001 100010080110111 0001001 100100090001011 0010111 1110100

Please refer to

So at this point you are able to reconstruct the last 12 digits.

The first EAN-13 digit is encoded by the pattern of L and G codes in

**LEFT PART**using the table below.

First digit First group of 6 digits Last group of 6 digits0LLLLLL RRRRRR1LLGLGG RRRRRR2LLGGLG RRRRRR3LLGGGL RRRRRR4LGLLGG RRRRRR5LGGLLG RRRRRR6LGGGLL RRRRRR7LGLGLG RRRRRR8LGLGGL RRRRRR9LGGLGL RRRRRR

Finally, to verify a barcode after decoding, the following

**CHECKSUM**calculation approach is used:

Multiply every second digit by 3, then add up all the digits. If barcode is correct its checksum would be a multiple of 10.

**Example**

It is easier to understand an example of encoding rather than decoding.

Suppose we want to encode the number 4003994155486.

The first digit is 4, so we will use the pattern LGLLGG in the left part.

We then look up codes 0(L), 0(G), 3(L), 9(L), 9(G), 4(G) in the table:

0001101 0100111 0111101 0001011 0010111 0011101

For the right part we look up 1(R), 5(R), 5(R), 4(R), 8(R), 6(R) :

1100110 1001110 1001110 1011100 1001000 1010000

Finally, add the guards.

**JFYI**

The first 3 digits of EAN-13 correspond to a country code. So, by reading barcodes printed on different products you may identify the country each product was manufactured in.

Input

A string

`scanline`of 95 bits representing a scanned EAN-13 barcode line of pixels (0-white, 1-black)Output

A single line of INVALID SCAN in case any corruption of the input sequence detected.

**13 decimal numbers without spaces**representing decoded EAN-13 barcode orConstraints

Example

Input

10100011010100111011110100010110010111001110101010110011010011101001110101110010010001010000101

Output

4003994155486

A higher resolution is required to access the IDE