Interleaving Sequences

An interval of a sequence $C$ is any nonempty contiguous subsequence of $C$. A sequence of length $k$ has $k(k+1)/2$ intervals, because each interval is determined by its start and end positions.

The stability of a sequence $[c_1, c_2, \ldots, c_k]$ is the largest integer $s$ such that there is an index $i$ ($1 \le i \le k-s+1$) with $c_i < c_{i+1} < \cdots < c_{i+s-1}$ or $c_i > c_{i+1} > \cdots > c_{i+s-1}$. For example, the stability of $[8, 6, 1, 3, 5, 7, 4, 2]$ is 4, because the strictly monotone interval $[1, 3, 5, 7]$ exists and no longer one does.

An interleaving of two sequences $A$ and $B$ is any sequence of length $|A|+|B|$ that contains a subsequence (not necessarily contiguous) equal to $A$, where the elements outside that subsequence form $B$ in order. For example, the interleavings of $[1, 2, 3]$ and $[4, 5]$ include $[1, 4, 2, 5, 3]$, $[4, 5, 1, 2, 3]$, and $[4, 1, 5, 2, 3]$. Neither $[1, 2, 3, 4, 3]$ nor $[1, 2, 3, 5, 4]$ is one.

Let $f(A, B)$ be the minimum possible stability of an interleaving of $A$ and $B$.

Given two sequences $A$ and $B$ of lengths $n$ and $m$, instead of $f(A, B)$, count for each integer $x$ from 1 to $n+m$ the number of pairs $(A', B')$ such that $A'$ is an interval of $A$, $B'$ is an interval of $B$, and $f(A', B') = x$. These counts can be very large, so print them modulo $10^9+7$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 300\,000$), the lengths of $A$ and $B$.

The second line contains $n$ integers $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le n+m$).

The third line contains $m$ integers $B_1, B_2, \ldots, B_m$ ($1 \le B_i \le n+m$).

All elements of $A$ and $B$ are pairwise distinct. In other words, the concatenation of $A$ and $B$ is a permutation of $1$ to $n+m$.

Print $n+m$ integers separated by single spaces. The $i$-th number is the number of pairs $(A', B')$ with $f(A', B') = i$, modulo $10^9+7$.

The intervals $[4, 5]$ does not apply here. For the whole sequences $[1, 2, 5, 7, 4]$ and $[8, 3, 6]$, $f = 2$, and one interleaving with stability 2 is $[1, 8, 2, 5, 3, 7, 4, 6]$.

For $[1, 2, 5, 7]$ and $[3]$, $f = 3$, and one interleaving with stability 3 is $[1, 2, 5, 3, 7]$. No interleaving of this pair has stability below 3.

For $[4]$ and $[6]$, $f = 2$, and both interleavings $[4, 6]$ and $[6, 4]$ are valid examples.

Every pair of intervals in this example can be interleaved so that the stability is at most 3. Therefore the answers for $x \ge 4$ are all 0.