Each fighter of the 25th Rifle Division has been given the newest communication device—a mobile telegraph. It can be used for sending telegrams to the command and to fellow fighters right at the battle field. Unfortunately, the design of telegraphs is still far from being perfect, so messages can be sent only between some pairs of telegraphs.

Each device has a unique number, which is a string consisting of ten decimal digits. A message can be sent from a telegraph a to a telegraph b only if the number b can be obtained from the number a by changing exactly one digit or by swapping two digits, and the time of sending a message from the telegraph a to the telegraph b depends on the length of the longest common prefix of their numbers: the longer the common prefix is, the faster the message is sent.

During a battle, Anka noticed from her well-camouflaged position the group of Whites trying to bypass Red Army fighters in the rear. What minimal time is required to deliver this information from Anka to Chapaev by telegraph, using, possibly, telegraphs of other Red Army fighters?

The first line contains the number n of fighters in the division (2 ≤ n ≤ 50000). The second line contains ten integers in the range from 1 to 10000 separated with a space written in the nonascending order. These are the times of sending a message from one telegraph to another if the length of their common prefix is zero, one, two, …, nine. The next n lines contain the numbers of telegraphs given to the fighters of the division. The number of Anka's telegraph is described first, and the number of Chapaev's telegraph is described last. All the numbers of telegraphs are different.

Output the only line “-1” if it is impossible to deliver the message to Chapaev. Otherwise, in the first line output the minimal time required to deliver the message. In the second line output the number of fighters in the delivery path, and in the third line output their numbers separated with a space in the order from Anka to Chapaev. The fighters of the 25th Division are numbered from 1 to n in the order in which their mobile telegraphs are described in the input. If there are several ways to deliver the message in minimal time, output any of them.