Description

A string of length $L$ hangs between the two trees arranged east and west, and $N$ ants are on this rope. These ants hope to climb to any tree through the rope, but this rope is too thin, so that two ants cannot crawl side by side or cross each other.

Each ant kept crawling forward at a speed of one unit distance per unit time, and when it came across the other ant, both ants would immediately turn around and continue to crawl forward. Now, the ants want to know if they can climb to any tree, and if so, they also want to know the time it takes. For convenience, we number the ants from 1 in the order of the initial position from east to west.

Input Format

Read from standard input.

The first line contains two positive integers $N$, $L$ ($N \le 10^{5}$，$L \le 10^{9}$, $N < L$).

The second line contains $N$ positive integers, and the i-th number $p_i$ ($0

The third line contains $N$ integers. If the i-th number $d_i$ is 1, it means that the i-th ant is heading west, and 0 means the i-th ant is heading east.

Output Format

Write to the standard output.

The output is only one line and contains $N$ numbers. The i-th number represents the time it takes for the i-th ant to climb to any tree, rounded to the nearest whole number. But if the i-th ant cannot climb down the rope, the i-th output is -1.

Sample

Input

3 6
1 3 5
1 1 0

Output

5 5 3

Explanation

The third ant met the second ant after crawling for one unit of time and turned around, and then crawled for two units of time to the tree on the west side.

The second ant meets the third ant and makes a U-turn after crawling for one unit of time, and the first ant meets the first ant and makes a U-turn after crawling for one unit of time, and then crawls for three units of time to the tree on the west side.

The first ant met the second ant after crawling 2 units of time and turned around, and then crawled 3 units of time to the tree on the east side.

Subtasks

Subtask 1 (17 points)

$1 \leq N \leq 10, L \leq 10^5$。

Subtask 2 (19 points)

$1 \leq N \leq 100, L \leq 10^9$。

Subtask 3 (27 points)

$1 \leq N \leq 5000, L \leq 10^9$。

Subtask 4 (37 points)

$1 \leq N \leq 10^5, L \leq 10^9$。