Substitution Sequence Range Counts

At first, the sequence consists of a single number. Every second, all numbers in the sequence are replaced simultaneously by a sequence of length 3 according to these rules.

• 1 becomes 132.
• 2 becomes 211.
• 3 becomes 232.

You are given the initial number, an integer N, and 0-indexed positions Left and Right. After N seconds, count how many 1s, 2s, and 3s appear from position Left through position Right, inclusive.

The first line contains the initial number. It is one of 1, 2, and 3.

The second line contains Left, the third line contains Right, and the fourth line contains N.

Print three space-separated integers: the number of 1s, the number of 2s, and the number of 3s in the requested interval.

• The initial number is one of 1, 2, and 3.
• 0 ≤ N ≤ 20
• 0 ≤ Left ≤ Right ≤ 3^N - 1
• Both Left and Right are less than 2,147,483,647.