$2^{r-1}$. We can repeat this process. Therefore, after $r$ applications of the merging procedure below, we obtain a single tape containing all the messages (in addition to the various length tapes containing the length information).

The first step is the merging of two signals into a single message. Let us introduce a message tape. For simplicity, we simply denote $|
0 \cdots 0 h_{i_1}\rangle $ by $| h_1\rangle$, etc.

$$\begin{aligned}
   ~& | h_1\rangle | l_1 \rangle |h_2\rangle | l_2 \rangle &
      | {\bf 0} \rangle_{\rm tape} \nonumber \\
\stackrel{\rm swap}{\longrightarrow} & | {\bf 0} \rangle | l_1 \rangle
      | h_2\rangle | l_2 \rangle &
      | 0 \cdots 0 h_1 \rangle_{\rm tape} \nonumber \\
\stackrel{\rm shift}{\longrightarrow} &  | {\bf 0} \rangle| l_1 \rangle
      | h_2\rangle | l_2 \rangle &
      | h_1  0 \cdots 0\rangle_{\rm tape} \nonumber \\
\stackrel{\rm swap}{\longrightarrow} & | {\bf 0} \rangle | l_1 \rangle
      | {\bf 0} \rangle | l_2 \rangle &
      | h_1  0 \cdots 0 h_2\rangle_{\rm tape} \nonumber \\
\stackrel{\rm shift}{\longrightarrow} & | {\bf 0} \rangle | l_1 \rangle
      | {\bf 0} \rangle | l_2 \rangle &
      | h_1 h_2 0 \cdots 0 \rangle_{\rm tape}  \;.
\label{merging}\end{aligned}$$

We remark that the swap operation between any two 