; Convert input a^k to output
; a^k#w
; where w is the binary representation of k
;
; 1) Write a # at the end of the input
; 2) ???
0 _ _ r add-#-0

add-#-0 a a r add-#
add-#-0 _ # r write-0
add-# a a r add-#
add-# _ # l rewind-and-start

rewind-and-start _ _ * start
rewind-and-start * * l rewind-and-start

start _ _ r calc-parity-of-as

calc-parity-of-as a A r a1
calc-parity-of-as A A r calc-parity-of-as
calc-parity-of-as # # l cleanup

a0 a A r a1
a0 A A r a0
a0 # # r write-0

a1 a a r a0
a1 A A r a1
a1 # # r write-1

write-1 _ 1 l rewind-and-start
write-0 _ 0 l rewind-and-start
write-1 0 1 r write-0
write-1 1 1 r write-1
write-0 0 0 r write-0
write-0 1 0 r write-1

cleanup A a l cleanup
cleanup _ _ * halt-accept