#if 0 cat <mistaken-paste #endif // thx Ebi-chan! // pragma GCC optimize("unroll-loops") // pragma GCC optimize("O3") #pragma GCC diagnostic ignored "-Wincompatible-pointer-types" #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #define BIG 2000000007LL #define VERYBIG 200000000000000007LL #define ULTRABIG 300000000000000000000LL #define MOD 1000000007LL #define FOD 998244353LL #define HOD 1000000009LL #define IOD 100000007LL typedef uint64_t ull; typedef int64_t ll; #define N_MAX 1048576 #ifdef __cplusplus #include #include // #include #include #include #include #include // #include // #include #include using std::queue; using std::priority_queue; using std::stack; // using std::tuple; using std::set; using std::map; using std::vector; using std::greater; using std::pair; using std::string; // using std::get; // using std::function; // using std::array; using std::cin; using std::cout; using std::endl; template pair operator+(pair l, pair r) { return pair(l.first + r.first, l.second + r.second); } #endif #ifndef M_PI #define M_PI 3.14159265358979323846264338327950 #endif typedef struct { ll a; ll b; } hwll; typedef struct { ll a; ll b; ll c; } hwllc; typedef struct { hwll a; hwll b; } linell; typedef struct { double a; double b; } hwreal; ll n, m; ll h, w; ll k; ll q; ll va, vb, vc, vd, ve, vf; ull ua, ub, uc, ud, ue, uf; long double vra, vrb, vrc; double vda, vdb, vdc; char ch, dh; ull umin (ull x, ull y) { return (x < y) ? x : y; } ull umax (ull x, ull y) { return (x > y) ? x : y; } ll smin (ll x, ll y) { return (x < y) ? x : y; } ll smax (ll x, ll y) { return (x > y) ? x : y; } double dmin (double x, double y) { return (x < y) ? x : y; } double dmax (double x, double y) { return (x > y) ? x : y; } ull gcd (ull x, ull y) { if (y == 0) { return x; } else { return gcd(y, x % y); } } ull bitpow (ull a, ull x, ull modulo) { ull result = 1; while (x) { if (x & 1) { result *= a; result %= modulo; } x /= 2; a = (a * a) % modulo; } return result; } ull divide (ull a, ull b, ull modulo) { return (a * bitpow(b, modulo - 2, modulo)) % modulo; } ull udiff (ull a, ull b) { if (a >= b) { return a - b; } else { return b - a; } } ll sdiff (ll a, ll b) { if (a >= b) { return a - b; } else { return b - a; } } int bitcount (ull n) { int result = 0; while (n) { if (n & 1) result++; n /= 2; } return result; } #define BEGCMP(NAME) int32_t NAME (const void *left, const void *right) #define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right #define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1 // int32_t pullcomp (const void *left, const void *right) { // ull l = *(ull*)left; // ull r = *(ull*)right; // if (l < r) { // return -1; // } // if (l > r) { // return +1; // } // return 0; // } BEGCMP(pullcomp){ DEFLR(ull); CMPRET(l, r); return 0; } BEGCMP(prevcomp){ DEFLR(ll); CMPRET(r, l); return 0; } BEGCMP(pllcomp){ DEFLR(ll); CMPRET(l, r); return 0; } BEGCMP(pcharcomp){ DEFLR(char); CMPRET(l, r); return 0; } BEGCMP(pdoublecomp){ DEFLR(double); CMPRET(l, r); return 0; } int32_t pstrcomp (const void *left, const void *right) { char* l = *(char**)left; char* r = *(char**)right; return strcmp(l, r); } BEGCMP(phwllABcomp){ DEFLR(hwll); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } BEGCMP(phwllREVcomp){ DEFLR(hwll); CMPRET(l.b, r.b); CMPRET(l.a, r.a); return 0; } BEGCMP(ptriplecomp){ DEFLR(hwllc); CMPRET(l.a, r.a); CMPRET(l.b, r.b); CMPRET(l.c, r.c); return 0; } BEGCMP(ptripleREVcomp){ DEFLR(hwllc); CMPRET(l.b, r.b); CMPRET(l.a, r.a); CMPRET(l.c, r.c); return 0; } BEGCMP(ptripleCABcomp){ DEFLR(hwllc); CMPRET(l.c, r.c); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } BEGCMP(phwrealcomp){ DEFLR(hwreal); CMPRET(l.a, r.a); CMPRET(l.b, r.b); return 0; } int32_t pquadcomp (const void *left, const void *right) { linell l = *(linell*)left; linell r = *(linell*)right; ll ac = phwllABcomp(&(l.a), &(r.a)); if (ac) return ac; ll bc = phwllABcomp(&(l.b), &(r.b)); if (bc) return bc; return 0; } int32_t pfracomp (const void *left, const void *right) { hwll l = *(hwll*)left; hwll r = *(hwll*)right; CMPRET(l.a * r.b, l.b * r.a); return 0; } bool isinrange (ll left, ll x, ll right) { return (left <= x && x <= right); } bool isinrange_soft (ll left, ll x, ll right) { return (left <= x && x <= right) || (left >= x && x >= right); } void sw (ll *l, ll *r) { if (*l == *r) return; ll t = *l; *l = *r; *r = t; } void uw (ull *l, ull *r) { if (*l == *r) return; ull t = *l; *l = *r; *r = t; } ull frac[N_MAX * 10], invf[N_MAX * 10]; void f_init (ll n, ll m) { frac[0] = 1; for (ll i = 1; i <= n; i++) { frac[i] = frac[i - 1] * i % m; } invf[n] = divide(1, frac[n], m); for (ll i = n - 1; i >= 0; i--) { invf[i] = invf[i + 1] * (i + 1) % m; } } ull ncr (ll n, ll r, ull m) { if (n < 0 || r < 0 || n < r) return 0; return frac[n] * (invf[r] * invf[n - r] % m) % m; } ll a[N_MAX * 10]; // ull a[N_MAX + 5]; // ll a[3005][3005]; ll b[N_MAX * 5]; // ull b[N_MAX + 5]; // ll b[3005][3005]; ll c[N_MAX * 5]; ll d[N_MAX * 5]; ll e[N_MAX * 4]; char s[N_MAX + 1]; // char s[3010][3010]; char t[N_MAX + 1]; // char t[3010][3010]; char u[N_MAX + 1]; hwll xy[N_MAX]; hwllc tup[N_MAX]; // ll table[3005][3005]; ll table[2005][2005]; ull gin[N_MAX]; // here we go // ull parent[501910], size[501910], edges[501910]; // void init (ull n) { // for (ll i = 0; i < n; i++) { // parent[i] = i; // size[i] = 1; // } // } // ll find (ull x) { // if (parent[x] == x) return x; // return parent[x] = find(parent[x]); // } // bool unite (ull v, ull u) { // v = find(v); // u = find(u); // if (v == u) return false; // if (size[v] < size[u]) { // ull tmp = v; // v = u; // u = tmp; // } // size[v] += size[u]; // parent[u] = v; // return true; // } ll func1 (ll x) { ll result = 0; for (ll i = 1; i <= n; i++) { ll y = x - i; if (y < 2) continue; if (y > n * 2) y = n * 2; result += d[y]; } // printf("%lld: %lld\n", x, result); return result; } ll func2 (ll x, ll sum) { ll result = 0; for (ll i = 1; i <= x; i++) { ll y = sum - i; if (y < 2 || y > n * 2) continue; result += c[y]; } // printf("%lld %lld: %lld\n", x, sum, result); return result; } void query (ll x, ll y) { ll s = 0, t = 0; for (ll i = 0; i < 10; i++) { if (x & (1LL << i)) { b[s++] = i; } if (y & (1LL << i)) { c[t++] = i; } } puts("Yes"); printf("%lld", s); for (ll i = 0; i < s; i++) printf(" %lld", b[i] + 1); putchar('\n'); printf("%lld", t); for (ll i = 0; i < t; i++) printf(" %lld", c[i] + 1); putchar('\n'); exit(0); } ll dp[123456][3][2]; ll mat[6][6]; ll matp[6][6], powg[6][6], tmp[6][6]; void matpow (ll x) { ll i, j, ki; for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { matp[i][j] = ((i == j) ? 1 : 0); powg[i][j] = mat[i][j]; } } while (x) { if (x % 2) { for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { tmp[i][j] = 0; for (ki = 0; ki < 6; ki++) { tmp[i][j] += (matp[i][ki] * powg[ki][j]) % MOD; } tmp[i][j] %= MOD; } } for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { matp[i][j] = tmp[i][j]; } } } x /= 2; for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { tmp[i][j] = 0; for (ki = 0; ki < 6; ki++) { tmp[i][j] += (powg[i][ki] * powg[ki][j]) % MOD; } tmp[i][j] %= MOD; } } for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { powg[i][j] = tmp[i][j]; } } } } ll solve () { ll i, j, ki, li; // ull result = 0; ll result = 0; double dresult = 0; // ull maybe = 0; ll maybe = 0; // ull sum = 0; ll sum = 0; ll item; ll *dpcell; va %= 10; vb %= 10; vc %= 10; k -= 3; // for (i = 0; i <= 9; i++) { // for (j = 0; j <= 9; j++) { // for (ki = 0; ki <= 9; ki++) { // va = i; // vb = j; // vc = ki; // for (li = 0; li < 1000; li++) a[li] = b[li] = 0; // ll index = 0; // while (true) { // ll vd = (va + vb + vc) % 10; // va = vb; // vb = vc; // vc = vd; // index++; // item = (va * 100 + vb * 10 + vc); // if (b[item] > 0) { // break; // } // a[index] = item; // b[item] = index; // } // if (index == 125) printf("%lld %lld %lld\n", i, j, ki); // } // } // } ll index = 0; while (true) { ll vd = (va + vb + vc) % 10; va = vb; vb = vc; vc = vd; index++; item = (va * 100 + vb * 10 + vc); if (index >= 126) abort(); if (b[item] > 0) { k = (k - b[item]) % (index - b[item]) + b[item]; break; } a[index] = item; b[item] = index; if (k == index) { break; } } result = a[k] % 10; printf("%lld\n", result); // printf("%.15f\n", dresult); // puts(s); return 0; success: // puts("YES"); puts("Yes"); // printf("%lld\n", result); // puts("0"); // puts("First"); return 0; fail: // puts("NO"); // puts("No"); // puts("0"); puts("-1"); // puts("-1 -1 -1"); // puts(":("); return 1; } int main (int argc, char *argv[]) { int32_t i, j; // scanf("%llu", &m); // scanf("%lld", &w); // scanf("%lld%lld", &h, &w); // scanf("%lld", &n, &m); // scanf("%lld", &k, &n, &m); // scanf("%llu%llu", &h, &w); // scanf("%lld", &q); scanf("%lld%lld%lld", &va, &vb, &vc, &vd); // va--; // vb--; // scanf("%llu%llu%llu", &ua, &ub, &uc, &ud, &ue); // scanf("%s", s); // scanf("%s", t); // scanf("%s", u); scanf("%lld", &k); // scanf("%lld", &m); // scanf("%lld", &n); // for (i = 0; i < n; i++) { // // scanf("%s", s[i]); // // scanf("%lld", &c[i]); // scanf("%lld", &a[i]); // } // scanf(" %c", &ch); // scanf("%llu", &q); for (i = 0; i < 0; i++) { // scanf("%lld%lld", &xy[i].a, &xy[i].b); // scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c); // scanf("%lld", &c[i]); scanf("%lld", &a[i]); // scanf("%lld", &b[i]); // scanf("%lld", &c[i]); // scanf("%lld", &d[i]); // scanf("%lld", &e[i]); // a[i]--; // b[i]--; // c[i]--; // d[i]--; // xy[i].a--; // xy[i].b--; // tup[i].a--; // tup[i].b--; } // scanf("%lld%lld", &va, &vb); // scanf("%llu", &m); // scanf("%llu", &q); // scanf("%s", t); // for (i = 0; i < n; i++) { // // scanf("%lld%lld", &xy[i].a, &xy[i].b); // // xy[i].a--; // // xy[i].b--; // // scanf("%lld", &a[i], &b[i]); // // scanf("%lld", &b[i]); // // a[i]--; // // b[i]--; // scanf("%lld", &c[i]); // // scanf("%lld", &d[i]); // // scanf("%lld", &e[i]); // c[i]--; // // d[i]--; // } // for (i = 0; i < q; i++) { // // scanf("%lld%lld", &xy[i].a, &xy[i].b); // scanf("%lld", &c[i]); // // xy[i].a--; // // xy[i].b--; // } // for (i = 0; i < h; i++) { // for (j = 0; j < w; j++) { // scanf("%lld", &table[i][j]); // // table[i][j]--; // } // } // for (i = 0; i < n; i++) { // scanf("%s", s[i]); // } // for (i = 0; i < n; i++) { // scanf("%s", t[i]); // } // scanf("%llu", &q); // for (i = 0; i < q; i++) { // scanf("%lld%lld%lld", &e[i], &c[i], &d[i]); // c[i]--; // } solve(); return 0; }