Problem Background

The members of LAOI have organized a mock contest for CSP-J with $10^{100}$ problems!

Problem Description

The contest follows the ICPC rules, sorting primarily by the number of problems solved in descending order and secondarily by the penalty time in ascending order.

There are $n$ giants participating in this contest, which lasts for $m$ minutes.

At the beginning of the $i$-th minute ($0 \le i \le m-1$), the $s_i$-th giant first submits $t_i$ wrong answers (each with a penalty of $x$ minutes), and then solves a problem. Thus, their number of problems solved increases by 1, and their total penalty time increases by $x \times t_i + i$ minutes.

The $i$-th giant has a total of $k_i$ wrong answers and solves $a_i$ problems (guaranteed that $\sum_{i=1}^n a_i = m$). Why didn't the giants solve all the problems? Because they found the problems too easy and left.

If the $i$-th giant, after finishing all their submissions, finds themselves in the first place on the leaderboard (no ties allowed), they are said to have "dominated the contest."

Construct sequences $\{s_m\}$ and $\{t_m\}$ such that the $i$-th giant has $k_i$ wrong answers, solves $a_i$ problems, and maximizes the number of people who "dominate the contest."

Input Format

There are three lines in total.

The first line contains three integers $n, m, x$.

The second line contains $n$ integers, representing $\{a_n\}$.

The third line contains $n$ integers, representing $\{k_n\}$.

Output Format

The first line outputs the maximum number of people who "dominate the contest."

The second and third lines output one optimal solution:

The second line contains $m$ integers, representing $\{s_m\}$.

The third line contains $m$ integers, representing $\{t_m\}$.

Sample Input and Output

Input Sample #1

3 9 20
3 3 3
0 1 2

Output Sample #1

3
3 3 3 2 2 2 1 1 1
1 0 1 0 1 0 0 0 0

Input Sample #2

3 16 3
5 5 6
2 0 8

Output Sample #2

3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 3
0 0 1 0 0 1 1 0 2 1 0 2 0 0 1 1

Notes

Sample 1 Explanation

At minute $2$, giant $3$ finishes their submissions, solves $3$ problems, and has a penalty time of $20 \times 2 + 0 + 1 + 2 = 43$ minutes.

At minute $5$, giant $2$ finishes their submissions, solves $3$ problems, and has a penalty time of $20 \times 1 + 3 + 4 + 5 = 32$ minutes.

At minute $8$, giant $1$ finishes their submissions, solves $3$ problems, and has a penalty time of $20 \times 0 + 6 + 7 + 8 = 21$ minutes.

Data Range

The data is not guaranteed to be random.

This problem uses subtask testing.

For $100\%$ of the data, it is guaranteed that:

• $m \ge 3n$;
• $3 \le n \le 10^5$;
• $9 \le m \le 3 \times 10^5$;
• $0 \le x \le 5 \times 10^4$;
• $0 \le k_i \le 4 \times 10^4$;
• $3 \le a_i \le 3 \times 10^5$;
• $\sum_{i=1}^n a_i = m$.

见题面 Input 部分

见题面 Output 部分