On appelle intervalle d'une suite numérique $C$ toute sous-suite non vide et contiguë de celle-ci. En particulier, cela signifie que chaque suite de longueur $k$ possède $\frac{k(k+1)}{2}$ intervalles, car chaque intervalle est déterminé par son début et sa fin.
Pour une suite donnée d'entiers, nous appelons stabilité la longueur du plus long intervalle strictement monotone qu'elle contient. Plus précisément, la stabilité d'une suite $[c_1, c_2, \dots, c_k]$ est le plus grand entier $s$ tel qu'il existe un indice $i$ ($1 \le i \le k - s + 1$) tel que $c_i < c_{i+1} < \dots < c_{i+s-1}$ ou $c_i > c_{i+1} > \dots > c_{i+s-1}$. Par exemple, la stabilité de la suite $[8, 6, 1, 3, 5, 7, 4, 2]$ est $4$, car elle contient l'intervalle strictement monotone $[1, 3, 5, 7]$, et il n'en existe pas de plus long.
On appelle entrelacement de deux suites $A$ et $B$ toute suite de longueur $|A| + |B|$ qui possède une sous-suite (pas nécessairement contiguë) égale à $A$, telle que tous les éléments en dehors de cette sous-suite forment la suite $B$. Par exemple, les entrelacements des suites $[1, 2, 3]$ et $[4, 5]$ sont les suites $[1, 4, 2, 5, 3]$, $[4, 5, 1, 2, 3]$ et $[4, 1, 5, 2, 3]$, mais pas $[1, 2, 3, 4, 3]$ ni $[1, 2, 3, 5, 4]$.
Enfin, nous notons $f(A, B)$, où $A$ et $B$ sont des suites d'entiers, la stabilité minimale possible de leur entrelacement.
Étant donné deux suites d'entiers $A$ et $B$, de longueurs respectives $n$ et $m$, votre tâche est de calculer, pour chaque entier $x$ de $1$ à $n + m$ inclus, le nombre de paires $(A', B')$ telles que $A'$ est un intervalle de $A$, $B'$ est un intervalle de $B$ et $f(A', B') = x$. Comme ces nombres peuvent être très grands, il suffit de donner leurs restes modulo $10^9 + 7$.
Vous pouvez supposer que tous les éléments des suites $A$ et $B$ sont distincts.
Entrée
La première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n, m \le 300\,000$), représentant respectivement les longueurs des suites $A$ et $B$.
La deuxième ligne de l'entrée contient la suite de $n$ entiers $A_1, A_2, \dots, A_n$ ($1 \le A_i \le n + m$) — la suite $A$ mentionnée.
La troisième ligne de l'entrée contient la suite de $m$ entiers $B_1, B_2, \dots, B_m$ ($1 \le B_i \le n + m$) — la suite $B$ mentionnée.
Il est garanti que tous les éléments des suites $A$ et $B$ sont distincts. En d'autres termes, la concaténation des suites $A$ et $B$ forme une permutation des nombres de $1$ à $n + m$.
Sortie
La seule ligne de la sortie standard doit contenir $n + m$ nombres séparés par des espaces ; le $i$-ième de ces nombres doit être égal au reste de la division par $10^9 + 7$ du nombre de paires $(A', B')$ telles que $A'$ est un intervalle de la suite $A$, $B'$ est un intervalle de la suite $B$ et $f(A', B') = i$.
Exemples
Entrée 1
5 3 1 2 5 7 4 8 3 6
Sortie 1
0 84 6 0 0 0 0 0
Remarque
Pour les intervalles correspondant aux suites entières, on a $f([1, 2, 5, 7, 4], [8, 3, 6]) = 2$, et un entrelacement de stabilité égale à $2$ est par exemple la suite $[1, 8, 2, 5, 3, 7, 4, 6]$.
Si l'on considère les intervalles $[1, 2, 5, 7]$ et $[3]$, on obtient $f([1, 2, 5, 7], [3]) = 3$, et un entrelacement de stabilité égale à $3$ est par exemple la suite $[1, 2, 5, 3, 7]$. On peut démontrer que la paire de suites $([1, 2, 5, 7], [3])$ ne peut pas être entrelacée pour obtenir une suite de stabilité inférieure à $3$.
Pour les intervalles $[4]$ et $[6]$, on a $f([4], [6]) = 2$, et de bons exemples sont ses deux entrelacements possibles : $[4, 6]$ et $[6, 4]$.
Chaque paire d'intervalles dans cet exemple peut être entrelacée de telle sorte que la stabilité de l'entrelacement obtenu ne soit pas supérieure à $3$. Par conséquent, les réponses pour $x \ge 4$ sont égales à $0$.