题目看似很多细节，但是没必要特殊考虑，特殊考虑可能需要浪费很多时间。

考虑如果从头开始一天一天的往后跳，假如跳 $10^7$ 天，如果能预处理得到 $10^7$ 内步的日期，如果询问 $10^7$ 天内的日期，可以 $O(1)$ 回答。

先暴力一天一天的往后跳，预处理出前 $10^7$ 天的日期，年份能到达 $22666$ 年，所有的特殊情况都可以通过预处理的方式算出来。

对于询问分成两类：

• 对于 $r_i \le 10^7$ 直接输出预处理好的日期

• 对于 $r_i > 10^7$ 二分年份是哪一年，这里的日期一定是格里高利历，判断闰年只有一种条件，相比于直接二分所有可能的年份，要好写很多很多，基本没有什么细节了。

  代码算是比较短的了。

  #include <cstdio>
  #include <bits/stdc++.h> 
  #define int long long 
  using namespace std;
  const int _ = 1e7 + 100;
  const int LIM = 22666;
  int Day[2][30] = { {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {-1, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };
  bool pd(int Y){
    if(Y < 0) return Y % 4 == -1;
    else if(Y <= 1582) return Y % 4 == 0;
    else return (Y % 400 == 0) || (Y % 4 == 0 && Y % 100 != 0);
  }
  int CNTR(int Y){ //求 年份在[1, Y]之间，如果全部按照格里高利日历的闰年判断方法，得到的闰年数量。
    int ans = 0;
    ans += Y / 400;
    ans += (Y / 4 - Y / 100);
    return ans;
  }
  void next(int &Y, int &M, int &D){ // 往下增加一天，得到的日期。
    if(Y <= -1){
        D++; int md = Day[pd(Y)][M];
        if(D > md) D = 1, M ++;
        if(M > 12) M = 1, Y ++;
        if(Y >= 0) Y = 1;
    }
    else {
        D += (Y == 1582 && M == 10 && D == 4 ? 11 : 1);
        int md = Day[pd(Y)][M];
        if(D > md) D = 1, M ++;
        if(M > 12) M = 1, Y ++;
    }
  }
  struct Date{
    int D, Y, M;
    Date(int a, int b, int c) { Y = a; M = b; D = c; }
    Date(){}
  }A[_];
  int check(int Y){ // 求出[LIM, Y]年之间有多少天。
    int ALL_Y = Y - LIM; // 总共有多少年
    int D = ((CNTR(Y) - CNTR(LIM))) * 366; // 闰年的数量 * 366
    D += (ALL_Y - (CNTR(Y) - CNTR(LIM))) * 365; // 平年的数量 * 365
    // 这里是一个前缀和，求出 [1, Y] 之间的闰年数量 - [1, LIM] 之间的闰年数量 就是[LIM, Y] 之间的闰年数量。
    return D;
  }
  signed main(){ ios::sync_with_stdio(false);
    int Y = -4713, M = 1, D = 1;
    for(int i = 0; i <= 1e7 + 20; i++){ A[i] = Date(Y, M, D); next(Y, M, D); } // 预处理
    int Q; cin >> Q; 
    while(Q--){
        int R; cin >> R;
        if(R <= (int)(1e7 + 11)) { printf("%lld %lld %lld", A[R].D, A[R].M, abs(A[R].Y)); if(A[R].Y < 0) puts(" BC"); else puts(""); }
        else {
            int res = R - (int)(1e7) - 11;
            int l = LIM, r = 2e9, Y = l;
            while(l < r){
                int mid = (l + r) >> 1;
                if(check(mid) >= res) r = mid, Y = mid;
                else l = mid + 1;
            }
            res -= check(Y - 1); 
            int M = 1;
            for(int i = 1; i <= 12; i++) {
                int md = Day[pd(Y)][i];
                if(res - md <= 0) { M = i; break; }
                else res -= md;
            } int D = res;
            printf("%lld %lld %lld\n", D, M, Y);
        }
    }
    return 0;
  }