Maximizing Energy Consumption in an Ancient Matching System

In your company, an ancient matching system is used to match two strings: a to-be-matched string and a pattern string. The to-be-matched string is a strict binary string (i.e. it contains only \(0\) and \(1\)), while the pattern string is composed of four types of characters: \(0\), \(1\), \(\ast\), and \(\wedge\). Here, \(\ast\) represents the ability to match zero or more arbitrary binary characters, and \(\wedge\) represents matching exactly one binary character.

The system supports two matching methods: maximum matching and minimum matching. Both methods work similarly in that they try to match the given strings from the starting positions, but they differ in the enumeration order for \(\ast\):

• Maximum Matching: When encountering a \(\ast\), the system enumerates the possible number of characters to match from \(L\) to 0 (where \(L\) is the remaining length of the to-be-matched string). Before each enumeration, it consumes 1 unit of energy.
• Minimum Matching: Similar to the maximum matching method except that it enumerates from 0 to \(L\).

For literal characters (\(0\) or \(1\)) and for \(\wedge\), the system will consume 1 unit of energy for each character comparison (provided the to-be-matched string is not exhausted), otherwise it backtracks to the previous \(\ast\) decision. When the pattern string is exhausted, the to-be-matched string must also be exhausted for a successful match. If all attempts fail, the system returns "No"; otherwise, it returns "Yes" when a complete match is found.

Your task is to construct both a pattern string and a to-be-matched string, each of length \(n\) (\(n \ge 1\)), for a given matching method (either maximum or minimum) so that:

1. The system returns "Yes" (i.e. the two strings match).
2. The total energy consumption is maximized using the underlying brute-force matching algorithm.

Hint: One strategy is to force the system to explore as many unsuccessful enumeration branches as possible for the \(\ast\) operator. For example, consider a pattern that starts with a \(\ast\) followed by a fixed literal string. If you choose the literal part so that the only correct match for the \(\ast\) is not the first attempted possibility, the system will try many alternatives before arriving at the unique successful branch.

A concrete construction is as follows. Let the pattern string be:

[ P = \ast ; S ]

and the to-be-matched string be:

[ T = \underbrace{0,0,\ldots,0}_{n\text{ times}}. ]

Here, choose \(S\) (a binary string of length \(n-1\)) to be all zeros. Thus, the pattern string becomes:

[ P = \ast ; \underbrace{0 0 \ldots 0}_{n-1}]

and the to-be-matched string is:

[ T = \underbrace{0 0 \ldots 0}_{n}].

For the match to succeed, the \(\ast\) must match exactly 1 character. With the maximum matching method, \(\ast\) will enumerate from \(n\) downwards, and with the minimum matching method, it will enumerate from 0 upwards. In both cases, only the branch where \(\ast\) matches one character will lead to a successful match, and the system will expend maximal energy in exploring wrong choices.

inputFormat

The input consists of a single line containing an integer \(n\) (the length of both the pattern and the to-be-matched strings) and a string that specifies the matching method. The matching method is either maximum or minimum, indicating which matching strategy the ancient system uses.

For example:

5 maximum

outputFormat

Output two lines:

• The first line is the constructed pattern string of length \(n\).
• The second line is the constructed to-be-matched string of length \(n\).

These strings must be chosen such that the ancient system returns "Yes" and the energy consumption is maximized.

sample

1 maximum

*
0

</p>