P7075 [CSP-S 2020] Julian Day.

To make calculations easier, astronomers use the Julian day (Julian day) to represent time. A Julian day is defined as the number of days that have passed from **12:00 noon on January 1, 4713 BC to some later moment**. If it is less than one full day, it is written as a decimal. With this astronomical calendar, every moment is mapped evenly onto a number line, so it is convenient to compute differences between times. Now you are given a Julian day with no fractional part. Please compute the corresponding Gregorian calendar date for that Julian day (it must be 12:00 noon of some day). The calendar we use today is the Gregorian calendar. It was introduced in AD 1582 by Pope Gregory XIII as a modification of the earlier Julian calendar (note: the Julian calendar is not directly related to the Julian day). Specifically, dates are determined by the following rules: 1. On and after October 15, 1582 (inclusive): use the Gregorian calendar. The number of days in each month is: January $31$ days, February $28$ or $29$ days, March $31$ days, April $30$ days, May $31$ days, June $30$ days, July $31$ days, August $31$ days, September $30$ days, October $31$ days, November $30$ days, December $31$ days. In leap years, February has $29$ days; otherwise it has $28$ days. A year is a leap year if it is a multiple of $400$, or if it is a multiple of $4$ but not a multiple of $100$. 2. October 5, 1582 (inclusive) to October 14, 1582 (inclusive): these dates do not exist. These dates were removed, so the day after October 4 is October 15. 3. On and before October 4, 1582 (inclusive): use the Julian calendar. The days in each month are the same as in the Gregorian calendar, but a year is a leap year as long as it is a multiple of $4$. 4. Although the Julian calendar was only introduced in 45 BC, and there were some adjustments in its early period, today people are used to extending the final Julian calendar rules backward for all dates before October 4, 1582. Note that **there is no year 0**, i.e., the year after 1 BC is AD 1. Therefore, years such as 1 BC, 5 BC, 9 BC, 13 BC, ... should be treated as leap years.

The first line contains an integer $Q$, the number of queries. Then follow $Q$ lines, each containing a non-negative integer $r_i$, representing a Julian day.

For each Julian day $r_i$, output one line with a date string $s_i$. There are $Q$ lines in total. The format of $s_i$ is as follows: 1. If the year is AD, output `Day Month Year`. The day (Day), month (Month), and year (Year) have no leading zeros, and are separated by one space. For example, for 12:00 noon on November 7, 2020 AD, output `7 11 2020`. 2. If the year is BC, output `Day Month Year BC`. The year (Year) should be the numeric value of that year; the rest is the same as the AD format. For example, for 12:00 noon on February 1, 841 BC, output `1 2 841 BC`.

**Constraints** | Test Point ID | $Q =$ | $r_i \le$ | |:-:|:-:|:-:| | $1$ | $1000$ | $365$ | | $2$ | $1000$ | $10^4$ | | $3$ | $1000$ | $10^5$ | | $4$ | $10000$ | $3\times 10^5$ | | $5$ | $10000$ | $2.5\times 10^6$ | | $6$ | $10^5$ | $2.5\times 10^6$ | | $7$ | $10^5$ | $5\times 10^6$ | | $8$ | $10^5$ | $10^7$ | | $9$ | $10^5$ | $10^9$ | | $10$ | $10^5$ | the answer year does not exceed $10^9$ | Translated by ChatGPT 5