Our friend the king has a fairly large army that is divided into a number of battalions. Once a year, in order to ensure that his army is fighting fit, he organises war exercises. Here the army is divided into two teams and they fight each other in mock battles.

Each team is a collection of battalions -- that is, each battalion is to assigned to one team or the other and cannot be broken up.

The sizes of these battalions are not all the same. Some of them are huge while others are small. To ensure that the war exercises are useful, the two teams should be of roughly the same size. So he asks the minister to divide the battalions into two teams in such a way that the difference in the total size of the two teams is minimized.

For instance, suppose there are 6 battalions and their sizes are as follows:

Battalion No       Size 
     1              20
     2              30
     3             100
     4              30 
     5              20 
     6              30                         

Then, by using Battalions 1 and 3 in one team and the other four battalions in the other team, the minister would get one team with size 120 and the other with size 110. Thus the difference is sizes is 10. You can verify that this is the best possible.

Your task is to help the minister to select the teams.

The first line of the input contains a single integer N indicating the number of battalions. The following N lines (lines 2,3,...,N+1) contain one positive integer each. The integer on line i+1 indicates the size of the ith battalion.

You may assume that N ≤ 20.

The first line of the output should be a single positive integer indicating the minimum possible difference in the sizes of the two teams. Following this there must be N lines (lines 2, ... N+1) of output, each containing a 0 or a 1. This is a description of a grouping that yields this optimal difference. The value on line i+1 describes whether battalion i goes to team 0 or team 1. If there is more than one such optimal grouping it suffices to describe any one.

IARCS BASIC