Note: this problem is for instructional purposes only. The encoding described below is NOT the one actually used by the U.S. Post Office, although it is similar. For information about bar codes in the real world, try here. (Thanks to Tom Seven for this link.)
The Post Office has gotten sick and tired of trying to read hastily scribbled zip codes and is now requiring that all zip codes be barcoded. Zip codes consist of the standard 5-digit code, optionally followed by a 4-digit "plus-4" code, optionally followed by a 2-digit "delivery" code. You cannot have a delivery code without a plus-4 code. An example of each format is shown below.
65804 65804-0087 65804-0087+01
Barcodes use sequences of long and short bars; we will use "." to represent a short bar and "!" to represent a long one. A zip code is barcoded as follows
!NZZZZZPPPPDDC!
where N is the length of the zip code (either 5, 9, or 11); Z, P, and D are the digits of the zip, plus-4, and delivery codes; and C is the checksum. The P and D digits are optional. The checksum is the smallest nonnegative number that, when added to all the digits of the zip code and the length, will make the result a multiple of 10. For example, with the zip code 65804 the sum of the length and the digits is 5+6+5+8+0+4=28, so the checksum is 2. Each number is encoded in binary, where "." means 0 and "!" means 1. The only exception is that zero is encoded as 10.
The input will contain one or more zip codes, each on a line by itself with no leading or embedded blanks. For each zip code output the corresponding barcode as shown in the example below.
Input must be read from the file "prob30.in", and output must be
written to the file "prob30.out". All output to the screen will be
ignored.
<BOF> 65807 90210-8721+02 12345-5678 <EOF>
!.!.!.!!..!.!!...!.!..!!!!..!! !!.!!!..!!.!...!....!!.!.!....!!!..!....!!.!...!..!!!! !!..!...!..!...!!.!...!.!.!.!.!!..!!!!...!.!.!