def Base_10_to_n(X, n):
    if X == 0:
        return "0"
    ans = ""
    cnt = 0
    while X > 0:
        tmp = X % n
        if cnt % 2 == 1 and tmp != 0:
            tmp = n-tmp
            X += tmp
        X //= n
        cnt += 1
        ans = str(tmp) + ans
    return ans

t,b = map(int,input().split())
n = [int(input()) for i in range(t)]
for i in range(t):
    print(Base_10_to_n(n[i],abs(b)))