#P17748. 生成数组

生成数组

题目描述

小Z特别喜欢排列。这天,他生成了两个 11 到 nn 的排列,{pi}\{p_i\} 和 {qi}\{q_i\}。小Z的好朋友小T特别喜欢数组,于是小T想生成两个数组 {ai}\{a_i\} 和 {bi}\{b_i\}。但是,小Z十分喜欢刁难别人,他并不想让小T随便生成两个数组,他给出了一个正整数 kk,并想让小T生成的数组满足以下条件:

  1. a,ba,b 长度都是 nn,每个元素是 [−n,n][-n,n] 内的整数。
  2. 对所有 1≤i<n1\le i<n,有 api≤api+1a_{p_i}\le a_{p_{i+1}}。
  3. 对所有 1≤i<n1\le i<n,有 bqi≤bqi+1b_{q_i}\le b_{q_{i+1}}。
  4. 小Z喜欢一个二元组 (i,j)(i,j),当且仅当 1≤i<j≤n1\le i<j\le n,并且 ai+bj<0a_i+b_j<0。小Z希望他喜欢的二元组的个数恰好为 kk。
  5. 若有多个满足条件的答案,任意一个都可以被接受。

小T一下子被小Z难住了,他找到了小J。可小J也不太会,便找到了你。作为小J的好朋友,你当然会慷慨地帮助他了。

输入格式

从标准输入读入。 第一行两个数 n,kn,k,意义如上所述。

第二行 nn 个数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示小Z生成的第一个排列。

第三行 nn 个数 q1,q2,…,qnq_1,q_2,\ldots,q_n,表示小Z生成的第二个排列。

输出格式

输出到标准输出。 如果没有满足条件的数组,输出 No(不带引号)。

否则输出三行,第一行为 Yes(不带引号)。

下面两行每行 nn 个数,分别表示 {ai}\{a_i\} 和 {bi}\{b_i\}。

样例输入

5 3
3 5 1 2 4
1 2 3 4 5

样例输出

Yes
2 3 -1 5 1
-5 -3 -2 -2 0

样例说明

不难发现生成的数组满足上面的条件,其他满足条件的数组也是正确的。

数据范围

所有数据:1≤n≤3000001\le n\le300000,0≤k≤n(n−1)/20\le k\le n(n-1)/2,p,qp,q 均为合法排列。

数据比例 附加限制
5% n=1n=1
另5% k=0k=0
另20% 对所有 ii,pi=qi=ip_i=q_i=i
另10% n≤4n\le4
另30% n≤2000n\le2000