There are $n$ penguins, where the width of the $i$-th penguin is $w_i$. They enter the refrigerator in an order specified by the permutation $p_i$: the $p_i$-th penguin enters the refrigerator at position $i$.

The refrigerator has a width of $W$, and its depth is considered infinite. After all these penguins have entered the refrigerator, they can swap positions if the sum of the widths of adjacent penguins does not exceed $W$. A penguin can swap positions multiple times.

Calculate how many different exit orders are possible from the refrigerator, as well as the lexicographically smallest order among all possible ways for the penguins to exit the refrigerator.

The refrigerator has only one door and operates as a “last in, first out” (LIFO) structure, which means the penguins will exit in the reverse order of their entry.

Input

The first line contains two positive integers, $n$ and $W$ ($1 \le n \le 10^6$, $1 \le W \le 10^9$), representing the number of penguins and the width of the refrigerator, respectively.

The second line contains a permutation of length $n$, denoted as $p_i$ ($1 \le p_i \le n$), representing the order in which the penguins enter the refrigerator.

The third line contains $n$ positive integers, $w_i$ ($1 \le w_i \le W$), each of which represents the width of the penguin with the corresponding number $i$.

It is guaranteed that $p_i$ is a permutation of $\{1, 2, \dots, n\}$.

Output

For the first line, output an integer representing the ordinal number of the penguin coming out of the refrigerator, modulo $10^9 + 7$.

For the second line, output a permutation of length $n$, representing the lexicographically smallest order of penguins coming out of the refrigerator among all possible orders.

Examples

Input 1

5 10
1 2 3 4 5
6 5 3 9 2

Output 1

3
5 4 2 1 3

Input 2

5 10
1 2 3 4 5
2 4 3 3 8

Output 2

30
1 5 2 3 4