#include <iostream>
#include <vector>
 
class SequenceGenerator{
private:
	static std::vector<int> results;
public:
	static int getNthInSequence(int n){
		if (results.size() == 0){
			results.push_back(0); // just to ignore the 0 index
			results.push_back(1);
			results.push_back(2);
			results.push_back(5);
		}
		if (n < results.size())
			return results.at(n);
 
		int nMinus1 = getNthInSequence(n - 1);
        int nMinus3 = getNthInSequence(n - 3);
        int result = nMinus1 + nMinus1 - nMinus3;
        results.push_back(result);
        return result;
	}
};
 
std::vector<int> SequenceGenerator::results;
 
int main() {
 
	for (int i = 1; i <= 30; i++){
		std::cout << SequenceGenerator::getNthInSequence(i) << " ";
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKY2xhc3MgU2VxdWVuY2VHZW5lcmF0b3J7CnByaXZhdGU6CglzdGF0aWMgc3RkOjp2ZWN0b3I8aW50PiByZXN1bHRzOwpwdWJsaWM6CglzdGF0aWMgaW50IGdldE50aEluU2VxdWVuY2UoaW50IG4pewoJCWlmIChyZXN1bHRzLnNpemUoKSA9PSAwKXsKCQkJcmVzdWx0cy5wdXNoX2JhY2soMCk7IC8vIGp1c3QgdG8gaWdub3JlIHRoZSAwIGluZGV4CgkJCXJlc3VsdHMucHVzaF9iYWNrKDEpOwoJCQlyZXN1bHRzLnB1c2hfYmFjaygyKTsKCQkJcmVzdWx0cy5wdXNoX2JhY2soNSk7CgkJfQoJCWlmIChuIDwgcmVzdWx0cy5zaXplKCkpCgkJCXJldHVybiByZXN1bHRzLmF0KG4pOwoJCQoJCWludCBuTWludXMxID0gZ2V0TnRoSW5TZXF1ZW5jZShuIC0gMSk7CiAgICAgICAgaW50IG5NaW51czMgPSBnZXROdGhJblNlcXVlbmNlKG4gLSAzKTsKICAgICAgICBpbnQgcmVzdWx0ID0gbk1pbnVzMSArIG5NaW51czEgLSBuTWludXMzOwogICAgICAgIHJlc3VsdHMucHVzaF9iYWNrKHJlc3VsdCk7CiAgICAgICAgcmV0dXJuIHJlc3VsdDsKCX0KfTsKCnN0ZDo6dmVjdG9yPGludD4gU2VxdWVuY2VHZW5lcmF0b3I6OnJlc3VsdHM7CgppbnQgbWFpbigpIHsKCQoJZm9yIChpbnQgaSA9IDE7IGkgPD0gMzA7IGkrKyl7CgkJc3RkOjpjb3V0IDw8IFNlcXVlbmNlR2VuZXJhdG9yOjpnZXROdGhJblNlcXVlbmNlKGkpIDw8ICIgIjsKCX0KCQoJcmV0dXJuIDA7Cn0=