This page is still under construction.

Parts of this page are still being built. What you see 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