Background

It feels like I forgot something... Never mind, it is probably not something important anyway.

Problem Description

You found $n$ pieces of text on your computer. Somehow, for no clear reason, you feel they are all copies of the same record.

• First, the original record is a string of unknown length (it can even be empty), called the record string. For each copy, it splits the record string into three (possibly empty) string segments. The split method is not guaranteed to be the same across copies. For convenience, call these three segments in order front, middle, and back.
• In some copies, some segments may have been forgotten. Specifically, the front may be replaced by QIANMIANWANGLE, the middle may be replaced by ZHONGJIANWANGLE, and the back may be replaced by HOUMIANWANGLE. When a replacement happens, it means this segment is completely forgotten; otherwise, it means this segment is fully preserved.
• You have a feeling that all characters in the record string are lowercase English letters.
• The $n$ copies do not have to be consistent with each other.

Your goal is to find the original record string. The record string must consist only of lowercase English letters. You want it to match as many copy strings as possible.

• The requirement for a record string to match a copy string is: there exists a way to split the record string into three parts such that each part is equal to the corresponding part of the copy string, or that part of the copy string was forgotten (in this case, for this part, the record string may be any possibly empty lowercase English string).

You need to output the maximum number of copy strings that can be matched by some record string. As for the record string itself, you feel it is not very important, so you do not need to output it.

/ I fear no forgetting /

Input Format

To avoid the input being too large, the input is compressed to some extent. Please read the input format carefully.

The first line contains a positive integer $n$, the number of records.

The next $n$ lines each contain three non-empty strings. For the first part, it is either a non-empty lowercase string, or Q (meaning QIANMIANWANGLE), or E meaning this part is an empty string (since the empty string is invisible, E is used as a placeholder). There are no other possibilities. The second part is one of: a non-empty lowercase string, Z (meaning ZHONGJIANWANGLE), or E. The last part is one of: a non-empty lowercase string, H (meaning HOUMIANWANGLE), or E.

Output Format

Output one integer in one line, the maximum number of copies that can be matched among all possible record strings.

3
nflsalgo Z H
Q nflspc H
Q Z qidong

3

Hint

Explanation for Sample 1

You want this string to be nflsalgonflspcqidong. You are sure that no other string can match the existing records better than it.

Constraints and Notes

For all testdata, the total length of all input strings is at most $5\times 10 ^ 5$.

• Subtask 1 ($30$ points): It is guaranteed that the “back” part of every copy is H.
• Subtask 2 ($70$ points): No special constraints.

Source: NFLSPC #6 K by Troverld

Translated by ChatGPT 5