Substitution Sequence Range Counts

Time limit2sMemory limit128 MB

Summary

Count occurrences of 1, 2, 3 in a fixed interval of a sequence generated by simultaneous ternary substitution after N steps, without building the whole sequence.

Level: Medium6 of 10
Topics: Recursion, Divide and conquer, Math, String
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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.

Examples4

Example 1
Input
```
1
2
6
2
```
Expected output
```
0 4 1
```
Example 2
Input
```
1
0
2
1
```
Expected output
```
1 1 1
```
Example 3
Input
```
3
1
4
2
```
Expected output
```
2 1 1
```
Example 4
Input
```
2
4
12
3
```
Expected output
```
2 4 3
```