Cards
On the day of birth Vasya gave to his brother Pete set of N cards. Vasya and then Peter wrote one number on each card, Vasya on the one hand, and Peter - on the other. The brothers scattered the cards across the room and fled. All this outrage saw their grandmother Lyudmila Petrovna. She worked for many years as an accountant, so she decided to refresh and invented a game: you have some cards to turn over "Vasya" side, and some "Petya", and so that the amount was the maximum possible. But, since she loves both brothers are equally strong, it added an additional condition that the number of cards turned upside down, "Petya" party should be different from the number of cards turned upside down "Vasya" side, no more than K.
Lyudmila Petrovna easily coped with the problem, but you can?
Input
The first line contains the numbers N and K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) — number of cards. Further, the N rows contains a description of cards - two integers: the first number is written on one side Vasya card, the second written by PETER on the other side. Vasya and Peter do not know the numbers that exceed the modulo 10^9.
Output
The first line of the output file should contain one number - the maximum possible amount. Next, bring out the N numbers - for each card output 1 if it Petya's party and 0 if Vasin.
If the answers are several output any.