Suppose you are in front of N machines, each machine has fixed number of balls (each ball of certain color). You see the balls in each machine.

Your goal is to get 2 balls of the same color. When you press the button of one certain machine, the machine would drop out a random ball and you take this ball.

Find minimum number of pressings X such that there's one sequence of machine presses of length X that would get you 2 similar balls no matter what you get in each draw.

sample:

4 machines

3 balls 1 2 3

1 ball 1

1 ball 2

1 ball 3

Answer 2:

first press first machine, depending on what it gives you press one of the reamining

sample2:

2 machines

2 balls 1 2

2 balls 1 2

answer 3:

If you decide to press only 2 buttons, no matter what machines you press there's always a probability to get {1,2}

so you need a third click to ensure


----------------------------------------------------------------------------------



You have N words of same length L

they are written on top of each other in a grid format

abcd

bcde

efgh

find a permutation of columns such that when you apply it all words are sorted in lexicographical order or state that it's impossible. in case of multiplle solutions output least lexico permutation.

N*L <= 10^6