Before putting the shuffled deck on top of the second deck, insert a paper above it, so the paper is acting as the seperator between the two decks. Now, denote $d_1(x)$ by the number of cards between the $(x)^{th}$ card of the first deck and the paper, so for the bottom most card, it is $35$ and for the card just below the paper, it's $0$. Define $d_2(x)$ analogously for the second deck. Now notice that the set $\{d_i(x)\}_{x=1}^{36}$ is a permutation of $\{ 0,\cdots,35 \}$, and you're done.