When Does Cron Run Next?

The story

Your team's job scheduler runs everything from a crontab. Before a risky change, an engineer wants to know exactly when each job fires next ("will the backup collide with the deploy window?"). Sounds easy until you meet months with 28 to 31 days, leap years, and the oldest quirk of cron: the day-of-month OR day-of-week rule.

Write the calculator. Everything is UTC.

The task

Input:

1. a line with now, a Unix timestamp in seconds;
2. a line with n, the number of expressions;
3. n lines, each a crontab expression of five space-separated fields: minute hour day-of-month month day-of-week.

Output: for each expression, in order, the first minute strictly after now at which it fires, as YYYY-MM-DD HH:MM (UTC), or never.

Field syntax. Each field is a comma-separated list of items. An item is one of: * (every value), */n (every n-th value, counting from the field's smallest value), a (one value), a-b (a range, inclusive), a-b/n (every n-th value in the range, starting at a).

| field | allowed values | |---|---| | minute | 0-59 | | hour | 0-23 | | day-of-month | 1-31 | | month | 1-12 | | day-of-week | 0-6 (0 = Sunday) |

All input is valid; there are no names (MON, JAN) and no @daily shortcuts.

Which days qualify. The month must be allowed. Then:

• if neither the day-of-month field nor the day-of-week field starts with *, a day qualifies when either matches (the classic OR rule);
• if at least one of the two starts with * (* and */2 both count), a day qualifies only when both match.

Timing rules. now is truncated to its minute and the search starts with the following minute: at 22:13:59 the next minute is 22:14, and at exactly 22:14:00 it is 22:15. Print never when the expression matches no real date at all (for example 31 April or 30 February). Any other expression fires within 12 years: 29 February can take up to 8 years, because 2100 is not a leap year.

Example

1700000000
5
* * * * *
*/15 * * * *
0 9 * * 1-5
30 2 29 2 *
59 23 31 12 *

1700000000 is Tuesday 2023-11-14 22:13:20 UTC. Output:

2023-11-14 22:14
2023-11-14 22:15
2023-11-15 09:00
2024-02-29 02:30
2023-12-31 23:59

The third expression means "09:00 on weekdays": today's 09:00 has passed, so the next one is Wednesday. The fourth needs the next leap day, in 2024.

1700000000
5
* * * * *
*/15 * * * *
0 9 * * 1-5
30 2 29 2 *
59 23 31 12 *