Determining the Resilient Spirit Award

In the XCPC contest, each team attempts several problems and can make multiple submissions for each problem. A submission by team t on problem p is considered an effective AC submission if and only if:

• Prior to this submission, team t had not solved problem p.
• This submission is an AC (accepted) submission and, in the end, team t solved problem p.

Note that even after a team has solved a problem, it can still submit for that problem. Such submissions are ineffective and do not change the team's solved status.

The contest log provides all submissions in order. Each submission is a triple \( (tid_i, pid_i, state_i) \) where:

• tid_i is the team ID submitting the record,
• pid_i is the problem ID, and
• state_i is either AC (passed) or WA (not passed).

A team earns a medal if it eventually solves at least \( k \) distinct problems (using effective AC submissions).

Your task is to determine the team that wins the Resilient Spirit Award by computing four different criteria:

1. The team corresponding to the last AC submission (regardless of validity).
2. The team corresponding to the last effective AC submission.
3. The team (among those without a medal) corresponding to the last effective AC submission.
4. The team corresponding to the submission that causes its solved count to change from 0 to 1 (i.e. its first effective AC submission), considering the last such submission in contest order.

Notes on effective AC submission:

A submission \( S_i \) is effective if and only if:

\[ \text{Effective}(S_i) \iff \bigl(\forall j < i,\, \text{if } tid_j = tid_i \text{ then } pid_j \neq pid_i\bigr) \quad \text{and} \quad state_i = \text{AC}. \]</p>

inputFormat

The input begins with two space-separated integers \( n \) and \( k \) (the number of submissions and the medal threshold, respectively). This is followed by \( n \) lines, each containing a submission record formatted as:

tid pid state

Here, tid and pid are positive integers denoting the team ID and problem ID, and state is a string which is either AC (accepted) or WA (wrong answer).

outputFormat

Output four space‐separated integers on one line:

1. The team ID from the last AC submission.
2. The team ID from the last effective AC submission.
3. The team ID from the last effective AC submission among teams that did not earn a medal (i.e. solved fewer than \( k \) problems). If no such submission exists, output -1.
4. The team ID from the last submission that changed a team’s solved count from 0 to 1 (i.e. its first effective AC submission).

sample

10 2
1 1 WA
2 1 AC
1 1 AC
2 1 AC
3 2 WA
3 2 AC
2 2 AC
2 3 AC
1 2 WA
3 3 WA

2 2 3 3