| 问题描述 |
|---|
XX晚会临近，校内舞蹈队需要几个人去参加演出，队内一共有$$n$$个正式队员和$$m$$个替补队员。 为了整体队形显得美观，教练想让她们最好不要按照身高从矮到高排队，换句话说，就是想让队列中队员身高的最长递增子序列$$(LIS)^†$$最小。 但是由于正式队员之间需要舞蹈配合，因此她们的位置不能被改变，所以让$$m$$个替补队员插入到正式队员的队列中，如果你是教练你会如何安排这个队列，让最终队列的$$LIS$$最小呢？ †：$$LIS$$是指在一个给定序列中，找到一个最长的子序列，使得该子序列中的元素是严格递增的，例：$$LIS([2,1,1,3]) = 2， LIS([1,7,9]) = 3$$
|
| 输入描述 |
第一行输入包含一个整数$$T(1≤T≤1e4)$$。 对于每组案例， 第一行输入包含一个整数$$n$$和整数$$m$$，分别代表了有$$n$$个正式队员和$$m$$个替补队员。$$(1≤n,m≤1e5)$$ 第二行输入包含$$n$$个整数，$$a_1,a_2,...,a_n(1≤a_i≤1e9)$$分别代表$$i$$个正式队员的身高$$a_i$$。 第三行输入包含$$m$$个整数，$$b_1,b_2,...,b_m(1≤b_i≤1e9)$$分别代表$$i$$个替补队员的身高$$b_i$$。 保证所有测试用例中$$n$$ 的总和不超过$$1e6$$，$$m$$的总和不超过$$1e6$$。 |
| 输出描述 |
针对每组样例，输出$$(n+m)$$个整数组成的序列，满足题意，且序列的$$LIS$$最小，如果有多个答案，则输出字典序最大的那个序列，数与数之间用空格分隔，最后一个数后面也有空格，然后换行 |
| 样例输入复制样例 |
2 2 1 6 4 5 5 5 1 7 2 4 5 5 4 1 2 7 |
| 样例输出 |
6 5 4 7 5 4 2 1 7 2 4 5 1 |
| 提示说明 |
在第一个测试案例， $$LIS(a)=LIS([6,4])=1$$ 。我们可以在身高为$$6$$的正式队员 和 身高为$$4$$的正式队员 之间插入身高为$$ 5$$ 的替补队员，最后序列的 $$LIS([6,5,4])=1 $$。 在第二个测试案例中，$$ LIS(a)=([1,7,2,4,5]) = 4 $$。插入后， 序列的$$ LIS([7,5,4,2,1,7,2,4,5,1])=4$$ 。
|
| 相关 |