Proving regular languages are closed under a form of interleaving I've got the following definitions:

$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\,(L_1,L_2)\ \  = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$
when both $L_1$ and $L_2$ are languages.

I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Thanks in advance.
Hint. Because $L_1$ and&nbsp;$L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and&nbsp;$M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA&nbsp;$M$. For each character it receives, $M$&nbsp;can decide to act either like&nbsp;$M_1$ or like&nbsp;$M_2$.