$a

.
-t.
.g/^\(.\).*\(.\)$/s//\2&\1/
.g/^.$/s//&&&/
s/./&\
/g
d
?^$?+,$-2g/^/+,+2t.\
-2,.j\
s/111/0/\
s/110/1/\
s/101/1/\
s/100/0/\
s/011/1/\
s/010/1/\
s/001/1/\
s/000/0/
$-,$d
?^$?,$jp
w
!exec ed '%' < '%'
q

# DATA
00000000000000000000000000000100