B. Bus Game
time limit per test
1 second
memory limit per test
1024 MB
input
standard input
output
standard output

There are $$$n$$$ consecutive bus seats arranged in a line, numbered from $$$1$$$ to $$$n$$$. Due to long-term disrepair, $$$m$$$ of these seats are broken.

Alice and Bob take turns seating passengers, with Alice moving first. In each move, the current player must choose an unbroken and currently empty seat $$$i$$$ for a passenger, subject to the following condition:

All seats $$$j$$$ satisfying $$$|j - i| \le k$$$ and $$$j \ne i$$$ must be empty (that is, all other seats within distance at most $$$k$$$ from $$$i$$$ must be unoccupied. Note that broken seats do not affect this distance check; the distance is still computed across broken seats).

After the passenger sits down, seat $$$i$$$ becomes occupied. If the current player can no longer find any legal empty seat for seating a passenger, the game ends immediately. Alice wants the total number of seated passengers to be as large as possible, while Bob wants it to be as small as possible. Both players play optimally.

Please output the final possible seat configuration of the bus as a string.

Input

The first line contains three integers $$$n$$$, $$$k$$$, and $$$m$$$ ($$$1 \le n \le 20$$$, $$$1 \le k \le 20$$$, $$$0 \le m \le n$$$), representing the total number of seats, the distance constraint, and the number of broken seats, respectively.

The second line contains $$$m$$$ distinct integers, indicating the indices of the broken seats.

Output

For each test case, output a string of length $$$n$$$ on a single line, representing the final seat configuration of the bus:

  • Character 'a' indicates that the seat is occupied by a passenger seated by Alice.
  • Character 'b' indicates that the seat is occupied by a passenger seated by Bob.
  • Character 'x' indicates that the seat is broken (and cannot be occupied).
  • Character '.' indicates that the seat is intact but remains empty in the end.

If there are multiple possible results, output any one of them.

Examples
Input
1 1 0
Output
a
Input
5 2 1
3
Output
a.xb.
Note

In the first sample, Alice seats a passenger at seat $$$1$$$. After that, there is no legal empty seat left, so Bob cannot make a move and the game ends immediately. The final state is a.

In the second sample, seat $$$3$$$ is broken, so the initial state is ..x...

  • Alice may choose seat $$$1$$$, making the state a.x... Since the distance constraint is $$$k=2$$$, seat $$$2$$$ then becomes unavailable.
  • Bob may choose seat $$$4$$$, making the state a.xb.. Similarly, seat $$$5$$$ then becomes unavailable.
  • Neither player has any legal seat to choose, so the game ends.
In this playthrough, both players play optimally. Note that a.x.b is also a valid and correct final state.