#include using namespace std; template inline void read(T &x){ T s = 0; int st = 1; char c = getchar(); while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();} while(c >= '0' && c <= '9'){s = (s <<3) +(s << 1) + (c ^ 48); c = getchar();} x = s * st; } template inline void read(T &x, Args &...args){ read(x); read(args...); } template inline void write(T x){ if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + 48); } #define LL long long const int N = 2e3 + 5, M = 9e6 + 5; LL f[M]; int main(){ // freopen("alive.in", "r", stdin); // freopen("alive.out", "w", stdout); // cerr <