J. The Grand Fleet's Logbook
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The New World is a chaotic sea, but even the most notorious pirate crews have a rhythm to their madness. "Big News" Morgans, president of the World Economy News Paper, has discovered that every pirate crew follows a bizarre, endlessly repeating cycle of daily activities. He is utilizing this predictability to track their movements, anticipate clashes, and write his next front-page headline.

There are $$$K$$$ pirate crews currently being tracked. Each crew $$$i$$$ enters the New World on a specific starting date and follows an infinitely repeating activity cycle represented by a string $$$P_i$$$. The string consists of the characters S (Sailing), F (Fighting), P (Partying), and D (Docked).

For example, if a crew's pattern is SFFD, they will spend their first active day sailing, the next two days fighting, the fourth day docked, and on the fifth day, the cycle restarts with sailing. A crew is considered strictly inactive on any date prior to their starting date.

Morgans has a series of $$$Q$$$ queries to track the fleets. You must process three types of queries:

  • Type 1 (1 DD/MM/YYYY C): Find all active crews engaged in a specific activity on a given date. Here, DD/MM/YYYY is the date to check, and C is a single character (S, F, P, or D) representing the target activity.
  • Type 2 (2 $$$N_i$$$ MM YYYY): Calculate the total number of days a specific crew spent Sailing (S), Fighting (F), and Partying (P) during a given calendar month. Here, $$$N_i$$$ is the name of the crew, MM is the two-digit month (e.g., 01 to 12), and YYYY is the four-digit year.
  • Type 3 (3 $$$N_1$$$ $$$N_2$$$ DD/MM/YYYY): Morgans anticipates a clash. Here, $$$N_1$$$ and $$$N_2$$$ are the names of two distinct crews, and DD/MM/YYYY is the starting date. Starting from this date, check a window of exactly $$$69$$$ days (the given date and the $$$68$$$ days following it). Find the first date within this window where both specified crews are active and Fighting (F) on the exact same day.
Input

The first line contains a single integer $$$K$$$ ($$$1 \le K \le 50$$$) — the number of pirate crews.

The following $$$K$$$ lines describe the crews. The $$$i$$$-th line contains three space-separated strings:

  • $$$N_i$$$ ($$$1 \le |N_i| \le 20$$$) — the name of the crew, consisting only of uppercase English letters. All crew names are distinct.
  • $$$D_i$$$ — the starting date of the crew's cycle, given in the strict format DD/MM/YYYY (with leading zeros for single-digit days and months).
  • $$$P_i$$$ ($$$1 \le |P_i| \le 100$$$) — the activity cycle of the crew, consisting only of characters from the set {S, F, P, D}.

The next line contains a single integer $$$Q$$$ ($$$1 \le Q \le 5000$$$) — the number of queries.

The following $$$Q$$$ lines each contain a space-separated query in one of the following formats:

  • 1 DD/MM/YYYY C: Where $$$C$$$ is a single character from the set {S, F, P, D}.
  • 2 $$$N_i$$$ MM YYYY: Where $$$N_i$$$ is a valid crew name from the input, MM is a $$$2$$$-digit month (01 to 12), and YYYY is a $$$4$$$-digit year.
  • 3 $$$N_1$$$ $$$N_2$$$ DD/MM/YYYY: Where $$$N_1$$$ and $$$N_2$$$ are valid, distinct crew names, and the date is given in standard format.

All dates in the input are guaranteed to be valid and fall within the range 01/01/2000 to 31/12/2050 inclusive. Additionally, for Type 3 queries, it is guaranteed that the entire $$$69$$$-day window (the given date and the $$$68$$$ days following it) will strictly fall on or before 31/12/2050.

Output

For each query, output the answer on a new line:

  • Type 1: Output the names of all active crews performing the queried activity on that date. The names must be space-separated and printed in lexicographical (alphabetical) order. If no active crew is performing the activity, output NONE.
  • Type 2: Output three space-separated integers representing the total number of S days, F days, and P days the crew had in that month, respectively. If the month occurs entirely before the crew's start date, output 0 0 0.
  • Type 3: Output the first date of the clash in the exact format DD/MM/YYYY. If the two crews never fight on the same day within the $$$69$$$-day window, output PEACE.
Example
Input
4
STRAWHAT 28/02/2024 SFF
HEART 01/03/2024 FDD
KID 01/03/2024 SFP
BUGGY 01/01/2024 P
6
1 01/03/2024 F
1 29/02/2024 D
2 STRAWHAT 02 2024
2 HEART 02 2024
3 STRAWHAT HEART 28/02/2024
3 BUGGY KID 01/01/2024
Output
HEART STRAWHAT
NONE
1 1 0
0 0 0
01/03/2024
PEACE
Note
  • Leap Year Rules: A year is a leap year if it is exactly divisible by $$$4$$$. However, if the year is divisible by $$$100$$$, it is not a leap year, unless it is also exactly divisible by $$$400$$$. For example, the years $$$2000$$$ (divisible by $$$400$$$), $$$2004$$$, and $$$2024$$$ are leap years, whereas $$$2100$$$ (divisible by $$$100$$$ but not $$$400$$$) and $$$2001$$$ are not.
  • Month Lengths: $$$31$$$ days (January, March, May, July, August, October, December), $$$30$$$ days (April, June, September, November), and February has $$$28$$$ days ($$$29$$$ in a leap year).

Explanation of the test case

The year 2024 is a leap year, meaning February has 29 days.

  • Query 1 (1 01/03/2024 F): We are looking for crews Fighting (F) on March 1st.
    • STRAWHAT started on Feb 28th. March 1st is Day $$$3$$$ of their journey (index $$$2$$$). Their pattern is SFF, so on index $$$2$$$ they are Fighting (F).
    • HEART started on March 1st. This is Day $$$1$$$ (index $$$0$$$). Their pattern is FDD, so they are Fighting (F).
    • KID started on March 1st. On Day $$$1$$$ (index $$$0$$$) of their SFP pattern, they are Sailing (S).
    • BUGGY only Parties (P).
    Both HEART and STRAWHAT are Fighting, so they are printed in alphabetical order.

  • Query 2 (1 29/02/2024 D): We are looking for Docked (D) crews on Leap Day. HEART and KID have not started their journeys yet. STRAWHAT is on Day $$$2$$$ (index $$$1$$$ of SFF $$$\rightarrow$$$ F). BUGGY is Partying. No active crew is Docked, so the output is NONE.

  • Query 3 (2 STRAWHAT 02 2024): We must count the activities for STRAWHAT during February 2024. Since they started on Feb 28th, they were only active for two days in this month: Feb 28th (S) and Feb 29th (F). The count is $$$1$$$ S, $$$1$$$ F, $$$0$$$ P.

  • Query 4 (2 HEART 02 2024): HEART does not begin their journey until March 1st. They were entirely inactive during February, resulting in 0 0 0.

  • Query 5 (3 STRAWHAT HEART 28/02/2024): We scan forward from Feb 28th to find the first day both crews Fight. HEART is inactive on the 28th and 29th. On March 1st, as calculated in Query 1, both crews are active and Fighting (F) simultaneously.

  • Query 6 (3 BUGGY KID 01/01/2024): We check the $$$69$$$-day window starting Jan 1st for a clash. However, BUGGY's pattern is entirely P (Partying). Because they never Fight (F), a clash is impossible. The output is PEACE.