#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using Long = unsigned long long;
struct XLong {
static Long const F=100000000ULL;
vector<Long> d;
XLong()=default;
XLong(vector<Long>&& i): d{move(i)} {}
XLong(Long i): d{i} {}
//make all array elements in range of 8 digits
void inRange() {
Long rem=0;
for (Long& dp: d) {
dp += rem;
rem = dp/F;
dp %= F;
}
while(d.back()==0)
d.pop_back();
}
//plus
XLong operator + (XLong const& r) const {
size_t m= 1 + max(d.size(), r.d.size());
XLong ret{vector<Long>(m, 0)};
for(size_t i=0; i<d.size(); i++)
ret.d[i] = d[i];
for(size_t i=0; i<r.d.size(); i++)
ret.d[i] += r.d[i];
ret.inRange();
return ret;
}
//multiply
XLong operator * (XLong const& r) const {
size_t m= 1 + 2*max(d.size(), r.d.size());
XLong ret{vector<Long>(m, 0ULL)};
for (size_t i=0; i<d.size(); i++) {
for (size_t j=0; j<r.d.size(); j++) {
int p=i+j;
Long dp=d[i]*r.d[j];
ret.d[p] += dp%F;
ret.d[p+1] += dp/F;
}
}
ret.inRange();
return ret;
}
//output
void print() {
inRange();
for (int i=d.size()-1; i>=0; i--) {
if (i==d.size()-1)
printf("%lld", d[i]);
else
printf("%08lld", d[i]);
}
}
};
int main() {
XLong A{1ULL};
XLong B{1ULL};
for (int i=2; i<12; i++) {
XLong C=B*B + A;
A=B;
B=C;
cout<<i<<' ';
C.print();
cout<<endl;
}
return 0;
}
I2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIExvbmcgPSB1bnNpZ25lZCBsb25nIGxvbmc7CgpzdHJ1Y3QgWExvbmcgewogICAgc3RhdGljIExvbmcgY29uc3QgRj0xMDAwMDAwMDBVTEw7CiAgICB2ZWN0b3I8TG9uZz4gZDsKICAgIFhMb25nKCk9ZGVmYXVsdDsKICAgIFhMb25nKHZlY3RvcjxMb25nPiYmIGkpOiBke21vdmUoaSl9IHt9CiAgICBYTG9uZyhMb25nIGkpOiBke2l9IHt9CiAgICAKICAgIC8vbWFrZSBhbGwgYXJyYXkgZWxlbWVudHMgaW4gcmFuZ2Ugb2YgOCBkaWdpdHMKICAgIHZvaWQgaW5SYW5nZSgpIHsKICAgICAgICBMb25nIHJlbT0wOwogICAgICAgIGZvciAoTG9uZyYgZHA6IGQpIHsKICAgICAgICAgICAgZHAgKz0gcmVtOwogICAgICAgICAgICByZW0gPSBkcC9GOwogICAgICAgICAgICBkcCAlPSBGOwogICAgICAgIH0KICAgICAgICB3aGlsZShkLmJhY2soKT09MCkKICAgICAgICAgICAgZC5wb3BfYmFjaygpOwogICAgfQogICAgLy9wbHVzCiAgICBYTG9uZyBvcGVyYXRvciArIChYTG9uZyBjb25zdCYgcikgY29uc3QgewogICAgICAgIHNpemVfdCBtPSAxICsgbWF4KGQuc2l6ZSgpLCByLmQuc2l6ZSgpKTsKICAgICAgICBYTG9uZyByZXR7dmVjdG9yPExvbmc+KG0sIDApfTsKICAgICAgICBmb3Ioc2l6ZV90IGk9MDsgaTxkLnNpemUoKTsgaSsrKQogICAgICAgICAgICByZXQuZFtpXSA9IGRbaV07CiAgICAgICAgZm9yKHNpemVfdCBpPTA7IGk8ci5kLnNpemUoKTsgaSsrKQogICAgICAgICAgICByZXQuZFtpXSArPSByLmRbaV07CiAgICAgICAgcmV0LmluUmFuZ2UoKTsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQogICAgLy9tdWx0aXBseQogICAgWExvbmcgb3BlcmF0b3IgKiAoWExvbmcgY29uc3QmIHIpIGNvbnN0IHsKICAgICAgICBzaXplX3QgbT0gMSArIDIqbWF4KGQuc2l6ZSgpLCByLmQuc2l6ZSgpKTsKICAgICAgICBYTG9uZyByZXR7dmVjdG9yPExvbmc+KG0sIDBVTEwpfTsKICAgICAgICBmb3IgKHNpemVfdCBpPTA7IGk8ZC5zaXplKCk7IGkrKykgewogICAgICAgICAgICBmb3IgKHNpemVfdCBqPTA7IGo8ci5kLnNpemUoKTsgaisrKSB7CiAgICAgICAgICAgICAgICBpbnQgcD1pK2o7CiAgICAgICAgICAgICAgICBMb25nIGRwPWRbaV0qci5kW2pdOwogICAgICAgICAgICAgICAgcmV0LmRbcF0gKz0gZHAlRjsKICAgICAgICAgICAgICAgIHJldC5kW3ArMV0gKz0gZHAvRjsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXQuaW5SYW5nZSgpOwogICAgICAgIHJldHVybiByZXQ7CiAgICB9CiAgICAvL291dHB1dAogICAgdm9pZCBwcmludCgpIHsKICAgICAgICBpblJhbmdlKCk7CiAgICAgICAgZm9yIChpbnQgaT1kLnNpemUoKS0xOyBpPj0wOyBpLS0pIHsKICAgICAgICAgICAgaWYgKGk9PWQuc2l6ZSgpLTEpCiAgICAgICAgICAgICAgICBwcmludGYoIiVsbGQiLCBkW2ldKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcHJpbnRmKCIlMDhsbGQiLCBkW2ldKTsKICAgICAgICB9CiAgICB9Cn07CgppbnQgbWFpbigpIHsKCVhMb25nIEF7MVVMTH07CglYTG9uZyBCezFVTEx9OwoJZm9yIChpbnQgaT0yOyBpPDEyOyBpKyspIHsKCQlYTG9uZyBDPUIqQiArIEE7CgkJQT1COwoJCUI9QzsKCQljb3V0PDxpPDwnICc7CgkJQy5wcmludCgpOwoJCWNvdXQ8PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==