Think about a complete binary tree of height k that uses the set 2 features. Each leaf corresponds to a particular integer. This tree can represent any Boolean function over k-bit integers, just by labeling each leaf "true" or "false" in the appropriate manner. So this tree can represent the function that used set 1 features. But this tree is very big. Can you modify it so that it is smaller, with only O(mk) nodes?
That's it! You're on your own now!