Power Tree slow by boothby

import sys\x0d
s=sys.stdin.read()\x0d
n=int(s[1:])+1\x0d
q=[1]\x0d
T={1:[1]}\x0d
for x in q:\x0d
 for t in T[x]:y=x+t;T[y]=T.get(y,0)or y>n or q.append(y)or T[x]+[y]\x0d
for t in[[T[i][-2]for i in range(2,n)],T[n-1]][s[0]<'d']:print t,

Note that non-ascii characters in the above source code will be escaped (such as \x9f).

download

return top