Hey, I was upsolving some problems and one of them was this one: 599E - Сэнди и Орешки

I liked the problem and after reading the editorial and some silly mistakes in the implementation I got accepted and feel that I learned something, but there's something I don't understand in the editorial, the time complexity.

I understand how to check the fulfillment of the conditions before a transition in O(N³) or O(N·Q) but I don't understand where does the O(3^N) come from.

Could anyone give me an explanation or at least some hints about the 3^N? ;)

Here's my solution btw 14830356

Thanks :)