Given a set of integers A = { a1,a2,a3,...an } and an integer N. You need to find a way to reach N, starting from 1 and at each step multiplying current value by any element of A. Repetition of element is allowed. Since there may be many solutions having the minimum number of states to reach N you can print the lexicographically smallest series among the solutions which contains the least number of states.

For eg: N = 12 , A = [ 2,3,4 ]

a) 1 — > 2 — > 2 — > 3

b) 1 — > 4 -> 3

c) 1 — > 3 -> 4 ( This is the best solution )