C. Cool Pairs
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

You have two permutations of $$$n$$$ elements, $$$p_1, p_2, \ldots, p_n$$$ and $$$q_1, q_2, \ldots, q_n$$$, and one integer $$$k$$$.

You need to find two integer arrays, $$$a$$$ and $$$b$$$, with the following properties:

  • The elements of the arrays must be integers such that $$$-n \leq a_i, b_i \leq n$$$.
  • The permutations induce the following order: $$$a_{p_1} \leq a_{p_2} \leq \ldots \leq a_{p_n}$$$ and $$$b_{q_1} \leq b_{q_2} \leq \ldots \leq b_{q_n}$$$.
  • A pair $$$(i, j)$$$ is cool if $$$i < j$$$ and $$$a_i + b_j < 0$$$. The number of cool pairs must be exactly $$$k$$$.
Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$: the number of elements and the required number of cool pairs ($$$1 \leq n \leq 300\,000$$$, $$$0 \leq k \leq \frac{n \cdot (n - 1)}{2}$$$).

The second line contains $$$n$$$ space-separated integers: the permutation $$$p_1, p_2, \ldots, p_n$$$.

The third line contains $$$n$$$ space-separated integers: the permutation $$$q_1, q_2, \ldots, q_n$$$.

It is guaranteed that each integer from $$$1$$$ to $$$n$$$ appears exactly once in each permutation.

Output

If there is no such pair of integer arrays that the number of cool pairs is equal to $$$k$$$, print "No" on a single line.

Otherwise, print "Yes" on the first line, and print the arrays $$$a$$$ and $$$b$$$ on the next two lines. Separate array elements by spaces.

Example
Input
5 3
3 5 1 2 4
1 2 3 4 5
Output
Yes
2 3 -1 5 1
-5 -3 -2 -2 0