有 $n$ 只企鹅，第 $i$ 只企鹅的宽度为 $w_i$。它们按照排列 $p_i$ 指定的顺序进入冰箱：第 $p_i$ 只企鹅在第 $i$ 个位置进入冰箱。

冰箱的宽度为 $W$，深度视为无限。在所有企鹅进入冰箱后，如果相邻企鹅的宽度之和不超过 $W$，它们就可以交换位置。一只企鹅可以多次交换位置。

计算从冰箱中出来的不同出队顺序的数量，以及所有可能的出队顺序中字典序最小的顺序。

冰箱只有一个门，采用“后进先出”（LIFO）结构，这意味着企鹅将按照它们进入顺序的逆序离开。

输入格式

第一行包含两个正整数 $n$ 和 $W$ ($1 \le n \le 10^6$, $1 \le W \le 10^9$)，分别表示企鹅的数量和冰箱的宽度。

第二行包含一个长度为 $n$ 的排列，记为 $p_i$ ($1 \le p_i \le n$)，表示企鹅进入冰箱的顺序。

第三行包含 $n$ 个正整数 $w_i$ ($1 \le w_i \le W$)，分别表示编号为 $i$ 的企鹅的宽度。

保证 $p_i$ 是 $\{1, 2, \dots, n\}$ 的一个排列。

输出格式

第一行输出一个整数，表示企鹅离开冰箱的不同顺序数量，对 $10^9 + 7$ 取模。

第二行输出一个长度为 $n$ 的排列，表示所有可能的出队顺序中字典序最小的顺序。

样例

输入 1

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

输出 1

3
5 4 2 1 3

输入 2

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

输出 2

30
1 5 2 3 4