A cube has side length $s$. One dimension is increased by $3$, another is decreased by $3$, and the third is left unchanged. The volume of the new rectangular solid is $36$ less than that of the cube. What was the volume of the cube?