Under construction

Still being built. Things may change

ABC

Interview

Time limit2sMemory limit512 MB

Summary
Find the lexicographically smallest length-N string over A, B, C that has exactly K pairs i < j with S[i] < S[j].
Level

Medium4 of 10

Topics
Greedy, Combinatorics, Implementation
Solved
No attempts yet

Problem

Given integers NN and KK, write a program that finds a string SS meeting both of these conditions.

  • SS has length NN and uses only the characters A, B, and C.
  • Exactly KK pairs (i,j)(i, j) satisfy 0≤i<j<N0 \le i < j < N and S[i] < S[j].

Characters compare in alphabetical order, so A < B < C.

Input

The first line contains NN and KK, separated by a space. (3≤N≤303 \le N \le 30, 0≤K≤N(N−1)/20 \le K \le N(N-1)/2)

Output

Print on the first line the lexicographically smallest string SS that meets the conditions. If no such SS exists, print -1.

Examples4

  1. Example 1

    Input
    3 3
    Expected output
    ABC

  2. Example 2

    Input
    3 0
    Expected output
    AAA

  3. Example 3

    Input
    5 10
    Expected output
    -1

  4. Example 4

    Input
    15 36
    Expected output
    AAAAAAAAAAAABBB