题目描述

33DAI 在整理一份日程记录。他把 $2026$ 年 $1$ 月 $1$ 日记作第 $1$ 天，此后每过一天编号加一：$2026$ 年 $1$ 月 $2$ 日是第 $2$ 天，$2026$ 年 $1$ 月 $31$ 日是第 $31$ 天，依此类推。

日期由年、月、日组成。一年有 $12$ 个月：$1$、$3$、$5$、$7$、$8$、$10$、$12$ 月各有 $31$ 天，$4$、$6$、$9$、$11$ 月各有 $30$ 天，$2$ 月平年有 $28$ 天、闰年有 $29$ 天。两种规则下月份的天数都不变，唯一的区别是哪些年份是闰年：

• 规则一（现行公历，即格里高利历）：年份 $y$ 是闰年，当且仅当（$y$ 能被 $4$ 整除，且 $y$ 不能被 $100$ 整除），或者（$y$ 能被 $400$ 整除）。
• 规则二：在规则一的基础上再加一条 —— 若 $y$ 能被 $3200$ 整除，则 $y$ 不是闰年。

给定 $t$ 个整数 $x$，33DAI 想知道：第 $x$ 天在两种规则下分别是哪一年哪一月哪一日。

输入格式

从标准输入读入数据。

输入的第一行是一个整数 $t$（$1 \le t \le 10^5$），表示询问的个数。

接下来 $t$ 行，每行一个整数 $x$（$1 \le x \le 10^{18}$），表示一次询问。

输出格式

输出到标准输出。

输出 $t$ 行，顺序与输入一致。对每个询问输出一行六个整数 $y_1, m_1, d_1, y_2, m_2, d_2$，用一个空格隔开：

• $y_1, m_1, d_1$：第 $x$ 天在规则一下的年、月、日；
• $y_2, m_2, d_2$：第 $x$ 天在规则二下的年、月、日。

年、月、日都不补前导零。

2
1
2

2026 1 1 2026 1 1
2026 1 2 2026 1 2

3
365
366
731

2026 12 31 2026 12 31
2027 1 1 2027 1 1
2028 1 1 2028 1 1

3
428854
428855
428856

3200 2 29 3200 3 1
3200 3 1 3200 3 2
3200 3 2 3200 3 3

1
1000000000000000000

2737907006990533 8 20 2737909349534656 4 26

样例解释

• 样例 1：第 $1$ 天即 $2026$ 年 $1$ 月 $1$ 日，第 $2$ 天是它的后一天，即 $2026$ 年 $1$ 月 $2$ 日；两种规则下这两天的日期相同。
• 样例 2：$2026$ 年是平年，有 $365$ 天，所以第 $365$ 天是 $2026$ 年 $12$ 月 $31$ 日，第 $366$ 天是 $2027$ 年 $1$ 月 $1$ 日；$2027$ 年也有 $365$ 天，所以第 $731$ 天是 $2028$ 年 $1$ 月 $1$ 日。
• 样例 3：$3200$ 能被 $400$ 整除，按规则一是闰年，$2$ 月有 $29$ 天；按规则二它不是闰年，$2$ 月只有 $28$ 天。所以第 $428854$ 天在规则一下是 $3200$ 年 $2$ 月 $29$ 日，在规则二下是 $3200$ 年 $3$ 月 $1$ 日；第 $428855$ 天在规则一下是 $3200$ 年 $3$ 月 $1$ 日，在规则二下是 $3200$ 年 $3$ 月 $2$ 日。

提示

• 第 $x$ 天可能落在很远的将来（年份最大接近 $3 \times 10^{15}$），读入与计算请使用 $64$ 位整型；输出 $t$ 行，每行六个整数用单个空格隔开，年、月、日都不补前导零。

数据范围

对于所有测试数据，保证 $1 \le t \le 10^5$，$1 \le x \le 10^{18}$。

共 $15$ 个测试点，按测试点计分：子任务 $1$、$2$ 的每个测试点 $6$ 分，子任务 $3$ 的每个测试点 $8$ 分。