Minimizing Anger in Musical Score

In this problem, a string represents a musical score where each character corresponds to a note. A substring is defined as a contiguous segment of characters in the score. An accent is defined as an occurrence of two consecutive identical characters. For example, the string (\tt eeeee) contains 4 accents.

Sept is preparing to compose a musical score of length (n) for Tpes. Tpes calculates his anger value (x) using two rules:

1. For every accent (i.e. every occurrence of two consecutive identical characters in the entire score), his anger increases by (a).
2. For every substring of length (k) that does not contain any accent, his anger increases by (b).

Your task is to construct a musical score (i.e. a string of length (n)) so that the anger value (x) is minimized.

Observations:

A score with no accent (for example, an alternating pattern like ababab...) will contribute ((n-k+1) \times b) to the anger value (because each substring of length (k) has no accent). On the other hand, using a string with many accents (for example, a constant string like aaaaa...) produces (n-1) accents and thus gives an anger of ((n-1) \times a). It may be possible to mix these strategies by forcing the minimum number of accents so that every substring of length (k) contains at least one accent, thereby avoiding the extra penalty (b).

A greedy strategy to cover all substrings (when (k \ge 2)) is as follows:

• If (n < k), then there is no substring of length (k) and the optimal score is any string with no accent (e.g. an alternating pattern).
• Otherwise, we have two candidate strategies:
  
  Strategy 1: Use an alternating pattern (such as "ababab..."), so no accent appears. The anger is ((n-k+1) \times b).
  Strategy 2: Insert the fewest possible accents such that every substring of length (k) contains at least one accent. A greedy algorithm shows that the minimum number of accents required is (\lceil (n-k+1)/(k-1) \rceil) when (k \ge 2). In such a constructed score, the anger is (\lceil (n-k+1)/(k-1) \rceil \times a).

Choosing the strategy with the lower anger, the final answer is constructed as follows:

• If (n < k) or if (k = 1), output an alternating pattern (e.g. "abab...")
• Otherwise, compute

(\text{cost}{\text{no accent}} = (n-k+1) \times b), and (\text{cost}{\text{coverage}} = \lceil (n-k+1)/(k-1) \rceil \times a).

If (\text{cost}{\text{no accent}} \le \text{cost}{\text{coverage}}), output the alternating pattern; otherwise, output a string constructed as follows:

1. Use a greedy algorithm to select positions where an accent (i.e. two consecutive same characters) is inserted.
   Let (A) be the set of indices (0-indexed) where an accent pair should start. Initialize (i = 0) and while (i \leq n-k), choose an index (pos = \min(n-2, i+k-2)) and add it to (A). Then update (i = pos+1).
2. Construct the answer string by setting the first character to 'a'. For every index (i) from 0 to (n-2):
   
   • If (i \in A), set (s[i+1] = s[i]) (to force an accent at position (i)).
   • Otherwise, choose a letter different from (s[i]) (for instance, alternate between 'a' and 'b').

This ensures that every substring of length (k) has at least one accent while keeping the total number of accents as low as possible.

The input consists of four space‐separated integers (n, k, a, b), and the output should be the constructed musical score.

inputFormat

The input consists of a single line with four space-separated integers: (n) (the length of the musical score), (k) (the length of the substring to check), (a) (the anger added per accent), and (b) (the anger added per substring of length (k) without an accent).

outputFormat

Output a string of length (n) representing the musical score that minimizes the anger value (x).

sample

5 3 10 1

ababa

</p>