Python 2, 427 bytes

b=S=lambda l:sorted(l)[::-1]
A=lambda a,b,o=0:A(a^b,{n+1for n in[b&a,b-a][o]},o)if b else a
M=lambda a,*b:reduce(A,({n+m for n in a}for m in b))
def D(a,b):
 q=a-a
 while b<=S(a):n=max(a)-b[0];n-=S(M(b,n))>S(a);q|={n};a=A(a,M(b,n),1)
 return q,a
exec"a=b;b=[]\nfor d in raw_input():b=A(M(b,3,1),{i for i in range(4)if int(d)>>i&1})\n"*2
for n in D(a,S(b)):
 s=''
 while n:n,d=D(n,[3,1]);s=`sum(2**n for n in d)`+s
 print s or 0

Reads the input through STDIN, each number on a separate line, and prints the result to STDOUT.

Explanation

Instead of representing integers as arrays of digits, we represent each integer as the set of "on" bits in its binary representation. That is, an integer n is represented as the set of indices of the bits that equal 1 in the binary representation of n. For example, the number 10, 1010 in binary, is represented as the set {1, 3}. This representation allows us to express some of the arithmetic operations rather succinctly, using Python's set operations.

To add two sets, we (recursively) take the sum of their symmetric difference, and the set of succeeding integers to their intersection (which corresponds to the collective carry, and hence eventually becomes the empty set, at which point we have the final sum.) Similarly, to subtract two sets, we (recursively) take the difference of their symmetric difference, and the set of succeeding integers to their (set) difference (which corresponds to the collective borrow, and hence eventually becomes the empty set, at which point we have the final difference.) The similarity of these two operations allows us to implement them as a single function (A).

Multiplication (M) is simply distributed addition: given two sets A and B, we take the sum, as described above, of all the sets {A+b | b∈B} (where A+b is the set {a+b | a∈A}).

Integer comparison becomes lexicographical comparison of the two sets, sorted in descending order.

To divide (D) two sets, A and B, we start with the empty set as the quotient, and repeatedly find the largest integer n, such that B+n is less than or equal to A (which is simply the difference between the maxima of A and B, possibly minus-1), add n as an element to the quotient, and subtract B+n from A, as described above, until A becomes less than B, i.e., until it becomes the remainder.

There is no free lunch, of course. We pay the tax by having to convert from-, and to-, decimal. In fact, the conversion to decimal is what takes most of the run time. We do the conversion "the usual way", only using the above operations, instead of ordinary arithmetic.