#include <iostream>
#include <vector>
#include <string>

std::string s = "59766299734185935790261115703620877190381824215209853207763194576128635631359682876612079355215350473577604721555728904226669021629637829323357312523389374096761677612847270499668370808171197765497511969240451494864028712045794776711862275853405465401181390418728996646794501739600928008413106803610665694684578514524327181348469613507611935604098625200707607292339397162640547668982092343405011530889030486280541249694798815457170337648425355693137656149891119757374882957464941514691345812606515925579852852837849497598111512841599959586200247265784368476772959711497363250758706490540128635133116613480058848821257395084976935351858829607105310340";
std::vector<int> pattern {0, 1, 0, -1};

void solve(std::string message, int offset, int repeat) {
  int n = s.length();
  std::vector<int> v(n * repeat);
  for (int j = 0; j < repeat; j++) {
    for (int i = 0; i < n; i++) {
      v[j * n + i] = s[i] - '0';
    }
  }

  int N = v.size();
  std::vector<int> v2(N);
  std::vector<int> cumsum(N + 1);
  for (int phase = 0; phase < 100; phase++) {
    // Precompute cumulative sums in O(N) so we can do fast range sums
    cumsum[0] = 0;
    for (int i = 0; i < N; i++) {
      cumsum[i + 1] = cumsum[i] + v[i];
    }
    // O(N / 1 + N / 2 + N / 3 + ... + N / N) which is harmonic, O(N log N)
    for (int i = 0; i < N; i++) {
      int total = 0;
      int w = i + 1;
      // Sum intervals of width w (special casing the first and last interval) in O(N/w)
      for (int j = -1, p = 0; j < N; j += w, p = (p + 1) % 4) {
        int start = j;
        if (start < 0) {
          start = 0;
        }
        int end = j + w;
        if (end >= N + 1) {
          end = N;
        }
        total += pattern[p] * (cumsum[end] - cumsum[start]);
      }
      v2[i] = std::abs(total) % 10;
    }
    std::swap(v, v2);
  }

  std::cout << message << " ";
  for (int i = offset; i < offset + 8; i++) {
    std::cout << v[i];
  }
  std::cout << std::endl;
}

int main() {
  solve("Part1", 0, 1);
  int offset = std::stoi(s.substr(0, 7));
  solve("Part2", offset, 10000);
}