CF878D Magic Breeding

Nikita and Sasha play a computer game where you have to breed some magical creatures. Initially, they have $ k $ creatures numbered from $ 1 $ to $ k $ . Creatures have $ n $ different characteristics. Sasha has a spell that allows to create a new creature from two given creatures. Each of its characteristics will be equal to the maximum of the corresponding characteristics of used creatures. Nikita has a similar spell, but in his spell, each characteristic of the new creature is equal to the minimum of the corresponding characteristics of used creatures. A new creature gets the smallest unused number. They use their spells and are interested in some characteristics of their new creatures. Help them find out these characteristics.

N/A

N/A

In the first sample, Sasha makes a creature with number $ 3 $ and characteristics $ (2,2) $ . Nikita makes a creature with number $ 4 $ and characteristics $ (1,1) $ . After that they find out the first characteristic for the creature $ 3 $ and the second characteristic for the creature $ 4 $ .