ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2013, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. The secret module

Time limit: 1.0 second
Memory limit: 64 MB
Palpatine: Rise, my friend.
Darth Vader: The Death Star will be completed on schedule.
Palpatine: You’ve done well, Lord Vader.
The Death Star space station was created to keep the whole Galaxy under control. This station was equipped with the most powerful weapons and could carry thousands destroyers. The Death Star also had some precautions introduced in order to prevent the rebels from approaching. Specifically, all destroyers that approached the station were subject to thorough examination. There was a special module responsible for managing the entrance control. The module read and checked the arriving ship’s identification number.
The ship’s number is a non-negative integer, it is read from the left to the right. The number can have any length. Leading zeroes should not affect the module verdict. The checking module is a finite deterministic automaton with n states. Initially, the automaton is at the first state. It checks a ship’s number as follows. It reads a digit and changes its state according to some rule, determined by the current state and the analyzed digit. If the automaton reads the ship’s number to the end and finishes in a terminal state, then the station lets the ship in. Otherwise, the ship is destroyed. Any ship with an empty identification number also has to be destroyed, hence the initial state is non-terminal for sure.
This system worked perfectly well until the day the rebels destroyed the station. The designers of the new Death Star decided to use a similar technology for checking ships’ numbers. But the rebels already know the numbers of many enemy ships. So, in order to raise security levels, the identification numbers of all imperial destroyers were increased by some number k.
Your task is to make a special module for the new Death Star. The module should let a ship in if and only if its number is the new number of one of the imperial destroyers.


The first line of the input contains integer k (1 ≤ k ≤ 8). Then the automaton’s description follows. The first line of the description contains the number of the states in the automaton n (1 ≤ n ≤ 100). The second line of the description contains n numbers ti (ti ∈ {0, 1}). ti = 1, if the i-th state is terminal and ti = 0 otherwise. The i-th of the next n lines contains 10 integers that correspond to the numbers of states the automaton will change to if it is in state i and reads digit 0, 1, …, 9 correspondingly.


If there is no proper automaton for the Death Star, print "Impossible". If there is one, print "Success", then print the automaton’s description in the same format as in the input. Your automaton should have at most 25 600 states. It is guaranteed that if there is a proper automaton, then there also is one that fits into the given limit.


0 0 1 0
1 2 4 4 4 4 4 4 4 4
4 2 4 4 4 4 4 4 3 4
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
0 0 0 0 1
1 2 3 4 4 4 4 4 4 4
4 2 3 4 4 4 4 4 4 4
4 5 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
Problem Author: Denis Dublennykh (prepared by Eugene Kurpilyansky)
To submit the solution for this problem go to the Problem set: 1999. The secret module