import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n,m = map(int,input().split())
for i in range(n):
    a = int(input())
    if a == 0:
        print(0)
        continue
    ans = []
    kai = 0
    while a:
        ans.append(a%(-m))
        a-=a%(-m)*(-1)**kai
        a//=m
    ans = ans[::-1]
    print("".join(map(str,ans)))