import sequtils,strutils
var
    t,B,N : int
proc pow(a, b : int) :int=
    if b == 0:
        return 1
    elif b == 1:
        return a
    elif b mod 2 == 0:
        return pow(a * a, b div 2)
    else:
        return pow(a, b - 1) * a


(t, B) = stdin.readline.split.map(parseInt)
B *= -1
for i in 0..<t:
    N = stdin.readline.parseInt
    if N == 0:
        echo 0
        continue
    var s : string = ""
    for k in 0..33:
        if N == 0:
            break
        if k mod 2 == 0:
            var c = (N mod pow(B, k + 1)) div pow(B, k)
            N -= c * pow(B, k)
            s = $c & s
        else:
            var c = (N mod pow(B, k + 1)) div pow(B, k)
            if c != 0:
                c = B - c
            N += c * pow(B , k)
            s = $c & s
    echo s